USACO 2017 December · Gold · all three problems

← Full December 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec17results. 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 — A Pie for a Pie

Statement

Bessie has N pies, Elsie has N pies. Each cow ranks the other cow's pies by preference. Bessie gives Elsie pie b first; Elsie will accept it iff its rank among Elsie's preferences is ≤ D from her best available. If she accepts, she must reciprocate with one of her pies whose rank in Bessie's preferences is ≤ D from Bessie's best. The chain continues until someone can't reciprocate. For each starting pie b that Bessie could give, output the length of the shortest valid chain, or −1 if impossible.

Constraints

1 ≤ N ≤ 10⁵, 0 ≤ D ≤ N.
Each cow ranks all N of the other's pies (a permutation).
Time limit: 2s.

Key idea

Build a bipartite-layered graph: nodes are (cow, pie) pairs. From a B-pie b, an edge goes to any E-pie e whose B-ranking is in the top D of pies E can give back; symmetrically the other direction. The "length" we want is the minimum number of trades until the chain dead-ends — equivalently, multi-source BFS from terminal (dead-end) pies backward. Reverse the edges and BFS from sinks; each source's BFS layer is the answer.

Complexity target

O(N · D) edges in the worst case, BFS is linear in edges.

Reference solution (C++)

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

// Schematic reference: build the rank-D neighbor lists for both sides,
// then reverse-BFS from chain terminators. Real input parsing details
// follow the USACO statement; here we sketch the graph layer.
int N, D;
vector<vector<int>> nbrB, nbrE; // nbrB[b] = list of E-pies B-pie b can reach
vector<int> distB, distE;

