# AtCoder Grand Contest 033

Updated:

AtCoder Grand Contest 033

# Solutions

## B - LRUD Game

$0$-indexed とする。操作を逆順に見ていく。時系列を逆順にする。

## C - Removing Coins

### 解答の正当化

• 最初に選ぶ頂点が根である場合：その根以外の根を $1$ 段階取り除く
• 最初に選ぶ頂点が根以外である場合：全ての根を $1$ 段階取り除く

ことに相当する。

## D - Complexity

Let $N = \max(H, W)$. Assume $0$-indexed.

### Observation

This problem has a strict memory limit. To be short, we have to solve this problem in less than or equal to $O(N ^ 3 \log N)$-time.

First we notice that, suppose we have two rectangles $R _ 0$ and $R _ 1$ with $R _ 0 \subset R _ 1$, the complexity of $R _ 0$ is less than or equal to that of $R _ 1$.

Second we notice that in this problem the complexity of the entire grid does not exceed $16$. This is where $\log N$ appears.

Thus, we define two DP tables as follows.

$dp1[k][x _ 0][x _ 1][y _ 0] = y _ 1$: Fix the level $k$ and the $x$-range $[x _ 0, x _ 1)$. It gives the maximum of $y _ 1$ that satisfies the level $[x _ 0, x _ 1) \times [y _ 0, y _ 1)$ is less than or equal to $k$.
$dp2[k][y _ 0][y _ 1][x _ 0] = x _ 1$: Fix the level $k$ and the $y$-range $[y _ 0, y _ 1)$. It gives the maximum of $x _ 1$ that satisfies the level $[x _ 0, x _ 1) \times [y _ 0, y _ 1)$ is less than or equal to $k$.

We can update $dp1$ and $dp2$ by doubling.

### Solution

First of all we have calculate $dp1[0]$ and $dp2[0]$ directly from the input. This is a routine work, but take care not to make a bug.

Then, we update $dp1[k]$ and $dp2[k]$ by using both $dp1[k - 1]$ and $dp2[k - 1]$ for $k = 1, \dots, 16$.

#### Idea

By definition, we admit that the complexity of the rectangle $R$ is less than or equal to $k$ if and only if there exists a separation $R _ 1 \cup R _ 2 = R$ whose complexity is both less than or equal to $k - 1$. If the line of the separation is parallel to $x$-axis, we can extract the information from $dp1$. If it is parallel to $y$-axis, we can from $dp2$. This is done by the combination of two-pointer and doubling.

#### Algorithm

For $k = 1, \dots, 16$, for $0 \leq x _ 0 \leq x _ 1 \leq H$, we compute $dp1[k][x _ 0][x _ 1]$. Let $y _ 0 = y _ 1 = W$. While $y _ 0 \geq 0$, if either of the followings holds; \begin{align} dp1[k - 1][x _ 0][x _ 1][dp1[k - 1][x _ 0][x _ 1][y _ 0]] &\geq y _ 1, \\\ dp2[k - 1][y _ 0][y _ 1][dp2[k - 1][y _ 0][y _ 1][x _ 0]] &\geq x _ 1, \end{align} we set $dp1[k][x _ 0][x _ 1][y _ 0] = y _ 1$ and $y _ 0 \mathbin{ {-} {-} };$; otherwise $y _ 1 \mathbin{ {-} {-} }$. We can also fill $dp2[k]$ in the same way.

The answer is $\text{argmin} _ {k} dp0[k][0][H][0] = W.$