USACO 2016 December · Platinum · all three problems

← Full December 2016 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec16results. 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 — Lots of Triangles

Statement

Given N trees at distinct 2D integer positions with no three collinear, for each v in 0..N−3 count the number of triangles formed by 3 of the trees whose strict interior contains exactly v other trees.

Constraints

3 ≤ N ≤ 300.
Coordinates are integers up to 10⁶.
No three trees are collinear.
Time limit: 2s. Memory limit: 256 MB.

Key idea

There are C(N, 3) ≈ 4.5 · 10⁶ triangles. For each triangle compute its area (twice the signed cross product) and the number of trees strictly inside it. To count interior points fast, precompute for every ordered pair (i, j) the value A(i, j) = signed twice-area of triangle (i, j, O) summed over all trees O strictly above segment i→j (a "below-edge" counter). Then for a triangle (i, j, k) the count of trees in the interior is a signed sum of A(i,j) + A(j,k) + A(k,i), corrected so that only strictly interior points are counted (no three collinear means no edge points). The classical formulation uses the count of points strictly below each directed edge; combining three signed counts yields interior count in O(1) per triangle.

Complexity target

O(N³): precompute pair tables in N² · N = N³ = 2.7 · 10⁷, then a single O(N³) enumeration.

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

    // below[i][j] = number of trees k strictly below the directed line i->j
    // (i.e., cross(j-i, k-i) < 0). No three collinear, so no zero crosses.
    vector<vector<int>> below(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j) if (i != j)
        for (int k = 0; k < N; ++k) if (k != i && k != j) {
            ll cr = (x[j] - x[i]) * (y[k] - y[i])
                  - (y[j] - y[i]) * (x[k] - x[i]);
            if (cr < 0) below[i][j]++;
        }

    // For each triangle (i,j,k) in counterclockwise order the count of trees
    // strictly inside equals below[i][j] + below[j][k] + below[k][i] - (N - 3).
    // If the orientation flips we just compute the absolute interior count via
    // forcing CCW order by swapping j,k when the signed area is negative.
    vector<ll> ans(N, 0);
    for (int i = 0; i < N; ++i)
      for (int j = i + 1; j < N; ++j)
        for (int k = j + 1; k < N; ++k) {
            int a = i, b = j, c = k;
            ll cr = (x[b] - x[a]) * (y[c] - y[a])
                  - (y[b] - y[a]) * (x[c] - x[a]);
            if (cr < 0) swap(b, c);  // force CCW
            int inside = below[a][b] + below[b][c] + below[c][a] - (N - 3);
            if (inside >= 0 && inside <= N - 3) ans[inside]++;
        }
    for (int v = 0; v <= N - 3; ++v) cout << ans[v] << "\n";
}

Pitfalls

Orientation matters. The signed cross-product identity only works for a fixed (CCW) orientation; swap two vertices when the signed area is negative.
Subtract (N − 3). The three vertices themselves contribute to below sums; subtract their fixed contribution.
64-bit cross products. Coordinates up to 10⁶ give products up to 10¹².
Don't reinvent area-based point-in-triangle for each triangle. That's O(N⁴) = 8 · 10⁹ — TLE.

Problem 2 — Team Building

Statement

FJ has N cows with scores a_i; FP has M cows with scores b_j. Each picks an ordered team of K cows (sorted by score descending). FJ wins iff every one of his cows outscores FP's correspondingly ranked cow. Count, mod 10⁹+9, the number of pairs of size-K subsets for which FJ wins.

Constraints

1 ≤ N, M ≤ 1000, 1 ≤ K ≤ 10.
Scores fit in 32-bit integers.
Answer mod 1 000 000 009.
Time limit: 2s. Memory limit: 256 MB.

Key idea

Sort both score arrays descending. Process the merged event sequence with DP state (i, j, k) = number of ways to pick FJ's top-k cows from his first i cows and FP's top-k cows from his first j cows such that every pairing chosen so far is a win. Transitions: skip FJ's i-th cow, skip FP's j-th cow, or "couple" them as the next-ranked pair when a_i > b_j. The trick is the "next pair" couples the (k+1)-th cow from each side; coupling requires the FJ score to exceed the FP score that's getting matched. State count: 1001 · 1001 · 11 ≈ 1.1 · 10⁷.

Complexity target

O(N · M · K) ≈ 10⁷ updates, well under 2 s.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, K; cin >> N >> M >> K;
    vector<int> a(N), b(M);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end(), greater<int>());

    // dp[i][j][k] = ways to use first i FJ cows, first j FP cows, having
    // formed k winning pairs so far. We always consider the i-th FJ cow and
    // the j-th FP cow as the next candidates for the (k+1)-th ranked slot.
    vector dp(N + 1, vector(M + 1, vector<ll>(K + 1, 0)));
    dp[0][0][0] = 1;

    for (int i = 0; i <= N; ++i)
      for (int j = 0; j <= M; ++j)
        for (int k = 0; k <= K; ++k) if (dp[i][j][k]) {
            ll v = dp[i][j][k];
            // Option 1: skip FJ's next cow (don't put cow i+1 onto team).
            if (i < N) dp[i + 1][j][k] = (dp[i + 1][j][k] + v) % MOD;
            // Option 2: skip FP's next cow.
            if (j < M) dp[i][j + 1][k] = (dp[i][j + 1][k] + v) % MOD;
            // Option 3: couple FJ's cow i+1 with FP's cow j+1 as the (k+1)-th
            // ranked pair. Requires a[i] > b[j] (0-indexed inputs).
            if (i < N && j < M && k < K && a[i] > b[j])
                dp[i + 1][j + 1][k + 1] = (dp[i + 1][j + 1][k + 1] + v) % MOD;
        }

    cout << dp[N][M][K] << "\n";
}

