PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Temirlan Baibolov
Tester: Shubham Anand Jain, Aryan Choudhary
Editorialist: Temirlan Baibolov
DIFFICULTY:
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 read(){
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;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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 readChar(int l, int r){
char ret = getchar();
assert(ret != -1);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
char readChar(){
return readChar(1, 1);
}
char readCharLn(){
char ret = readChar();
getchar();
return ret;
}
ll n, m, e;
int link[LIM] = {0};
int edges[LIM] = {0};
int sz[LIM] = {0};
bool used[LIM] = {0};
bool tried[LIM] = {0};
int find(int x){
if(x == link[x]) return x;
return link[x] = find(link[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];
link[b] = a;
edges[a] = edges[a] + edges[b] + 1;
}
vp32 adj[LIM];
bool vis[LIM];
vector<pair<p32,p32>> ans;
vector<p32> extra;
void solve(int node){
vis[node] = 1;
forstl(r, adj[node]){
if(vis[r.fi]) continue;
solve(r.fi);
}
queue<pair<int, int>> up, down;
forstl(r, adj[node]){
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;
int tests = readIntLn(1, 100);
ll sum_mn = 0;
forsn(quer,1,tests+1){
extra.clear();
ans.clear();
n = readIntSp(1, 200'000);
m = readIntSp(1, 200'000);
e = readIntLn(0, 1);
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();
else c = readCharLn();
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();
else c = readCharLn();
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){
link[i] = i;
sz[i] = 1;
edges[i] = 0;
vis[i] = 0;
adj[i].clear();
}
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++;
adj[i].pb(mp(j+n, num_edges));
adj[j+n].pb(mp(i, num_edges));
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);
adj[i].pb(mp(j+n, num_edges));
adj[j+n].pb(mp(i, num_edges));
num_edges++;
need = 0;
}
else if(edges[find(n+j)] % 2 == 1){
unite(i, j+n);
adj[i].pb(mp(j+n, num_edges));
adj[j+n].pb(mp(i, num_edges));
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;
}