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\).