Lights out - shortlist

[•Cosmin]

http://www.infoarena.ro/blog/lighs-out-shortlist

[•PlayLikeNeverB4]

1. Generate all possible button press combinations (2⁹) and for each of them check if it turns off all of the lights.

4. After we fix the button presses for the first column, then we can greedily calculate the necessary button presses for all of the lights. In order to speed up the greedy part, we will use bitmasks. If for a column we have an initial light combination init_mask and then choose a button combination button_mask, then after pressing the buttons the light mask will be final_mask = init_mask xor (button_mask << 1) xor button_mask xor (button_mask >> 1). final_mask from the previous column will be button_mask for the current column (the only choice).

5. You didn’t specify the initial state of the nodes, but it doesn’t matter.

We can solve it using dynamic programming. Each state will be a pair (node, b, p) where b denotes whether we must press node’s button or not and p denotes whether we pressed node’s parent’s button.

For the current node we can recursively calculate all (child_node, child_b, b) states.

Let’s denote a = 1 if node is initially on and a = 0 if it’s off. For node to be off after all of the operations, a + b + p + sum(child_b) must be even. In order to decide which of the children’s buttons to press, we use dynamic programming again. The state will be (i, s) denoting the minimum number of button presses to switch off the subtrees of the first i children and the parity of sum(child_b) is s.

The final answer is the minimum of (root, 0, 0) and (root, 1, 0).

6 + 7. We create a system of n linear equations modulo 2 with n variables and solve it using Gaussian elimination. The number of solutions is 2^f, where f is the number of free variables.

[•Cosmin]

Good job so far! 

An observation for other people reading the comments:
In all the problems if you repeat the same move twice it cancels out. Also If you change the order of the moves the result stays the same.
(In math terms the button push operation is commutative, associative and it's own inverse)

4. Just to make it a bit more clear: once you have a set of moves on the first column, the moves on the second column are forced and then the moves on the 3rd are forced and so on. After doing the first column and the forced moves on the rest of the columns you can check if this yields a solution for the last column.

[•tamionv]

For problem 2, are P, Q fixed beforehand, or can we choose them differently for each move ?

[•Cosmin]

fixed.

[•retrograd]

[2]: You can prove that there is maximum one way to solve the problem by induction on N. Basically, if I understood the problem correctly, there is only one move that would toggle the top left cell (i.e. toggling the top left rectangle). So using the top left rectangle or not is uniquely determined by that state. In the same way you can argue that the one to the right of the top left one determines the next rectangle to the left, and so on. So the first line determines the first line of available rectangles, and so on.

[3]: You can observe that choosing whether to toggle the first row or not "forces" the decision on all the columns (based on the cells of the matrix), which, again, determines the choice upon the other rows. So the solution is uniquely determined by choosing whether to toggle the first row or not. So we can compute both cases and just take the minimum. Note that there isn't always a solution. (e.g. [101, 000, 101])

[•Cosmin]

Good job. I think we're left with 8 and 9