## 10309 - Turn the Lights Off

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

### 10309 - Turn the Lights Off

can anybody give a test case where this code fails,or give me a hint
why it doesn't work? thanks!
Last edited by broderic on Sat Aug 24, 2002 3:39 pm, edited 1 time in total.

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
not sure what was wrong, but i just got it accepted.
probably something dumb.

ambition
New poster
Posts: 2
Joined: Fri Aug 16, 2002 3:47 am
try not to use \n in scanf() function.

for example:

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

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

### 10309

Any hint for 10309 ["Turn the Lights Off"] would help.

thanx

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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.

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
hey man, thanx a lot.

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Polynomial time algorithm

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.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
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?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Brute force on the first row, 2^10 different possibilities, and it trickles down, basically..

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
But the problem need the minimum number of times!!It's difficult!!
I should do it by BFS or by Recursion ?Which is better?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I got Accepted !! Thanks a lot!! ^_^|

knapsack
New poster
Posts: 3
Joined: Tue Jun 25, 2002 8:12 pm

### 10309

Can anyone help me with the input and output for the 'Turn the lights off' problem????

TheKiler
New poster
Posts: 6
Joined: Wed Jun 22, 2005 2:26 am
Location: Poland, Poznan

### Thing to point out

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.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hi fellows!

What's the proper approach for this problem - bfs??
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke