PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh
DIFFICULTY:
2963
PREREQUISITES:
PROBLEM:
You are given an array A of length N.
You can do the following operation on the array atmost once:
- Choose any non-negative integer X and a subarray [L, R] (1 \leq L \leq R \leq N) and update A_i = A_i \& X for all L \leq i \leq R. Here \& denotes bitwise AND operation.
Find the maximum bitwise XOR of all the elements of the updated array you can achieve.
EXPLANATION:
Let D be inital bitwise XOR of all the elements of the array A. It can be shown that all the bits in the binary representation of D set to 1 will always be set to 1 in the final answer.
Proof that the bits in D set to 1 will always be set to 1 in the final answer
Let us say that the i^{th} bit is set to 1 in D but it is set to 0 in the final answer.
\implies The operation is done exactly once choosing an integer X such that i^{th} bit in X was 0. (as (i^{th} bit)\: \&\: 1=i^{th} bit and this does not change the result).
Set i^{th} bit to 1 in X, this will set the i^{th} bit to 1 in the final answer as the count of i^{th} bits set to 1 won’t change due to the operation.
This means we need to focus on the bits set to 0 in D and we want to change the parity of count of these to odd so that these can be included in the final answer.
Observation
\& operation cannot set a bit to 1 from 0 it can only set it to 0 from 1 or leave it unchanged
We need to apply the operation on a subarray in a way such that \sum_{i=0}^{30} 2^{i} , where i represents the bits which have an odd count in the subarray, is maximum i.e. the bitwise XOR of the subarray is maximum.
This problem is now deduced to a simpler problem : Find the maximum bitwise XOR of a subarray of A where we are concerned only with bits set to 0 in D.
Let P_i represent the bitwise XOR of elements in the prefix of length i of the array A.Take bitwise\: OR of each element of P with D to remove the effect of the bits set to 1 in D.
The bitwise XOR of the subarray [L, R] now is same as taking the XOR of P_R and P_{L-1}.
We need to find max ( max (XOR of two elements of the array P ), max(P_i)). Let this value be Max.
Finding the maximum bitwiseXOR of two numbers in an array is a standard problem which can easily be solved using a trie data structure in O(Nlog(2^{30})).
Maximum XOR of Two Numbers in an Array
Thus, the final answer is (D \:|\: Max)
For details of implementation please refer to the attached solutions.
TIME COMPLEXITY:
O(Nlog(max(A_i))) for each test case.
SOLUTION:
Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=6000023;
bool vis[N];
vector <int> adj[N];
int child[N][3];
int nxt=1;
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;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
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,' ');
}
void construct_trie(vector <string> &v,int n)
{
for(int i=0;i<n;i++)
{
string s=v[i];
int node=0;
for(auto ch:s)
{
if(child[node][ch-'0']==0)
child[node][ch-'0']=nxt++;
node=child[node][ch-'0'];
}
}
}
vector <string> s;
int MAX=((1<<30)-1);
ll sumN=0;
void solve()
{
ll n=readInt(2,200000,'\n');
sumN+=n;
assert(sumN<=200000);
int A[n+1]={0};
ll overall=0;
for(int i=1;i<=n;i++)
{
if(i==n)
A[i]=readInt(0,MAX,'\n');
else
A[i]=readInt(0,MAX,' ');
overall^=A[i];
}
ll out=overall;
ll rem=((1<<30)-1);
rem^=overall;
for(int i=1;i<=n;i++)
A[i]=(A[i]&rem);
int B[n+1]={0};
ll ans=0;
s.clear();
for(int i=0;i<=nxt;i++)
{
child[i][0]=0;
child[i][1]=0;
}
nxt=1;
vector <string> s;
string tmp="";
for(int i=0;i<31;i++)
tmp+='0';
s.pb(tmp);
for(int i=1;i<=n;i++)
{
B[i]=(B[i-1]^A[i]);
ll temp=B[i];
string fun="";
for(int j=0;j<31;j++)
{
fun=(char)('0'+temp%2)+fun;
temp/=2;
}
s.pb(fun);
}
construct_trie(s,n+1);
for(int i=1;i<=n;i++)
{
string fun="";
ll temp=B[i];
for(int j=0;j<31;j++)
{
fun=(char)('0'+temp%2)+fun;
temp/=2;
}
ll maxi=0;
int curr=0;
int start=0;
for(int j=30;j>=0;j--)
{
if(child[start][(int)('1'-fun[curr])]!=0)
{
maxi+=(1<<j);
start=child[start]['1'-fun[curr++]];
}
else
{
start=child[start][fun[curr++]-'0'];
}
}
ans=max(ans,maxi);
}
out|=ans;
cout<<out<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,10000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester-1's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
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) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
I m=(1<<30)-1;
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
t=readInt(1,10000,'\n');
I ns=0;
while(t--){
I n;
n=readInt(2,200000,'\n');
ns+=n;
assert(ns<=200000);
I a[n];
I tot=0;
asc(i,0,n){
if(i!=n-1){
a[i]=readInt(0,m,' ');
}else{
a[i]=readInt(0,m,'\n');
}
tot^=a[i];
}
asc(i,0,n){
a[i]&=(m^tot);
}
asc(i,1,n){
a[i]^=a[i-1];
}
I mx = 0;
I ms = 0;
OS(I) s;
dsc(i,0,30){
I k=(1<<i);
ms|=k;
asc(j,0,n){
s.insert(a[j]&ms);
}
I temp=(mx|k);
forw(it,s){
if(s.find(temp^(*it))!=s.end()){
mx=temp;
break;
}
}
clr(s);
}
I ans=(mx|tot);
cout<<ans<<"\n";
}
return 0;
}
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
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;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
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,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;
using ii = pair<ll,ll>;
struct Node{
Node* l = NULL;
Node* r = NULL;
};
typedef struct Node node;
struct trie{
node* root = new node();
void insert(int val){
node *curr = root;
rev(i,29){
if(val&(1<<i)){
if(curr->r==NULL) curr->r = new node();
curr = curr->r;
}
else{
if(curr->l==NULL) curr->l = new node();
curr = curr->l;
}
}
}
int max_xor(int val){
int ans = 0;
node* curr = root;
rev(i,29){
if(val&(1<<i)){
if(curr->l){
ans += (1<<i);
curr = curr->l;
}
else if(curr->r) curr = curr->r;
}
else{
if(curr->r){
ans += (1<<i);
curr = curr->r;
}
else if(curr->l) curr = curr->l;
}
}
return ans;
}
};
void solve(){
int n = readIntLn(2,2e5);
sum_n+=n;
vector<int> a(n);
int xr = 0;
rep(i,n){
if(i<n-1) a[i] = readIntSp(0,(1<<30)-1);
else a[i] = readIntLn(0, (1<<30)-1);
xr^=a[i];
if(i) a[i]^=a[i-1];
}
int z = (1<<30)-1;
z = z^xr;
struct trie t;
int mx = 0;
rep(i,n){
a[i]&=z;
mx = max(mx, t.max_xor(a[i]));
t.insert(a[i]);
}
cout<<(xr|mx)<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,1e4);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
assert(sum_n<=2e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class Node
{
public:
Node *one;
Node *zero;
};
class trie
{
Node *root;
public:
trie() { root = new Node(); }
void insert(int n)
{
Node *temp = root;
for (int i = 30; i >= 0; i--)
{
int bit = (n >> i) & 1;
if (bit == 0)
{
if (temp->zero == NULL)
{
temp->zero = new Node();
}
temp = temp->zero;
}
else
{
if (temp->one == NULL)
{
temp->one = new Node();
}
temp = temp->one;
}
}
}
int max_xor_helper(int value)
{
Node *temp = root;
int current_ans = 0;
for (int i = 30; i >= 0; i--)
{
int bit = (value >> i) & 1;
if (bit == 0)
{
if (temp->one)
{
temp = temp->one;
current_ans += (1 << i);
}
else
{
temp = temp->zero;
}
}
else
{
if (temp->zero)
{
temp = temp->zero;
current_ans += (1 << i);
}
else
{
temp = temp->one;
}
}
}
return current_ans;
}
int max_xor(vll arr, int n)
{
int max_val = 0;
for (int i = 0; i < n; i++)
{
max_val = max(max_xor_helper(arr[i]), max_val);
insert(arr[i]);
}
return max_val;
}
};
void sol(void)
{
int n, ans = 0;
cin >> n;
vll v(n), p(n);
for (int i = 0; i < n; i++)
cin >> v[i], ans ^= v[i];
p[0] = v[0];
for (int i = 1; i < n; i++)
p[i] = p[i-1] ^ v[i];
for (int i = 0; i < n; i++)
p[i] |= ans;
trie T;
T.insert(ans);
cout << ((ans) ^ (T.max_xor(p, n))) << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}