Pagini: [1]   În jos
 Ajutor Subiect: Lights out - shortlist  (Citit de 5993 ori) 0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « : Iunie 09, 2016, 06:41:14 »

http://www.infoarena.ro/blog/lighs-out-shortlist
 Memorat
PlayLikeNeverB4
Nu mai tace

Karma: 212
Deconectat

Mesaje: 719

 « Răspunde #1 : Iunie 09, 2016, 13:01:11 »

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

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 2f, where f is the number of free variables.
 « Ultima modificare: Iunie 09, 2016, 13:33:38 de către George Marcus » Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #2 : Iunie 09, 2016, 21:20:39 »

Good job so far!

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.
 Memorat
tamionv
Echipa infoarena
De-al casei

Karma: 16
Deconectat

Mesaje: 121

 « Răspunde #3 : Iunie 17, 2016, 21:17:29 »

For problem 2, are P, Q fixed beforehand, or can we choose them differently for each move ?
 Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #4 : Iunie 20, 2016, 19:11:17 »

fixed.
 Memorat
Client obisnuit

Karma: 3
Deconectat

Mesaje: 50

 « Răspunde #5 : Iunie 30, 2016, 09:10:39 »

[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])
 « Ultima modificare: Iunie 30, 2016, 09:21:09 de către Lucian Bicsi » Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #6 : Iulie 21, 2016, 02:07:16 »

Good job. I think we're left with 8 and 9
 Memorat
 Pagini: [1]   În sus
Schimbă forumul: