MATXOR - Editorial

Can anyone tell what is wrong with this approach ? https://www.codechef.com/submit/MATXOR

if(n==m) matrix will be symmetric so XOR of all elements except diagonal will become 0 and answer will be simply the xor of diagonal elements
if(n!=m) except the elements a[0][0] and a[n-1][m-1] all elements will be repeated twice so XOR=0 so answer should be the XOR of a[0][0] and a[n-1][m-1].

corner cases will be n==1 and m==1

The link your shared doesn’t have any code. If you want to share your code, use pastebin.

  • 1 \leq N,M \leq 2⋅10^6
  • the sum of N over all test cases does not exceed 2\cdot10^6\implies \sum\limits_{t}N <= 2 \cdot10^6
  • the sum of M over all test cases does not exceed 2\cdot10^6\implies \sum\limits_{t}M <= 2 \cdot10^6

One way to view this, for consideration of the worst case for N and M, is to consider T = 1 and devise your algorithm.
Now we can satisfy all the four constraints, and understand that we need a linear time solution.

updated now

It still doesn’t work. Use pastebin, or paste your code here, in between a pair of 3 back ticks (`).

int l = max(1, x - m), r = min(n, x - 1);
if(r >= l && (r - l + 1) % 2 == 1)
please tell what does this line meant

My code with very easy logic please refer it
Algorithm

  1. Traverse loop from 2 to m+n
  2. check if number of daigonal of number s present odd number of times then push i+k in vector
    3.traverse vector and take xor of all element in vector

example
m=4 n=3 k=4;
then 2d representation look like
2 3 4
3 4 5
4 5 6
5 6 7

like if we traverse from 2 to 7
for 2 it is present odd time push i+k in vector
for 3 it is present even time so it cant be pushed

here is my code do upvote my answer guys if you find it helpful thank you

#include<bits/stdc++.h>
#define REP(i,n) for (int i = 1; i <= n; i++)
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define vi vector
#define vii vector
#define ll long long int
#define INF 1000000000
#define endl ‘\n’
const double PI = 3.141592653589793238460;
typedef std::complex Complex;
typedef std::valarray CArray;
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test;
cin>>test;
while(test–)
{
int n,m,k;
cin>>n>>m>>k;
long long int ans = 0;
int row = 1;
vector array;
for(int i = 2;i<=n+m;i++)
{

			 		if(i-row>m)
			 		{
			 			row++;
					}
					int c = i-row;
					int d = c;
					if(d+row>n)
					{
						d = n-row+1;
					}
					if(d&1)
					{
						array.push_back(i+k);
					}
				}
			   	long long int A = 0;
				if(array.size()>1)
				{
					
						for(int i = 0 ;i<array.size();i++)
						{
							A = A^array[i];
						}
				}
				cout<<A<<endl;

 }

}

I also did it in the same way! :uwu:

See this solution for O(1) approach.
You can find xor of a range in O(1) (link 1) & xor of alternate elem of a range in O(1) (link 2).
Now consider rows pairwise (eg 1 & 2 ; 3 & 4 and so on). You can see that by xoring a pair (eg: 1 & 2) you will get (A[1][1] ^ A[2][m]) i.e for each pair of rows it boils down to xor of just 2 elem. Okay 1 dimension reduced i.e O(n) complexity. 1 more to go.
If you see first value of result of all such pairs they form a sequence with a difference of 2. Similarly second value of result of all such pairs form a sequence with a difference of 2. Both of these can be evaluated in O(1) using link 2.
Edge case: When n is odd, one row will be left after considering rows pairwise which we can handle separately in O(1) using link 1.

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while (t–)
{
/* code /
int N,M,K;
cin>>N>>M>>K;
int matrix[N][M];
int xor_matrix=0;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
matrix[i][j]=i+j+K;
xor_matrix^=
(*(matrix+i)+j);
}
}
cout<<xor_matrix<<"\n";
}
return 0;
}
Can someone tell me why is this code giving runtime error for the second test case.(any help would be helpful)

Your matrix is N x M and u r accessing values out of matrix. I hope, it will help u to get rid of RE

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define llv vector
#define line cout<<"\n"
#define MOD 1000000007
#define forloop for(i=0;i<n;i++)
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0);

int main() {
ll t;
cin>>t;
while(t–)
{
int n,m,k;
int a=0,i;
cin>>n>>m>>k;
//for even

    for(i=1;i<n;i+=2)  // at most n times 
        a=a^(i+1+k);
        
    for(i=2;i<=n;i+=2)
        a=a^(i+m+k);
   
   //if n is odd then do xor for last row also 
   
   if(n%2 !=0)
   {
       for(i=1;i<=m;i++) // at most m times 
       a=a^(n+i+k);
   }
    cout<<a<<"\n";
}

}

y

awesome

why it is giving wa for my code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m,k,sum=0;
cin>>n>>m>>k;
sum=(k+2)^(k+m+n);
for(int i=2;i<=n;i++)
{
if(k+i+1<=k+m+1)
{
if(i%2==1)
{
sum=(sum)^(k+i+1);
}
}
else
{
int p=(k+i+1)-(k+m+1);
int c=i-§;
if(c%2==1)
{
sum=sum^(k+i+1);
}
}
}
int z=(k+m+n)-2;
while(z>k+n+1)
{
sum=sum^z;
z=z-2;
}
cout<<sum<<endl;
}
}

int data type is not feasible for Bitwise operations. Use Long Long int.

Great Editorial.
Thanks for such a good editorial.
Thanks.

The answer is coming out to be correct but its taking quite a long time to finish. Please can someone tell me how to use less for loops and solve this.

num = int(input())
list1 = []
while num > 0:
n, m, k = map(int, input().split())
for i in range(1, n+1):
for j in range(1, m+1):
list1.append(i+j+k)
num = num - 1

xor = list1[0]
for i in range(1, len(list1)):
xor = xor ^ list1[i]
print(xor)

The time complexity of your code is O(M \times N), whereas the desired time complexity is
O(M + N)

Can anyone please help me why my code for this problem is wrong:

Same problem also with me.

Why i am getting TLE? How can I optimise this code:

import java.util.;
import java.lang.
;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
long T;
Scanner input=new Scanner(System.in);
T=input.nextInt();
while(T>0)
{
long N,M,K;
long ans=0;
N=input.nextInt();
M=input.nextInt();
K=input.nextInt();
for(long i=1;i<=N;i++)
{ long temp=((i<=M)?i:M);
if(temp%2==1)
ans=ans^(K+i+1);
}
for(long j=2;j<=M;j++)
{ long t=((N<=M-j+1)?N:M-j+1);
if(t%2==1)
ans=ans^(K+N+j);
}
System.out.println(ans);
T–;

	}
	
}

}