# PAIRFLIP - Editorial

Author: Temirlan Baibolov
Tester: Shubham Anand Jain, Aryan Choudhary
Editorialist: Temirlan Baibolov

MEDIUM

# PREREQUISITES:

Greedy, Graphs, Advanced DFS Techniques, Two-path covering

# PROBLEM:

Chef has two matrices A and B, each with size N \times M. Each cell of the matrix A contains a character ‘0’ or ‘1’, while each cell of the matrix B contains ‘?’, ‘0’ or ‘1’.

The matrix A can be modified using zero or more operations. In one operation, Chef can choose two cells in the matrix A which lie either in the same row or in the same column and flip the characters in each of these cells (flipping means changing ‘1’ to ‘0’ or ‘0’ to ‘1’).

Chef wants the matrix A to match the matrix B. Formally, for each row r and column c, if the cell in row r and column c of B contains ‘0’ or ‘1’, then he wants the cell in row r and column c of A to contain the same character; otherwise (for cells containing ‘?’), it may contain either ‘0’ or ‘1’.

The difficulty of your task is described by a parameter E. If E = 0, you should only find the smallest number of operations required to achieve this goal. If E = 1, you should also find one sequence of operations with the smallest length which achieves it.

# QUICK EXPLANATION:

Build a bipartite graph with N vertices on the left and M vertices on the right. Add an edge (i, j) if A_{i,j} \neq B_{i, j}. The problem reduces to edge covering with paths of length 2, which can be done using DFS.

# EXPLANATION:

Making A = B is the same as making the matrix A \oplus B = 0. Let’s construct this matrix C = A \oplus B. For all valid cells (i, j), if B_{i, j} = \tt{?}, then C_{i, j} = \tt?. Else, C_{i,j} = A_{i,j} \oplus B_{i,j}.

Let’s first solve the problem without any \tt{?} symbols. If the number of ones in C is odd, the answer is -1 since the parity is always preserved and we will not be able to reach a state with 0 ones. Otherwise, build a bipartite graph with N vertices on the left and M vertices on the right. For each valid cell (i, j) with C_{i,j} = 1, add an edge connecting vertex i on the left side and j on the right side. Now you may have noticed that row/column operations correspond to paths of length 2 in this graph. So, to achieve the best result we should cover the edges of the graph with as many paths of length 2 as possible.

Consider each separate connected component. Say, the component we are looking at has e edges. Theoretically the best result we could possibly achieve is \lfloor e / 2 \rfloor paths. And indeed, there is a well-known DFS-like approach which always achieves this bound. See this problem and its editorial for the explanation.

Now, we may be left with some components with the only unmatched edge. The number of such components will always be even. Thus, we can just form pairs out of those edges and each pair will require two operations to be covered.

The solution is almost done. The only question unanswered is how to deal with \tt{?} cells. Those cells let us add some optional edges if we want. Those cells are useful if and only if we have an odd number of edges without them. In this case we just have to carefully choose and add one edge which minimizes the answer.

Time and space complexity is O(NM) per each query.

# SOLUTIONS:

Setter's Solution
// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = (int)2e5 + 5;

bool usedRow[MAXN], usedCol[MAXN];
int rowC[MAXN], colC[MAXN];
vector<array<int, 4>> ans;
string A[MAXN], B[MAXN];
int edges[MAXN];
int n, m, E;

void colorRow(int, int);
void colorCol(int, int);
void dfsRow(int, int);
void dfsCol(int, int);

void colorRow(int v, int c) {
rowC[v] = c;

rep (to, 0, m) {
if (A[v][to] == '1') {
++edges[c];

if (!colC[to]) {
colorCol(to, c);
}
}
}
}

void colorCol(int v, int c) {
colC[v] = c;

rep (to, 0, n) {
if (A[to][v] == '1') {
++edges[c];

if (!rowC[to]) {
colorRow(to, c);
}
}
}
}

void doRow(int r, int i, int j) {
assert(0 <= r && r < n && 0 <= i && i < m && 0 <= j && j < m);
assert(i != j);
ans.pb({0, r + 1, i + 1, j + 1});
A[r][i] ^= 1;
A[r][j] ^= 1;
}

void doCol(int c, int i, int j) {
assert(0 <= c && c < m && 0 <= i && i < n && 0 <= j && j < n);
assert(i != j);
ans.pb({1, c + 1, i + 1, j + 1});
A[i][c] ^= 1;
A[j][c] ^= 1;
}

