Editorial for DMOPC '22 Contest 4 P2 - Fake Painting

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: yzhao123

After performing all brushstrokes, there are $4$ ~4~ possible final orientations - not flipped, vertically flipped, horizontally flipped, and both vertically and horizontally flipped. Note that a vertical or horizontal flip can be performed without changing the values of the grid. For example, performing $3$ ~3~ operations choosing the same cell with $K$ ~K~ as $1$ ~1~, $1$ ~1~, $-2$ ~-2~ and all horizontal flips will simply flip the grid horizontally. The same logic applies to vertical flips. Thus, any final orientation can be reached. That means we can check each possible final orientation, and if one of them works, the answer is yes.

Subtask 1

We run the following check for each orientation: calculate a $2 \times 2$ ~2 \times 2~ array $D$ ~D~ which represents the differences between $A_{i,j}$ ~A_{i,j}~ and $T_{i,j}$ ~T_{i,j}~. Let $D_{1,1} = a$ ~D_{1,1} = a~, $D_{1,2} = b$ ~D_{1,2} = b~, $D_{2,1} = c$ ~D_{2,1} = c~, and $D_{2,2} = d$ ~D_{2,2} = d~. Then, $a+d=b+c$ ~a+d=b+c~ must hold. To see this clearly, draw out a $2 \times 2$ ~2 \times 2~ chessboard with alternating white and black tiles. Whenever an operation is performed, $K$ ~K~ is added to $1$ ~1~ white tile and $1$ ~1~ black tile. Thus, the sum of the black tiles must equal the sum of the white tiles.

Subtask 2

We calculate the difference array $D$ ~D~ with size $N \times M$ ~N \times M~ this time. Note that each cell $(i,j)$ ~(i,j)~ is only connected to cell $(N-i+1,j)$ ~(N-i+1,j)~, $(i,M-j+1)$ ~(i,M-j+1)~, and $(N-i+1,M-j+1)$ ~(N-i+1,M-j+1)~. Now, there are a few cases to consider.

If $i \neq N-i+1$ ~i \neq N-i+1~ and $j \neq N-j+1$ ~j \neq N-j+1~, this is the same as the $2 \times 2$ ~2 \times 2~ case, and we can follow the same logic as above.
If $i=N-i+1$ ~i=N-i+1~ and $j=M-j+1$ ~j=M-j+1~, $D_{i,j}$ ~D_{i,j}~ is the centre cell. Since $2K$ ~2K~ can be arbitrarily added to the cell, $D_{i,j}$ ~D_{i,j}~ must be even.
If $i=N-i+1$ ~i=N-i+1~, then there are only $2$ ~2~ cells to consider, $D_{i,j}$ ~D_{i,j}~ and $D_{i,M-j+1}$ ~D_{i,M-j+1}~. We can arbitrarily add $2K$ ~2K~ to either of the cells or add $K$ ~K~ to both cells, which can achieve any combination of values such that $D_{i,j} + D_{i,M-j+1}$ ~D_{i,j} + D_{i,M-j+1}~ is even. The same logic applies to the case with $j=M-j+1$ ~j=M-j+1~.

After trying all $4$ ~4~ possible orientations, we have our answer.

Remarks

We actually only have to try $2$ ~2~ final orientations, since the cases with no flip/both flips and horizontal flip/vertical flip have the same checks.

Comments

There are no comments at the moment.