## 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

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:

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: