wil93's blog

Lights (simple problem)
By wil93, 13 years ago, In English

This is intended to be simple, but I still have not understood how to solve it.

You have a building. Its windows are disposed like a grid with N rows and M columns.
Each window has a light (on / off). Here's an example of such a building:

1 0 1 1 0
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
0 1 0 0 1

with N = M = 5.

You have N+M special buttons: N buttons to toggle the state of ALL the lights of the i-th row, and M buttons to toggle the state of ALL the lights of the j-th column.

Toggle(x):
   if (x = 1) then x = 0
   else x = 1

You want to turn off all the lights using these N+M buttons, however this isn't always possibile. Determine if it's possible to turn off all the lights and, in that case, wich buttons has to be pressed (see examples).

SAMPLE INPUT:
5 5
1 0 1 1 0
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
0 1 0 0 1

OUTPUT:
Rows: 1 0 1 0 0
Columns: 0 1 0 0 1

- - -

SAMPLE INPUT:
5 5
1 0 1 1 0
0 1 1 0 1
1 0 1 1 0
0 1 0 0 1
0 0 1 0 1

OUTPUT:
Impossible

- - -

UPDATE: I forgot this...

Constraints:
  • 1 < N < 500
  • 1 < M < 500
  • The building has at least one lighted window.
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
If N and M are even it's always possible. You can simulate it this way:
always push button X from N row buttons, and push button Y from M column button, if the cell (X, Y) is turned on. After finite number of moves u'll reach that is needed.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    It can not be always possible, because there are only 2^(N+M) button configurations, and 2^(N*M) windows configurations.

    To solve the problem, assume that you don't press the button corresponding to the first row. Then you can find out if you should or should not press every column button. After that it's easy to solve the rest. 
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I see my mistake, the state of (X,Y) window remains unchanged after 2 clicks. 
      Don't you know, is there a way to solve this problem similar to problem when we are clicking the window (X, Y), we toggle the state of lights in X-th row and in Yth column, via solving a linear equations system with binary coefficients?
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I took me a while to understand what you said, but now I think I understand!

      Suppose we DON'T press the button for first row. Then we MUST press the buttons for all the colums having 1 in the first row!

      For example:

      1 0 1 1 0
      0 1 0 0 1
      1 0 1 1 0
      0 1 0 0 1
      0 1 0 0 1

      If we don't toggle the first row, then we MUST toggle the first, third and fourth column (if we don't, there will surely remain some lighted windows).

      The same idea holds if we DO use the first row: the columns (now) having a 1 in the first row must be pressed!

      So the algorithm is...

      i=1
      for j=1 to M
         if ON(i,j) then TOGGLE_COLUMN(j)

      At the end we MUST be in a situation like this:

      0 0 0 0 0
      1 1 1 1 1
      0 0 0 0 0
      1 1 1 1 1
      1 1 1 1 1

      Then, we toggle the remaining rows.
      If we don't see this situation, we output "Impossible" :)
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

if N = M = 5, you can use bruteforce:
(code deleted)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry I forgot this:

    Constraints:
    • 1 < N < 500
    • 1 < M < 500
    • The building has at least one lighted window.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      This is a problem from TC, no?

      It can be solved like this:

      1) Make all the lights in the 1st row on or off (check both) by using column switches
      2) If all the lights in i-th row are off, then toggle i-th row. If all the lights are on, do nothing. Else there is no solution for current 1) case.

      → Reply
      • 13 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        This is a problem from the italian olympiads... My solution (thanks to winger :) is above.

        Anyway (if my solution is correct) your algorithm has higher complexity, right?
        If you check both 1 and 0 for each row *each column of the first row* you have 2M, am I wrong?

        EDIT: Oh I understand now, you try to set ALL 1s to the first row and ALL 0s. Then you check for the rows (like in the last part of my previous post). Yes, I think it works. Thanks :)

        Anyway, when you say: "Else there is no solution for current 1) case."
        If there's no solution for current 1) case, then there's no solution for the other 1) case, am I wrong?

        If I am right, we can do half of the work (anyway it would be a reduction by a constant)
        → Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I've seen simillar problem not too much time ago, it can be solved by solving a system of N + M linear equations (modulo 2).
→ Reply