Contest Duration: - (local time) (300 minutes) Back to Home
Official

Another solution

## Overview

By looking at the board after performing the given $$K$$ operations, we can define a comparison function between rows and between columns, and using it we obtain a valid shape for the union of rectangles in the remaining $$(N^2-K)$$ operations.

## Construction

For simplification, we insert some operations at the beginning of the input: we prepare a board with $$(N+1)$$ rows and $$(N+1)$$ columns, and press stamps $$(N+1, N+1), (N, N+1), \ldots, (1, N+1), (N+1, N), \ldots, (N+1, 1)$$ in this order at position $$(1, 1)$$. From now on let $$(N, K) \gets (N+1, 2N+1+K)$$. This doesn’t change the existence of a solution.

Let $$f[x][y]$$ be the color of cell $$(x, y)$$ after performing the given $$K$$ operations. Here we represent colors by operation indices $$1, \ldots, K$$.

For rows $$x, x'$$, we define a relation $$f[x] \prec f[x']$$ as the following condition: We can take a $$y$$ which maximizes $$\max\{ f[x][y], f[x'][y] \}$$ among $$y$$’s with $$f[x][y] \ne f[x'][y]$$, so that $$f[x][y] < f[x'][y]$$.

[Fact] For $$x \ne x'$$, exactly one of $$f[x] \prec f[x']$$ and $$f[x'] \prec f[x]$$ holds.

Let’s call a permutation $$(x_1, \ldots, x_N)$$ of $$(1, \ldots, N)$$ to be a good permutation iff, for each $$h = 1, \ldots, N$$, $$\{x_1, \ldots, x_h\}$$ forms $$h$$ contiguous integers.

[Procedure 1] Let initially $$p$$ to be an empty sequence, and $$l = 1,\, r = N$$. Repeat the following:

• If $$l = r$$, then prepend $$l$$ to $$p$$ and finish.
• If $$f[l] \prec f[r]$$, then prepend $$l$$ to $$p$$, and let $$l \gets l+1$$.
• If $$f[r] \prec f[l]$$, then prepend $$r$$ to $$p$$, and let $$r \gets r-1$$.

In this way we obtain a good permutation $$p = (x_1, \ldots, x_N)$$.

Exchanging the roles of rows and columns, we obtain a good permutation $$(y_1, \ldots, y_N)$$ similarly.

[Procedure 2] We can now construct a correct answer to the problem as follows: Select unused stamps in decreasing lexicographical order of $$(h, w)$$, and paint the rectangle $$\{x_1, \ldots, x_h\} \times \{y_1, \ldots, y_w\}$$.

Finding $$f$$ is the same as the intended solution (Even brute force in $$O(N^4)$$ time with a small constant factor can be accepted). Other procedures can be done in $$O(N^2)$$ time.

## Proof of correctness

### Proof of [Fact]

We have enlarged the board (from $$N \times N$$ to $$(N+1) \times (N+1)$$ and it makes it hold that $$x \ne x'$$ implies $$f[x] \ne f[x']$$.

The problematic situation is that, there are multiple choices for $$y$$ in the definition of $$\prec$$, and we have $$f[x][y] > f[x'][y],\, f[x][y'] < f[x'][y']$$. However this contradicts the fact that we paint a rectangle in the operation $$f[x][y] (= f[x'][y'])$$.

### Properties of the operation

By considering the operations in reverse order, the goal becomes to increasing the area of the union of the rectangles $$1$$ each time.

For a particular sequence of $$N^2$$ operations, we denote by $$U(k)$$ the union of the rectangles in operations with indices $$>k$$, and by $$I(k, x)$$ the set of columns in row $$x$$ of $$U(k)$$, by $$J(k, y)$$ the set of rows in column $$y$$ of $$U(k)$$.

[Property 1] The goal is achieved iff the following conditions hold for any $$k$$:

• The set of stamps $$(h, w)$$ used in operations with indices $$>k$$ constitute a Young diagram.
• There exists a good permutation $$(x_1, \ldots, x_N)$$ such that $$I(k, x_1) \supseteq \cdots \supseteq I(k, x_N)$$.
• There exists a good permutation $$(y_1, \ldots, y_N)$$ such that $$J(k, y_1) \supseteq \cdots \supseteq J(k, y_N)$$.
• The two conditions above means that $$U(k)$$ becomes a Young diagram if we sort rows and columns, and this coincides the Young diagram of $$(h, w)$$’s.

We can prove this by induction. Please refer to the editorial of the intended solution for better understanding.

[Property 2] Furthermore, the goal is achieved iff the following conditions hold for any $$k$$:

• The set of stamps $$(h, w)$$ used in operations with indices $$>k$$ constitute a Young diagram.
• If the rectangle in operation $$k$$ uses row $$x$$ but does not use row $$x'$$, then $$I(k, x) \supseteq I(k, x')$$.
• If the rectangle in operation $$k$$ uses column $$y$$ but does not use column $$y'$$, then $$J(k, y) \supseteq J(k, y')$$.

We can prove this by induction as well. Let’s prove the correctness of the construction using this condition.

### What is a solution?

[Shape Condition] The exact condition for $$U(K)$$ (along with $$I(K, x), J(K, y)$$) to appear in any possible sequence of $$N^2$$ operations achieving the goal, is the following:

• There exists a good permutation $$(x_1, \ldots, x_N)$$ such that $$I(K, x_1) \supseteq \cdots \supseteq I(K, x_N)$$.
• There exists a good permutation $$(y_1, \ldots, y_N)$$ such that $$J(K, y_1) \supseteq \cdots \supseteq J(K, y_N)$$.
• The Young diagram of stamps $$(h, w)$$ unused in the given $$K$$ operations coincides with the Young diagram obtained from $$U(K)$$ by sorting rows and columns.

This is enough because we can perform [Procedure 2].

From now on, we treat the problem as to find $$U(K)$$ satisfying these conditions. We say such $$U(K)$$ is a solution if it achives the goal with the given $$K$$ operations. Here we take a solution to consider, since its existence is guaranteed by the constraints.

### Modifying a solution

We show that we can modify the solution so that $$I(K, x_1) \supseteq \cdots \supseteq I(K, x_N)$$, where $$(x_1, \ldots, x_N)$$ is a good permutation obtained by [Procedure 1] based on $$f$$. We are going to swap rows of $$U(K)$$ along with [Procedure 1].

Consider the case where $$f[l] \prec f[r]$$. From the definition of $$\prec$$, we have an operation $$k$$ such that:

• In each of operations $$k+1, \ldots, K$$, the rectangle uses both or none of rows $$l$$ and $$r$$.
• In operation $$k$$, the rectangle uses row $$r$$ but does not use row $$l$$.

Assume $$I(K, l) \supseteq I(K, r)$$. The first condition above gives $$I(k, l) \supseteq I(k, r)$$. On the other hand, the second condition above with [Property 2] gives $$I(k, l) \subseteq I(k, r)$$. Thus we have $$I(k, l) = I(k, r)$$. In this case $$U(K)$$ is still a solution after we swap its rows $$l$$ and $$r$$. What we need to check are:

• [Shape Condition]. This is kept because $$I(K, x)$$ for $$x < l$$ or $$r < x$$ is a subset of each of $$I(K, l)$$ and $$I(K, r)$$, which is an invariant of this procedure.
• [Property 2]. This is kept because of the first condition above for operations $$k+1, \ldots, K$$, and because $$I(*, l)$$ and $$I(*, r)$$ remain the same for operations $$1, \ldots, k$$.

In this way, we have $$I(K, l) \subseteq I(K, r)$$ with a swap of rows if needed.

The case where $$f[r] \prec f[l]$$ is just symmetric and we have $$I(K, l) \supseteq I(K, r)$$.

The modification completes when $$l = r$$. In the same way, we can modify the solution so that $$J(K, y_1) \supseteq \cdots \supseteq J(K, y_N)$$, where $$(y_1, \ldots, y_N)$$ is a good permutation obtained by [Procedure 1] based on $$f$$. Here we only swap columns and it does not affect the condition for $$I$$.

Since the set of cells satisfying the [Shape Condition] is unique for given $$(x_1, \ldots, x_N)$$ and $$(y_1, \ldots, y_N)$$, the solution after our modification is exactly what we have constructed based on $$f$$.

posted:
last update: