Velocity Reviews > N -ROOM LIGHTS PROBLEM

# N -ROOM LIGHTS PROBLEM

ALIABBAS J PETIWALA
Guest
Posts: n/a

 04-01-2006
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.

Michael Mair
Guest
Posts: n/a

 04-01-2006
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.