Baltic OI 2015 - Hacker

Author: Michael Cao

Official Analysis

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

Observation

At the end of the game, the first player will control a subarray (a contiguous subsequence) of the circular array of length exactly n2\left \lceil{\frac{n}{2}}\right \rceil, and the second player will control the remaining elements.

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 n2\left \lceil{\frac{n}{2}}\right \rceil.

Observation 2

Observation

For some first move made by the first player claiming index xx, the second player can always force the first player to control any subarray of length n2\left \lceil{\frac{n}{2}}\right \rceil containing xx.

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 n2\left \lceil{\frac{n}{2}}\right \rceil containing the first players first move depending on the second players first move.

Computing the Solution

Using these observations, the answer equals:

max1xnminvSxv\max_{1 \leq x \leq n}\min_{v \in S_x}v

where SxS_x represents a set of sums for all subarrays of length n2\left \lceil{\frac{n}{2}}\right \rceil containing xx in the circular array, c\texttt{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 2n2n and call it a\texttt{a}. Now, we only need to compute subarrays on a linear array, where Sx=SxSx+n(1xn)S_x = S'_x \cup S'_{x + n} (1 \leq x \leq n) where SxS'_x represents the set of subarrays containing xx in a\texttt{a}.

Using A Sorted Set

If we iterate over xx (1x2n)(1 \leq x \leq 2n) in a\texttt{a}, then we can store the running sorted set SxS'_x and use it to update SxmodnS_{x \bmod n}. For x0x \geq 0, add the sum over the subarray [x,x+n21][x, x + \left \lceil{\frac{n}{2}}\right \rceil - 1] to SxS'x (you can compute this using prefix sums). Additionally, if xn2x \geq \left \lceil{\frac{n}{2}}\right \rceil, remove the sum over [xn2+1,x][x - \left \lceil{\frac{n}{2}}\right \rceil + 1, x]. Then, we can compute the minimum value of SxS'x for some xx by querying for the smallest value in the sorted set.

Warning!

Make sure to use a std::multiset because there can be duplicate sums.

Implementation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!