Pitfalls

Mod is 10⁹+9, not 10⁹+7. Easy to wire the wrong constant.
Strict inequality. "FJ wins" means a > b at every rank — equality counts as a loss.
Sort both arrays descending. The DP assumes that you're picking the top-k of each subset in order.
State size. 1001 · 1001 · 11 · 8 bytes ≈ 90 MB — borderline; consider a 2D rolling layer or use 32-bit if memory is tight.

Problem 3 — Robotic Cow Herd

Statement

Bessie builds K distinct robotic cows. Each cow is a length-N sequence picking one microcontroller per location; location i has M_i choices with positive costs. The cost of a robot is the sum of chosen microcontrollers. Robots must be pairwise distinct. Find the minimum total cost of any K such robots.

Constraints

1 ≤ K ≤ 10⁵; 1 ≤ N ≤ 10⁵; sum M_i ≤ 10⁵.
1 ≤ M_i ≤ 10.
1 ≤ P_i,j ≤ 10⁸.
Time limit: 4s. Memory limit: 256 MB.

Key idea

For each location sort its prices ascending and convert them into deltas d_i,0 = 0, d_i,j = P_i,j − P_i,0. The cheapest robot picks the minimum at every location with total cost C₀ = Σ P_i,0. Every other robot has cost C₀ + Σ (added deltas). We need the K smallest sums of non-zero δ-selections over locations. Build a min-heap seeded with the cheapest non-zero δ from any single location; on each pop, push two successors: (a) advance to the next δ in the same location, (b) add the next location's first δ on top, plus a "replace" trick to avoid double counting. Locations with only one choice contribute nothing and can be skipped. This is the classic "K smallest sums via heap" technique.

Complexity target

O((Σ M + K) log K). Heap operations dominate; with the standard 3-successor scheme each pop yields at most a constant number of pushes.

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;
    // Read each location and build sorted delta arrays (skip d=0 baselines).
    vector<vector<ll>> d;
    ll base = 0;
    for (int i = 0; i < N; ++i) {
        int m; cin >> m;
        vector<ll> p(m);
        for (auto& v : p) cin >> v;
        sort(p.begin(), p.end());
        base += p[0];
        if (m == 1) continue;
        vector<ll> cur;
        for (int j = 1; j < m; ++j) cur.push_back(p[j] - p[0]);
        d.push_back(move(cur));
    }
    // Sort locations by their smallest delta ascending — heap is fed in that order.
    sort(d.begin(), d.end(), [](auto& A, auto& B){ return A[0] < B[0]; });
    int L = d.size();

    // Heap state: (current sum, location-index considered, delta-index at that loc).
    // From state (s, loc, idx) generate:
    //   replace : (s - d[loc][idx-1] + d[loc][idx], loc, idx+1) if idx+1 in range -- handled differently below
    // Standard "K smallest" enumeration:
    //   (s + d[loc+1][0] - d[loc][idx], loc+1, 0)  // jump to next location
    //   (s + d[loc+1][0], loc+1, 0)                 // also keep current loc's pick
    // We use the well-known 3-edge variant: replace current pick by next at same
    // loc, advance to next loc (discarding current), advance to next loc (keeping).
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    ll ans = base;  // Robot 0 = baseline.
    if (K == 1 || L == 0) { cout << ans << "\n"; return 0; }
    pq.emplace(d[0][0], 0, 0);
    for (int r = 1; r < K; ++r) {
        if (pq.empty()) break;  // ran out of distinct robots
        auto [s, loc, idx] = pq.top(); pq.pop();
        ans += s;
        // Next delta at same location (replace current pick).
        if (idx + 1 < (int)d[loc].size())
            pq.emplace(s - d[loc][idx] + d[loc][idx + 1], loc, idx + 1);
        // Advance to next location, discarding current pick.
        if (loc + 1 < L) {
            pq.emplace(s - d[loc][idx] + d[loc + 1][0], loc + 1, 0);
            // Advance to next location, KEEPING current pick (only from idx==0
            // to avoid duplicates).
            if (idx == 0) pq.emplace(s + d[loc + 1][0], loc + 1, 0);
        }
    }
    cout << ans << "\n";
}

Pitfalls

Deduping heap states. The "keep current pick when idx == 0" rule is the canonical fix for K-smallest-sum duplication; getting it wrong over-counts robots.
Discard zero-delta singletons. Locations with M = 1 only force the baseline; including them yields infinite zero-cost moves and breaks distinctness counting.
Sort locations by smallest non-zero delta. The heap descent assumes monotone "first delta" order.
64-bit answer. Up to 10⁵ · 10⁸ = 10¹³ per robot, summed over K = 10⁵ robots; use long long throughout.
Editorial cross-check. This problem has a notoriously tricky heap recurrence — verify against the official editorial.

What Platinum December 2016 was actually testing

P1 — N³ geometric counting. Precompute "points below a directed edge"; combine three signed counts per triangle for an O(N³) sweep.
P2 — 3D DP with skip/skip/match transitions. Sort both score arrays, then DP on (FJ index, FP index, pairs used).
P3 — K smallest sums via heap. Convert to delta arrays, run a deduped priority queue expansion over locations.