Introduction to the Problem

The major challenge of this problem is to discover that it is not necessary to "generate" all the possible combinations of buttons presses because there are no more than ~8~ possible final configurations. The time necessary to solve one problem is constant since it does not depend on the number of button presses.

This problem does not allow the contestants to develop only one part of the algorithm, with the only exception that the additional information about the lamps that are known to be on or off may not be programmed in order to pass some of the tests. The evaluation of the contestants' solutions will focus on the capability to generate all solutions and in the correct processing of the special cases (buttons pressed only one or two times).

Algorithms

Overall description

To solve this problem, it is necessary to "discover" that:

1. the order buttons are manipulated is not relevant;
2. when a button is pressed twice, the consequences of the first movement are "erased".

Taking into account the previous rules, one can find out that there are ~16~ (~2^4~ — four buttons, and two possibilities: button pressed or not pressed) possible combinations of the buttons. For example, when no button is pressed, or all the buttons were pressed an even number of times, all lamps are on, the initial state. But if only the button that changes the state of all the even lamps is pressed an odd number of times, then all the even lamps are on and all the odd lamps are off. Following this line of reasoning, we obtain table 1.

Button 1	Button 2	Button 3	Button 4	# movements	Status of the lamps
0	0	0	0	0	all on
0	0	1	0	1	even on; odd off
0	1	0	0	1	even off; odd on
0	1	1	0	2	all off
1	0	0	0	1	all off
1	0	1	0	2	even off; odd on
1	1	0	0	2	even on; odd off
1	1	1	0	3	all on
0	0	0	1	1	all on but ~3k+1~ are off
0	0	1	1	2	even on but ~3k+1~ are off; odd off but ~3k+1~ are on
0	1	0	1	2	even off; odd on but ~3k+1~ are off but ~3k+1~ are on
0	1	1	1	3	all off but ~3k+1~ are on
1	0	0	1	2	all off but ~3k+1~ are on
1	0	1	1	3	even off but ~3k+1~ are on; odd on but ~3k+1~ are off
1	1	0	1	3	even on but ~3k+1~ are off; odd off but ~3k+1~ are on
1	1	1	1	4	all on but ~3k+1~ are off but ~3k+1~ are on

From the previous table, we can conclude that there are only ~8~ possibilities, since the last column is common to two lines. So we will build table 2, where all the lamps will be associated with a type:

Type	Meaning
1	lamp is even and is not a successor of ~3k~
2	lamp is even and is a successor of ~3k~
3	lamp is odd and is not a successor of ~3k~
4	lamp is odd and is a successor of ~3k~

The eight possible combinations can be expressed by table 3, where a 1 means that a lamp is on, and a 0 means that a lamp is off:

Using this last table and the column of the first table that contains the minimum number of times that a button has to be pressed to obtain that combination, we can find out that if only one button is pressed, the only possible final combinations are 2, 3, 4, and 5.

If the counter of buttons presses contains the number two, then two possibilities may occur:

1. The same button was pressed twice (combination 1)
2. Two different buttons were pressed (combinations 2, 3, 4, 6, 7, and 8)

If the counter of buttons presses contains the number three, then all combinations may occur:

1. The same button was pressed three times (combination 2, 3, 4, or 5)
2. One button was pressed twice (combinations 2, 3, 4, 6, 7, or 8)
3. Three different buttons were pressed (combination 1, 6, 7, or 8)

So, we can conclude that when the counter of button presses is at least ~3~, all combinations may occur.

The information about lamps that are known to be on or off may be used to reject some of the possible combinations.