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.
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
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–;
}
}
}