PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: jay129
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix (XOR) sums, dynamic programming
PROBLEM:
You’re given an array A. You can choose any non-negative integer X and then perform the following process:
- For each i from 1 to N,
- If A_i = X, add X to your score.
- Otherwise, set X := X\oplus A_i
Find the maximum possible score.
EXPLANATION:
Let’s call an index i good if its value is added to the answer - meaning the value of X equals A_i when at index i.
Suppose i and j are consecutive good indices.
Then, X must equal A_i when at index i, will be updated at every index between i and j, and then will equal A_j at index j.
This means:
That is, the subarray XOR from i to j must equal 0.
Since we’re dealing with subarray XORs, let’s try to translate this in terms of prefix XORs instead.
Let P be the prefix XOR array of A, so that
P_i = A_1\oplus A_2\oplus\cdots\oplus A_i
Then, i and j are consecutive good indices if and only if P_{i-1} \oplus P_j = 0, or equivalently P_{i-1} = P_j.
In particular, note that if i is a good index, the next good index is uniquely determined: it’s the smallest j\gt i such that P_j = P_{i-1}.
With this observation, we can build a directed graph with the edge i\to j existing if and only if j is the next good index assuming i is a good index.
Note that this graph is acyclic.
To build the graph quickly, iterate over indices in reverse order and maintain the last seen occurrence of each prefix sum.
If the first good index is fixed, the final score is obtained by simply taking the sum of all values on the path starting from i.
These sums can easily be computed using dynamic programming because the graph is acyclic, by processing indices in descending order:
- Let dp_i denote the sum of values on the path starting at i.
- If no outgoing edge i\to j exists, dp_i = A_i.
- Otherwise, if the edge i\to j exists, dp_i = A_i +dp_j.
Since we’re free to choose the initial value of X, the path can start anywhere, and the answer is thus simply \max(dp).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
vector<ll>a(n),dp(n,0);
map<ll,ll>m;
ll ans=0,pfxor=0,tmp;
// to get x=a[i] for some i
// we can get initial value of x using the following recurrence:
// if there is an index j<i such that a[j]^a[j+1]...^a[i]=0 and j is maximised
// Since a[i]!=0, there is no possible k such that a[j]^a[j+1]...^a[k]=0
// as this means a[k+1]^a[k+2]...a[i]=0 and k+1<i which contradicts our condition,
// hence
//initial value of x=a[i] = initial value of x=a[j]
// else x=prefix xor till i
for(int i=0;i<n;i++){
cin>>a[i];
pfxor^=a[i];
if(m.find(pfxor)!=m.end()){
dp[i]=m[pfxor]+a[i];
}
else dp[i]=a[i]; // there was no pfxor present before so we will start with x=pfxor
// Hence, there will not be any case for getting j such that a[j]^a[j+1]...^a[i]=0 so only possible way is x=prefix xor till i
tmp=(pfxor^a[i]);
m[tmp]=dp[i];
ans=max(ans,dp[i]);
}
cout<<ans<<'\n';
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pref = [0]*(n+1)
for i in range(n): pref[i+1] = pref[i] ^ a[i]
next = {}
dp = [0]*(n+1)
for i in reversed(range(1, n+1)):
if pref[i-1] not in next: dp[i] = a[i-1]
else: dp[i] = a[i-1] + dp[next[pref[i-1]]]
next[pref[i]] = i
print(max(dp))