By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,694 Members | 1,882 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,694 IT Pros & Developers. It's quick & easy.

N -ROOM LIGHTS PROBLEM

P: n/a
N -ROOM LIGHTS PROBLEM
========================

THERE IS A BIG SQURE ROOM OF SIDE N WHICH CONSISTS OF N X N SMALLER
SQUARE ROOMS(ARRANGED LIKE CHESS BOARD)
EACH ROOM HAS A LIGHT.

WHEN the light of a smaller room k is toggled then all the
neighboring room's lights get toggled (max 5 lights get toggled
including the kth room if center room gets clicked )
THE PROBLEM IS to formulate an algorithm which will generate an order
in which the lights have to be toggled such that
all the n X n rooms get lit, initially no room is lit.
(toggle means that if the light is on then it is toggled of & if it is
off then it is switched on)
(question asked by Microsoft at IIT)
me>CAN a divide and conquer strategy work?
Me>I think that dynamic programming techniq can be used to solve this
problem?
Dear wade u got it wrong as u said " A light is On iff the number of
Up switches in the room and its horizontal/vertical (not diagonal)
neighbors is odd."

If u toggle a light near the wall of the room as shown:

if its possible I am attaching a sample program.

Apr 1 '06 #1
Share this Question
Share on Google+
1 Reply


P: n/a
ALIABBAS J PETIWALA schrieb:
N -ROOM LIGHTS PROBLEM
========================

THERE IS A BIG SQURE ROOM OF SIDE N WHICH CONSISTS OF N X N SMALLER
SQUARE ROOMS(ARRANGED LIKE CHESS BOARD)
EACH ROOM HAS A LIGHT.

WHEN the light of a smaller room k is toggled then all the
neighboring room's lights get toggled (max 5 lights get toggled
including the kth room if center room gets clicked )
THE PROBLEM IS to formulate an algorithm which will generate an order
in which the lights have to be toggled such that
all the n X n rooms get lit, initially no room is lit.
(toggle means that if the light is on then it is toggled of & if it is
off then it is switched on)
(question asked by Microsoft at IIT)
me>CAN a divide and conquer strategy work?
Me>I think that dynamic programming techniq can be used to solve this
problem?

Dear wade u got it wrong as u said " A light is On iff the number of
Up switches in the room and its horizontal/vertical (not diagonal)
neighbors is odd."

If u toggle a light near the wall of the room as shown:

if its possible I am attaching a sample program.


This is not a C question; if you have found an algorithm
and have problems implementing it in C, you can show it
to us. If you do, then describe your expectations, your
problems, and copy&paste the program.

<OT>
Hints:
- Does order matter?
- N=1 and N=2 are special cases
- What happens if you toggle each room's switch exactly once?
</OT>
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 1 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.