Title confirmed; approach is my own working notes. The "Cake Game" title is verified against the December 2024 Silver results. The approach and code below are how I'm thinking about the problem, not the official editorial — always cross-check against the canonical statement on usaco.org.

2024 December Silver · "Cake Game"

← All past problems · Official statement

The premise

Bessie and Elsie play a game on a circular arrangement of N cake slices, each with a positive value. They take turns picking slices, alternating until K slices remain. Each can only pick a slice that's currently at the "edge" (adjacent to an empty position or the start). Compute the maximum total value Bessie can guarantee to leave for herself if both play optimally.

(Paraphrased; see PDF for exact statement and constraints.)

Constraints

1 ≤ K ≤ N ≤ 5·10⁵
Slice values fit in a 32-bit signed integer
Time limit: 2 seconds

Key observation

The remaining cake is always a contiguous arc. Whoever is picking always picks from an end of the arc; after each turn the arc shortens from one of the two ends. Over N − K total turns, the surviving slice indices form some contiguous window of length K on the circular array.

So the answer reduces to: find the maximum sum over any contiguous window of length K on the circular array.

Approach

Duplicate the array (a concatenated with a) so circularity becomes linearity.
Use a sliding window of length K, maintaining the running sum in O(1) per step.
Return the maximum sum seen.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // duplicate for circular sliding window
    vector<int> b(2 * n);
    for (int i = 0; i < 2 * n; ++i) b[i] = a[i % n];

    ll sum = 0;
    for (int i = 0; i < k; ++i) sum += b[i];
    ll best = sum;

    for (int i = k; i < n + k; ++i) {
        sum += b[i] - b[i - k];
        best = max(best, sum);
    }

    cout << best << "\n";
}

Complexity

O(N) time and memory. Comfortable at N = 5·10⁵.

Pitfalls

Sums overflow. N up to 5·10⁵ with values up to 10⁹ → sum up to 5·10¹⁴. Use long long.
K = N edge case. The arc covers the whole circle exactly once; you should not double-count.
Confusing K (slices kept) with N − K (slices taken). Re-read the problem carefully.

What to take away

"Pick from either end" games often collapse to "a contiguous window remains."
Circular array trick: duplicate the array, treat as linear, slide a window of the desired length.
When the players are symmetric and "fair" turn-taking is forced, game theory often degenerates into a deterministic geometry problem.