Question : “SPOJ.com - Problem XORX”
Can anyone help me in this question , I don’t know how to solve tried to figure out but no sense , please help @galencolin @everule1 @udayan14 @aryan12 @carre
first XOR all numbers with x and then find the maxium subarray XOR as explained here
[EDIT] nop, I simplified it and that’s not right, let me think it a little bit
Bro this is different I think , I know it is solved by Trie.
UPD : Yeah please think , and explain to me -
I found one solution if u explain from this I will be very thankful -
before reading that I think that somethiing can be done mantaining 2 tries, one of them to get the odd-lenght subarrays and other to even-lenght
How ? elaborate more.
they both do almost the same, in the get function of the tree they xor the current bit with the bit of the value of X, and that’s it, it’s fine and simple
Not able to understand that guy code , that’s why I ask here .
Have you read the solution I linked? It’s almost the same, the only difference is that when you query the tree you XOR with x value also
The query should do the following for each bit
if current_prefix_bit ^ X_bit ==1 got to 0 branch of tree
else go to 1 branch of tree
Yeah I know that solution u linked (gfg) , in that we find the max xor of subarray ending at i'th index and find maximum value from each i , but how this is applied here I don’t know .
One more : “added xorx.cpp by ashukeshri · Pull Request #7 · t3nsor/SPOJ · GitHub”
Here he just find the answer by passing the value (pre^x) into query and find max val [ just like your gfg link ] , but after that he use this loop why -?
for(ll i=id;i>=0;i--)
{
xo=(xo^arr[i]);
if((xo^m)==ans)
{
return xo;
}
the difference here is that he queries before inserting current prefix so at the end he needs to xor with the current prefix
// Problem: x-Xor It!
// Contest: SPOJ - Classical
// URL: https://www.spoj.com/problems/XORX/
// Memory Limit: 1536 MB
// Time Limit: 1399 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define PB push_back
#define INF INT_MAX
#define RINF INT_MIN
#define MOD 1000000007
#define watch(x) cout << (#x) << " is " << (x) << endl
#define watch_vector(v) FOR(i,0,(v).size(),1) cout<<v[i]<<" ";cout<<endl;
#define fill_vector(v) FOR(i,0,(v).size(),1) cin>>v[i];
#define setprec(ans) cout<<fixed<<std::setprecision(9)<<ans<<endl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<string> VS;
typedef long long int ll;
#define sort_vector(v) sort((v).begin(),(v).end());
struct TrieNode{
TrieNode *right, *left;
};
TrieNode* constructNode(){
TrieNode* root = new TrieNode;
root->right = NULL;
root->left = NULL;
return root;
}
void insert(int x, TrieNode* root){
for(int i=31;i>=0;i--){
int bit = (x>>i)&1;
if(bit){
if(!root->right) root->right = constructNode();
root=root->right;
}
else{
if(!root->left) root->left = constructNode();
root=root->left;
}
}
}
pair<int, int> search(int x, int k, TrieNode* root){
//maximize wrt x
//k is kind of xor of subarray from start to current index
int sum=0, max_xor=0;
for(int i=31;i>=0 && root != NULL;i--){
int bitx = (x>>i)&1;
int bitk = (k>>i)&1;
if(bitx == 1 && bitk == 1){
//1 is good
if(root->right) root = root->right, max_xor += (1<<i);
else if(root->left) root = root->left, sum += (1<<i);
else root = root->left;
}
else if(bitx == 1 && bitk == 0){
//0 is good
if(root->left) root = root->left, max_xor += (1<<i);
else if(root->right) root = root->right, sum+=(1<<i);
else root = root->right;
}
else if(bitx == 0 && bitk == 1){
//0 is good
if(root->left) root = root->left, sum+=(1<<i), max_xor += (1<<i);
else root = root->right;
}
else if(bitx == 0 && bitk == 0){
//1 is good
if(root->right) root=root->right, sum+=(1<<i), max_xor += (1<<i);
else root = root->left;
}
}
return {sum, max_xor};
}
int solve(){
int n, x;
cin>>n>>x;
VI a(n);
for(int i=0;i<n;i++) cin>>a[i];
TrieNode *dummy = constructNode();
insert(0, dummy);
int ref = 0;
int sum=-1, max_xor=-1;
for(int i=0;i<n;i++){
ref^=a[i];
pair<int, int> p1 = search(x, ref, dummy);
if(p1.second > max_xor) sum = p1.first, max_xor = p1.second;
insert(ref, dummy);
}
return sum;
}
int main()
{
ios_base:: sync_with_stdio(false); cin.tie(0);
// #ifndef ONLINE_JUDGE
// //for getting input from input.txt
// freopen("input.txt","r", stdin);
// //for writing output to output.txt
// freopen("output.txt","w", stdout);
// #endif
/*
Reminder: Always store sum in ll variable.
*/
int t;
cin>>t;
while(t--){
cout<<solve()<<endl;
}
return 0;
}