# [Catching Apples](https://open.kattis.com/problems/catchingapples) editorial

## Subtask 1: $N \leq 20$
We are not aware of a "clean" way to solve this subtask.
Simply use any paradigm for solving problems with big search spaces - simulated annealing, backtracking or just trying lots of random solutions is likely to work with enough determination in C++.

## Transforming the problem
Instead of imagining apples falling downwards, let's imagine our robots walking in the $(x,t)$ plane. Every second, a robot can walk to either $(x-1,t+1)$, $(x, t+1)$ or $(x+1,t+1)$.

Thus, a position $(x_a,t_a)$ is reachable from $(x_r,y_r)$ if

$$t_a-t_r \geq |x_a-x_r|$$

In words, the number of seconds until we reach $t_a$ must be greater than or equal to the distance in the $x$ axis for us to have enough time.

As an example, suppose we are at $x=5$ and $t=2$. Then, the red cone is the set of all reachable points.


Unfortunately, it's hard to work with cones. Thankfully, there are coordinate transformations that should help us. Let's bash the algebra.

An equivalent condition to the above one is that $(a,b)$ is above these two lines.


This gives that $(x_a,t_a)$ must fulfill:

$$t_a-t_r \geq x_a - x_r$$

and

$$t_a-t_r \geq x_r - x_a$$

Equivalently,

$$t_a - x_a \geq t_r - x_r$$

and

$$t_a + x_a \geq x_r + t_r$$

To capture these inequalities, we can make the transformation

$$f(x,t)=(t-x, t+x)$$

Now, suppose $(u,v)=f(x_r,t_r)$ and $(a,b)=f(x_a,t_a)$. Then, $(u,v)$ can reach $(a,b)$ if

$$u \leq a, \;\;\text{and}\;\; v \leq b$$

Thus, each robot can reach a square to the right and up of it:

Now, let's develop an algorithm. From now on, we will only work with transformed coordinates. We want the smallest number of chains to cover all points, where in every chain, we can only go right or up.

To do this, let's sort all apple locations by $(x,y)$ lexicographically increasing (first by $x$, breaking ties by $y$).

## Subtask 4: we only need the number of robots
The count is the smallest number of increasing subsequences needed to cover all points. Considering the points and vertices, and drwaing edges to reachable points, this asks for the smallest number of paths to cover a directed acyclic graph. By [Dilworth's theorem](https://en.wikipedia.org/wiki/Dilworth%27s_theorem), this is known to be equal to the size of the largest set of nodes where no pair can reach each other. In this specific graph, this would equal to the longest decreasing subsequence, which we can find using your favorite way to compute longest decreasing subsequence in $O(N\log(N))$. Unfortunately, this doesn't easily tell us which robot is assigned to which apple. Note that you don't need to know Dilworth's theorem for this subtask: this special case is more well-known than the general theorem.

## Subtask 2, 3: small number of robots or apples

Let's develop a general algorithm that is constructive.
We will start with having $0$ robots, and process apples one by one in the sorted, letting one existing robot move to the apple, or adding a new robot. First, we can realize that doing the process in this way, every robot can reach the apple when only considering the $x$ coordinate. So the only thing that matters is the $y$ coordinate. Now, which robot should we assign to take the apple? Since $x$ doesn't matter, and lower $y$ always leaves is with more options, it should be the one with highest $y$ that can take the apple!

So, for each apple $y$ value $y_a$, the algorithm is:
- Among all robots with $y \leq y_a$, let the one with highest $y$ take the apple.
- If no such robots exists, add a new robot and let it take the apple.

This can be simulated in $O(NR)$, where $R$ is the number of robots needed.

n=int(input())
apples=[]
for i in range(n):
    t,x=map(int,input().split())
    apples.append((t-x, t+x, i))

apples.sort()

robots = []
which_robot = [-1] * n
def filter_robots(y): # Return all robots that can catch this apple
    return [i for i in range(len(robots)) if robots[i][1] <= y]

for i, (x, y, apple_index) in enumerate(apples):
    if good_robots := filter_robots(y): # There is some robot
        catching_robot = max(good_robots, key=lambda i: robots[i][1])
        which_robot[apple_index] = catching_robot+1
        robots[catching_robot] = (x,y)
    else: # Add a new robot
        robots.append((x,y))
        which_robot[apple_index] = len(robots)

print(len(robots))
print(*which_robot)

## Full solution
To optimize the previous solution, let's concretely formulate what makes it slow. We need a data structure that allows us to extract the largest $y$ less than a certain $y$, remove it and then insert a new $y$ value. This is exactly what C++ sets solve. We can store pairs $(y, i)$, where $i$ is the index of the robot. This is enough for a full solution.

To optimize it further, we can realize that when we erase and insert, we don't actually change the order of items. Thus, it suffices to just store a vector and do binary searches in it. To make sure that adding new robots is done by adding to the end, we will store the list of robots in reverse. This also works in Python. The final algorithm is very similar to patience sorting, which is because we are basically computing the longest decreasing subsequence.