You are given a grid with $$$n$$$ rows and $$$m$$$ columns filled with zeros and ones. In one move, you can choose any cell in the grid and flip all of the bits in the adjacent cells. You do not flip the bit in the cell you chose.
For example, if you choose the cell $$$(3, 1)$$$ and then the cell $$$(2, 2)$$$.
0 0 0 0 0 0 0 1 0
0 0 0 -> 1 0 0 -> 0 0 1
0 0 0 0 1 0 0 0 0
You are given that you can make the grid into all zeros in some number of operations. Find the minimum number of operations to make the grid all zeros and output any minimum sequence of operations.
I think it can be solved row-by-row: from the second-highest row you apply the operation to make all of the highest row $$$0$$$ and then go to the third-highest to make the second-highest all 0, down to the final row. But I'm not sure if this is the minimum.
You would create a system of equations over GF(2) and solve. Look up lights out puzzle, I believe this is just a modified version.
There is not a single solution. For example, consider a possible solution G. If you flip every cell in any of the two diagonals you also get a solution. I believe this implies you cannot use methods like Gaussian elimination. Even if you somehow force some kind of solution like this you still have to prove it minimizes number of moves.
where each
vᵢis a null-space basis vector and eachcᵢ ∈ {0,1}.So yeah, flipping along a diagonal (or any weird pattern) is just adding some combination of those null vectors. It’s still covered by Gaussian elimination.
If you want the minimal solution (e.g., with fewest 1s), brute force over all
2^kcombinations of basis vectors — totally doable ifkis small. This guarantees the minimal Hamming weight.Bottom line: multiple solutions don’t break Gauss-Jordan. They highlight its power.
Thanks! I didn’t know that
If there are multiple solutions it will still work, but it would not necessarily return the minimum. What the other guy said about brute forcing basis vectors should still be much faster than the naive solution in this case.
I’d greedily perform the move which reduces the number of 1 the most at each step. I don’t have a proof for it but I’d definitely do this in a contest
After putting some more thought i realized this solution is stupid. Unfortunately I couldn’t come up with a better solution other than BFS: each grid is its own state and you have their distance to the empty grid. You run a bfs until you reach the final state. The time complexity of this is O((N+E)*K), where N is the number of states, E the number of transitions and K a factor for how heavy it is representing each state. As each cell you will either turn on or off you can use bitmasks, so you could use a vector of long longs (with size n*m/64)to represent each state. As the number of transitions of each state is n*m, let U = n*m, the final complexity is:
(2^U * U) * U /64 = 2^U * U^2 / 64. You can solve this way for U up to something like 18.