## Thursday, June 1, 2017

### Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Problem Statement:
Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Summary:
An integer array A of size n <= 5000 has entries which ranges from 1 to 5000. We pick disjoint segments of the array such that for each segment S:
1. If i in S, then any j s.t. a[j] == a[i] must also be in S
2. The score of S is computed as the XOR of its elements
Goal is to maximise the sum of scores of the chosen segments.

Solution:
I like this problem. This is solvable using a dynamic programming approach.

Suppose dp[i] is the maximum score we can get when we are only allowed to pick segments in A[0...i]. To find dp[i], we can:
1. Skip A[i]. So dp[i] is at least as good as dp[i-1].
2. Form a segment using A[i]. To do this we need to check a few things. First, say the smallest segment we can form (satisfying the above condition) is A[j...k] (i.e. j <= i && i <= k). Now, if k > i, then we cannot use A[i] to form the current segment, as we will be using elements beyond [0..i]. If k == i, then we know that dp[i] is at least as good as dp[j-1] + score of A[j...i].

With that, the implementation is quite straightforward.

Implementation:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;

int main(){
int n;
scanf("%d",&n);
int a[5010];
vector<pair<int,int>> b;
for (int i = 0; i < n; ++i) {
scanf("%d",&a[i]);
b.push_back({a[i], i});
}
sort(b.begin(), b.end());
int r[5010][2];
int prev = b[0].second;
for (int i = 1; i < n; ++i) {
if (b[i].first == b[i-1].first) continue;
int val = b[i-1].first;
int last = b[i-1].second;
r[val][0] = prev;
r[val][1] = last;
prev = b[i].second;
}
r[b.back().first][0] = prev;
r[b.back().first][1] = b.back().second;
int dp[5010];
int mark[5010];
for (int i = 0; i < n; ++i) {
dp[i] = dp[i-1];
bool can_choose = true;
int last = i;
int cur = 0;
memset(mark, 0, sizeof(mark));
for (int j = i; j >= last; --j) {
if (r[a[j]][1] > i) {
can_choose = false;
break;
}
last = min(last, r[a[j]][0]);
if (!mark[a[j]]) {
cur ^= a[j];
mark[a[j]] = 1;
}
}
if (!can_choose) continue;
dp[i] = max((last - 1 >= 0 ? dp[last-1] : 0) + cur, dp[i-1]);
}
printf("%d\n",dp[n-1]);
return 0;
}