U USACO Prep

USACO 2024 December · Silver · all three problems

← Full December 2024 set · Official results · Focused notes on Cake Game

Source. Problem titles and constraints below are from usaco.org/index.php?page=dec24results. Reference C++ is mine; cross-check the official editorial before treating it as authoritative.

Problem 1 — Cake Game

Statement

N cake slices with positive values are arranged in a circle. Bessie and Elsie alternately eat one slice from either end of the surviving arc until K slices remain. Both play optimally — but because the game is forced (you can only pick from an end), the surviving slices always form a contiguous arc of length K. Compute the maximum sum of any length-K contiguous window on the circular array.

Constraints

Key idea

"Both players pick from an end" forces the remaining slices to be contiguous on the circle. The answer is the maximum sum of any K consecutive entries on the circular array — solve with a sliding window after duplicating the array.

Complexity target

O(N).

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;

    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";
}

Pitfalls

Problem 2 — Deforestation

Statement

N trees sit at integer positions on a number line. K constraints each specify an interval [l, r] and a count t saying "at least t trees in [l, r] must survive." Determine the maximum number of trees that can be cut down while every constraint stays satisfied.

Constraints

Key idea

Classic interval-cover greedy. Sort constraints by right endpoint. Sweep left to right; for each interval, count how many of its trees are still alive (multiset of surviving x-coordinates); if you have more alive than needed, cut the surplus — but cut the leftmost ones, because they are least likely to be useful to later intervals. Equivalently: sort intervals by r, sort trees by position, and for each interval keep the rightmost t trees inside it, killing the rest of the inside-trees that aren't reserved by other constraints.

Complexity target

O((N + K) log N).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, K; cin >> N >> K;
        vector<int> x(N);
        for (auto& v : x) cin >> v;
        vector<tuple<int,int,int>> cs(K); // (r, l, t)
        for (auto& [r, l, t] : cs) { cin >> l >> r >> t; }
        sort(cs.begin(), cs.end()); // by r ascending

        sort(x.begin(), x.end());
        // 'alive[i]' = whether tree i still stands
        vector<char> alive(N, 1);
        long long kept = 0;

        for (auto [r, l, t] : cs) {
            // Find indices of trees with l <= x[i] <= r.
            int lo = lower_bound(x.begin(), x.end(), l) - x.begin();
            int hi = upper_bound(x.begin(), x.end(), r) - x.begin() - 1;
            // Count currently alive in [lo, hi].
            int liveCount = 0;
            for (int i = lo; i <= hi; ++i) liveCount += alive[i];
            // Need at least t alive. If liveCount < t: revive rightmost dead ones.
            // (Equivalently: keep rightmost t inside the window.)
            int need = max(0, t - liveCount);
            for (int i = hi; i >= lo && need > 0; --i)
                if (!alive[i]) { alive[i] = 1; --need; }
            // Now kill leftmost surplus inside the window.
            int surplus = max(0, liveCount + (t - liveCount > 0 ? (t - liveCount) : 0) - t);
            // Simpler second pass: kill from the left until exactly t alive remain inside.
            int curAlive = 0;
            for (int i = lo; i <= hi; ++i) curAlive += alive[i];
            for (int i = lo; i <= hi && curAlive > t; ++i)
                if (alive[i]) { alive[i] = 0; --curAlive; }
        }
        for (auto a : alive) kept += a;
        cout << (long long)N - kept << "\n";
    }
}

[verify] The sweep above is O((N+K)·window-size) per test and may need a Fenwick tree to hit the official time limit on max inputs; the intended editorial uses a BIT for live-count queries and a sorted multiset of alive positions for surgical removals.

Pitfalls

Problem 3 — 2D Conveyor Belt

Statement

On an N×N grid, each cell is either a fixed conveyor (L, R, U, D), an unbuilt cell (?), or empty. An item placed on a conveyor follows its arrow; the cell is "usable" if the item eventually leaves the grid. Over Q days Farmer John commits one ? cell to a specific direction. After each commit, report the minimum number of unusable cells achievable by completing the remaining ? cells optimally.

Constraints

Key idea

A cell escapes iff there is a path of conveyors (with each step's direction matching that cell's label) that reaches the boundary. Reverse the graph: from each boundary edge, do a multi-source BFS backwards — a cell with label L is reachable in the reverse graph from its right neighbor (since L would push something there), and a ? cell is reachable from any already- reachable neighbor (we still get to choose its direction). Initially every ? counts as escaping because we can always orient it toward the boundary. When a ? is committed to a direction, it locks in: now its escape depends only on that specific outgoing neighbor; the cells upstream of that ? may flip from usable to unusable. Maintain reachability with a DSU-on-reverse-graph or a timestamped BFS that processes flips lazily.

Complexity target

O(N² + Q · α(N²)) amortised; raw worst-case re-BFS is O(Q · N²) which is borderline at N=1000.

Reference solution (C++)

// Sketch: maintain reachable[i][j] = "can escape under current commitments".
// Initially every '?' is reachable (orient toward border). Each commit may
// only *shrink* the reachable set, so we re-BFS from the committed cell:
//
//   - When (r,c) commits to direction d, its escape now depends on the
//     single neighbor in direction d. If that neighbor is unreachable,
//     mark (r,c) unreachable; then propagate to all upstream cells that
//     used to route through (r,c).
//
// This is monotone: a cell never becomes reachable again, so total work
// across all Q queries is O(N^2) amortised after the initial BFS.
#include <bits/stdc++.h>
using namespace std;
int N, Q;
vector<string> g;
vector<vector<char>> reach;
int dr[256], dc[256];
long long unusable;

void killCell(int r, int c) {
    if (r < 0 || r >= N || c < 0 || c >= N || !reach[r][c]) return;
    // Recheck whether (r,c) still escapes.
    char d = g[r][c];
    if (d == '?') return; // ? always escapes (orient toward boundary)
    int nr = r + dr[(int)d], nc = c + dc[(int)d];
    if (nr < 0 || nr >= N || nc < 0 || nc >= N) return; // exits the grid
    if (reach[nr][nc]) return;                              // still routes out
    reach[r][c] = 0; ++unusable;
    // Propagate backward: who used (r,c) as their next step?
    for (auto [ddr, ddc, expect] : initializer_list<tuple<int,int,char>>{
            {-1, 0, 'D'}, {1, 0, 'U'}, {0, -1, 'R'}, {0, 1, 'L'}})
        if (r+ddr>=0 && r+ddr<N && c+ddc>=0 && c+ddc<N
            && g[r+ddr][c+ddc] == expect)
            killCell(r+ddr, c+ddc);
}

int main() {
    dr['U']=-1; dr['D']=1; dr['L']=0; dr['R']=0;
    dc['U']=0;  dc['D']=0; dc['L']=-1; dc['R']=1;
    cin >> N >> Q;
    g.assign(N, string(N, '?'));
    for (auto& row : g) cin >> row;
    reach.assign(N, vector<char>(N, 1));
    unusable = 0;
    // Initial pass: for every committed cell that doesn't escape, kill it.
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            if (g[r][c] != '?') killCell(r, c);
    while (Q--) {
        int r, c; char d; cin >> r >> c >> d; --r; --c;
        g[r][c] = d;
        killCell(r, c);
        cout << unusable << "\n";
    }
}

[verify] Recursive kill can stack-overflow on N=1000; convert to an explicit stack for submission. Editorial may use a cleaner DSU formulation.

Pitfalls

What Silver December 2024 was actually testing