Блог пользователя wil93

Lights (simple problem)
Автор wil93, 13 лет назад, По-английски

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.
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    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. 
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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" :)
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

if N = M = 5, you can use bruteforce:
(code deleted)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Sorry I forgot this:

    Constraints:
    • 1 < N < 500
    • 1 < M < 500
    • The building has at least one lighted window.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

        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)
        → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
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).
→ Ответить