Binary Table minimize operations

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Original Problem

Easy Version: Div 2, Div 1
Hard Version: Div 2, [Div 1](https://codeforces.net/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

Code solution without minimizing (with comments)

Problem C1 - Eliminate each 1x1 cells

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

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

Problem C2 - Eliminate odd row, odd column then eliminate 2x2 cells

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

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

Problem C2 - Eliminate rows then columns then last 2x2 cells

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

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

Rev.	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)

Original Problem

History