void dfsRow(int v, int pr = -1) {
usedRow[v] = 1;
int u = -1;

rep (to, 0, m) {
if (A[v][to] == '1' && !usedCol[to]) {
dfsCol(to, v);
}

if (to != pr && A[v][to] == '1') {
if (u == -1) {
u = to;
}
else {
doRow(v, u, to);
u = -1;
}
}
}

if (pr != -1 && u != -1 && A[v][pr] == '1') {
doRow(v, u, pr);
}
}

void dfsCol(int v, int pr = -1) {
usedCol[v] = 1;
int u = -1;

rep (to, 0, n) {
if (A[to][v] == '1' && !usedRow[to]) {
dfsRow(to, v);
}

if (to != pr && A[to][v] == '1') {
if (u == -1) {
u = to;
}
else {
doCol(v, u, to);
u = -1;
}
}
}

if (pr != -1 && u != -1 && A[pr][v] == '1') {
doCol(v, u, pr);
}
}

void solve() {
cin >> n >> m >> E;

rep (i, 0, n) {
cin >> A[i];
}

rep (i, 0, n) {
cin >> B[i];
}

fill(rowC, rowC + n, 0);
fill(colC, colC + m, 0);
fill(usedRow, usedRow + n, 0);
fill(usedCol, usedCol + m, 0);
fill(edges + 1, edges + n + m + 1, 0);
int total = 0, colors = 0;
ans.clear();

rep (i, 0, n) {
rep (j, 0, m) {
if (B[i][j] == '?') {
A[i][j] = '0';
}
else if (A[i][j] == B[i][j]) {
A[i][j] = '0';
}
else {
A[i][j] = '1';
++total;
}
}
}

rep (i, 0, n) {
if (!rowC[i]) {
colorRow(i, ++colors);
}
}

rep (i, 0, m) {
if (!colC[i]) {
colorCol(i, ++colors);
}
}

rep (i, 1, colors + 1) {
assert(edges[i] % 2 == 0);
edges[i] /= 2;
}

assert(accumulate(edges + 1, edges + colors + 1, 0) == total);

if (total % 2 == 1) { // need extra edge
array<int, 3> best = {2, -1, -1};

rep (i, 0, n) {
rep (j, 0, m) {
if (B[i][j] == '?') {
int u = rowC[i], v = colC[j], w = 0;

if (u == v) {
w = (edges[u] % 2 == 0);
}
else {
w = (edges[u] % 2 == 0 && edges[v] % 2 == 0);
}

best = min(best, {w, i, j});
}
}
}

if (best[0] == 2) {
cout << -1 << '\n';
return;
}

A[best[1]][best[2]] = '1';
}

rep (i, 0, n) {
if (!usedRow[i]) {
dfsRow(i);
}
}

pii tmp(-1, -1);

rep (i, 0, n) {
rep (j, 0, m) {
if (A[i][j] == '1') {
if (tmp == mp(-1, -1)) {
tmp = mp(i, j);
}
else {
doRow(i, tmp.se, j);
doCol(tmp.se, tmp.fi, i);
tmp = mp(-1, -1);
}
}
}
}

assert(tmp == mp(-1, -1));
cout << sz(ans) << '\n';

if (E == 1) {
for (array<int, 4> it : ans) {
cout << "RC"[it[0]] << ' ' << it[1] << ' ' << it[2] << ' ' << it[3] << '\n';
}
}
}

int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int tt;
cin >> tt;

while (tt--) {
solve();
}

return 0;
}

Tester's Solution
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln '\n'
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
out<<"{ ";
forstl(x,c) out<<x<<" ";
out<<"}"; return out;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=2e5+5,MOD=1e9+7;
const ld EPS = 1e-9;

int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}

long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
char ret = getchar();
assert(ret != -1);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}
}
getchar();
return ret;
}

ll n, m, e;

int edges[LIM] = {0};
int sz[LIM] = {0};
bool used[LIM] = {0};
bool tried[LIM] = {0};

int find(int x){
}

void unite(int a, int b){
a = find(a);
b = find(b);
if(a == b){
edges[a]++;
return;
}
if(sz[a]<sz[b]) swap(a,b);
sz[a]+=sz[b];
edges[a] = edges[a] + edges[b] + 1;
}

bool vis[LIM];

vector<pair<p32,p32>> ans;
vector<p32> extra;

void solve(int node){
vis[node] = 1;
if(vis[r.fi]) continue;
solve(r.fi);
}
queue<pair<int, int>> up, down;
if(used[r.se]) continue;
if(!tried[r.se]){
up.push(r);
tried[r.se] = 1;
continue;
}
down.push(r);
}
while(down.size() >= 2){
auto t1 = down.front();
down.pop();
auto t2 = down.front();
down.pop();
used[t1.se] = 1;
used[t2.se] = 1;
ans.pb(mp(mp(node, t1.fi), mp(node, t2.fi)));
}
if(down.size() == 1 && up.size() > 0){
auto t1 = down.front();
down.pop();
auto t2 = up.front();
up.pop();
used[t1.se] = 1;
used[t2.se] = 1;
ans.pb(mp(mp(node, t1.fi), mp(node, t2.fi)));
}
while(up.size() >= 2){
auto t1 = up.front();
up.pop();
auto t2 = up.front();
up.pop();
used[t1.se] = 1;
used[t2.se] = 1;
ans.pb(mp(mp(node, t1.fi), mp(node, t2.fi)));
}
if(down.size() == 1){
auto t1 = down.front();
down.pop();
used[t1.se] = 1;
extra.pb(mp(node, t1.fi));
}
}

void merge_two(p32 a, p32 b){
if(a.fi > a.se) swap(a.fi, a.se);
if(b.fi > b.se) swap(b.fi, b.se);
// assert(a.se >= n);
// assert(b.se >= n);
p32 mid = mp(a.fi, b.se);
ans.pb(mp(a, mid));
ans.pb(mp(mid, b));
}

void print_op(p32 a, p32 b){
if(a.fi > a.se) swap(a.fi, a.se);
if(b.fi > b.se) swap(b.fi, b.se);

if(a.fi == b.fi){
cout<<"R "<<a.fi+1<<" "<<a.se-n+1<<" "<<b.se-n+1<<ln;
}
else{
cout<<"C "<<a.se-n+1<<" "<<a.fi+1<<" "<<b.fi+1<<ln;
}
}

