Binary Table minimize operations
Разница между en1 и en2, 552 символ(ов) изменены
Is there an algorithm other than brute-force to find minimum number of operations in these problem ?### Original Problem↵

Easy Version: [Div 2](https://codeforces.me/contest/1440/problem/C1), [Div 1](https://codeforces.me/contest/1439/problem/A1) /
-
 Hard Version: [Div 2](https://codeforces.me/contest/1440/problem/C2), [Div 1](https://codeforces.me/contest↵
/1439/problem/A2)
)

> 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$↵

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↵

<spoiler summary="
SCode solutions without minimizing (with comments)">↵

<spoiler summary="Problem C1 - Eliminate each 1x1 cells">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵

using namespace std;↵

#define all(x) (x).begin(), (x).end()↵
int main()↵
{↵
    int q;↵
    cin >> q;↵
    ↵
    while (q-->0) /// For each query↵
    {↵
        /// Input↵
        int n, m;↵
        cin >> n >> m;↵
        ↵
        string s[n];↵
        for (int i = 0; i < n; ++i)↵
            cin >> s[i];↵
            ↵


        /// Calculation↵
        int cnt = 0;↵
        for (int i = 0; i < n; ++i)           /// For each '1' appear↵
            cnt += 3 * count(all(s[i]), '1'); /// We use 3 operations to turn off it↵
                                              /// These operations are independent↵
 ↵
        /// Output the result↵
        cout << cnt << '\n';↵
        for (int i = 0; i < n; ++i)↵
        {↵
            for (int j = 0; j < m; ++j)↵
            {↵
                if (s[i][j] == '1')↵
                {↵
                    int cx = i + 1; /// +1 because we use 0-based loop↵
                    int cy = j + 1; /// +1 because we use 0-based loop↵
                    int px = (cx < n) ? cx + 1 : cx - 1; /// Next row↵
                    int py = (cy < m) ? cy + 1 : cy - 1; /// Next col↵

                    /// Notice that these operation are independent↵
                    /// They wont affect others cells, just turn off [i][j]↵

                    cout << px << ' ' << cy << ' ';  ///  X O  |  + +  |  O X↵
                    cout << cx << ' ' << py << ' ';  ///  O O  |  + _  |  X O↵
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 1 -> 2↵

                    cout << px << ' ' << cy << ' ';  ///  O X  |  + _  |  X X↵
                    cout << px << ' ' << py << ' ';  ///  X O  |  + +  |  O X↵
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 2 -> 3↵

                    cout << cx << ' ' << py << ' ';  ///  X X  |  + +  |  O O↵
                    cout << px << ' ' << py << ' ';  ///  O X  |  _ +  |  O O↵
                    cout << cx << ' ' << cy << '\n'; ///   Operation: 3 -> 0↵
                }↵
            }↵
        }↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Benchmark">↵

$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$↵

For $N$ ones in table, it need exact $3 \times N$ operations↵

For every $N \cdot M$ table, it need averagely $\frac{3N}{2}$ operations↵

|rows|columns|total count|total cases|average percase | maximum case|↵
|----|----|-----------|----------|----------|----|↵
| 2 | 2 | 96 | 16 | 150% | 12 |↵
| 2 | 3 | 576 | 64 | 150% | 18 |↵
| 2 | 4 | 3072 | 256 | 150% | 24 |↵
| 2 | 5 | 15360 | 1024 | 150% | 30 |↵
| 2 | 6 | 73728 | 4096 | 150% | 36 |↵
| 2 | 7 | 344064 | 16384 | 150% | 42 |↵
| 2 | 8 | 1572864 | 65536 | 150% | 48 |↵
| 2 | 9 | 7077888 | 262144 | 150% | 54 |↵
| 2 | 10 | 31457280 | 1048576 | 150% | 60 |↵
| 2 | 11 | 138412032 | 4194304 | 150% | 66 |↵
| 2 | 12 | 603979776 | 16777216 | 150% | 72 |↵
| 3 | 2 | 576 | 64 | 150% | 18 |↵
| 3 | 3 | 6912 | 512 | 150% | 27 |↵
| 3 | 4 | 73728 | 4096 | 150% | 36 |↵
| 3 | 5 | 737280 | 32768 | 150% | 45 |↵
| 3 | 6 | 7077888 | 262144 | 150% | 54 |↵
| 3 | 7 | 66060288 | 2097152 | 150% | 63 |↵
| 3 | 8 | 603979776 | 16777216 | 150% | 72 |↵
| 4 | 2 | 3072 | 256 | 150% | 24 |↵
| 4 | 3 | 73728 | 4096 | 150% | 36 |↵
| 4 | 4 | 1572864 | 65536 | 150% | 48 |↵
| 4 | 5 | 31457280 | 1048576 | 150% | 60 |↵
| 4 | 6 | 603979776 | 16777216 | 150% | 72 |↵
| 5 | 2 | 15360 | 1024 | 150% | 30 |↵
| 5 | 3 | 737280 | 32768 | 150% | 45 |↵
| 5 | 4 | 31457280 | 1048576 | 150% | 60 |↵
| 5 | 5 | 1258291200 | 33554432 | 150% | 75 |↵
| 6 | 2 | 73728 | 4096 | 150% | 36 |↵
| 6 | 3 | 7077888 | 262144 | 150% | 54 |↵
| 6 | 4 | 603979776 | 16777216 | 150% | 72 |↵
| 7 | 2 | 344064 | 16384 | 150% | 42 |↵
| 7 | 3 | 66060288 | 2097152 | 150% | 63 |↵
| 8 | 2 | 1572864 | 65536 | 150% | 48 |↵
| 8 | 3 | 603979776 | 16777216 | 150% | 72 |↵
| 9 | 2 | 7077888 | 262144 | 150% | 54 |↵
| 10 | 2 | 31457280 | 1048576 | 150% | 60 |↵
| 11 | 2 | 138412032 | 4194304 | 150% | 66 |↵
| 12 | 2 | 603979776 | 16777216 | 150% | 72 |↵
</spoiler>↵

<spoiler summary="Problem C2 - Eliminate odd row, odd column then eliminate 2x2 cells">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <vector>↵

using namespace std;↵

#define all(x) (x).begin(), (x).end()↵

/// Each line of the answer↵
struct node { ↵
    int a, b, c, d, e, f; ↵
    node (int a, int b, int c, int d, int e, int f)↵
    :       a(a),  b(b),  c(c),  d(d),  e(e),  f(f) {}↵
};↵

vector<node> res;↵
vector<vector<int> > a;↵
void flip(const node &x)↵
{↵
    a[x.a][x.b] ^= 1;↵
    a[x.c][x.d] ^= 1;↵
    a[x.e][x.f] ^= 1;↵
    res.push_back(x);↵
}↵

int main()↵
{↵
    int q;↵
    cin >> q;↵
    ↵
    while (q-->0) /// For each query↵
    {↵
        /// Input↵
        int n, m;↵
        cin >> n >> m;↵
        ↵
        a.assign(n + 1, vector<int>(m + 1, 0));↵
        for (int i = 1; i <= n; ++i)↵
        {↵
            string s;↵
            cin >> s;↵
            ↵
            for (int j = 1; j <= m; ++j)↵
                a[i][j] = s[j - 1] - '0'; /// Convert string to array↵
        }↵
        ↵
        res.clear();↵
        ↵
        /// Odd row elimination↵
        if (n & 1)↵
        {↵
            for (int j = 1; j <= m; ++j) /// Eliminate 2x1 cells by once↵
            {↵
                int p = (j == m) ? (j - 1) : (j + 1);↵
                if (a[n][j]) flip(node(n-0,j   ,   n-1,j   ,   n-1,p));↵
            }↵
            --n; /// <- Last row eliminated↵
        }↵
        ↵
        /// Odd column elimination↵
        if (m & 1)↵
        {↵
            for (int i = 1; i <= n; ++i) /// Eliminate 1x2 cells by once↵
            {↵
                int p = (i == n) ? (i - 1) : (i + 1);↵
                if (a[i][m]) flip(node(i,m-0   ,   i,m-1   ,   p,m-1));↵
            }↵
            --m; /// <- last col eliminated↵
        }↵
        ↵
        /// Eliminate 2x2 cells by once↵
        for (int i = 1; i <= n; i += 2)↵
        {↵
            for (int j = 1; j <= m; j += 2)↵
            {↵
                int x = 0, y = 0, z = 0, t = 0;↵
                if (a[i + 0][j + 0]) x ^= 0, y ^= 1, z ^= 1, t ^= 1;↵
                if (a[i + 1][j + 0]) x ^= 1, y ^= 0, z ^= 1, t ^= 1;↵
                if (a[i + 0][j + 1]) x ^= 1, y ^= 1, z ^= 0, t ^= 1;↵
                if (a[i + 1][j + 1]) x ^= 1, y ^= 1, z ^= 1, t ^= 0;↵
            ↵
                if (x) flip(node(i+1,j+0   ,   i+0,j+1   ,   i+1,j+1));↵
                if (y) flip(node(i+0,j+0   ,   i+0,j+1   ,   i+1,j+1));↵
                if (z) flip(node(i+0,j+0   ,   i+1,j+0   ,   i+1,j+1));↵
                if (t) flip(node(i+0,j+0   ,   i+1,j+0   ,   i+0,j+1));↵
            }↵
        }↵
        ↵
        /// Output the result↵
        cout << res.size() << '\n';↵
        for (const node &x : res)↵
        {↵
            cout << x.a << ' ' << x.b << ' ';↵
            cout << x.c << ' ' << x.d << ' ';↵
            cout << x.e << ' ' << x.f << '\n';↵
        }↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Benchmark">↵


$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$↵

For $S$ ones in table, it need maximumly $min(N \cdot M, 3 \times S)$ operations↵

For every $N \cdot M$ table, it need averagely $\frac{N}{2}$ operations and maximumly $N * M$ operations↵

|rows|columns|total count|total cases|average percase | maximum case|↵
|----|----|-----------|----------|----------|----|↵
| 2 | 2 | 32 | 16 | 50% | 4 |↵
| 2 | 3 | 192 | 64 | 50% | 6 |↵
| 2 | 4 | 1024 | 256 | 50% | 8 |↵
| 2 | 5 | 5120 | 1024 | 50% | 10 |↵
| 2 | 6 | 24576 | 4096 | 50% | 12 |↵
| 2 | 7 | 114688 | 16384 | 50% | 14 |↵
| 2 | 8 | 524288 | 65536 | 50% | 16 |↵
| 2 | 9 | 2359296 | 262144 | 50% | 18 |↵
| 2 | 10 | 10485760 | 1048576 | 50% | 20 |↵
| 2 | 11 | 46137344 | 4194304 | 50% | 22 |↵
| 2 | 12 | 201326592 | 16777216 | 50% | 24 |↵
| 3 | 2 | 192 | 64 | 50% | 6 |↵
| 3 | 3 | 2304 | 512 | 50% | 9 |↵
| 3 | 4 | 24576 | 4096 | 50% | 12 |↵
| 3 | 5 | 245760 | 32768 | 50% | 15 |↵
| 3 | 6 | 2359296 | 262144 | 50% | 18 |↵
| 3 | 7 | 22020096 | 2097152 | 50% | 21 |↵
| 3 | 8 | 201326592 | 16777216 | 50% | 24 |↵
| 4 | 2 | 1024 | 256 | 50% | 8 |↵
| 4 | 3 | 24576 | 4096 | 50% | 12 |↵
| 4 | 4 | 524288 | 65536 | 50% | 16 |↵
| 4 | 5 | 10485760 | 1048576 | 50% | 20 |↵
| 4 | 6 | 201326592 | 16777216 | 50% | 24 |↵
| 5 | 2 | 5120 | 1024 | 50% | 10 |↵
| 5 | 3 | 245760 | 32768 | 50% | 15 |↵
| 5 | 4 | 10485760 | 1048576 | 50% | 20 |↵
| 6 | 2 | 24576 | 4096 | 50% | 12 |↵
| 6 | 3 | 2359296 | 262144 | 50% | 18 |↵
| 6 | 4 | 201326592 | 16777216 | 50% | 24 |↵
| 7 | 2 | 114688 | 16384 | 50% | 14 |↵
| 7 | 3 | 22020096 | 2097152 | 50% | 21 |↵
| 8 | 2 | 524288 | 65536 | 50% | 16 |↵
| 8 | 3 | 201326592 | 16777216 | 50% | 24 |↵
| 9 | 2 | 2359296 | 262144 | 50% | 18 |↵
| 10 | 2 | 10485760 | 1048576 | 50% | 20 |↵
| 11 | 2 | 46137344 | 4194304 | 50% | 22 |↵
| 12 | 2 | 201326592 | 16777216 | 50% | 24 |↵
</spoiler>↵

<spoiler summary="Problem C2 - Eliminate rows then columns then last 2x2 cells">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <vector>↵

using namespace std;↵

#define all(x) (x).begin(), (x).end()↵

/// Each line of the answer↵
struct node { ↵
    int a, b, c, d, e, f; ↵
    node (int a, int b, int c, int d, int e, int f)↵
    :       a(a),  b(b),  c(c),  d(d),  e(e),  f(f) {}↵
};↵

vector<node> res;↵
vector<vector<int> > a;↵
void flip(const node &x)↵
{↵
    a[x.a][x.b] ^= 1;↵
    a[x.c][x.d] ^= 1;↵
    a[x.e][x.f] ^= 1;↵
    res.push_back(x);↵
}↵

int main()↵
{↵
    int q;↵
    cin >> q;↵
    ↵
    while (q-->0) /// For each query↵
    {↵
        /// Input↵
        int n, m;↵
        cin >> n >> m;↵

        /// Initalization↵
        res.clear();↵
        a.assign(n + 1, vector<int>(m + 1, 0));↵
        for (int i = 1; i <= n; ++i)↵
        {↵
            string s;↵
            cin >> s;↵
            ↵
            for (int j = 1; j <= m; ++j)↵
                a[i][j] = s[j - 1] - '0'; /// Convert string to array↵
        }↵
        ↵


        /// Odd column elimination↵
        if (m & 1)↵
        {↵
            for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once↵
            {↵
                if (a[i0][m] == 0) continue;↵
                int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1);↵
//                if (a[i1][m]) flip(node(i0,m-0   ,   i1,m-0   ,   i0,m-1));↵
//                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));↵

                if (a[i1][m]) /// Greedy one more step↵
                {↵
                    int p = a[i1][m-1] ? i1 : i0; /// Select the one with one↵
                    flip(node(i0,m-0   ,   i1,m-0   ,   p,m-1));↵
                }↵
                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));↵
            }↵
            --m; /// <- Last col eliminated↵
        }↵
        ↵


        /// Row Elimination: n * m -> 2 * m remaining↵
        while (n > 2)↵
        {↵
            for (int j0 = 1; j0 <= m; ++j0) /// Eliminate 2x1 cells by once↵
            {↵
                if (a[n][j0] == 0) continue;↵
                int j1 = (j0 == m) ? (j0 - 1) : (j0 + 1);↵
//                if (a[n][j1]) flip(node(n-0,j0   ,   n-0,j1   ,   n-1,j0));↵
//                else          flip(node(n-0,j0   ,   n-1,j0   ,   n-1,j1));↵

                if (a[n][j1])  /// Greedy one more step↵
                {↵
                    int p = a[n-1][j1] ? j1 : j0; /// Select the one with one↵
                    flip(node(n-0,j0   ,   n-0,j1   ,   n-1,p));↵
                }↵
                else          flip(node(n-0,j0   ,   n-1,j0   ,   n-1,j1));↵
            }↵
            --n; /// <- Last row eliminated↵
        }↵
        ↵


        /// Col Elimination: 2 * m -> 2 * 2 remaining↵
        while (m > 2)↵
        {↵
            for (int i0 = 1; i0 <= n; ++i0) /// Eliminate 1x2 cells by once↵
            {↵
                if (a[i0][m] == 0) continue;↵
                int i1 = (i0 == n) ? (i0 - 1) : (i0 + 1);↵
//                if (a[i1][m]) flip(node(i0,m-0   ,   i1,m-0   ,   i0,m-1));↵
//                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));↵

                if (a[i1][m]) /// Greedy one more step↵
                {↵
                    int p = a[i1][m-1] ? i1 : i0; /// Select the one with one↵
                    flip(node(i0,m-0   ,   i1,m-0   ,   p,m-1));↵
                }↵
                else          flip(node(i0,m-0   ,   i0,m-1   ,   i1,m-1));↵
            }↵
            --m; /// <- Last col eliminated↵
        }↵
        ↵


        /// Cells Elimination: 2 * 2 -> 0 * 0 remaining - Using modular equations↵
        int x = 0, y = 0, z = 0, t = 0;↵
        if (a[1][1]) x ^= 0, y ^= 1, z ^= 1, t ^= 1;↵
        if (a[2][1]) x ^= 1, y ^= 0, z ^= 1, t ^= 1;↵
        if (a[1][2]) x ^= 1, y ^= 1, z ^= 0, t ^= 1;↵
        if (a[2][2]) x ^= 1, y ^= 1, z ^= 1, t ^= 0;↵

        if (x) flip(node(2,1   ,   1,2   ,   2,2));↵
        if (y) flip(node(1,1   ,   1,2   ,   2,2));↵
        if (z) flip(node(1,1   ,   2,1   ,   2,2));↵
        if (t) flip(node(1,1   ,   2,1   ,   1,2));↵
     ↵


        /// Output the result↵
        cout << res.size() << '\n';↵
        for (const node &x : res)↵
        {↵
            cout << x.a << ' ' << x.b << ' ';↵
            cout << x.c << ' ' << x.d << ' ';↵
            cout << x.e << ' ' << x.f << '\n';↵
        }↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Benchmark">↵

$\text{Average case} = \frac{\text{Total count}}{\text{Rows}\ \cdot \text{Columns}\ \cdot \text{Total case}}$↵

For every $N \cdot M$ table, it need averagely $\frac{N}{2}$ operations and maximumly $min(N \cdot M, \lceil \frac{n + 1}{2} \rceil + \lceil \frac{m(n - 2)}{2} \rceil + (m - 2) + 3)$ operations↵

|rows|columns|total count|total cases|average percase | maximum case|↵
|----|----|-----------|----------|----------|----|↵
| 2 | 2 | 32 | 16 | 50% | 4 |↵
| 2 | 3 | 176 | 64 | 45.8333% | 5 |↵
| 2 | 4 | 880 | 256 | 42.9688% | 6 |↵
| 2 | 5 | 4240 | 1024 | 41.4062% | 7 |↵
| 2 | 6 | 19824 | 4096 | 40.332% | 8 |↵
| 2 | 7 | 90768 | 16384 | 39.5717% | 9 |↵
| 2 | 8 | 408944 | 65536 | 38.9999% | 10 |↵
| 2 | 9 | 1819280 | 262144 | 38.5556% | 11 |↵
| 2 | 10 | 8011120 | 1048576 | 38.2% | 12 |↵
| 2 | 11 | 34980496 | 4194304 | 37.9091% | 13 |↵
| 2 | 12 | 151666032 | 16777216 | 37.6667% | 14 |↵
| 3 | 2 | 176 | 64 | 45.8333% | 5 |↵
| 3 | 3 | 1968 | 512 | 42.7083% | 7 |↵
| 3 | 4 | 19824 | 4096 | 40.332% | 8 |↵
| 3 | 5 | 194352 | 32768 | 39.541% | 10 |↵
| 3 | 6 | 1816240 | 262144 | 38.4911% | 11 |↵
| 3 | 7 | 16814096 | 2097152 | 38.179% | 13 |↵
| 3 | 8 | 151165600 | 16777216 | 37.5424% | 14 |↵
| 4 | 2 | 880 | 256 | 42.9688% | 6 |↵
| 4 | 3 | 19824 | 4096 | 40.332% | 8 |↵
| 4 | 4 | 405088 | 65536 | 38.6322% | 10 |↵
| 4 | 5 | 7938304 | 1048576 | 37.8528% | 12 |↵
| 4 | 6 | 148856720 | 16777216 | 36.969% | 14 |↵
| 5 | 2 | 4240 | 1024 | 41.4062% | 7 |↵
| 5 | 3 | 193216 | 32768 | 39.3099% | 10 |↵
| 5 | 4 | 7897792 | 1048576 | 37.6596% | 12 |↵
| 5 | 5 | 311233920 | 33554432 | 37.102% | 15 |↵
| 6 | 2 | 19824 | 4096 | 40.332% | 8 |↵
| 6 | 3 | 1816240 | 262144 | 38.4911% | 11 |↵
| 6 | 4 | 148979200 | 16777216 | 36.9994% | 14 |↵
| 7 | 2 | 90768 | 16384 | 39.5717% | 9 |↵
| 7 | 3 | 16718864 | 2097152 | 37.9627% | 13 |↵
| 8 | 2 | 408944 | 65536 | 38.9999% | 10 |↵
| 8 | 3 | 151165600 | 16777216 | 37.5424% | 14 |↵
| 9 | 2 | 1819280 | 262144 | 38.5556% | 11 |↵
| 10 | 2 | 8011120 | 1048576 | 38.2% | 12 |↵
| 11 | 2 | 34980496 | 4194304 | 37.9091% | 13 |↵
| 12 | 2 | 151666032 | 16777216 | 37.6667% | 14 |↵

</spoiler>↵

</spoiler>↵

История

 
 
 
 
Правки
 
 
  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)