Original Problem
The statement
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}{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
Analizer
#include <iostream>
#include <cstdio>
#include <vector>
#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);
}
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 = 0;
ll total = 0;
map<int, int> M;
map<int, int>::iterator it;
for (int mask = 0; mask < lim; ++mask)
{
++M[f[mask]];
total += f[mask];
maximum = max(maximum, 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;
}
}
}
cout << "In total amount of " << lim << " binary table " << n << " x " << m << endl;
for (it = M.begin(); it != M.end(); ++it)
{
cout << " - " << (it->second) << " cases need";
cout << " minimum " << (it->first) << " operations" << endl;
}
cout << endl;
double mean = double(total) / lim;
double rate = (double(total) / (lim * n * m)) * 100;
cout << "In optimal solution, in each table " << n << " x " << m << endl;
cout << " A) You need averagely " << mean << " operations" << endl;
cout << " > Which is about " << rate << "% of " << n * m << " operations" << endl;
cout << " B) 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;
}
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 optimal solution, in each table 3 x 3
A) You need averagely 3.09766 operations
> Which is about 34.4184% of 9 operations
B) 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
