Editorial for UTS Open '18 P5 - Room 666 - Olympiads Online Judge

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$ $0$ or $1$ $1$ times. There are $2^K$ $2^{K}$ cases, where $K = \frac{N(N+2)}{2}$ $K = \frac{N (N + 2)}{2}$ is the number of switches. Since $K \le 12$ $K \leq 12$ , it is possible to brute force all $2^K$ $2^{K}$ possibilities.

Time Complexity: $\mathcal{O}(N^2 \cdot 2^K)$ $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$ $i$ or column $j$ $j$ , the value at $(i, j)$ $(i, j)$ will change, and so will all the switches in four triangles at the top, bottom, left, and right.
$\text{[math]}$
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)$ $(i, j)$ changes, so we can solve the lock by repeating this process for each $1$ $1$ in the grid.

$\text{[math]}$

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

Subtask 3

Like the solution to subtask 2, we can change $(i, j)$ $(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)}$ $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)$ $(i_{1}, j_{1})$ gets flipped for any $(i_2, j_2)$ $(i_{2}, j_{2})$ whose value is $1$ $1$ and contains $(i_1, j_1)$ $(i_{1}, j_{1})$ in its "flip set", $S_{(i_2, j_2)}$ $S_{(i_{2}, j_{2})}$ . In other words, the number of times $(i_1, j_1)$ $(i_{1}, j_{1})$ should be flipped is the XOR of $V_{(i_2, j_2)}$ $V_{(i_{2}, j_{2})}$ for all $(i_2, j_2)$ $(i_{2}, j_{2})$ such that $(i_1, j_1) \in S_{(i_2, j_2)}$ $(i_{1}, j_{1}) \in S_{(i_{2}, j_{2})}$ , where $V_{(i, j)}$ $V_{(i, j)}$ is the value of $(i, j)$ $(i, j)$ . Now we need a third observation:

$(i_1, j_1) \in S_{(i_2, j_2)}$ $(i_{1}, j_{1}) \in S_{(i_{2}, j_{2})}$ if and only if $(i_2, j_2) \in S_{(i_1, j_1)}$ $(i_{2}, j_{2}) \in S_{(i_{1}, j_{1})}$ .

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

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

Comments

There are no comments at the moment.