P16904 [CCO 2026] Asymmetry

Alice and Bob will play a game with a grid with $N$ rows and $M$ columns where $M$ is even. There is also a positive integer $K$. Initially, each cell of the grid contains a value between $0$ and $K$, inclusive, and each cell is **unmarked**. The players take turns alternately, **with Alice going first**. The game ends when the current player cannot make a move. On each player's turn, they select an **unmarked** cell of the grid and an integer $a$ between $0$ and $K$, inclusive. Then, they set the value of that cell to $a$ and **mark** all cells in the same column as the one selected (including the selected cell). The *asymmetry* of the grid is the sum of the absolute differences between the value of one cell and its corresponding cell when **horizontally** reflected across the middle of the grid over all such pairs of cells. More formally, it is $$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right),$$ where $g_{i,j}$ is the value of the cell in the $i$-th row from the top and $j$-th column from the left. For example, the following $2 \times 4$ grid has an asymmetry of $|8-0|+|4-2|+|6-6|+|7-9|=12$. $$ \begin{array}{|c|c|c|c|} \hline 8 & 4 & 2 & 0 \\ \hline 6 & 7 & 9 & 6 \\ \hline \end{array} $$ Alice wishes to minimize the asymmetry of the grid when the game ends while Bob wishes to maximize it. If both players play optimally, what is the asymmetry of the final grid?

The first line of input will consist of $3$ space-separated integers $N$, $M$, and $K$ ($1 \le N,M \le 2\,000$, $M$ is even, $1 \le K \le 10^9$). The next $N$ lines each contain $M$ integers, where the $i$-th line contains integers $g_{i,1},\ldots,g_{i,M}$ ($0 \le g_{i,j} \le K$), the values of the cells from left to right in the $i$-th row from the top.

Output a single integer, the asymmetry of the final grid if Alice and Bob play optimally.

**Explanation of Output for Sample Input $1$** There are only $2$ columns, so each player will make $1$ move. With Alice going first, she can perform the following moves: - Select one of the cells with a value of $1$ in the first column and set its value to $0$. Then the optimal move for Bob is to set the value of the cell on the same row in the second column to $1$. The final grid will be like the original grid with exactly one of the first $2$ rows of $0$s and $1$s swapped. Such a grid has an asymmetry of $|1-0|+|0-1|+|0-0|=2$. - Select one of the cells in the second column and first $2$ rows and set its value to $1$. Then the optimal move for Bob is to set the value of the cell on the same row in the first column to $0$. Again, the final grid will be like the original grid with exactly one of the first $2$ rows of $0$s and $1$s swapped. Such a grid has an asymmetry of $2$. - Select one of the cells in the third row and set its value to $1$. Then the optimal move for Bob can be to set the value of the other cell in the third row to $0$. Note that the cell selected already had the value of $0$, and that such a move is allowed. Then, the final grid will have a $0$ and a $1$ in each row, resulting in an asymmetry of $3$. - Select any cell and set its value to its current value. Then the optimal move for Bob is to set the value of the cell in the remaining unmarked column and third row to $1$. The final grid will have a $0$ and a $1$ in each row, resulting in an asymmetry of $3$. We see that regardless of how Alice makes her move, Bob will be able to play in such a way that the asymmetry is at least $2$. If Alice selects her first move optimally, she can ensure that Bob cannot make the final asymmetry more than $2$. Thus, the asymmetry if both players play optimally is $2$. **Explanation of Output for Sample Input $2$** There is only a single row, so for each move, the current player will select an unmarked cell and set it to any value between $0$ and $21$, inclusive. The game ends after each player has made $5$ moves, resulting in all $10$ cells being marked. **Explanation of Output for Sample Input $3$** Note that the answer may not fit within a $32$-bit integer. The following table shows how the $25$ available marks are distributed: | Marks Awarded | Bounds on $N$ | Bounds on $M$ | Bounds on $K$ | |:-:|:-:|:-:|:-:| | $2$ marks | $N=1$ | $2 \le M \le 2\,000$ | $1 \le K \le 10^9$ | | $3$ marks | $1 \le N \le 2\,000$ | $M=2$ | $K=1$ | | $3$ marks | ^ | ^ | $1 \le K \le 10$ | | $3$ marks | ^ | ^ | $1 \le K \le 10^9$ | | $4$ marks | ^ | $2 \le M \le 2\,000$ | $K=1$ | | $4$ marks | ^ | ^ | $1 \le K \le 10$ | | $6$ marks | ^ | ^ | $1 \le K \le 10^9$ |