↵
- Easy Version: [Div 2](https://mirror.codeforces.com/contest/1440/problem/C1), [Div 1](https://mirror.codeforces.com/contest/1439/problem/A1)
- Hard Version: [Div 2](https://mirror.codeforces.com/contest/1440/problem/C2), [Div 1](https://mirror.codeforces.com/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="
↵
<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>↵
↵
