Editorial for UTS Open '18 P5 - Room 666


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

Subtask 1:

Note that the order in which flips are performed doesn't matter, and that flipping a switch twice has no effect. So, you only need to consider the cases where each switch is flipped 0 or 1 times. There are 2^K cases, where K = \frac{N(N+2)}{2} is the number of switches. Since K \le 12, it is possible to brute force all 2^K possibilities.

Time Complexity: \mathcal{O}(N^2 \cdot 2^K)

Subtask 2:

Solving this requires two observations:

  • When you use a 'flip' move on every switch in row i or column j, the value at (i, j) will change, and so will all the switches in four triangles at the top, bottom, left, and right.
  • When you flip four switches that form a rectangle, only those four will change.

Combining these two observations, we can reset the switches in the four triangles by splitting them into rectangles as shown below, then flipping the corners of each rectangle to reset their values. This way, only the value of (i, j) changes, so we can solve the lock by repeating this process for each 1 in the grid.

Time Complexity: \mathcal{O}(N^4)

Subtask 3:

Like the solution to subtask 2, we can change (i, j) on its own by flipping a certain set of switches: the ones in its row or column, and the ones in the four triangles. Call this set S_{(i, j)} Now we reverse engineer the solution to find out which switches would be flipped an odd number of times. The switch at (i_1, j_1) gets flipped for any (i_2, j_2) whose value is 1 and contains (i_1, j_1) in its "flip set", S_{(i_2, j_2)}. In other words, the number of times (i_1, j_1) should be flipped is the XOR of V_{(i_2, j_2)} for all (i_2, j_2) such that (i_1, j_1) \in S_{(i_2, j_2)}, where V_{(i, j)} is the value of (i, j). Now we need a third observation:

  • (i_1, j_1) \in S_{(i_2, j_2)} if and only if (i_2, j_2) \in S_{(i_1, j_1)}.

Therefore, the number of times to flip (i_1, j_1) is the XOR of everything in its "flip set" S_{(i_1, j_1)}. This can be calculated in \mathcal O(1) with a 2D XOR prefix sum array.

Time Complexity: \mathcal{O}(N^2)


Comments

There are no comments at the moment.