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

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



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

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

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« 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.

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

Mesaje: 1.799



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

Good job so far!  Weightlift

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

Karma: 16
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« 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 Deconectat

Mesaje: 1.799



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

fixed.
Memorat
retrograd
Client obisnuit
**

Karma: 3
Deconectat Deconectat

Mesaje: 50



Vezi Profilul
« 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 Deconectat

Mesaje: 1.799



Vezi Profilul
« 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
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines