PROBLEM LINK:Author: 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 doublecounting 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:
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)$:
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:
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 caseIt'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 doublecounting 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 doublecounted cells (which we can subtract from our answer). Finally, the Chef's location is quadruplecounted 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 ChefOur 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 $n1$ 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:
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:
Finally, $(x_n,y_n)$ itself is newly unreachable, so we count it separately. Algorithm with two arraysIt 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:
And our goal will be to:
The algorithm will look like this:
It's easy to see why this algorithm is correct. Unfortunately it is slow. Range queriesClearly, 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 wellknown 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 ChefThe 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:
The first condition prevents the rightup path, and the second prevents the upright 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$.
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 rightup 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 nonproblem, 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.
This question is marked "community wiki".
asked 21 Jun '15, 22:14
