XORFOLD - Editorial

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. :slight_smile:

2 Likes

As per the Conditions given check the string. Take a result variable and initialise with zero If the character is ‘0’ then xor 0 with the result else xor 1 with the result. If the end result is 1 then print yes else no. And yes do it for all the input characters.

1 Like

Hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

2 Likes

can you please elaborate or just give an example so that i can understand please

1 Like

it is quite easy. It just says that if last bit is 0 then answer is NO and if last bit is 1 then answer is 1.

1 Like

Can anybody tell me what is the problem in this code.
On execution it is showing the TLE.
But on changing the type of the variable arr from int to char it is showing right answer .Pls explain !

#include
using namespace std;

int main()
{
int t,count=0,m,n,i,j;
cin>>t;
while (t–)
{
count=0;
cin>>n>>m;
int arr;
for(i=0;i<n*m;i++)
{

              cin>>arr;
              if(arr==1)
              count++;
              
       }
              if(count%2==0)
              cout<<"NO\n";
              else
              cout<<"YES\n";
              
       }
     	return 0;  
}

@kalashjain , The problem here is that the input matrix contains characters and you are accepting an integer form stdin every time. Just accept a char and compare it with ‘1’ as per the logic of your code.

2 Likes