MATXOR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Prashant Shishodia
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

XOR-properties, Difference Array

PROBLEM

You are given a matrix A of dimensions N \times M which is defined as A_{i, j} = K + i + j. Your task is to find the bitwise xor of all elements of the matrix of given dimensions.

QUICK EXPLANATION

Each unique number in the matrix will contribute either itself or a 0 to the resultant XOR. Find the number of appearances (say Y) for each unique number populating the matrix. If Y for the unique number X present in the matrix is even, it will contribute (X⊕X) XOR’d with itself Y/2 times, resulting in a 0. Whereas if Y is odd, the number itself will be contributed because (X⊕X) will be XOR’d with itself (Y-1)/2 times, which in turn will be XOR’d with the remaining X, thus contributing 0⊕X.

EXPLANATION

We have a matrix A of dimensions N \times M where each element of the matrix is defined as A_{i, j} = K + i + j. We need to find the bitwise XOR of all elements of the matrix.

Let’s forget K for a moment.

The first observation that we can make is that the number of distinct values present in the matrix will lie in a range [2, N+M] such that every number of this range is present in the matrix.

Proof

Suppose we have an integer S that is the sum of two integers i and j, where i and j lie in a given range. Then, we can always obtain integers S-1 and S+1 incrementing and decrementing either i or j respectively.

Since i and j in context of the given question (row and column indices respectively), lie in a the continuous range of 1 to N, hence for every i\gt 1, i\lt n, j\gt 1 and j\lt m, (i-1, i+1, j-1, j+1) will also lie in the given range, implying that S+1 and S-1 are obtainable. If we are unable to increment i and j, then the sum corresponding to these row and column designations would be the maximum possible for the given range of i and j thus making S+1 unobtainable. Whereas if we are unable to decrement i and j, we would obtain minimum possible S and would not be able to obtain S-1.

This means the S values populating the matrix will lie between 1+1 (corresponding to i=1, j=1 which can’t be decremented further) and N+M (corresponding to i=N, j=M which can’t be incremented further).

Now we are left with finding the number of cells in the matrix such that i+j=X, for all X in the range [2, N+M].

For every row i, our j will vary from 1 to M. The minimum and maximum value present in row i will be i+1 and i+M respectively. Also all the values of range [i+1, i+M] will be present in row i as proved above.

As each row represents a contiguous range [i+1, i+M], we would use the difference array (representing the values in the matrix 2 to M+N) to increment the count of all numbers in a range. We would traverse each row and increment the numbers in the range it represents by 1.

On dissolving the difference array we obtain the number of times (say C) each of the numbers from 2 to N+M are present in the matrix. Now a number from the matrix will contribute to the resultant XOR only if it is present odd number of times i.e. only numbers with odd corresponding C values will contribute to the final XOR. Since if we xor a number with itself even number of times, then the resultant is 0. As

X \oplus X = 0

Now for each element X of the range [2, N+M], if it is present an odd number of times, then we include (X+K) in the resultant XOR. Finally, we output the resultant XOR.

TIME COMPLEXITY:

O(N+M) per test case

SOLUTIONS:

Setter
#include <bits/stdc++.h>

using namespace std; 

int main(){
    ios_base::sync_with_stdio(0); 
    int t; cin>>t; 
    while(t--){
        int n, m, k; cin>>n>>m>>k; 

        int ans = 0; 
        for(int x = 2; x <= n + m; ++x){
            // i + j = x, 1 <= i <= n, 1 <= x - i <= m
            //  max(1, x - m) <= i <= min(n, x - 1)
            int l = max(1, x - m), r = min(n, x - 1); 
            if(r >= l && (r - l + 1) % 2 == 1)ans ^= (k + x); 
        }
        cout<<ans<<"\n"; 
    }
    return 0; 
}
Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define double long double
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
 
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 sum_n=0,sum_m=0;
void solve() {
	int n=readIntSp(1,1000000),m=readIntSp(1,1000000),k=readIntLn(1,1000'000'000);
	sum_n+=n;
	sum_m+=m;
	assert(sum_n<=1000000&&sum_m<=1000000);
	int ans=0;
	fr(i,2,n+m)
		if(min({i-1,n,m,n+m-i+1})&1)
			ans^=(k+i);
	cout<<ans<<endl;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=readIntLn(1,100000);
//	int t;
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
 
Editorialist
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve()
{
  int n,m,k;
  cin>>n>>m>>k;
 
  int diff_arr[n+m+5]={};
 
  for(int i=1;i<=n;i++)
  {
    int l=i+1;
    int r=i+m;
 
    diff_arr[l]++;
    diff_arr[r+1]--;
  }
 
  int ans=0;
 
  for(int i=2;i<=n+m;i++)
  {
    diff_arr[i]+=diff_arr[i-1];
 
    if(diff_arr[i]%2)
    {
      ans^=(k+i);
    }
  }
 
  cout<<ans<<"\n";
}
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
  {
    solve();
  }
 
return 0;
}
 
