Блог пользователя SPyofgame

Автор SPyofgame, история, 4 года назад, По-английски

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
  • Проголосовать: нравится
  • +56
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Auto comment: topic has been updated by SPyofgame (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

This blog is better formatted, and better quality than my university assignments.