### SPyofgame's blog

By SPyofgame, history, 2 weeks ago,

### Original Problem

You are given a binary table of size $n×m$. This table consists of symbols $0$ and $1$

You can make such operation: select $3$ different cells that belong to one $2×2$ square and change the symbols in these cells (change $0$ to $1$ and $1$ to $0$)

Your task is to make all symbols in the table equal to $0$. You dont have to minimize the number of operations. (It can be proved, that it is always possible)

And the constraints are

• $2 \leq N, M \leq 100$
• Easy Version: Limited in $3 \cdot N \cdot M$ operations
• Hard Version: Limited in $1 \cdot N \cdot M$ operations
Code solution without minimizing (with comments)

### Extended version

But what if I have to minimize number of operations ?

• Is there an algorithm other than brute-force to find minimum number of operations in these problem ?

• I am wondering if I can use Gauss-Elimination (mod 2) or Greedy-DP to solve in somehow

• I wrote an analizer for small $N \cdot M$ tables so that you can check too. (Modify by a bit, we can answer query of all $N \cdot M$ tables, but the complexity is $O(2^{n \cdot m})$)

Analizer
Test with 3x3 tables
With (n, m) = (2, 2) || show_case = true; show_trace = true;
• And if the ones are connected, here is the analizer (I will optimize the algo later)
Small checker
Observation
Test with 9x9 tables

• +66

 » 2 weeks ago, # |   +3 Auto comment: topic has been updated by SPyofgame (previous revision, new revision, compare).
 » 2 weeks ago, # |   -9 Thanks, it's very helpful. :)
 » 2 weeks ago, # |   +14 This blog is better formatted, and better quality than my university assignments.
•  » » 2 weeks ago, # ^ |   +3 Thank you