 Afişează mesaje
|
|
Pagini: [1] 2 3 ... 29
|
|
15
|
Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Lights out - shortlist
|
: 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.
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
