D - Grid Repainting 3 Editorial by evima
We can rephrase the problem as follows:
We have a bipartite graph with yellow vertices \(1, 2, \cdots, H\) and grey vertices \(1, 2, \cdots, W\).
The edges in this graph correspond to red squares throughout the process.
That is, initially, there is an edge connecting yellow vertex \(i\) and grey vertex \(j\) bidirectionally if and only if \(c_{i, j}=\)R, and you can do the following:
Operation X: Choose a yellow vertex with degree \(1\) or above and erase all edges incident to it.
Operation Y: Choose a grey vertex with degree \(1\) or above and erase all edges incident to it.
The number of white squares will be \(HW - (H-X)(W-Y)\), where \(X\) and \(Y\) are the number of times Operation X and Y are done, respectively. Find one way to maximize this count.
For example, the following grid:
RRR
BBR
BBR
BRR
corresponds to the following graph:
(“操作前”: “Before the operations”, “操作 X/Y を行う”: “Do Operation X/Y”)
First, let us consider the case the graph is a tree.
We will first prove it is impossible to erase all vertices, by contradiction. Assume it is possible to erase all of them. In such a case, there would be a moment where there is just one vertex. However, the degree of that vertex would be \(0\) at that moment, so we would be unable to do any operation, leading to a contradiction.
On the other hand, it is possible to erase all but one vertex, by repeatedly erasing a vertex with degree \(1\). This is possible because a tree always has a vertex with degree \(1\), and erasing it does not disconnect the tree, so we can continue doing it until the graph has no edge, when it has just one vertex.
Since we can choose which vertex to erase in the final operation, we have two optimal choices:
- Do Operation X \(H\) times and Operation Y \(W - 1\) times.
- Do Operation X \(H - 1\) times and Operation Y \(W\) times.
(Illustration of an example)
(The yellow sentence to the left says, “Note that although all squares become white, the number of operations is not ‘full’ (\(H + W\)).”)
Next, let us consider the case the graph is forest.
Let \(K\) be the number of connected components with two or more vertices. If the \(i\)-th connected component contains \(a_i\) yellow vertices and \(b_i\) gray vertices, it is optimal to do one of the following actions:
- Type A: Do Operation X \(a_i\) times and Operation Y \(b_i-1\) times.
- Type B: Do Operation X \(a_i-1\) times and Operation Y \(b_i\) times.
Since we can make this choice for each connected component independently, the total numbers of operations will be one of the following:
- Do Operation X \((a_1 + a_2 + \cdots + a_K)\) times and Operation Y \((b_1 + b_2 + \cdots + b_K) - K\) times.
- Do Operation X \((a_1 + a_2 + \cdots + a_K) - 1\) times and Operation Y \((b_1 + b_2 + \cdots + b_K) - (K - 1)\) times.
- Do Operation X \((a_1 + a_2 + \cdots + a_K) - 2\) times and Operation Y \((b_1 + b_2 + \cdots + b_K) - (K - 2)\) times.
- \(\vdots\)
- Do Operation X \((a_1 + a_2 + \cdots + a_K) - K\) times and Operation Y \((b_1 + b_2 + \cdots + b_K)\) times.
Now, let \(x\) be the number of times we do the type-A action. Then, the number of white squares, \(f(x)\), is represented by the following quadratic function:
\[ f(x) = HW - (H - (a_1 + a_2 + \cdots + a_K - x))(W - (b_1 + b_2 + \cdots + b_K - (K - x))). \]
Since it is convex downward, the optimal choice is one of the following:
- Do the type-A action for every connected component.
- Do the type-B action for every connected component.
For example, in the case shown in the figure below, we can achieve the maximum number of white squares, \(76\), by entirely resorting to the type-A action.
(Illustration of an example)
(“操作Xの回数”: “count of Operation X”, “白の個数”: “number of white squares”)
Finally, let us consider the problem for a general graph.
It turns out that adding edges to trees does not change the answer, because it is impossible to erase all vertices in a connected component, whatever the graph is.
Thus, we can extract a spanning tree from each component using a Union-Find tree, for example, and ignore the remaining edges without changing the final number of white squares. Then, we will have a forest, and we have already solved this case.
(“最大白マス数”: “maximum number of white squares”. The bottom sentence says, “Adding edges to trees do not change the answer, as long as the connected components remain the same!”)
Summary of the solution:
Step 1: Rephrase the problem on a grid to a problem on a bipartite graph.
Step 2: Construct the bipartite graph according to the grid.
Step 3: For each connected component, extract its spanning tree and ignore the remaining edges.
Step 4: Based on the sizes of the connected components, choose to do the Type-A or Type-B action all the time.
Step 5: For each connected component, implement the chosen action by repeatedly erasing a vertex with degree \(1\), or in some other proper way.
It has the time complexity of \(O(HW)\). In Step 5, we can naively search a vertex with degree \(1\) in \(O(H+W)\) time for each operation and still make it run in time, since there will be at most \(H+W\) operations.
Sample Implementations:
posted:
last update: