C2/A2-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

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)

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 \cdot M}{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

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

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cstdio>
#include <deque>
#include <cmath>
#include <map>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}
#define all(x) (x).begin(), (x).end()
typedef long long ll;

int n, m;
void flip(int &mask, int i, int j) { mask ^= 1 << (i * m + j); }

int lim;
vector<int> F;
vector<int> trace;
void bfs(int s)
{
    trace.assign(lim, 0);
    F.assign(lim, -1);

    trace[s] = -1;
    F[s] = 0;

    deque<int> S;
    S.push_back(s);
    while (S.size())
    {
        int u = S.front();
        S.pop_front();

        for (int i = 1; i < n; ++i) /// Select row
        {
            for (int j = 1; j < m; ++j) /// Select column
            {
                vector<int> selected_x = {i - 1, i - 0, i - 1, i - 0};
                vector<int> selected_y = {j - 1, j - 1, j - 0, j - 0};

                int t = u; /// Make new mask
                for (int k = 0; k < 4; ++k) /// Fully 2x2 modified
                    flip(t, selected_x[k], selected_y[k]);

                for (int k = 0; k < 4; ++k) /// Select 1x1 cell not be modified
                {
                    int v = t;
                    flip(v, selected_x[k], selected_y[k]);

                    if (F[v] == -1) /// If not visited
                    {
                        trace[v] = u;
                        F[v] = F[u] + 1;
                        S.push_back(v);
                    }
                }
            }
        }
    }
}

void analize()
{
    int maximum = *max_element(all(F));
    ll total = accumulate(all(F), 0LL);
    vector<int> C(maximum + 1, 0);
    for (int mask = 0; mask < lim; ++mask)
        ++C[F[mask]];
    
    double closest = 1e9;
    int numerator = 0;
    int denominator = 0;
    int test = sqrt(lim);
    for (int nume = test; nume >= 1; --nume)
    {
        for (int deno = test; deno >= 1; --deno)
        {
            double value = double(nume) / deno * n * m;
            double delta = value - maximum;
            if (delta >= 1e-6 && closest >= delta)
            {
                closest = delta;
                numerator = nume;
                denominator = deno;
            }
        }
    }
    double mean = double(total) / lim;
    double rate = (double(total) / (lim * n * m)) * 100;

    cout << "In total amount of " << lim << " binary table " << n << " x " << m << endl;
    for (int operation = 0; operation <= maximum; ++operation)
    {
        cout << " - " << C[operation] << " cases need";
        cout << " minimum " << operation << " operations" << endl;
    }
    cout << endl;

    cout << "In an overkill solution, in each table " << n << " x " << m << endl;

    cout << "   A) In all cases, you need total " << total << " operations of " << lim << " cases" << endl;
    cout << "    > If your code return exact that value then it is operation minimized" << endl;

    cout << "   B) You need averagely " << mean << " operations" << endl;
    cout << "    > Which is about " << rate << "% of " << n * m << " operations" << endl;

    cout << "   C) And the maximum number of operations needed is " << maximum << endl;
    cout << "    > Which is approximately " << numerator << "nm/" << denominator << " operations" << endl;
    cout << "    > Which mean for each " << numerator << " ones in the table" << endl;
    cout << "      We only need maximumly " << denominator << " operations average" << endl;





    const bool show_case = false;
    const bool show_trace = false;
    if (show_case == false) return ;

    /// If you want to output cases
    vector<vector<int> > M(maximum + 1);
    for (int index = 0; index <= maximum; ++index) M[index].resize(C[index]);
    for (int mask = 0; mask < lim; ++mask)
        M[F[mask]][--C[F[mask]]] = mask; /// this look messy :D

    cout << "\n\n";
    for (int operation = 0; operation <= maximum; ++operation)
    {
        cout << "====X====X====X====X====X====X====X====X====X====X====\n";
        for (int mask : M[operation])
        {
            int cntbit = __builtin_popcount(mask);
            cout << "----x----x----x----x----x----x----x----x----\n";
            cout << "At (" << mask << ") = " << cntbit << " ones | Need " << operation << " operations :\n";

            do 
            {
                int sub = mask;
                for (int i = 1; i <= n; ++i)
                {
                    for (int j = 1; j <= m; ++j)
                    {
                        cout << (sub & 1);
                        sub >>= 1;
                    }
                    cout << '\n';
                }
                cout << '\n';
                if (show_trace == false) break; /// If you only want the mask and not the trace
            } while ((mask = trace[mask]) != -1);
        }
    }
}

int main()
{
    // file();
    cin >> n >> m;
    if (1LL * n * m > 20)
    {
        cout << "Well, I dont have enough data for that :(";
        cout << "- Please provide me smaller constraint";
        return 0;
    }

    lim = 1 << (n * m);
    bfs(0); /// fully zero binary table
    analize();

    return 0;
}

Test with 3x3 tables

In total amount of 512 binary table 3 x 3
 - 1 cases need minimum 0 operations
 - 16 cases need minimum 1 operations
 - 105 cases need minimum 2 operations
 - 220 cases need minimum 3 operations
 - 150 cases need minimum 4 operations
 - 20 cases need minimum 5 operations

In an overkill solution, in each table 3 x 3
   A) In all cases, you need total 1586 operations of 512 cases
    > If your code return exact that value then it is operation minimized
   B) You need averagely 3.09766 operations
    > Which is about 34.4184% of 9 operations
   C) And the maximum number of operations needed is 5
    > Which is approximately 9nm/16 operations
    > Which mean for each 9 ones in the table
      We only need maximumly 16 operations average

With (n, m) = (2, 2) || show_case = true; show_trace = true;

In total amount of 16 binary table 2 x 2
 - 1 cases need minimum 0 operations
 - 4 cases need minimum 1 operations
 - 6 cases need minimum 2 operations
 - 4 cases need minimum 3 operations
 - 1 cases need minimum 4 operations

In an overkill solution, in each table 2 x 2
   A) In all cases, you need total 32 operations of 16 cases
    > If your code return exact that value then it is operation minimized
   B) You need averagely 2 operations
    > Which is about 50% of 4 operations
   C) And the maximum number of operations needed is 4
    > Which is approximately 4nm/3 operations
    > Which mean for each 4 ones in the table
      We only need maximumly 3 operations average


====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (0) = 0 ones | Need 0 operations :
00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (14) = 3 ones | Need 1 operations :
01
11

00
00

----x----x----x----x----x----x----x----x----
At (13) = 3 ones | Need 1 operations :
10
11

00
00

----x----x----x----x----x----x----x----x----
At (11) = 3 ones | Need 1 operations :
11
01

00
00

----x----x----x----x----x----x----x----x----
At (7) = 3 ones | Need 1 operations :
11
10

00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (12) = 2 ones | Need 2 operations :
00
11

11
01

00
00

----x----x----x----x----x----x----x----x----
At (10) = 2 ones | Need 2 operations :
01
01

10
11

00
00

----x----x----x----x----x----x----x----x----
At (9) = 2 ones | Need 2 operations :
10
01

01
11

00
00

----x----x----x----x----x----x----x----x----
At (6) = 2 ones | Need 2 operations :
01
10

11
01

00
00

----x----x----x----x----x----x----x----x----
At (5) = 2 ones | Need 2 operations :
10
10

01
11

00
00

----x----x----x----x----x----x----x----x----
At (3) = 2 ones | Need 2 operations :
11
00

01
11

00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (8) = 1 ones | Need 3 operations :
00
01

10
10

01
11

00
00

----x----x----x----x----x----x----x----x----
At (4) = 1 ones | Need 3 operations :
00
10

11
00

01
11

00
00

----x----x----x----x----x----x----x----x----
At (2) = 1 ones | Need 3 operations :
01
00

10
10

01
11

00
00

----x----x----x----x----x----x----x----x----
At (1) = 1 ones | Need 3 operations :
10
00

01
10

11
01

00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (15) = 4 ones | Need 4 operations :
11
11

00
01

10
10

01
11

00
00

And if the ones are connected, here is the analizer (I will optimize the algo later)

Small checker

/// The algorithm can be improved with polynomino-generating

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cstdio>
#include <deque>
#include <cmath>
#include <map>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;

template<typename T> void maximize(T &res, T val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, T val) { if (res > val) res = val; }

const int mx[] = {+1, +0, -0, -1};
const int my[] = {+0, +1, -1, -0};

int n, m;
void flip(int &mask, int i, int j) { mask ^= 1 << (i * m + j); }
bool consecutive(int mask) /// All ones are connected
{
    vector<int> used(n, 0);
    used[0] = 1 << 0;
    int cnt = 0;

    deque<pi> S;
    S.push_back(pi(0, 0));
    while (S.size())
    {
        int x = S.front().first;
        int y = S.front().second;
        S.pop_front();

        for (int k = 0; k < 4; ++k)
        {
            int nx = x + mx[k];
            int ny = y + my[k];
            if (nx < 0 || nx >= n) continue;
            if (ny < 0 || ny >= m) continue;
            if (used[nx] >> ny & 1) continue;
            if ((mask >> (nx * m + ny)) & 1) 
            {
                ++cnt;
                used[nx] |= 1 << ny;
                S.push_back(pi(nx, ny));
            }
        }
    }

    int cntbit = __builtin_popcount(mask);
    return cnt == cntbit;
}

