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 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 operations choosing the same cell with K as 1, 1, -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 array D which represents the differences between A_{i,j} and T_{i,j}. Let D_{1,1} = a, D_{1,2} = b, D_{2,1} = c, and D_{2,2} = d. Then, a+d=b+c must hold. To see this clearly, draw out a 2 \times 2 chessboard with alternating white and black tiles. Whenever an operation is performed, K is added to 1 white tile and 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 with size N \times M this time. Note that each cell (i,j) is only connected to cell (N-i+1,j), (i,M-j+1), and (N-i+1,M-j+1). Now, there are a few cases to consider.

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

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


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


There are no comments at the moment.