PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Cakewalk
PREREQUISITES
None
PROBLEM
Given a matrix with N rows and M columns, each cell containing either 0 or 1. We should perform the following operation until the size of the grid becomes 1 \times 1:
- Suppose the present size of the grid is x \times y.
- Choose one of the x-1 horizontal lines or y-1 vertical lines crossing the grid.
- Fold the grid along this line. For each pair of cells that overlap after this folding, replace them with a single cell such that the value in this cell is the XOR of the values in the two overlapping cells. Thus, we obtain a new grid.
Determine whether there is a sequence of folds such that in the final 1 \times 1 grid, the only cell contains 1.
QUICK EXPLANATION
The value in the final cell is the XOR of all values in the matrix.
EXPLANATION
We have a matrix, and we need to perform the operation until the grid becomes a single cell
Observation
The XOR of the whole matrix is the XOR of values of all cells in the matrix.
Claim: The operation does not alter the bitwise XOR of the matrix. i.e. the XOR of the grid before and after the operation remains the same.
Proof: The cells, where two cells overlap due to operation store the XOR of both cells. Hence, that one cell contributes the same bitwise XOR as the two cells before operation. Hence, the XOR of whole grid remains same.
Implementation
Since the XOR of grid remains same, we know that the XOR of grid after all operations shall be same as XOR of initial grid. So if that XOR is zero, it is impossible to make XOR of grid 1. Otherwise it is possible.
Hence, just compute XOR of values of whole grid, and compare with 1 to determine whether it is possible or not.
TIME COMPLEXITY
The time complexity is O(N*M) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxn = 1e5, maxm = 1e5, maxnm = 1e5, maxtnm = 1e6;
int main()
{
int t, n, m;
cin >> t;
while(t--){
cin >> n >> m;
assert(n * m <= maxnm);
string s;
int cnt = 0;
for(int i = 0; i < n; i++){
cin >> s;
for(int j = 0; j < m; j++){
assert(s[j] >= '0' && s[j] <= '1');
cnt += s[j] - '0';
}
}
string ans = (cnt & 1) ? "YeS" : "No";
cout << ans << endl;
}
}
Tester's Solution
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
using namespace std;
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;
}
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,' ');
}
int main(){
int T = readIntLn(1, 20000);
int sumNM = 0;
while(T-->0){
int N = readIntSp(1, 100000), M = readIntLn(1, 100000);
assert(N*(long long int)M <= 100000);
sumNM += N*M;
assert(sumNM <= 1000000);
int ans = 0;
for(int i = 0; i< N; i++){
string s = readStringLn(M, M);
for(int j = 0; j< M; j++){
assert(s[j] == '0' || s[j] == '1');
ans ^= s[j]-'0';
}
}
if(ans == 1)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
assert(getchar()==-1);
cerr<<"SUCCESS\n";
}
Feel free to share your approach. Suggestions are welcomed as always. 