Page 1 of 2

### 10309 - Turn the Lights Off

Posted: Mon Jun 24, 2002 3:18 am
can anybody give a test case where this code fails,or give me a hint
why it doesn't work? thanks!

Posted: Mon Jun 24, 2002 6:08 am
not sure what was wrong, but i just got it accepted.
probably something dumb.

Posted: Sat Aug 24, 2002 11:06 am
try not to use \n in scanf() function.

for example:

scanf("%s", name)==1 may be right.

### 10309

Posted: Sun Sep 29, 2002 12:44 pm
Any hint for 10309 ["Turn the Lights Off"] would help.

thanx

Posted: Sun Sep 29, 2002 1:58 pm
i used recursion. though i guess there're better methods than mine. (i heard somebody use looping)

my algorithm:
go from the top-row,
- for each one in top-row, you can switch or not switch
for the rest of the rows,
- the upper row would determine whether you can switch or not. ie. if the upper row is off, you cannot switch; otherwise you must switch.

Posted: Tue Oct 01, 2002 7:14 pm
hey man, thanx a lot.

### Polynomial time algorithm

Posted: Mon Oct 07, 2002 12:30 pm
I like your idea, but there also is an algorithm (10x10)^3 precalc, O(10x10) solution, using Gauss-Jordan reduction mod 2. (XOR)
You can create a system of linear equations mod 2. The matrix would be 100x100. Every line coresponds to an i,j in the configuration. For line 0, (the upper-left corner), there would be three 1s corresponding to the (0,0)position and the two neighbours (0,1), (1,0). Solving the system actually yelds the switches needed to change the state of one light without changing anything else. The solution is also based on the fact that there is only one solution that doesn't repeat switches.

Posted: Wed May 14, 2003 4:23 pm
wyvmak wrote:i used recursion. though i guess there're better methods than mine. (i heard somebody use looping)

my algorithm:
go from the top-row,
- for each one in top-row, you can switch or not switch
for the rest of the rows,
- the upper row would determine whether you can switch or not. ie. if the upper row is off, you cannot switch; otherwise you must switch.
Hello
Could you give me an example?

Posted: Thu May 15, 2003 6:23 pm
Brute force on the first row, 2^10 different possibilities, and it trickles down, basically..

Posted: Fri May 16, 2003 3:46 pm
But the problem need the minimum number of times!!It's difficult!!
I should do it by BFS or by Recursion ?Which is better?

Posted: Sat May 17, 2003 12:23 am
Think carefully,
once you decided how to press the switched of first row (1024 ways). Then you will also know how to press the buttons in remaining rows.

Let define the top left corner is (1,1), the light below it is (2, 1).........

Once you decided how to press the first row. Then You can only switch the light (1, 1) by the switch (2 ,1). If light(1 ,1) is off after pressing the first row, then you can't touch the switch (2,1). Otherwsie you must press it. Following the logic, you will know how to press the 2nd row, and then 3rd row........10th row

So, what you need is just testing all the 1024 combinations of the first row

Posted: Sat May 17, 2003 4:56 am
I got Accepted !! Thanks a lot!! ^_^|

### 10309

Posted: Fri Apr 09, 2004 7:55 pm
Can anyone help me with the input and output for the 'Turn the lights off' problem????

### Thing to point out

Posted: Mon Sep 25, 2006 3:04 am
I thought that I might point out some funny thing while I was solving 5x5 puzzles, but I think they might be universal to such a problem of any size even though I don't how to prove it right or wrong.

Assuming NxN is a size of a puzzle.
• First I found out that all solutions are equal to solutions that change only

Code: Select all

SOLUTION_NUMBER=roundup( log2 N )
bulbs from the left or right in the first row.
• Then I found out that there indeed are only SOLUTION_NUMBER eventual last rows, which correspond to the just-left and just-right solutions above.
If this is right, the quickest solution would be to hard-code all of the possible last rows that can be encountered and use an appropriate solution.

Must check that out.

Posted: Tue Nov 21, 2006 10:22 am
Hi fellows!

What's the proper approach for this problem - bfs??