5 Likes

My solution without difference array: code

2 Likes

Solution without difference array.
O(n+m) time and O(1) auxiliary memory.

Approach: The sum of indicies can be in the range [2,m+n]. If a cell has a value z, the cell south-west of it will have the same value z, or in other words, the entire diagonal starting somewhere on the first row, or last column, will have the same value, and these will alternate odd and even. The diagonal starting at (1,1) will have just one occurence of the value (the fist cell itself). The diagonal starting at the next cell (1,2) will have two occurences. The diagonal starting at cell (n,m) will have one, the cell above it will have two, and so on. All the unique values the matrix can be obtained by just going through the boundary of the matrix.
Let x =min(m,n) and y = max(m,n).
Imagine traversing along the top and right boundary of the matrix. I divide these indices in three regions and process them individually.

  1. [1,x) - From first cell until minimum of rows or columns. We only need the ones with odd number of occurences.
  2. [x,y] - If x is odd, this region will have the same number of occurences everytime and we need to account for them all.
  3. (y,x+y] - Same as first region. Used a reverse loop for ease.
2 Likes
  • 1 ≤ T ≤ 10^5
  • 1 ≤ N,M ≤ 2⋅10^6

Time Limit: 0.5 s

Can anybody tell me how can we determine required Time Complexity ?
I messed up in this problem during contest, I tried/failed to find XOR of values in O(1) rather than O(n+m)
Thanks

How is this O(n+m) solution not giving TLE, isn’t it that T*(N+M) should < 10^8?

2 Likes

My solution in O(1) per test case

1 Like

Can you briefly explain your approach?

Same doubt

I later realised, that sum of N and M does not increases 210^6, so O(N+M) will be 410^6, over all test cases, so O(N+M) solution will work.

n^2 approach usually works when 2 sec time limit is given, but here we are given 0.5 seconds and linear solution with fast I/O usually take less than that.

https://www.codechef.com/viewsolution/44036841
easy approach

easy O(m+n) time and O(1) auxiliary memory solution
just take the elements which occurred odd number of times.

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

You can check it here .I have simply used the pattern

code

Check out my Easy to understand solution with explanation Solution Link

1 Like

Why this code is failing.
I checked if m==1 and n==1 then k;
else if m==1 or n==1 then loop 1,max(m,n) and ans^=(k+1+i)
else
cout<<(k+2)^(k+m+n);
https://www.codechef.com/viewsolution/44029182

A simple solution in Time Complexity of O(n).
Solution: 44001451 | CodeChef

Approach :-

  1. By observation, we can see that each row value starts at L = 1+i+k and ends at R = m+i+k , where i is the variable for loop on rows.
  2. Now, to calculate the XOR of first N natural numbers, refer this article Calculate XOR from 1 to n. - GeeksforGeeks .
  3. Now, if I calculate the XOR of (1 , R) and XOR of (1 , L - 1) using the above approach in O(1) and XOR them with each other, I get the XOR of (L,R). WHY ?
  4. Proof by example, say R = 10. L = 6. XOR of (1,10) will have all values from 1 to 10 and XOR of (1,6-1) will have all values from 1 to 5. If I XOR them with each other, I am actually XORing the range of (1,5) twice and (6,10) once and we know, X XOR X = 0 and 0 XOR Y = Y. So, Using this, I am able to calculate the XOR of each row in O(1).
  5. Using a variable and initializing it to 0. I can iterate through every row and XOR it with XOR of (L,R).
  6. Once the loop ends, our variable holds the XOR of the entire MATRIX.

I tried this using dynamic approach to make a xor in a sequence of initial(2+k) to last(m+n+k) then go row wise delete or alter the result of previous row from it
Solution is :Code

per test case your algo should take (N+M) time.

MyCode

testcases are running fine . I basically found the pattern that for a given n,m the pattern was something like 2 3 3 4 4 4 5 5 5 5 6 6 6 6 7 7 7 8 8 9 (for n+m = 3,3) so i took 2 pointers 1 at 2 and other at n+m and if cnt of the number in the pattern was odd took xor(since x xored k times is x if k is odd and is 0 if k is even and 0 xor num is num itself ) and stored in variable p. Testcases are running fine but WA on submission . Please help . Thanx in advance

Constraints

  • 1\le T\le 10^5
  • 1\le N, M\le 2.10^6
  • 1\le K\le 10^9
  • the sum of N over all test cases does not exceed 2⋅10^6
  • the sum of M over all test cases does not exceed 2⋅10^6

This was mentioned in Constraints. Since the sum of N and M are limited to 2.10^6, an O(M+N) solution would roughly take 4\times10^6 steps, inclusive of test cases. That’s how it is going to be.

  • the sum of N over all test cases does not exceed 2⋅10^6
  • the sum of M over all test cases does not exceed 2⋅10^6

This line is pretty much important. Ignoring this, most people don’t even attempt after seeing the constraints.