C2/A2-Binary Table minimize operations

Revision en13, by SPyofgame, 2020-11-22 13:16:03

### 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

#### History

Revisions

Rev. Lang. By When Δ Comment
en13 SPyofgame 2020-11-22 13:16:03 8
en12 SPyofgame 2020-11-22 13:14:57 7588 Tiny change: 'cdot k + 4, k \in \mathbb{N}$, we need' -> 'cdot k + 4 (k \in \mathbb{N})$, we need'
en11 SPyofgame 2020-11-21 12:04:30 2936
en10 SPyofgame 2020-11-21 11:12:55 1977
en9 SPyofgame 2020-11-19 15:23:51 60
en8 SPyofgame 2020-11-19 12:31:41 184
en7 SPyofgame 2020-11-19 12:25:20 461
en6 SPyofgame 2020-11-19 12:22:08 4568
en5 SPyofgame 2020-11-19 11:17:33 169 Tiny change: 'om/contest\n/1439/prob' -> 'om/contest/1439/prob'
en4 SPyofgame 2020-11-19 05:59:56 6
en3 SPyofgame 2020-11-19 05:59:11 532 Tiny change: ' and $1$\n\nYou can ' -> ' and $1$\nYou can '
en2 SPyofgame 2020-11-19 05:56:22 552 Tiny change: 'th comment)">\n\n<sp' -> 'th comments)">\n\n<sp'
en1 SPyofgame 2020-11-19 05:53:50 16258 Initial revision (published)