Lights out problem.

Revision en1, by radoslav11, 2016-12-21 17:34:29

Hello everyone!

I was solving a problem (from a Bulgarian competition) which is about the game [Lights Out](https://en.m.wikipedia.org/wiki/Lights_Out_(game)). In the problem you are given a NxM table (N*M<=1000) — the initial configuration of the game. You whant to make all the cells equal to zero. You should print a way to do this.

The problem can be solved with meet in the middle and bitmask dp, with the given constraints. Another way is using Gauss elimination modulo 2 with N*M equations for each cell. But this approach is O((N * M)3). It actually can be reduced to with a bitset.

In the editorial of the problem it is said that there exists a solution for much larger data — N,M<=500, using Gauss elimination but it isn't explained. But I cannot find it. I will appreciate your help!

Tags gauss, gauss elimination, lights out, linear algebra

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English radoslav11 2016-12-21 17:44:15 50 Tiny change: 'Out_(game)). In the ' -> 'Out_(game) ). In the '
en1 English radoslav11 2016-12-21 17:34:29 861 Initial revision (published)