A decision tree week

The Jul 16 - Jul 22 week provided the second and last chance to progress to the round of 100 in the TopCoder Open 2018, with 50 more advancers chosen in Round 3B (problems, results, top 5 on the left, parallel round results, analysis). qwerty787788 was the only one to solve all three problems correctly, and thus won the first place with quite a margin — congratulations to Borys and to everybody who advanced!

Facebook Hacker Cup 2018 Round 1 took place over the weekend of that week (problems, results, top 5 on the left, analysis). Being fast was not a requirement this time, as the penalty time did not factor into advancement, but of course a competition is always a competition :) Congratulations to Kevin (are you ksun48?..) on the win!

In my previous summary, I have mentioned a very nice AtCoder problem: two players play a game on an array of integers a_i with at most 300000 elements. The players make alternating turns, and on each turn a player takes a number from the array that is not previously taken. Moreover, when possible, a player must take a number adjacent to a number taken by the other player on the last turn. When taking such adjacent number is not possible (on first turn, or after a player has taken a number which has both neighbors either taken or nonexistent), any number can be taken. The game ends when all numbers have been taken, and each player tries to maximize the sum of the numbers they take. Which sum will each player get if both play optimally?

Let's color all numbers with alternating colors, first one is red, second one is blue, third one is red, and so on. First, suppose the total amount of numbers is even, in other words the last number is blue. The first player has a few options:

• Take the first number. Then the rest of the moves is uniquely determined, they will take all numbers from first to last, the first player taking all red numbers, and the second player taking all blue numbers.
• Take the last number. In this case everything is determined as well, but the first player gets all blue numbers, and the second player gets all red numbers.
• Take a number in the middle. In this case the second player has choices as well, so let's study this case more carefully.

Suppose the first player starts by picking a red number that is not the first number. The second player has two choices now: go left or right. If they go left, they will collect all blue numbers to the left, and the first player will collect all red numbers. Since the first number is red, the first player will be the last to move in this chain, and the second player will be able to pick any number. First key observation is that they can then take the last number, and thus collect all remaining blue numbers. So if the first player picks a red number, the second player can always take all blue numbers.

Similarly, if the first player starts by picking a blue number, the second player can take all red numbers. So the second player can always guarantee at least the minimum of the two sums: all red numbers or all blue numbers. However, the first player can force the second player to get at most that minimum (by taking the first or the last number). Hence with optimal play the second player will get exactly that minimum (and thus the first player will get the maximum of the two sums).

Note how we didn't have to explore all possibilities here — for example we didn't consider the case where the first player starts with a red number and the second player moves to the right. We don't need to: by finding an upper bound and a lower bound for the second player's score that match, we have proven that other options will not change the answer. This observation will also be key to solving the harder case, where the overall amount of numbers is odd.

When the overall amount of numbers is odd, both first and last numbers are red, and the first player can still take all red numbers by taking the first number. However, there's no way for the first player to do the opposite and take all blue numbers. Let's again consider the other options the first player has:

• Take a red number that is not the first or last. Then the second player can still collect all blue numbers as in the even case, and since the first player can force the second player to take all blue numbers, we have matching upper and lower bounds again, and we don't need to investigate other second player's strategies in this branch.
• Take a blue number. In this case the second player chooses a side, and takes all red numbers on that side, and then the first player is again first to play on the other (remaining) side, which once again has an odd amount of numbers.

The first player can continue picking blue numbers when they have a choice for some time, until they decide to pick a red number in some remaining segment. Then the second player will have gotten all red numbers outside this remaining segment, and all blue numbers inside this segment.

Can the first player choose this segment arbitrarily? No, since the second player decides whether we go left or right every time the first player picks a blue number. In fact, we can imagine the optimal strategy for the first player like a decision tree: we start by picking a certain blue number. If the second player takes all red numbers to the left, we are left with the right part, and will pick a certain blue number there; if we have the left part, we will pick a certain blue number there, and so on. Ultimately, each branch ends with us (first player) picking all red numbers in the segment.

Now we can notice that the decision tree structure actually does not matter much. The blue numbers used for branching in the decision tree split the other numbers into segments. In the end, the second player gets all blue numbers from one of those segments, and all red numbers from the rest. The first player can split all numbers into such segments arbitrarily, and the second player effectively gets to choose the segment it gets blue numbers from.

Note that we did not find an arbitrary strategy for both players — we have shown that the optimal strategy for them must look like this. The only remaining question is: how should the first player split all numbers into segments?

This is another cool side of the problem: after solving the "more mathematical" strategy part, the remaining "algorithmic" part is also interesting to solve! We have an array of numbers of odd length, with first, third, ... numbers colored red and the rest colored blue. We need to choose a set of blue numbers in such a way that minimizes the maximum of (sum of blue numbers minus sum of red numbers) over the segments between the chosen blue numbers.

There's a straightforward quadratic dynamic programming solution which finds the optimal way to split each prefix of our array, and iterates over all possible positions of the last taken blue number in each prefix.

In order to speed it up, we have to slow it down first. Let's add an outside binary search for the answer. Now instead of minimizing the maximum, we just need to check if there's a split such that on each segment the difference is below the threshold. This can still be done using a similar dynamic programming, for the overall runtime of O(n²*logn).

But now we can notice that in this simplified dynamic programming if position X of the last taken blue number is better than position Y for some prefix, it will be better for all bigger prefixes as well, since what happened before X/Y does not matter anymore (it just needs to be under the threshold), and the only thing that matters is the difference between blue and red numbers after X/Y. Whichever is smaller once will keep being smaller, since we add the same new numbers to both. So instead of trying all possible positions for the last taken blue number, we can try just two possibilities: the best position for the previous prefix, or just the previous blue number (which was not considered for the previous prefix because it was not there). This makes the solution run in overall O(n*logn) time.

Here is my entire solution from the contest:

int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) a[i] = in.nextInt();
int s1 = 0;
int s2 = 0;
for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
        s1 += a[i];
    else
        s2 += a[i];
}
if (n % 2 == 0) {
    out.println(Math.max(s1, s2) + " " + Math.min(s1, s2));
    return;
}
int left = s1 - s2;
int right = s1 + s2 + 1;
outer: while (right - left > 1) {
    int middle = (left + right) / 2;
    long bestSoFar = s1 - s2;
    int r1 = s1;
    int r2 = s2;
    for (int i = 1; i <= n; i += 2) {
        r1 -= a[i - 1];
        long cost = bestSoFar - (r1 - r2);
        if (i < n) r2 -= a[i];
        if (cost >= middle) {
            if (i == n) {
                left = middle;
                continue outer;
            } else {
                bestSoFar = Math.max(bestSoFar, r1 - r2);
            }
        }
    }
    right = middle;
}
out.println((s2 + left) + " " + (s1 - left));

Thanks for reading, and check back for more!