Baltic OI 2015 - Hacker

Intuition

In this problem, we're asked to play a game where players take turns claiming unclaimed elements in a circular array that are adjacent to one of their previously claimed elements (or any unclaimed element on their first turns). Both players try to maximize the sum of values of their chosen elements.

After playing around with the game, we can make some important observations.

Observation 1

Since each player can only choose an element not adjacent to any other element once (the first move), the elements each player claims must form a subarray. Also, notice that any move made by either player will increase the length of the subarray they control by one, and both players will always have a valid move. Therefore, because the first player moves first, the subarray they control will be of length $\lceil \frac{n}{2}\rceil$.

Observation 2

Consider the following strategy: for some move by the first player extending to the left or right, make the opposite move.

Using this strategy, the second player can force the first player to control any subarray of length $\lceil \frac{n}{2}\rceil$ containing the first players first move depending on the second players first move.

Computing the Solution

Using these observations, the answer equals:

where $S_x$ represents a set of sums for all subarrays of length $\lceil \frac{n}{2}\rceil$ containing $x$ in the circular array, $\text{c}$.

Transforming the Circular Array

First, to deal with the circular aspect of the array, let's concatenate it onto itself to create an array of length $2n$ and call it $\text{a}$. Now, we only need to compute subarrays on a linear array, where $S_x=S_x^{\prime }\cup S_{x+n}^{\prime }(1\le x\le n)$ where $S_x^{\prime }$ represents the set of subarrays containing $x$ in $\text{a}$.

Using An Ordered Set

If we iterate over $x$ $(1\le x\le 2n)$ in $\text{a}$, then we can store the running ordered set $S_x^{\prime }$ and use it to update $S_{x\mathrm{m}\mathrm{o}\mathrm{d}n}$. For $x\ge 0$, add the sum over the subarray $[x,x+\lceil \frac{n}{2}\rceil -1]$ to $S^{\prime }x$ (you can compute this using prefix sums). Additionally, if $x\ge \lceil \frac{n}{2}\rceil$, remove the sum over $[x-\lceil \frac{n}{2}\rceil +1,x]$. Then, we can compute the minimum value of $S^{\prime }x$ for some $x$ by querying for the smallest value in the ordered set.

Code

1#include <bits/stdc++.h> 
2using namespace std;
3 
4using ll = long long;
5 
6using vi = vector<int>;
7#define pb push_back
8#define rsz resize
9#define all(x) begin(x), end(x)
10#define sz(x) (int)(x).size()