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)~