Division Avoidance
Contest: European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3100
Tags: greedy, math

A newly discovered organism can be represented as a set of cells on an infinite grid. There is a coordinate system on the grid such that each cell has two integer coordinates $$$x$$$ and $$$y$$$. A cell with coordinates $$$x=a$$$ and $$$y=b$$$ will be denoted as $$$(a, b)$$$.

Initially, the organism consists of a single cell $$$(0, 0)$$$. Then zero or more divisions can happen. In one division, a cell $$$(a, b)$$$ is removed and replaced by two cells $$$(a+1, b)$$$ and $$$(a, b+1)$$$.

For example, after the first division, the organism always consists of two cells $$$(1, 0)$$$ and $$$(0, 1)$$$, and after the second division, it is either the three cells $$$(2, 0)$$$, $$$(1, 1)$$$ and $$$(0, 1)$$$, or the three cells $$$(1, 0)$$$, $$$(1, 1)$$$ and $$$(0, 2)$$$.

A division of a cell $$$(a, b)$$$ can only happen if the cells $$$(a+1, b)$$$ and $$$(a, b+1)$$$ are not yet part of the organism. For example, the cell $$$(1, 0)$$$ cannot divide if the organism currently consists of the three cells $$$(1, 0)$$$, $$$(1, 1)$$$ and $$$(0, 2)$$$, since the cell $$$(1, 1)$$$ that would be one of the results of this division is already part of the organism.

You are given a set of forbidden cells $$${(c_i, d_i)}$$$. Is it possible for the organism to contain none of those cells after zero or more divisions?

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of forbidden cells.

The next $$$n$$$ lines contain two integers each. The $$$i$$$-th of such lines contains $$$c_i$$$ and $$$d_i$$$ ($$$0 \le c_i, d_i \le 10^9$$$) — the coordinates of the $$$i$$$-th forbidden cell. It is guaranteed that all forbidden cells are distinct.

It is guaranteed that the sum of values of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print $$$\texttt{YES}$$$ if it is possible for the organism to contain no forbidden cells after zero or more divisions. Otherwise, print $$$\texttt{NO}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, dividing the following cells in the following order creates an organism without any forbidden cells: $$$(0, 0)$$$, $$$(1, 0)$$$, $$$(1, 1)$$$, $$$(0, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(1, 2)$$$, $$$(1, 1)$$$. The following picture demonstrates how the organism changes during this process:

In the second test case, you can see that, surprisingly, any organism always has at least one cell in the $$$0 \le x, y \le 3$$$ square, no matter how many divisions we do.

Example input:
2
4
0 0
1 0
0 1
1 1
16
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3

Example output:
YES
NO

Editorial:
Looking at the solution for the sample, the most difficulty seems to come from the condition in bold: A division of a cell $$$(a, b)$$$ can only happen if the cells $$$(a+1, b)$$$ and $$$(a, b+1)$$$ are not yet part of the organism. It forces us to clean up space, potentially recursively, before a division that we want to happen can actually happen.
What happens if we remove this condition, instead allowing to have multiple copies of a cell with the same coordinates in the organism? Then of course it is possible to avoid any finite set of forbidden cells, so this version of the problem is not very useful. However, consider the following modification instead: we allow to have multiple copies of a cell with the same coordinates temporarily, but the final state of the organism must have at most one copy of any cell, and of course zero copies of the forbidden cells. It turns out that this modification is equivalent to the original problem!
To see why, consider a sequence of operations that starts from $$$(0,0)$$$ and ends in a valid state as described above, but has multiple copies of some cells in its intermediate states. We claim that it is possible to reoder its sequence of operations in such a way that all operations stay valid, but we never have multiple copies of the same cell. Notice that reodering the operations does not change the end state, because each operation can be seen as subtracting 1 from the number of occurrences of the cell $$$(a,b)$$$ and adding 1 to the numbers of occurrences of the cells $$$(a+1,b)$$$ and $$$(a,b+1)$$$, and such subtractions and additions clearly commute.
To avoid getting multiple copies of the same cell, we can repeatedly do the following to produce a reordering: from all operations that are yet to be done in the reference sequence of operations, we choose the operation $$$(a,b)$$$ such that $$$(a,b)$$$ is part of the organism and $$$a+b$$$ is maximized. Maximizing $$$a+b$$$ guarantees that we are not going to have two copies of the same cell: when we decide to divide $$$(a,b)$$$, we cannot have $$$(a+1,b)$$$ in the organism, as otherwise $$$(a+1,b)$$$ would also be one of the operations yet to be done (since the final state has at most one cell at $$$(a+1,b)$$$), so we should have chosen $$$(a+1,b)$$$ as the opeation to do over $$$(a,b)$$$ since $$$a+1+b>a+b$$$, which is a contradiction.
Now we know that we can focus on what operations to do, and no longer care about the order in which we do them. It means that we can choose the order that suits us best, and as long as we do only necessary operations, we will always arrive at exactly the same result. It is natural to go by diagonals: first consider all operations with $$$a+b=0$$$, then all operations with $$$a+b=1$$$, then all operations with $$$a+b=2$$$, and so on. The operations with $$$a+b=z$$$ only create new cells with $$$a+b=z+1$$$, so those operations are independent within each value of $$$z$$$, and we never have to return to smaller values of $$$z$$$.
This leads to the following solution: we go in increasing order of $$$z$$$, and before processing a given value of $$$z$$$ we know how many copies of each cell with $$$a+b=z$$$ we have, as an array $$$d_{z,a}$$$. Now for each forbidden cell $$$(a,b)$$$ with $$$a+b=z$$$ we have to apply division to it $$$d_{z,a}$$$ times, which means that we have to add $$$d_{z,a}$$$ to $$$d_{z+1,a}$$$ and to $$$d_{z+1,a+1}$$$. Similarly, for each non-forbidden cell we have to apply division to it $$$\max(0,d_{z,a}-1)$$$ times. We continue while the array $$$d_z$$$ has at least one non-zero value. If this process terminates, the answer is $$$\texttt{YES}$$$. If it runs infinitely, the answer is $$$\texttt{NO}$$$.
For example, in the first sample case we get the following arrays:
• $$$d_0 = (1)$$$
• $$$d_1 = (1, 1)$$$
• $$$d_2 = (1, 2, 1)$$$
• $$$d_3 = (0, 2, 2, 0)$$$
• $$$d_4 = (0, 1, 2, 1, 0)$$$
• $$$d_5 = (0, 0, 1, 1, 0, 0)$$$
• $$$d_6 = (0, 0, 0, 0, 0, 0, 0)$$$
However, this solution is still not practical: how do we check if the process runs infinitely? Looking at a few examples can help spot a pattern: if we ever get a 3, then the process never stops. Having identified this pattern, it is relatively easy to prove. Since we always add the same number to two adjacent elements of $$$d_{z+1}$$$, getting a 3 in it means that one of its adjacent numbers will be at least 2. And then, even if there are no forbidden cells at all anymore, $$$3, 2$$$ becomes $$$2, 3, 1$$$ on the next diagonal, so we have a 3 adjacent to a 2 again, and this will repeat forever.
What if we never get a 3? Then it turns out that as soon as we pass all forbidden cells, we will start going down towards all zeros and eventually get there. With no forbidden cells, a 1 does not propagate to the next diagonal at all, and a 2 propagates two adjacent +1s to the next diagonal. So if we have a sequence that looks like $$$(2, 2, \dots, 2)$$$ with $$$k$$$ 2s, on the next diagonal we will get $$$(1, 2, 2, \dots, 2, 1)$$$ with $$$k-1$$$ 2s, so after $$$k$$$ diagonals the 2s will disappear.
This argument also demonstrates that the process will converge after $$$O(n)$$$ steps, since every forbidden cell will create a constant amount of additional 2s, and without forbidden cells the number of 2s decreases by at least 1 per step. Therefore we finally have a complete solution, albeit one that runs in $$$O(n^2)$$$ which is too slow for $$$n=10^6$$$.
In order to make it faster, we have to take a closer look at the changes of the array $$$d$$$. Suppose the array looks like $$$(0, 0, \dots, 0, 1, 2, 2, \dots, 2, 1, 0, 0, \dots, 0)$$$ for a certain diagonal. How is it going to look for the next diagonal depending on the locations of the forbidden cells on this diagonal?
• If a cell with a 0 is forbidden, this changes nothing.
• If a cell with a 2 is forbidden, then we are going to get a 3 on the next diagonal, and the answer will be $$$\texttt{NO}$$$.
• So the only interesting question is whether the two cells with 1 are forbidden:
• If none of the 1s are forbidden, then we get the same structure on the next diagonal, but with the left 1 moving one position to the right (and therefore the number of 2s decreases by one).
• If only the left 1 is forbidden, then we still get the same pattern on the next diagonal, but the left 1 stays in the same position (and therefore the number of 2s is unchanged).
• If only the right 1 is forbidden, then it moves one position to the right on the next diagonal (and therefore the number of 2s is also unchanged).
• Finally, if both 1s are forbidden, then we still get the same pattern on the next diagonal, but with the number of 2s actually increasing by one.
This suggests the following idea: when there are no 3s or higher on a diagonal, and when not all numbers are 0s, the array $$$d$$$ for it always has the form $$$(0, 0, \dots, 0, 1, 2, 2, \dots, 2, 1, 0, 0, \dots, 0)$$$: exactly two 1s, zero or more 2s in between the 1s, and 0s on the outside. This is not entirely correct: in the sample discussed above there is also the case of $$$(0, 0, \dots, 0, 2, 2, 0, 0, \dots, 0)$$$: exactly two 2s surrounded by all 0s. This pattern always appears after $$$(0, 0, \dots, 0, 1, 2, 1, 0, 0, \dots, 0)$$$ when the 2 is forbidden, and it is actually the only situation where a 2 can be forbidden without getting a 3. It turns out that this is the only special case, and we can easily prove by induction that we always have one of the patterns mentioned above.
Therefore as we go in increasing order of $$$z$$$, for the diagonal $$$a+b=z$$$ we can simply store two integers and a boolean: the position of the left 1, the position of the right 1, and whether we have the special $$$0, 2, 2, 0$$$ case. We need to find all forbidden cells on the given diagonal, which we can achieve by sorting the forbidden cells by the sum of the coordinates and keeping a pointer into the sorted array as we increase $$$z$$$. After that we can determine the state of the next diagonal in $$$O(1)$$$, so the total running time of this solution is $$$O(n\log n)$$$ if we use normal sorting, or $$$O(n)$$$ if we use counting/radix sorting (we can use counting sorting since we only care about the first $$$O(n)$$$ diagonals).
The time limit in this problem was pretty tight, so even the $$$O(n)$$$ solution had to be implemented with care. The reason for this was that the $$$O(n^2)$$$ solution mentioned above yields itself perfectly to optimizations. The only quadratic part is a couple of small inner loops looking roughly like this:
The C++ compilers are very good at vectorizing such code using SIMD instructions (which you can enable using some pragmas). But we can also help the compiler because we know that the values in our arrays are always only 0, 1 or 2, so we can actually represent our array as two bitsets. We could not get the compiler to efficiently vectorize std::bitset, but it turns out that gcc supports a relatively new syntax
This defines a new type that works like an array of 4 uint64's, but supports element-wise operations including bitwise operations that automatically use vectorization. Using this trick made the $$$O(n^2)$$$ solution mentioned above run in under 7 seconds for $$$n=10^6$$$, therefore to make sure this solution does not pass we had to set the tight time limit.
One other potentially relevant remark for implementing the solution: we have mentioned above that we only care about the first $$$O(n)$$$ diagonals, but what is the constant hidden in the $$$O$$$-notation? Initially one might think that a case with the following forbidden cells is the worst: $$$(0, 0), (1, 0), (2, 0), \dots, (\lceil\frac{n-1}{2}\rceil, 0), (0, 1), (0, 2), \dots, (0, \lfloor\frac{n-1}{2}\rfloor)$$$. The final state of the organism in this case is a big rectangle (so it also catches solutions that assume we only do a linear number of divisions), and we have $$$n+1$$$ nonzero diagonals in this case.
However, the $$$0, 2, 2, 0$$$ exception from the solution above allows to construct a testcase that is twice nastier: $$$(0, 0), (0, 1), (1, 0), (1, 1), (2, 2), \dots, (n-3, n-3)$$$. In this case the array $$$d$$$ constantly changes from $$$1, 2, 1$$$ to $$$0, 2, 2, 0$$$ and back, and we get $$$2n-2$$$ nonzero diagonals. So if your solution hardcodes the number of diagonals to process you need to go as high as $$$2n-2$$$.
For more context about the origins of this problem and related topics you can check out the following paper: F. Chung, R. Graham, J. Morrison, A. Odlyzko, Pebbling a Chessboard, Amer. Math. Monthly 102 (1995), pp. 113–123.