int lim;
vector<int> F;
vector<int> trace;
void bfs(int s)
{
    trace.assign(lim, 0);
    F.assign(lim, -1);

    trace[s] = -1;
    F[s] = 0;

    deque<int> S;
    S.push_back(s);
    while (S.size())
    {
        int u = S.front();
        S.pop_front();

        for (int i = 1; i < n; ++i) /// Select row
        {
            for (int j = 1; j < m; ++j) /// Select column
            {
                vector<int> selected_x = {i - 1, i - 0, i - 1, i - 0};
                vector<int> selected_y = {j - 1, j - 1, j - 0, j - 0};

                int t = u; /// Make new mask
                for (int k = 0; k < 4; ++k) /// Fully 2x2 modified
                    flip(t, selected_x[k], selected_y[k]);

                for (int k = 0; k < 4; ++k) /// Select 1x1 cell not be modified
                {
                    int v = t;
                    flip(v, selected_x[k], selected_y[k]);

                    if (F[v] == -1) /// If not visited
                    {
                        trace[v] = u;
                        F[v] = F[u] + 1;
                        S.push_back(v);
                    }
                }
            }
        }
    }
}

void analize()
{
    int maximum = *max_element(all(F));
    ll total = accumulate(all(F), 0LL);
    vector<int> C(maximum + 1, 0);
    for (int mask = 0; mask < lim; ++mask)
        ++C[F[mask]];
    
    cout << "In an overkill solution, in each table " << n << " x " << m << endl;
    /// If you want to output cases
    vector<vector<int> > M(maximum + 1);
    for (int index = 0; index <= maximum; ++index) M[index].resize(C[index]);
    for (int mask = 0; mask < lim; ++mask)
        M[F[mask]][--C[F[mask]]] = mask; /// this look messy :D

    int k = min(n, m);
    vector<int> maxi(k + 1, -1e9);
    vector<int> mini(k + 1, +1e9);
    for (int operation = 0; operation <= maximum; ++operation)
    {
        for (int mask : M[operation])
        {
            int cntbit = __builtin_popcount(mask);
            if (cntbit <= k) /// If (cntbit > k) then we lost the case 1x(cntbit) rectangle
            {
                if (consecutive(mask)) /// all ones are consecutive
                {
                    maximize(maxi[cntbit], operation);
                    minimize(mini[cntbit], operation);
                }
            }
        }
    }

    for (int i = 0; i <= k; ++i) 
    {
        cout << "- With " << i << " ones randomly on the table | ";
        cout << "You need " << "atleast " << mini[i] << " and atmost " << maxi[i] << " operations " << endl;
    }
}

int main()
{
    // file();
    cin >> n >> m;
    if (1LL * n * m > 25)
    {
        cout << "Well, I dont have enough data for that :(";
        cout << "- Please provide me smaller constraint";
        return 0;
    }

    lim = 1 << (n * m);
    bfs(0); /// fully zero binary table
    analize();

    return 0;
}
    }

    lim = 1 << (n * m);
    bfs(0); /// fully zero binary table
    analize();

    return 0;
}

Observation

Test with 9x9 tables

In an overkill solution, in each table 9 x 9
- With 0 ones consecutively random on the table | You need atleast 0 and atmost 0 operations 
- With 1 ones consecutively random on the table | You need atleast 3 and atmost 3 operations 
- With 2 ones consecutively random on the table | You need atleast 2 and atmost 2 operations 
- With 3 ones consecutively random on the table | You need atleast 1 and atmost 3 operations 
- With 4 ones consecutively random on the table | You need atleast 2 and atmost 4 operations 
- With 5 ones consecutively random on the table | You need atleast 3 and atmost 5 operations
- With 6 ones consecutively random on the table | You need atleast 2 and atmost 6 operations
- With 7 ones consecutively random on the table | You need atleast 3 and atmost 7 operations
- With 8 ones consecutively random on the table | You need atleast 4 and atmost 8 operations
- With 9 ones consecutively random on the table | You need atleast 3 and atmost 9 operations

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

Extended version

History