Gift#12321
Problem Author: | Andriy Kholod (Connect) |
Prepared by: | Andriy Kholod (Connect) |
Analysis: | Andriy Kholod (Connect) |
Solution
1) How to describe all operations with variables
Let r_i \in \{0,1\} be whether we invert row , and c_j \in \{0,1\} be whether we invert column . Then after all operations, the element will be: [ A'_{i,j} = A_{i,j} \oplus r_i \oplus c_j ]
Condition of symmetry: [ A_{i,j} \oplus r_i \oplus c_j \;=\; A_{i',j'} \oplus r_{i'} \oplus c_{j'} ] where i' = n-i+1, j' = m-j+1.
We move the known to one side: [ (r_i \oplus r_{i'}) \oplus (c_j \oplus c_{j'}) = A_{i,j} \oplus A_{i',j'} ]
2) Reducing to variables only for pairs
We will split the rows into pairs (i, i') and the columns into pairs (j, j'). The number of pairs: [ R=\lfloor n/2 \rfloor,\quad C=\lfloor m/2 \rfloor ]
We introduce new variables: [ R_i = r_i \oplus r_{i'},\quad C_j = c_j \oplus c_{j'} ] for i=0..R-1, j=0..C-1.
Then for each pair of rows and pairs of columns , we have the equation: [ R_i \oplus C_j = W_{i,j} ] where [ W_{i,j} = A_{i,j} \oplus A_{i',j'} ]
3) Necessary condition for existence (2x2 check)
For fixed and , consider 4 cells: [ (i,j),\ (i',j'),\ (i,j'),\ (i',j) ] The following must hold: [ A_{i,j}\oplus A_{i',j'} = A_{i,j'} \oplus A_{i',j} ] because both expressions equal R_i \oplus C_j (once through (j,j'), another time through the swapped columns). If for at least one such block the values differ — the solution does not exist, the answer is .
This is exactly what is done in the code:
x = A_{i,j} \oplus A_{i',j'}
y = A_{i,j'} \oplus A_{i',j}
if x \ne y — print
otherwise W_{i,j} = x
4) Fixations for odd or
If is odd, there is a central row . For it, i=i' and therefore r_i \oplus r_{i'}=0. Then from the condition: [ A'_{mid,j} = A'_{mid,j'} \Rightarrow (c_j \oplus c_{j'}) = A_{mid,j} \oplus A_{mid,j'} ] That is, for each pair of columns we get a fixed value C_j.
Similarly, if is odd, there is a central column and it fixes each R_i: [ (r_i \oplus r_{i'}) = A_{i,midc} \oplus A_{i',midc} ]
In the code, this is done through setVal and the arrays fixedR/fixedC.
5) Graph interpretation of the equations
We have a system: [ R_i \oplus C_j = W_{i,j} ] This is a bipartite graph: vertices on the left — R_i, on the right — C_j, and the edge has a "weight" W_{i,j}.
If we know the value of one vertex, then from the edge we immediately know the neighbor: [ C_j = R_i \oplus W_{i,j},\quad R_i = C_j \oplus W_{i,j} ] Thus, throughout the connected component, all values are uniquely determined (up to a global XOR, if the component is not fixed).
That is why the solution performs BFS on the components and assigns values to the variables.
6) Minimizing the number of operations
Important: we minimize the number of row/column operations, not the number of ones in the matrix.
How is this related to R_i and C_j?
If R_i = 1, then in the pair of rows (i,i') we need to invert exactly one row (this costs 1 operation). If R_i=0 — either we invert both or neither (we can do 0 operations in this pair, because "both" is never beneficial). Thus, the minimum cost for the pair is simply R_i.
Similarly for C_j — the cost of the pair of columns equals C_j.
Thus, minimizing the number of operations means minimizing: [ \sum_i R_i + \sum_j C_j ]
7) What we do in the connected component
During BFS for the component, we count:
— the number of vertices in the component (both -vertices and -vertices),
— how many of them received the value 1,
compFixed — whether there is at least one "fixed" vertex in the component (through the middle row/column).
If the component is fixed, then the values are already unique the cost of the component = .
If the component is not fixed, then we can simultaneously invert all values in the component: [ R_i \leftarrow R_i \oplus 1,\quad C_j \leftarrow C_j \oplus 1 ] and all equations will remain valid. Then we can choose the cheaper of the two options: [ \min(ones,\ tot-ones) ]
The sum over all components is the answer.
8) Asymptotics
We store only R \cdot C \le 2500 \cdot 2500 = 6.25 \cdot 10^6 values of .
BFS in such a "complete bipartite graph" is implemented as:
from the row vertex we go through all columns;
from the column vertex — through all rows.
In the worst case, this is O(R \cdot C) transitions, which fits within the limits.
Memory: for reading (in the code, the matrix is treated as rows) and for .
Solution Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back
static int n, m, R, C;
static vector<string> s;
static vector<vector<int>> W;
static vector<int> valR, valC;
static vector<int> fixedR, fixedC;
static vector<int> visR, visC;
static deque<int> q;
static ll answer;
int bitAt(int i, int j) {
return s[i][j] - '0';
}
bool setVal(vector<int>& val, vector<int>& fx, int idx, int need) {
if (val[idx] == -1) {
val[idx] = need;
fx[idx] = 1;
return true;
}
return val[idx] == need;
}
bool pushRow(int i, int v) {
if (valR[i] == -1) valR[i] = v;
else if (valR[i] != v) return false;
return true;
}
bool pushCol(int j, int v) {
if (valC[j] == -1) valC[j] = v;
else if (valC[j] != v) return false;
return true;
}
bool bfs_component(int start) {
bool compFixed = false;
ll ones = 0, tot = 0;
q.clear();
q.push_back(start);
while (!q.empty()) {
int node = q.front();
q.pop_front();
if (node < R) {
int i = node;
if (visR[i]) continue;
visR[i] = 1;
tot++;
if (fixedR[i]) compFixed = true;
if (valR[i] == 1) ones++;
int vr = valR[i];
for (int j = 0; j < C; j++) {
int needC = vr ^ W[i][j];
if (!pushCol(j, needC)) return false;
if (!visC[j]) q.push_back(R + j);
}
} else {
int j = node - R;
if (visC[j]) continue;
visC[j] = 1;
tot++;
if (fixedC[j]) compFixed = true;
if (valC[j] == 1) ones++;
int vc = valC[j];
for (int i = 0; i < R; i++) {
int needR = vc ^ W[i][j];
if (!pushRow(i, needR)) return false;
if (!visR[i]) q.push_back(i);
}
}
}
if (compFixed) answer += ones;
else answer += min(ones, tot - ones);
return true;
}
void solve() {
cin >> n >> m;
s.assign(n, "");
for (int i = 0; i < n; i++) {
s[i].reserve(m);
for (int j = 0; j < m; j++) {
char c;
cin >> c;
s[i].push_back(c);
}
}
R = n / 2;
C = m / 2;
W.assign(R, vector<int>(C, 0));
valR.assign(R, -1);
valC.assign(C, -1);
fixedR.assign(R, 0);
fixedC.assign(C, 0);
visR.assign(R, 0);
visC.assign(C, 0);
answer = 0;
for (int i = 0; i < R; i++) {
int i2 = n - 1 - i;
for (int j = 0; j < C; j++) {
int j2 = m - 1 - j;
int a1 = bitAt(i, j);
int a2 = bitAt(i2, j2);
int a3 = bitAt(i, j2);
int a4 = bitAt(i2, j);
int x = a1 ^ a2;
int y = a3 ^ a4;
if (x != y) {
cout << -1 << endl;
return;
}
W[i][j] = x;
}
}
if (n & 1) {
int mid = n / 2;
for (int j = 0; j < C; j++) {
int j2 = m - 1 - j;
int need = bitAt(mid, j) ^ bitAt(mid, j2);
if (!setVal(valC, fixedC, j, need)) {
cout << -1 << endl;
return;
}
}
}
if (m & 1) {
int midc = m / 2;
for (int i = 0; i < R; i++) {
int i2 = n - 1 - i;
int need = bitAt(i, midc) ^ bitAt(i2, midc);
if (!setVal(valR, fixedR, i, need)) {
cout << -1 << endl;
return;
}
}
}
for (int i = 0; i < R; i++) {
if (valR[i] != -1 && !visR[i]) {
if (!bfs_component(i)) {
cout << -1 << endl;
return;
}
}
}
for (int j = 0; j < C; j++) {
if (valC[j] != -1 && !visC[j]) {
if (!bfs_component(R + j)) {
cout << -1 << endl;
return;
}
}
}
for (int i = 0; i < R; i++) {
if (!visR[i]) {
if (valR[i] == -1) valR[i] = 0;
if (!bfs_component(i)) {
cout << -1 << endl;
return;
}
}
}
for (int j = 0; j < C; j++) {
if (!visC[j]) {
if (valC[j] == -1) valC[j] = 0;
if (!bfs_component(R + j)) {
cout << -1 << endl;
return;
}
}
}
cout << answer << endl;
}
signed main() {
speed;
int test = 1;
// cin >> test;
while (test--) solve();
return 0;
}