You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFNKCH - Editorial

PROBLEM LINK:

Contest
Practice

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.

This question is marked "community wiki".

asked 21 Jun '15, 22:14

kevinsogo's gravatar image

7★kevinsogo
1.7k474137
accept rate: 11%

edited 18 Jan '16, 06:23

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,344
×152
×52
×47
×2

question asked: 21 Jun '15, 22:14

question was seen: 1,027 times

last updated: 18 Jan '16, 06:23