Editorial for DMOPC '21 Contest 8 P4 - Grid Operations

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: zhouzixiang2004

Subtask 1

Hint

Note that the operations affect each white $2 \times 2$ subgrid in the same way, and similarly for black $2 \times 2$ subgrids.

Solution

For subtask 1, note that the operations affect each white $2 \times 2$ subgrid in the same way, and similarly for black $2 \times 2$ subgrids. It suffices to simulate the operations on a single white $2 \times 2$ subgrid and a single black $2 \times 2$ subgrid, and then copy a similar result to all the $N \times M$ subgrids to form the final answer grid.

Time Complexity: $\mathcal{O}(NM + Q)$

Subtask 2

Hint

If two operations of the same type are adjacent, we can delete both of them.

Hint 2

Analyze how a single number moves under a sequence of operations alternating between 1 and 2.

Solution

For subtask 2, first repeatedly delete any two adjacent operations of the same type so that we are left with a sequence of operations alternating between 1 and 2. Then, we can analyze how a single number moves under a sequence of operations of this form. We can find that it will move in one direction until it "hits" a boundary of the row, then start going in the opposite direction until it hits the opposite boundary of the row, and so on. The initial direction depends on whether the starting column is odd or even. With some math, we can calculate the final position of any number in constant time.

Time Complexity: $\mathcal{O}(NM + Q)$

Subtask 3

Hint

Does the order in which we perform the type 1/2 operations and the type 3/4 operations matter?

Solution

For subtask 3, note that since the operations affect either all rows in the same way or all columns in the same way, the type 1/2 operations and type 3/4 operations are independent. Thus we can calculate the final column of a number by simulating all the type 1/2 operations as in subtask 2 and then calculate the final row by simulating all the type 3/4 operations similarly.

Time Complexity: $\mathcal{O}(NM + Q)$

Subtask 4

Hint

The idea in subtask 3 no longer helps as the rows/columns are no longer independent. Try to find a simple way to visualize the operations. It may help to focus on a single row, that is, finding a simple way to describe the math in the subtask 2 solution.

Hint 2

The fact that type 2 and 4 operations do not swap the first and last columns/rows breaks a rotational symmetry in the problem. How can we visualize the operations in a way that preserves more symmetry?

Hint 3

Repeatedly reflect the grid over the boundaries infinitely.

Solution

For subtask 4, consider repeatedly reflecting the grid over the boundaries infinitely.

Now the operations are equivalent to:

Type 1: In every row, swap the numbers on columns $2k-1$ ~2k-1~ and $2k$ ~2k~ for all integers $k$ ~k~.
Type 2: In every row, swap the numbers on columns $2k$ ~2k~ and $2k+1$ ~2k+1~ for all integers $k$ ~k~.
Type 3: In every column, swap the numbers on rows $2k-1$ ~2k-1~ and $2k$ ~2k~ for all integers $k$ ~k~.
Type 4: In every column, swap the numbers on rows $2k$ ~2k~ and $2k+1$ ~2k+1~ for all integers $k$ ~k~.
Type 5: Rotate the $2 \times 2$ ~2 \times 2~ subgrids clockwise or counterclockwise in an alternating checkerboard pattern. (Here, the checkerboard pattern on the original grid does not get reflected; we assign a new checkerboard pattern to the infinite grid.)

This way, the cells $(x,y)$ with the same $(x \bmod 4,y \bmod 4)$ are equivalent. It suffices to simulate the operations $16$ times total on a single $4 \times 4$ subgrid of initial cells and fill out the rest of the final answer grid similarly according to this reflection pattern.

Time Complexity: $\mathcal{O}(NM + Q)$

Comments

There are no comments at the moment.