PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rainb0ysimp
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Familiarity with bitwise XOR
PROBLEM:
You’re given an array A.
The following move can be performed at most once:
- Pick an index 1 \leq i \leq N, and write A_i = 2^{k_1} + 2^{k_2} + 2^{k_3} + \ldots + 2^{k_m} for some m \gt 0 (the powers needn’t be distinct).
Then, delete A_i from the array and append all the 2^{k_j} to it.
Find the maximum possible bitwise XOR of the resulting array.
EXPLANATION:
Let’s fix i, the index we’re going to operate on.
Let X_i denote the bitwise XOR of the other N-1 elements.
X_i is easy to compute: it’s just (A_1\oplus A_2\oplus\ldots A_N)\oplus A_i, with the first term being a constant that only needs to be computed once.
Now that X_i is fixed, our task is to break A_i into powers of 2 such that the overall bitwise XOR is maximized.
As in most problems involving maximization (or minimization) of the result of bitwise operations, this can be done greedily from the highest bit to the lowest — this is because 2^0 + 2^1 + 2^2 + \ldots + 2^k \lt 2^{k+1}, so it’s always better to set a higher bit even at the cost of all lower bits.
So, we iterate over bits b from 60 down to 0; each time trying to decide whether it can be set in the resulting XOR or not.
That decision can be made as follows:
- If X_i has bit b set, we need to ensure that there are an even number of 2^b in the split; so that they all cancel out with each other and leave X_i alone.
- The easiest way to ensure this is to just have no occurrences of 2^b at all.
After all, you can always split a 2^b into two copies of 2^{b-1}.
- The easiest way to ensure this is to just have no occurrences of 2^b at all.
- If X_i doesn’t have bit b set, we’d like to set it ourselves, if possible.
That means having an odd number of 2^b copies.- Once again, the easiest way to ensure this is to keep exactly one copy of 2^b: all the remaining can be split into 2^{b-1} instead.
Note that since we’re going from higher bits to lower, pushing down to 2^{b-1} gives us more options for the future.
This “push downwards” idea can be implemented relatively simply by simply keeping a counter denoting the count of the current power of 2.
Let \text{ct} be this count, initially 0. Then, for each b,
- If A_i has bit b set, increase \text{ct} by 1.
- Now, if X_i has bit b set, we don’t want any 2^b, and want to make them all 2^{b-1}.
This can be represented by the transformation \text{ct} \to 2\cdot \text{ct}. - If X_i doesn’t have b set, we have two cases.
- If \text{ct} = 0, we can’t do anything, so just move on.
- Otherwise, one copy of 2^b remains, and everything else is pushed to 2^{b-1}.
That is, \text{ct} \to (2\cdot\text{ct})-2.
The only time this “keep for later” idea fails is for b = 0, in which case there isn’t any ‘later’.
So, here alone, we must use every copy of 2^0 we have - meaning the last bit will be decided by parity.
However, notice that any copies pushed down from higher bits don’t actually matter, since they’ll form an even number of copies!
TIME COMPLEXITY:
\mathcal{O}(60\cdot N) per testcase.
CODE:
Author's code (C++)
#include "bits/stdc++.h"
using namespace std;
#define int long long
int sum = 0;
void solve(){
int n;
cin >> n;
assert(n >= 1 and n <= 2e5);
int a[n], x = 0;
for (int i = 0; i < n; i++) cin >> a[i], x ^= a[i];
sum += n;
int t = 0;
for (int i = 60; i >= 1; i--) {
int cnt = 0;
for (int j = 0; j < n; j++) cnt += (a[j] >> i) & 1;
if (cnt % 2 == 0 and cnt) t = 1;
if (t) x |= 1LL << i;
}
cout << x << "\n";
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
assert(T >= 1 and T <= 1000);
while(T--) solve();
assert(sum <= 2e5);
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int co[60], ans=0;
memset(co, 0, sizeof(co));
for(int i=0;i<n;i++)
{
int a;
cin>>a;
ans^=a;
for(int j=0;j<60;j++)
co[j]+=((a >> j)&1);
}
int f=0;
for(int i=59;i>0;i--)
{
if(co[i]>1 && co[i]%2==0)
f=1;
if(f)
ans|=(1ll << i);
}
cout<<ans<<"\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans, full = 0, 0
for i in range(n): full ^= a[i]
ans = full
for i in range(n):
rem = full ^ a[i]
have, cur = 0, 0
for b in reversed(range(1, 60)):
if a[i] & 2**b: have += 1
if rem & 2**b == 0:
if have > 0:
have -= 1
cur += 2**b
else:
cur += 2**b
have *= 2
cur += rem%2 ^ a[i]%2
ans = max(ans, cur)
print(ans)
