Problem: nearly_nim (2023 finals)

Alice and Bob are servers at *Nim Sum Dim Sum*, a bustling dumpling restaurant. For a staff meal, the manager has generously provided \(N\) plates of dumplings in a row, numbered from \(1\) to \(N\). Initially, plate \(i\) has \(A_i\) dumplings. In classic fashion, the duo has decided to play a game.

Alice and Bob will take turns eating dumplings from the plates. On a given turn, a player must pick a plate adjacent to the last picked plate by the other player, and eat any positive number of dumplings from that plate. The first player who cannot do so on their turn loses. Alice goes first, and can choose any starting plate to eat from.

For example, suppose there are three plates holding \(4\), \(1\) and \(2\) dumplings respectively. On the first turn, Alice can eat \(3\) dumplings from the first plate. Bob must then eat the dumpling from the middle plate. Alice can respond by eating one dumpling from the third plate. Bob must then eat from plate \(2\), but since it’s empty now, he loses.

Assuming both players play optimally, how many starting moves can Alice make so that she wins? Two starting moves are considered different if Alice eats from different plates, or eats a different number of dumplings.

# Constraints

\(1 \le T \le 220\)
\(2 \le N \le 800{,}000\)
\(0 \le A_i \lt 2^{25}\)

The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).

# Input Format

Input begins with an integer \(T\), the number of cases. Each case will begin with a single integer \(N\) followed by the \(N\) integers \(A_1, ..., A_N\) on the next line.

# Output Format

For the \(i\)th case, output `"Case #i: "` followed by a single integer, the number of winning starting moves Alice has.

# Sample Explanation

In the first case, Alice can start by taking any number of dumplings from either the first or third plate. Bob will then have to take the solitary dumpling on the middle plate, and Alice can win by taking all the dumplings from the plate she didn't start with. This gives Alice 6 different winning starting moves.

In the second case, Alice cannot win because she takes one dumpling, Bob takes the other, and then Alice has no move to make.

In the third case, Alice's winning moves are to take \(1\) or \(2\) dumplings from the right-hand plate.

In the fourth case, Bob can always force a win.



Sample input:
6
3
4 1 2
2
1 1
2
2 4
3
1 3 2
6
2 2 3 3 4 4
8
6 2 8 3 1 8 5 3


Sample output:
Case #1: 6
Case #2: 0
Case #3: 2
Case #4: 0
Case #5: 0
Case #6: 19


Solution: Since you must eat dumplings on a plate adjacent to your opponent, after the first move, it's uniquely determined who will eat from even plates and who will eat from odd plates. Therefore, other than Alice's first move, neither player will ever eat more than one dumpling on a turn.

First, let's determine whether some board state is winning or losing for the current player. Suppose \(A[0] > A[1]\). In this case, Alice can win by eating from \(A[0]\), and will lose if she eats from \(A[1]\). Importantly, notice that if Alice eats from \(A[2...n]\), neither player will ever eat from \(A[1]\) as it will cause them to lose—their opponent can keep eating \(A[0]\), and \(A[1]\) will run out first.

Therefore (if \(A[0] > A[1]\) and the first move doesn't involve \(A[0]\)), we can replace \(A[0]\) and \(A[1]\) with \(0\)'s and it will not change the result of the game.

On the other hand if \(A[0] \leq A[1]\), then if our opponent ever eats from \(A[1]\), we should keep eating from \(A[0]\) as many times as possible to decrease \(A[1]\). We can prove this is optimal with a greedy principle: dumplings at position \(0\) can at best cause your opponent to have to eat one more dumpling from position \(1\), and at worst will never be eaten because your opponent won't give you the chance. Either way, we'll have to continue playing on pile \(2\), and it's better for us if the opponent has fewer dumplings left on pile \(1\).

Therefore (if \(A[0] \leq A[1]\) and the first move doesn't involve \(A[0]\)), then we can replace \(A[0]\) with \(0\), and \(A[1]\) with \(A[1]-A[0]\), and it will not change the result of our game.

Of course, these observations are symmetric, so they apply to \(A[N]\) and \(A[N-1]\) in the same way as \(A[0]\) and \(A[1]\).

If the first move was made at position \(A[7]\) for example, then in linear time we can repeatedly simplify each end of the array until the only elements that are left are \(A[6], A[7],\) and \(A[8]\). We either delete the first/last two elements, or delete the first/last element, and decrease the second/second last. When we're done, this leaves us with an array of size \(3\), and all that matters is the total number of dumplings in the middle vs. on the sides. If after she takes dumplings from \(A[7]\), Alice will win if \(A[7] \geq A[6]+A[8]\). This leaves us with \(\max(0, A[7]-A[6]-A[8])\) ways of winning that start with position \(7\).

This gives us an \(\mathcal{O}(N^2)\) solution since we are brute forcing the first move. But it turns out that each side is independent, so we can do a DP on each prefix and suffix to count what each prefix and suffix leaves you with, and this gives us an \(\mathcal{O}(N)\) solution.



Code: #include <iostream>
#include <vector>
using namespace std;

int solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  int ans = 0;
  vector<int> left(N + 1), right(N + 1);
  for (int i = 0; i < N; i++) {
    left[i + 1] = max(0, A[i] - left[i]);
  }
  for (int i = N - 1; i >= 0; i--) {
    right[i - 1] = max(0, A[i] - right[i]);
  }
  for (int i = 0; i < N; i++) {
    ans += max(0, A[i] - left[i] - right[i]);
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}