## Editorial for UTS Open '18 P5 - Room 666

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

##### 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 or times. There are cases, where is the number of switches. Since , it is possible to brute force all possibilities.

**Time Complexity:**

##### Subtask 2

Solving this requires two observations:

- When you use a 'flip' move on every switch in row or column , the value at 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 changes, so we can solve the lock by repeating this process for each in the grid.

**Time Complexity:**

##### Subtask 3

Like the solution to subtask 2, we can change 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 Now we reverse engineer the solution to find out which switches would be flipped an odd number of times. The switch at gets flipped for any whose value is and contains in its "flip set", . In other words, the number of times should be flipped is the XOR of for all such that , where is the value of . Now we need a third observation:

- if and only if .

Therefore, the number of times to flip is the XOR of everything in its "flip set" . This can be calculated in with a 2D XOR prefix sum array.

**Time Complexity:**

## Comments