int main(){
fastio;

ll sum_mn = 0;

forsn(quer,1,tests+1){
extra.clear();
ans.clear();
assert(n * m <= 200'000);
sum_mn += m * n;

int a[n][m];
int b[n][m];

forn(i,n){
forn(j,m){
char c;
if(j < m-1) c = readChar();
if(c == '0') a[i][j] = 0;
else if(c == '1') a[i][j] = 1;
}
}
forn(i,n){
forn(j,m){
char c;
if(j < m-1) c = readChar();
if(c == '0') b[i][j] = 0;
else if(c == '1') b[i][j] = 1;
else b[i][j] = -1;
}
}

// dsu of size n+m
forn(i,n+m){
sz[i] = 1;
edges[i] = 0;
vis[i] = 0;
}
forn(i,n*m){
used[i] = 0;
tried[i] = 0;
}

bool p = 0;
int chg = 0;
int num_edges = 0;
forn(i,n){
forn(j,m){
if(a[i][j] == b[i][j]) continue;
if(b[i][j] == -1){
p = 1;
continue;
}
// need to flip
chg++;
num_edges++;
unite(i, j+n);
}
}
// cout<<"OK"<<endl;
// ll tot_op = 0;
set<int> par;
forn(i,n+m) par.insert(find(i));

if(num_edges % 2 == 1){
int need = 1;
forn(i,n){
if(need == 0) break;
forn(j,m){
if(need == 0) break;
if(b[i][j] == -1){
if(edges[find(i)] % 2 == 1){
unite(i, j+n);
num_edges++;
need = 0;
}
else if(edges[find(n+j)] % 2 == 1){
unite(i, j+n);
num_edges++;
need = 0;
}
}
}
}
// cout<<"OK"<<endl;
// tot_op += need;
if(need){
p32 val = {-1,-1};
forn(i,n){
forn(j,m){
if(b[i][j] == -1){
val = mp(i,n+j);
}
}
}
if(val.fi != -1) extra.pb(val);
}
}

if((chg%2 == 1) && p == 0){
cout<<-1<<ln;
continue;
}

forstl(r,par){
if(sz[r] <= 1) continue;
// ans += (edges[r] + 1) / 2;
solve(r);
}

// cerr<<ans.size()<<ln;
// cerr<<extra.size()<<ln;

// if(extra.size()%2 == 1){
// 	cerr<<n<<" "<<m<<" "<<e<<endl;
// }

// assert(extra.size() % 2 == 0);
forn(i,extra.size()){
auto t1 = extra[i];
auto t2 = extra[i+1];
merge_two(t1,t2);
i++;
}
// cout<<ans<<ln;
cout<<ans.size()<<ln;
if(e == 1){
forstl(r, ans){
print_op(r.fi, r.se);
}
}

}

assert(sum_mn <= 200'000);
assert(getchar()==EOF);

return 0;
}

3 Likes

Everything else is fine (and also trivial) except the main part - That DFS algorithm which guarantees [e/2] paths in a connected component. I went into codeforces’s tutorial linked here. Still the algorithm is not clear at all. Can you explain it in more detail ?

@dotaveterans - I was reading your solution too. Still the algorithm is not very clear. Can you explain your solution ?

https://www.codechef.com/viewsolution/44742612

Thanks.

you could instead make the undirected graph into a directed graph where each vertex has even indegree.

3 Likes

So the reduced problem is -
Given a connected undirected graph with even number of edges, find a pairing of edges, such that in each pair, the edges share a node, and each edge is present in exactly 1 edge-pair. Note that in this problem, the graph is bipartite, but it doesn’t matter for the solution.

To do this, first take an arbitrary maximal edge-pairing. Let’s label all the edges that are part of a pairing as ‘P’ and others as ‘U’. Our goal is to make all edges as ‘P’.
First thing to note is that, all ‘U’ edges will be disconnected (otherwise your edge-pairing is not maximal).
The next step involves trying to modify the edge-pairings so that we can add at-least 1 more edge-pair.
To do this, consider a path like
U - P - P - P - U.

We can always find such a path, because

1. The component is connected.
2. There are even number of ‘U’ edges.
3. The edge pairings are maximal.

Then we try to restructure the current edge-pairings to include both of these ‘U’ edges.
If you look at the start of the above path, we can take the first ‘U’ and merge it with the ‘P’. However, to do this merge, you first need to unpair the ‘P’.
This is where there are a few cases.
If the other-half of ‘P’ is also in the path, i.e. the next ‘P’, we can simply pair them up, and now the path looks like U - P - P - U.
Otherwise, if the other-half of ‘P’ is outside this path, we can merge the ‘U’ with the first ‘P’, and the other-half of ‘P’ will now become the start of the path.
In both cases, the length of the path between the 'U’s reduces by at-least 1, while keeping the number of edge-pairings the same.
In the end, the path will look like U-U, which means we can simply pair these 2 edges, and this increases the number of edge-pairings by 1.
Repeat this process until there are no more ‘U’ edges in a component.

As you can probably tell, I’m very bad at explaining stuff. Lmk if something is unclear.

3 Likes

Hi there,

The main idea is to keep the following invariant (or whatever it is called):

If there is an unmatched edge in the subtree of vertex v, this edge should be equal to the parent edge of v in the DFS tree.

Suppose you are currently in the vertex v. First of all, recurse to your children and let them do their work. Now, take all unmatched edges connected to v and keep greedily pairing them off. If their number is even, everything is OK. Otherwise, pair everything except the parent edge. That’s basically it.

I also like the idea of @dotaveterans written above, never thought about it in this way.

1 Like

@dotaveterans , your explanation was good.

I was trying to solve this problem in another way , in my approach , i constructed the graph as follows

• Matrix elements which are different in A and B as vertices and
• Edge between two vertices exists when they are in same row or same column ( so we can use single operation on this elements ).

Now the problem was redefined as follows, Find the partition of this graph into single edges and single vertices such that every vertex appears exaclty once and the total number of edges and vertices is minimized.

Update

I was not able to solve this problem , but from what i understand from the editorial , now we can solve the above problem by constructing the new eqivalent graph and finding the optimal edge pairing of length two , correct ?? I am pretty sure , we can solve the above problem like this.

• I realized we can not construct the equivalent graph for any arbitrary graph.

If anyone knows any algorithm to solve the above problem , please do share it.