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;
}