U USACO Prep

USACO 2015 December · Gold · all three problems

← Full December 2015 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec15results. Each problem heading links to the canonical statement on usaco.org. Code is my own reference C++ — cross-check the official editorial before trusting it under contest pressure.

Problem 1 — High Card Low Card (Gold)

Statement

A deck has 2N cards numbered 1…2N (N even). Elsie holds some N of them and plays them in a known order over N rounds; Bessie has the remaining N and can permute. In the first N/2 rounds the higher card wins; in the last N/2 rounds the lower card wins. Output the maximum number of rounds Bessie can win.

Constraints

Key idea

Because Bessie permutes, the rounds split cleanly: the first N/2 of Elsie's plays go to the "high wins" pool, the last N/2 go to the "low wins" pool. For high-wins, run the standard horse-race greedy on those N/2 cards vs Bessie's hand. For low-wins, mirror: for each Elsie card (descending), use Bessie's largest remaining card < it. Sum the two. The catch: Bessie must commit which cards she'll use in each half — but since both halves are greedy and structurally symmetric, the optimal split is to give the high half her largest k cards (for some k chosen by sorting). In practice, treat the two halves independently using a multiset of Bessie's cards.

Complexity target

O(N log N) sort + multiset operations.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> elsie(N);
    vector<bool> taken(2*N + 1, false);
    for (auto& e : elsie) { cin >> e; taken[e] = true; }

    // Greedy: assign Bessie's largest cards to high-half rounds, smallest to low-half.
    vector<int> bessie;
    for (int v = 1; v <= 2*N; ++v) if (!taken[v]) bessie.push_back(v);
    sort(bessie.begin(), bessie.end());
    int half = N / 2;

    // Bessie's "high" pool = top `half` cards; "low" pool = bottom `half`.
    multiset<int> hi(bessie.begin() + half, bessie.end());
    multiset<int> lo(bessie.begin(), bessie.begin() + half);
    int wins = 0;
    // First half: high wins. For each Elsie card find smallest hi card > it.
    for (int i = 0; i < half; ++i) {
        auto it = hi.upper_bound(elsie[i]);
        if (it != hi.end()) { ++wins; hi.erase(it); }
        else hi.erase(hi.begin());
    }
    // Second half: low wins. For each Elsie card find largest lo card < it.
    for (int i = half; i < N; ++i) {
        auto it = lo.lower_bound(elsie[i]); // first >= elsie[i]
        if (it != lo.begin()) { --it; ++wins; lo.erase(it); }
        else lo.erase(lo.begin());
    }
    cout << wins << "\n";
}

Pitfalls

Problem 2 — Fruit Feast

Statement

Bessie's fullness starts at 0, capped at T. She can eat oranges (+A fullness) and lemons (+B fullness) unlimited times. At most once she can drink water, which halves her current fullness (floor). Eating a fruit that would push her over T is forbidden. Output the maximum final fullness she can reach.

Constraints

Key idea

Two BFS-style passes over fullness states. reach1[v] = true if v is reachable without ever drinking water; compute by iterating v from 0 up: if reach1[v] then reach1[v+A] and reach1[v+B] (if ≤ T). Then for each v with reach1[v], you may drink water, landing at v/2; mark reach2[v/2] = true. From every reach2 state, propagate +A/+B again. The answer is max v with reach1[v] OR reach2[v].

Complexity target

O(T) time and memory.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, A, B; cin >> T >> A >> B;

    vector<char> r1(T + 1, 0), r2(T + 1, 0);
    r1[0] = 1;
    for (int v = 0; v <= T; ++v) {
        if (!r1[v]) continue;
        if (v + A <= T) r1[v + A] = 1;
        if (v + B <= T) r1[v + B] = 1;
    }
    // Drink water at any reach1 state.
    for (int v = 0; v <= T; ++v) if (r1[v]) r2[v / 2] = 1;
    for (int v = 0; v <= T; ++v) {
        if (!r2[v]) continue;
        if (v + A <= T) r2[v + A] = 1;
        if (v + B <= T) r2[v + B] = 1;
    }
    int ans = 0;
    for (int v = 0; v <= T; ++v) if (r1[v] || r2[v]) ans = v;
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Bessie's Dream

Statement

On an N×M grid Bessie starts at (1,1) and wants to reach (N,M) in the minimum number of moves. Tiles: 0 red (impassable), 1 pink (normal), 2 orange (grants "orange smell"), 3 blue (passable only when she has smell), 4 purple (when entered, slides her one tile further in the same direction repeatedly until she's not on purple; also clears smell). Each move costs 1. Output the minimum moves or -1.

Constraints

Key idea

BFS on a 3D state (r, c, smell). Smell is a 0/1 bit; orange tiles set it to 1; purple slides clear it. Step cost is uniform → ordinary BFS works. When attempting to step into a purple tile, simulate the slide in the current direction until off purple or off-grid; if the landing tile is illegal (red, or blue without smell) the move is forbidden. Smell flips ON if you end on orange, OFF if you traversed purple.

Complexity target

O(N · M · 2 · 4) edges = ~8·10⁷ in the worst case; feasible in 2s with tight code.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<string> rowbuf;
int g[1005][1005];
int dist[1005][1005][2];
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) cin >> g[i][j];
    memset(dist, 0x3f, sizeof dist);
    // start: (0,0), smell = 0 if pink; if orange, smell = 1.
    int s0 = (g[0][0] == 2) ? 1 : 0;
    dist[0][0][s0] = 0;
    queue<tuple<int,int,int>> q; q.push({0, 0, s0});
    while (!q.empty()) {
        auto [r, c, s] = q.front(); q.pop();
        int d = dist[r][c][s];
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k], ns = s;
            if (nr<0||nc<0||nr>=N||nc>=M) continue;
            if (g[nr][nc] == 0) continue;            // red: blocked
            if (g[nr][nc] == 3 && ns == 0) continue; // blue: need smell
            if (g[nr][nc] == 4) {                    // purple: slide
                ns = 0;
                while (nr>=0&&nc>=0&&nr<N&&nc<M && g[nr][nc] == 4) { nr += dr[k]; nc += dc[k]; }
                if (nr<0||nc<0||nr>=N||nc>=M) continue;
                if (g[nr][nc] == 0) continue;
                if (g[nr][nc] == 3) continue;        // blue after slide with no smell
            }
            if (g[nr][nc] == 2) ns = 1;
            if (d + 1 < dist[nr][nc][ns]) {
                dist[nr][nc][ns] = d + 1;
                q.push({nr, nc, ns});
            }
        }
    }
    int ans = min(dist[N-1][M-1][0], dist[N-1][M-1][1]);
    cout << (ans >= 0x3f3f3f3f ? -1 : ans) << "\n";
}

Pitfalls

What Gold December 2015 was actually testing