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

## D - Add to Square Editorial by evima

### [1] Characterization of the grid after the operations

Let $$A$$ and $$B$$ denote the grid before and after the operations, respectively.

For each row and each column, the alternating sum of the written numbers is an invariant. That is, the following holds:

• For every $$i$$, $$\sum_{j=1}^W A_{ij} (-1)^{i+j} = \sum_{j=1}^W B_{ij} (-1)^{i+j}$$
• For every $$j$$, $$\sum_{i=1}^H A_{ij} (-1)^{i+j} = \sum_{i=1}^H B_{ij} (-1)^{i+j}$$

Thus, for these $$H+W$$ formulae to hold is a necessary condition for $$B$$ to be obtained by the operations.

Let us verify that this necessary condition is also a sufficient condition for $$B$$ to be obtained by the operations.

By matching $$A_{i,j}$$ to $$B_{i,j}$$ with the operation on $$A_{i,j}, A_{i,j+1}, A_{i+1,j}, A_{i+1,j+1}$$ in ascending order of $$i, j$$, we can match $$A_{i,j}$$ to $$B_{i,j}$$ for every $$1\leq i < H$$ and $$1\leq j < W$$.

If two grids have the same alternating sum in each row and each column, and the same number in the square $$(i,j)$$ for each $$1\leq i < H$$, $$1\leq j < W$$, they have the same numbers in all squares. Thus, when the necessary condition above holds, the procedure above can match $$A$$ to $$B$$.

### [2] Rephrasing the problem

For convenience in dealing with alternating sums, let us multiply the value in the square $$(i, j)$$ by $$(-1)^{i+j}$$ to rephrase the problem into the following.

You are given a state of the grid $$A$$. Among the states of the grid $$B$$ with the same sum in each row and each column, find one that minimizes $$\sum |B_{ij}|$$.

By letting $$x_i$$ and $$y_j$$ denote the sums of each row and each column in $$A$$, it can be further rephrased into the following.

You are given sequences $$(x_1, \ldots, x_H)$$ and $$(y_1, \ldots, y_W)$$ such that $$\sum x_i = \sum y_j$$. Among the states of the grid $$B$$ with the sum of each row equal to $$x_i$$ and the sum of each column equal to $$y_i$$, find one that minimizes $$\sum |B_{ij}|$$.

Furthermore, let us consider starting with $$B_{i,j} = 0$$ and changing it to $$B_{i,j} = b$$, which changes the differences between a row’s sum and $$x_i$$ and between a column’s sum and $$y_i$$. The problem is again rephrased into the following:

You are given sequences $$(x_1, \ldots, x_H)$$ and $$(y_1, \ldots, y_W)$$ such that $$\sum x_i = \sum y_j$$. Make all $$x_i$$ and $$y_j$$ $$0$$ with the minimum cost, using the following operation.

Operation $$(i, j, b)$$: Add $$-b$$ to each of $$x_i$$ and $$y_j$$, for a cost of $$|b|$$.

### [3] Constructing the optimal solution

Let $$X = \sum |x_i|$$ and $$Y = \sum |y_j|$$. Operation $$(i,j,b)$$ changes $$X$$ and $$Y$$ by at most $$|b|$$, so the following holds:

• The minimum cost $$\geq \max\{X, Y\}$$

Let us show that the equality in this inequality holds. Actually, the sequence of operations below achieves the minimum possible cost.

1. If there is $$(i,j)$$ such that $$x_i < 0$$ and $$y_j < 0$$, do Operation $$(i,j,-1)$$. Repeat this as long as possible.
2. If there is $$(i,j)$$ such that $$x_i > 0$$ and $$y_j > 0$$, do Operation $$(i,j,-_)$$. Repeat this as long as possible.
3. If there is $$(i_1,i_2)$$ such that $$x_{i_1} > 0$$ and $$x_{i_2} < 0$$, do Operation $$(i_1, 1, 1)$$ and Operation $$(i_2,1,-1)$$. Repeat this as long as possible.
4. If there is $$(j_1,j_2)$$ such that $$y_{j_1} > 0$$ and $$y_{j_2} < 0$$ , do Operation $$(1,j_1, 1)$$ and Operation $$(1,j_2,-1)$$. Repeat this as long as possible.

We need to verify that:

• An operation always decreases $$\max\{\sum |x_i|,\sum |y_j|\}$$ by the amount equal to the cost
• $$\sum |x_i| = \sum |y_j| = 0$$ is eventually reached

This can be proved using properties such as the following:

• During the process, $$\sum x_i = \sum y_j$$ always hold.
• Therefore, after repeating step 1. and 2. as much as possible, $$\sum |x_i|=0$$ or $$\sum |y_j| =0$$ holds.

This proof also gives a construction of an optimal solution, so the problem can be solved in $$\Theta(HW)$$ time by summing up the arguments so far.

### [4] Reference: Invariants and polynomials

The conclusion in [1] can also be derived from an argument using polynomials.

Let us associate a state of the grid $$A$$ with a bivariate polynomial $$\sum_{i,j} A_{i,j} x^iy^j$$. Then, the operation in the problem can be interpreted as adding a polynomial $$P$$ such that $$(1+x)(1+y) \mid P$$.

The polynomial ring $$\mathbb{Z}[x,y]$$ is a unique factorization domain, and $$fg\mid P \iff f\mid P \text{and} g\mid P$$ holds for irreducible polynomials $$f, g$$ ($$f\neq \pm g$$) and a polynomial $$P$$, so we have:

$(1+x)(1+y)\mid P(x,y) \iff 1+x\mid P(x,y) \text{and} 1+y\mid P(x,y) \iff P(-1,y) = P(x,-1) = 0$

This leads to the characterization based on the alternating sums of the rows and columns.

posted:
last update: