Original Problem
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
For all $$$n \cdot n$$$ tables with $$$S$$$ ones , if we play optimally in some good cases:
S = 1
- We need atleast/atmost $$$3$$$ operations
XO | + | OO | ++ | XX | ++ | OO
OO | ++ | XX | + | OX | + | OO
S # 1
- We need atmost $$$S$$$ operations
XXXX... | ++ | OOXX.. | ++ | OOOX.. | ++.. | ..OX | ++ | ..XO | + | ..OO
OOOO... | + | OXOO.. | + | OOXO.. | +.. | ..XO | + | ..XX | ++ | ..OO
S = 3k
- $$$\forall S = 3 \cdot k\ (k \in \mathbb{N})$$$, we need atleast $$$k$$$ operations, $$$3$$$ ones in each operation
XXX.. | ++ | OOX.. | +.. | ..XXX | ++ | ..OOX | + | ..XXX
XXX.. | + | OXX.. | ++.. | ..XXX | + | ..OXX | ++ | ..XXX
S = 3k + 4
- $$$\forall S = 3 \cdot k + 4\ (k \in \mathbb{N})$$$, we need atleast $$$k + 2$$$ operations, $$$3$$$ ones in each operation, and last $$$2$$$ operations for $$$4$$$ ones
XXX..XOX | +__.. | _++.. | ..XOX | ++_ | ..OOX | __+ | ..OOO
XXX..XOX | ++_.. | __+.. | ..XOX | +__ | ..OXX | _++ | ..OOO
S = 3k + 2
- $$$\forall S = 3 \cdot k + 2\ (k \in \mathbb{N})$$$, we need atleast $$$k + 2$$$ operations, $$$3$$$ ones in each operation, and last $$$2$$$ operations for $$$2$$$ ones
XXX..OX | +__.. | _++.. | ..OX | ++ | ..XO | + | ..OO
XXX..OX | ++_.. | __+.. | ..OX | + | ..XX | ++ | ..OO
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
Auto comment: topic has been updated by SPyofgame (previous revision, new revision, compare).
This blog is better formatted, and better quality than my university assignments.
Thank you