void bfs(const vector<int>& sourcesB) {
    queue<pair<int,int>> q;       // (side: 0=B,1=E, node)
    for (int b : sourcesB) { distB[b] = 1; q.push({0, b}); }
    while (!q.empty()) {
        auto [side, u] = q.front(); q.pop();
        if (side == 0) {
            for (int v : nbrB[u]) if (distE[v] == -1) {
                distE[v] = distB[u] + 1; q.push({1, v});
            }
        } else {
            for (int v : nbrE[u]) if (distB[v] == -1) {
                distB[v] = distE[u] + 1; q.push({0, v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // Read N, D, then the two preference matrices.
    // Build nbrB and nbrE so an edge b -> e exists iff e is among
    // E's top-D acceptable returns for the chain reaching b. (Details
    // omitted for length; the layered BFS itself is the heart of it.)
    distB.assign(N + 1, -1); distE.assign(N + 1, -1);
    vector<int> terminators; // B-pies that are immediately acceptable to Elsie
    bfs(terminators);
    // For each B-pie b Bessie starts with, print distB[b] (or -1).
    for (int b = 1; b <= N; ++b) cout << distB[b] << "\n";
}

Pitfalls

Direction of search. Forward BFS from each pie is O(N²); reverse-BFS from the natural sinks (acceptable-without-reciprocation pies) once gives all answers in one pass.
"Top D" is rank-based, not value-based. Build the neighbor lists from each cow's own preference list.
The chain alternates sides. Two distance arrays (one per side) prevent collapsing them and miscounting parity.
−1 when unreachable. Initialize with −1; never overwrite.

Problem 2 — Barn Painting

Statement

Given a tree on N nodes (barns) and three colors, count the number of valid 3-colorings such that no two adjacent nodes share a color. Some K nodes have a pre-fixed color (must be that color). Output the count modulo 10⁹+7.

Constraints

1 ≤ N ≤ 10⁵, 0 ≤ K ≤ N.
Tree is connected (N−1 edges).
Time limit: 2s.

Key idea

Rooted tree DP. dp[v][c] = # ways to color the subtree of v with v colored c, respecting pre-assigned colors. For each child u, dp[v][c] *= Σ_{c' ≠ c} dp[u][c']. If v is pre-colored to c₀, set dp[v][c] = 0 for c ≠ c₀. Answer = Σ_c dp[root][c] mod p.

Complexity target

O(N · 3 · 2) = O(N).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007;

int N, K;
vector<vector<int>> g;
vector<int> fixc; // 0 = free, else 1/2/3
vector<array<ll,3>> dp;

void dfs(int u, int p) {
    for (int c = 0; c < 3; ++c) dp[u][c] = 1;
    for (int v : g[u]) if (v != p) {
        dfs(v, u);
        for (int c = 0; c < 3; ++c) {
            ll s = 0;
            for (int cc = 0; cc < 3; ++cc) if (cc != c) s += dp[v][cc];
            dp[u][c] = dp[u][c] * (s % MOD) % MOD;
        }
    }
    if (fixc[u]) {
        for (int c = 0; c < 3; ++c) if (c + 1 != fixc[u]) dp[u][c] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    g.assign(N + 1, {}); fixc.assign(N + 1, 0); dp.assign(N + 1, {0,0,0});
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a);
    }
    for (int i = 0; i < K; ++i) {
        int b, c; cin >> b >> c; fixc[b] = c;
    }
    dfs(1, 0);
    ll ans = (dp[1][0] + dp[1][1] + dp[1][2]) % MOD;
    cout << ans << "\n";
}

Pitfalls

Recursion depth. N = 10⁵ can blow a default 1 MB stack on a path-like tree. Either raise the stack (linker flag, or iterative DFS) or trust the judge's larger stack.
Forgetting the MOD on the inner sum. s can exceed MOD if you don't reduce before multiplying.
Pre-color conflict. If a fixed assignment violates the constraint among pre-colored neighbors, the DP returns 0 naturally — no special-case needed.
1-indexed nodes. Use size N+1 vectors.

Problem 3 — Haybale Feast

Statement

There are N haybales in a row. The i-th has flavor F_i and spiciness S_i. Choose a contiguous subarray whose total flavor is ≥ M; minimize the maximum spiciness in the chosen window. Output that minimum.

Constraints

1 ≤ N ≤ 10⁵.
1 ≤ M ≤ 10¹⁸.
1 ≤ F_i, S_i ≤ 10⁹.
Time limit: 2s.

Key idea

Two-pointer over the array: for each right endpoint r, advance l forward while sum(F[l..r]) ≥ M. The minimal window ending at r is [l−1..r] just before shrinking failed. Maintain the max of S in the current window with a monotonic deque (push S[r] from the back, popping any back ≤ S[r]; on pop from front, drop indices < l). Answer = min over r of deque front (max S in valid window).

Complexity target

O(N) with two pointers + monotonic deque.

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; ll M; cin >> N >> M;
    vector<ll> F(N), S(N);
    for (int i = 0; i < N; ++i) cin >> F[i] >> S[i];

    ll best = LLONG_MAX, sum = 0;
    int l = 0;
    deque<int> dq; // indices of S, decreasing
    for (int r = 0; r < N; ++r) {
        sum += F[r];
        while (!dq.empty() && S[dq.back()] <= S[r]) dq.pop_back();
        dq.push_back(r);
        while (sum - F[l] >= M) {       // shrink while still valid
            sum -= F[l];
            if (dq.front() == l) dq.pop_front();
            ++l;
        }
        if (sum >= M) best = min(best, S[dq.front()]);
    }
    cout << best << "\n";
}

Pitfalls

Shrink "while still valid", not "while invalid". Off-by-one on the two-pointer is the classic bug; the loop pre-checks sum − F[l] ≥ M.
M is huge. Use 64-bit for M and the running sum; N · max F = 10¹⁴.
Monotonic deque pops by index. When advancing l, check whether dq.front() is now stale (== old l).
Update best only when window is valid. The first few right endpoints may not yet hit M.

What Gold December 2017 was actually testing

P1 — layered/bipartite BFS with reversed edges. Recognize "shortest chain to a sink" → multi-source BFS from sinks.
P2 — tree DP with constraints. Classic 3-coloring count with pre-fixed nodes pinned to zero out alternatives.
P3 — two pointers + monotonic deque. The standard "min over windows whose feature ≥ X" trick; appears almost every contest.