10309 - Turn the Lights Off

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10309 - Turn the Lights Off

Post by broderic » 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!
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
Location: Canada

Post by broderic » Mon Jun 24, 2002 6:08 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

Post by ambition » Sat Aug 24, 2002 11:06 am

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

for example:

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

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

10309

Post by Adil » Sun Sep 29, 2002 12:44 pm

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

thanx

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » 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.

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

Post by Adil » Tue Oct 01, 2002 7:14 pm

hey man, thanx a lot. :D

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

Polynomial time algorithm

Post by scythe » 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.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » 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
I can't understand your method.
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:

Post by Larry » Thu May 15, 2003 6:23 pm

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » 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?
:oops:

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » 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
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sat May 17, 2003 4:56 am

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

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

10309

Post by knapsack » Fri Apr 09, 2004 7:55 pm

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

Thanks in advance......

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

Thing to point out

Post by TheKiler » 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.

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

Post by serur » Tue Nov 21, 2006 10:22 am

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

Post Reply

Return to “Volume 103 (10300-10399)”