U USACO Prep

2024 December Gold · "Cake Game" (Gold variant)

← All past problems · Official statement

The premise

Same circular cake setup as the Silver problem, but now K = 1 and each player picks optimally to maximize the value of the slice they finally receive. The slice remaining after N−1 moves is whichever arc-end was not chosen on the last move. Compute the value the first player (Bessie) ends up with.

(Paraphrased. The actual Gold variant has more structure; this is a clean teaching restatement.)

Why this jumps from Silver to Gold

Silver's "window of length K" reduction breaks: both players actively choose which end to chip away at, so the surviving slice is not just any window — it's the slice that results from a game-theoretic min-max process.

Key observation

Game DP on intervals. Define dp[l][r] = the value Bessie ends up with when the remaining arc spans indices [l, r] on the duplicated array and it is the current player's turn (parity encoded by whether r − l + 1 is odd or even). The current player chooses to remove either a[l] or a[r], and Bessie's outcome propagates by min or max depending on whose turn it is.

For the "K = 1, single slice survives" version, an O(N²) interval DP solves it directly. For larger K and tighter constraints, you must observe additional symmetries — often the answer collapses to a min over windows or a rotational invariant.

Reference DP (C++)

// dp[l][r] = value Bessie ends with given arc [l..r], Bessie's turn iff (r-l) even
int n; cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int i = 0; i < n; ++i) dp[i][i] = a[i];  // single slice left = Bessie gets it if her turn

for (int len = 2; len <= n; ++len) {
    for (int l = 0; l + len - 1 < n; ++l) {
        int r = l + len - 1;
        bool bessie = (n - len) % 2 == 0;   // turns elapsed parity
        int takeL = dp[l + 1][r];
        int takeR = dp[l][r - 1];
        dp[l][r] = bessie ? max(takeL, takeR) : min(takeL, takeR);
    }
}

cout << dp[0][n - 1] << "\n";

Complexity

O(N²) time, O(N²) memory. Fine for N up to ~5000. The real Gold problem at N = 5·10⁵ requires an O(N) observation — see the official editorial for the full reduction.

Pitfalls

What to take away