Original Problem
- Easy Version: Div 2, Div 1
- Hard Version: Div 2, [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$$$. 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$$$
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
