[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.

• Sample Code (Python)：https://atcoder.jp/contests/arc135/submissions/29110785

---

[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.