C2/A2-Binary Table minimize operations

Правка en10, от SPyofgame, 2020-11-21 11:12:55

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)