Canadian Computing Olympiad 2026: Day 2, Problem 1

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 $$\displaystyle \sum_{1\le i\le N}\left(\sum_{1\le j\le M/2}\left|g_{i,j}-g_{i, M-j+1}\right|\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~.

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?

Input Specification

The first line of input will consist of three space-separated integers ~N~, ~M~, and ~K~ (~1 \leq N, M \leq 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}\dots,g_{i,M}~ (~0\leq g_{i,j}\leq K~), the values of the cells from left to right in the ~i~-th row from the top.

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\leq N \leq 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\le2\,000~	~K=1~
4 marks			~1\le K\le 10~
6 marks			~1\le K\le 10^9~

Output Specification

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

Sample Input 1

3 2 1
1 0
1 0
0 0

Output for Sample Input 1

2

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 two 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 two 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 two 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~.

Sample Input 2

1 10 21
4 2 0 6 7 6 9 9 10 21

Output for Sample Input 2

55

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.

Sample Input 3

4 6 986754321
219759391 882760615 762656191 423465948 621463211 136889371
215621504 385106915 740086459 417915224 551800597 572994766
176308756 365311996 635683450 907755406 590000050 586083433
607011121 457147795 837558908 684766852 946836347 303039615

Output for Sample Input 3

3972378656

Explanation of Output for Sample Input 3

Note that the answer may not fit within a 32-bit integer.