10309 - Turn the Lights Off

[broderic]

can anybody give a test case where this code fails,or give me a hint
why it doesn't work? thanks!

Code: Select all

[broderic]

not sure what was wrong, but i just got it accepted.
probably something dumb.

[ambition]

try not to use \n in scanf() function.

for example:

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

[Adil]

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

thanx

[wyvmak]

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.

[Adil]

hey man, thanx a lot.

[scythe]

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]

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
I can't understand your method.
Could you give me an example?

[Larry]

Brute force on the first row, 2^10 different possibilities, and it trickles down, basically..

[hank]

But the problem need the minimum number of times!!It's difficult!!
I should do it by BFS or by Recursion ?Which is better?

[..]

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

[hank]

I got Accepted !! Thanks a lot!! ^_^|

[knapsack]

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

Thanks in advance......

[TheKiler]

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]

Hi fellows!

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