PROBLEM LINK:
Author: Kevin Atienza
Tester: Utkarsh Lath and Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Range trees, sqrt decomposition
PROBLEM:
Chef is in a new kitchen, which is a W\times H grid. He’s always in (x_C,y_C). A cell is reachable if it can be reached from (x_C,y_C) by traveling only horizontally or vertically, and turning at most once. The i th appliance is placed at (x_i,y_i), making that cell impassable. For every i, what is the number of reachable cells after placing the first i appliances?
QUICK EXPLANATION:
We can treat the four quadrants from (x_C,y_C) as different instances of the same problem. (Though we need to handle double-counting in cells in the same row/column as (x_C,y_C).) In each separate problem, after rotation/reflection, we can assume that (x_C,y_C) = (1,1).
We compute the number of reachable cells R by placing the appliances one by one and adjusting R. Let’s assume first that all appliances are not aligned with Chef, i.e. (x_i,y_i) satisfies x_i > 1 and y_i > 1.
We maintain two arrays:
- X_{\min}[y] (for 1 < y \le H). X_{\min}[y] is the smallest unreachable cell (x,y) among all x. Initially it is W+1.
- Y_{\min}[x] (for 1 < x \le W) is defined similarly. Initially it is H+1.
A cell (x,y) is not reachable iff x \ge X_{\min}[y] and y \ge Y_{\min}[x]. Therefore, on placing a new appliance (x_n,y_n):
- If x_n \ge X_{\min}[y_n] and y_n \ge Y_{\min}[x_n], then nothing needs to be done.
- Otherwise, decrease R by one (for (x_n,y_n) itself).
- Count the number of points (x_n,y) that become unreachable, i.e. how many y s are there such that y_n < y < Y_{\min}[x_n] and X_{\min}[y] \le x_n, and subtract this from R.
- Similarly, count the number of points (x,y_n) that become unreachable, and subtract this from R.
- Finally, set X_{\min}[y_n] = \min(X_{\min}[y_n], x_n) and Y_{\min}[x_n] = \min(Y_{\min}[x_n], y_n).
Therefore, we need to support the following operation in an array A[1]\ldots, A[L] quickly (along with updates):
Given i,j and v, find the number of k such that i \le k \le j and A[k] \le v.
This can be done using sqrt decomposition or 2D range trees.
Next, we have to handle appliances (x_n,y_n) where x_n = 1 or y_n = 1. There is a simple trick to this:
- extend the grid by one cell downwards and leftwards
- move the position of Chef from (1,1) to (0,0)
- Replace every appliance (1,y) with the following series of appliances: [(1,y), (1,y+1), (1,y+2), \ldots (1,y'-1)] where (1,y') is a previous appliance of that form with the smallest y'.
- Replace every appliance (x,1) with the following series of appliances: [(x,1), (x+1,1), (x+2,1), \ldots (x'-1,1)] where (x',1) is a previous appliance of that form with the smallest x'.
You also have to adjust R to account for the added cells (x,y) where x = 0 or y = 0 (by subtracting W + H + 1).
Therefore, we have reduced the problem to the case without appliances aligned to Chef!
EXPLANATION:
Reducing to the corner case
It’s intuitive that we can treat the four quadrants relative to (x_C,y_C) as separate problems. For example, placing an appliance on a given quadrant does not affect the number of reachable cells in other quadrants. Also, placing an appliance sharing the same row or column as (x_C,y_C) only affects the number of reachable cells in the two quadrants where it belongs. Therefore, we can split the problem into four problems of the same kind as the original but with the Chef in one of the corners.
Doing it this way though, we are double-counting the cells that are aligned to (x_C,y_C) (because they are counted in two quadrants). Thankfully, the answer can easily be adjusted in O(1) time accounting for this. We only need to keep track of four numbers: The nearest appliances in each of the four cardinal directions relative to (x_C,y_C) (north, south, east and west). If we know these numbers, we can compute exactly how many reachable cells there are in the four directions, and thus the exact number of double-counted cells (which we can subtract from our answer). Finally, the Chef’s location is quadruple-counted so we need to adjust for that too (but this is very easy).
Therefore, we can assume that (x_C,y_C) is in a corner, or to be even simpler, (x_C,y_C) = (1,1) by rotation/reflection. The remainder of the editorial focuses on the exact same problem, but with (x_C,y_C) = (1,1).
No appliances aligned with Chef
Our general algorithm will be to maintain the number of reachable cells R, starting with WH, then adjusting it after placing each appliance. Our goal, after placing each appliance, is to compute the number of newly unreachable cells.
Let’s assume first that all placed appliances are not aligned with Chef, i.e. all (x_n,y_n) satisfies x_n > 1 and y_n > 1. Also, assume we have placed the first n-1 appliances \{(x_i,y_i) : 1 \le i < n \} already, and that we have computed the number of reachable cells R up to that point. We now want to place (x_n,y_n), and we have to adjust R, so we want to know how many newly unreachable cells there are after placing (x_n,y_n).
Remember that the Chef is at (1,1), so after placing (x_n,y_n), the only cells that it could have blocked are those found above or to the right of it. But not all of them. For example, it only blocks (x,y) for x = x_n and y > y_n if there already exists an appliance (x_m,y_m) such that y = y_m and x > x_m. In general,
A block (x,y) is unreachable if and only if there are two placed appliances (x',y), (x,y') such that y \ge y' and x \ge x'.
If we define two new functions:
- X_{n}(y) be the smallest value x such that (x,y) is one of the first n appliances. (or W+1 if no such appliance exists.)
- Y_{n}(x) be the smallest value y such that (x,y) is one of the first n appliances. (or H+1 if no such appliance exists.)
Then the above statement is equivalent to:
A block (x,y) is unreachable if and only if y \ge Y_{n}(x) and x \ge X_{n}(y).
After placing the appliance (x_n,y_n), there are two kinds of newly unreachable cells, those above (x_n,y_n) and those to the right. With this formulation:
- The number of newly unreachable cells above (x_n,y_n) is the number of y s such that y_n < y < Y_{n-1}(x_n) and X_{n-1}(y) < x_n.
- The number of newly unreachable cells to the right of (x_n,y_n) is the number of x s such that x_n < x < X_{n-1}(y_n) and Y_{n-1}(x) < y_n.
Finally, (x_n,y_n) itself is newly unreachable, so we count it separately.
Algorithm with two arrays
It looks promising that maintaining two arrays X[y] and Y[x] will give us a fast solution. On placing (x_n,y_n), our assumptions will be:
- We know R after placing all appliances < n.
- X contains all values of X_{n-1}
- Y contains all values of Y_{n-1}
And our goal will be to:
- Count the number of newly unreachable cells, and subtract it from R. (Then print R)
- Update X and Y so they will both contain values of X_n and Y_n.
The algorithm will look like this:
- If x_n \ge X[y_n] and y_n \ge Y[x_n], then nothing needs to be done, i.e. R, X and Y will stay the same. (why?)
- Otherwise, we decrease R by one (for the point (x_n,y_n)).
- Count how many y s there are such that y_n < y < Y[x_n] and X[y] < x_n and subtract it from R.
- Count how many x s there are such that x_n < x < X[y_n] and Y[x] < y_n and subtract it from R.
- To update X, we only need to set X[y_n] = \min(X[y_n], x_n). All other values stay the same.
- To update Y, we only need to set Y[x_n] = \min(Y[x_n], y_n). All other values stay the same.
It’s easy to see why this algorithm is correct. Unfortunately it is slow.
Range queries
Clearly, computing the adjustments for R takes linear time in the worst case, so we must be able to support the following operation in an array A[1]\ldots, A[L] quickly:
Given i,j and v, find the number of k such that i < k < j and A[k] < v.
Our structure must be able to handle updates in the array too. But these are just standard dynamic 2D range queries. A well-known way to process them is to use a 2D range tree which can be constructed in O(L \log L) time and answers queries in O(\log^2 L) time each. With fractional cascading, the query time may be reduced to O(\log L).
Another algorithm for 2D range queries, which is much simpler to implement, is good old sqrt decomposition. We partition the array into \Theta(L/U) blocks of size U each. (The last block can have fewer than U elements.) For each block, we also maintain a sorted version of it. An update in such a structure takes only O(U) time, by inserting it in the sorted version a la insertion sort. To answer a 2D range query, we simply use binary search for v on all blocks completely contained in [i,j] (with worst case O(L/U \log U)), and then adjust for the extra O(U) elements at both ends of [i,j], for those elements outside of blocks completely contained in [i,j] (with worst case O(U)).
To obtain an optimal running time, we must choose U such that O(L/U \log U) = O(U). The best choice for U is \Theta(\sqrt{L \log L}), so the running time of a query would be O(\sqrt{L \log L}). (The presence of the square root sign is why this is called sqrt decomposition.) This is theoretically slower than O(\log L), but has the advantage of being simpler to code, and possibly actually running faster due to the hidden O constant being smaller.
Appliances aligned to Chef
The algorithm above is now fast enough to answer the problem, assuming there are no appliances on the same row or column as Chef. Here, we will discuss how to handle such appliances, i.e. appliances (x_n,y_n) where x_n = 1 or y_n = 1. The problem with these appliances is that the following property is not true:
A block (x,y) is unreachable if and only if y \ge Y_{n}(x) and x \ge X_{n}(y).
For example, given two appliances (1,5) and (3,2), the block (3,6) is unreachable, but “x \ge X_{n}(y)” is not true. The correct criterion now for unreachability is the following:
A block (x,y) is unreachable if and only if the following two conditions hold:
- y \ge Y_{n}(x) or x \ge X_{n}(1).
- x \ge X_{n}(y) or y \ge Y_{n}(1).
The first condition prevents the right-up path, and the second prevents the up-right path. So if both are true, then there is no path to (x,y).
There is actually a simple trick that makes our algorithm above applicable to us! The trick here is to replace every appliance with x = 1 or y = 1 with a series of appliances. Specifically, suppose we want to place the appliance (x_n,1). Let (x_m,1) be the placed appliance of that form with the minimum x.
- If x_m < x_n, then placing (x_n,1) does nothing, because (x_n,1) is already unreachable.
- Otherwise, x_m > x_n. In this case, we replace (x_n,1) with a series of appliances (x_m-1,1), (x_m-2,1), (x_m-3,1), \ldots, (x_n,1).
A similar replacement can be done to appliances of the form (1,y_n). With these modifications, our algorithm above will now work!
But why does this work? The key here is noticing that by placing (x_n,1), we’re effectively blocking all right-up paths which turn at a point (x,1) where x \ge x_n. Thus, we can emulate the effect by setting Y[x] = 1 for all x \ge x_n. The case is similar when placing (1,y_n).
One problem you might say is that increases the number of appliances, but this is a non-problem, because the number of appliances we add is less than W + H.
With this modification, our algorithm above will now work in all cases!
Time Complexity:
O((N + W + H)\sqrt{(W + H) \log (W + H)})
AUTHOR’S AND TESTER’S SOLUTIONS:
Will be uploaded soon.