U USACO Prep

USACO 2018 December · Platinum · all three problems

← Full December 2018 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec18results. 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 — Balance Beam

Statement

Bessie stands on a balance beam at integer positions 0..N+1. At each interior position k ∈ [1, N] she can (a) jump off and collect f(k), or (b) flip a fair coin and move to k−1 or k+1 with probability 1/2 each. Reaching 0 or N+1 pays 0. Bessie plays optimally; for each starting position i ∈ [1, N], output ⌊105 · E[optimal payoff from i]⌋.

Constraints

Key idea

Let g(i) be the optimal expected payoff from position i. Then g(0) = g(N+1) = 0 and on the interior g(i) = max(f(i), (g(i−1) + g(i+1)) / 2). The set of points where it is optimal to stop forms the upper concave envelope of f(·) (and the endpoints 0). For i not on the hull, g is linear between adjacent hull stop-points; otherwise g(i) = f(i). Compute the upper convex hull of {(k, f(k)) : 0 ≤ k ≤ N+1} treating boundary as height 0, then interpolate linearly for non-hull points.

Complexity target

O(N) via a monotonic-stack upper-hull pass.

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> f(N + 2, 0);                 // f[0] = f[N+1] = 0
    for (int i = 1; i <= N; ++i) cin >> f[i];

    // Upper convex hull on (x, f[x]) for x = 0..N+1.
    // A point is on the hull iff stopping there beats the linear chord through
    // the surrounding hull points.
    vector<int> hull;
    auto cross = [&](int a, int b, int c) -> long long {
        // (b - a) x (c - a): positive => left turn
        ll x1 = b - a, y1 = f[b] - f[a];
        ll x2 = c - a, y2 = f[c] - f[a];
        return x1 * y2 - y1 * x2;
    };
    for (int i = 0; i <= N + 1; ++i) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), i) >= 0)
            hull.pop_back();
        hull.push_back(i);
    }
    // For each i in [1, N], find adjacent hull points and interpolate.
    int p = 0;
    for (int i = 1; i <= N; ++i) {
        while (hull[p + 1] < i) ++p;
        int L = hull[p], R = hull[p + 1];
        // E[payoff] = f[L] + (f[R] - f[L]) * (i - L) / (R - L)
        // Scale by 1e5 and floor.
        // Use 128-bit to avoid overflow: f up to 1e9, R-L up to 1e5.
        __int128 num = (__int128)f[L] * (R - L) * 100000
                     + (__int128)(f[R] - f[L]) * (i - L) * 100000;
        __int128 den = (__int128)(R - L) * 100000;
        // We want floor(1e5 * (f[L] + (f[R]-f[L])*(i-L)/(R-L)))
        __int128 numerator = (__int128)100000 * ( (__int128)f[L] * (R - L)
                            + (__int128)(f[R] - f[L]) * (i - L) );
        __int128 denominator = (R - L);
        ll ans = (ll)(numerator / denominator);
        cout << ans << "\n";
    }
}

Pitfalls

Problem 2 — Sort It Out

Statement

A permutation p[1..N] of 1..N. Choose a subset S of cow IDs and yell at them repeatedly in increasing ID order until p is sorted; the smallest such S has size N − LIS(p). Among all minimum-size sorting subsets, output the K-th lexicographically smallest one (as a sorted list of IDs, one per line, with the size on the first line).

Subtasks

Constraints

Key idea

Minimum non-yelled set is a longest increasing subsequence of p (the cows you don't yell at must already be in order). So min |S| = N − LIS. Output set = complement of one LIS. Lex-smallest output of S corresponds to lex-largest LIS by values; enumerate LIS extensions greedily, at each value branch multiplying ways using digit-DP-style counts on the LIS layer counts. Walk the K-th branch.

Complexity target

O(N log N) for the LIS structure plus O(N · L) traversal where L = LIS length, with big-integer-ish K capped at 1018.

Reference solution (C++)

// Sketch — full solution is > 50 lines; this is the LIS + counting skeleton.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll CAP = (ll)2e18;

int N; ll K;
vector<int> p;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    p.resize(N + 1);
    for (int i = 1; i <= N; ++i) cin >> p[i];

    // Compute LIS length L via patience sorting; lis[i] = length of LIS ending at i.
    vector<int> tails, lis(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        auto it = lower_bound(tails.begin(), tails.end(), p[i]);
        lis[i] = (it - tails.begin()) + 1;
        if (it == tails.end()) tails.push_back(p[i]); else *it = p[i];
    }
    int L = tails.size();

    // Bucket indices by lis-layer, in reverse i order, smallest p[i] first so
    // we can greedily pick lex-largest LIS values => lex-smallest complement.
    vector<vector<int>> layer(L + 2);
    for (int i = 1; i <= N; ++i) layer[lis[i]].push_back(i);

    // ways[i] = number of LISes extending from i to the end (going through layers
    // lis[i]+1..L), respecting i < j and p[i] < p[j]. Cap at CAP.
    vector<ll> ways(N + 2, 0);
    auto add = [&](ll& a, ll b){ a = min(CAP, a + b); };
    // ways for layer L = 1 each.
    for (int i : layer[L]) ways[i] = 1;
    for (int lvl = L - 1; lvl >= 1; --lvl)
        for (int i : layer[lvl])
            for (int j : layer[lvl + 1])
                if (j > i && p[j] > p[i]) add(ways[i], ways[j]);

    // Choose the K-th LIS by walking layer by layer, picking the smallest p[i]
    // (so the complement is lex-smallest) whose ways >= K.
    vector<bool> inLIS(N + 2, false);
    int prev_i = 0, prev_v = 0;
    for (int lvl = 1; lvl <= L; ++lvl) {
        // candidates in this layer with index > prev_i and value > prev_v,
        // sorted by p ascending (so smaller value picked first => complement small).
        vector<int> cand;
        for (int i : layer[lvl]) if (i > prev_i && p[i] > prev_v) cand.push_back(i);
        sort(cand.begin(), cand.end(), [&](int a, int b){ return p[a] < p[b]; });
        for (int i : cand) {
            if (ways[i] >= K) { inLIS[i] = true; prev_i = i; prev_v = p[i]; break; }
            K -= ways[i];
        }
    }
    // Output complement as sorted values.
    vector<int> out;
    for (int i = 1; i <= N; ++i) if (!inLIS[i]) out.push_back(p[i]);
    sort(out.begin(), out.end());
    cout << out.size() << "\n";
    for (int v : out) cout << v << "\n";
}

Pitfalls

Problem 3 — The Cow Gathering

Statement

A tree on N nodes plus M ordering constraints of the form "ai must leave before bi". Cows depart one by one; at every moment the remaining cows must form a connected subtree (i.e., the departing cow is always a leaf of the current induced subtree). For each cow i ∈ [1, N], output 1 if she can be the last cow to leave under some valid order respecting all constraints, else 0.

Constraints

Key idea

Fix any node r as the candidate "last". Then every other cow leaves before r, which forces every constraint edge a → b to point toward r in the tree rooted at r (otherwise b leaves before its required successor a along the path). Equivalently: root the tree at any node, then for each constraint a → b the path from b to a in the rooted tree determines a set of "forbidden roots". With careful DP on the tree (re-rooting + counting violated constraints per candidate root), a node is a valid last iff its violation count is 0. Topological feasibility itself is checked once by a Kahn-style BFS treating the leaves as removable nodes whose constraints are satisfied.

Complexity target

O((N + M) log N) using LCA + re-rooting; O(N + M) with subtree counting.

Reference solution (C++)

// Sketch — re-rooting violation count. Full solution + LCA is > 80 lines.
#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<vector<int>> G;
vector<int> parent, depth, tin, tout;
int timer = 0;
vector<vector<int>> up;  // binary lifting
int LOG;

void dfs(int u, int p) {
    parent[u] = p; tin[u] = timer++;
    up[0][u] = p;
    for (int k = 1; k < LOG; ++k) up[k][u] = up[k-1][ up[k-1][u] < 0 ? u : up[k-1][u] ];
    for (int v : G[u]) if (v != p) { depth[v] = depth[u] + 1; dfs(v, u); }
    tout[u] = timer++;
}

bool isAnc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }

int main() {
    cin >> N >> M;
    G.assign(N + 1, {});
    parent.assign(N + 1, 0); depth.assign(N + 1, 0);
    tin.assign(N + 1, 0); tout.assign(N + 1, 0);
    LOG = 1; while ((1 << LOG) < N) ++LOG;
    up.assign(LOG, vector<int>(N + 1, 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);
    }
    dfs(1, 0);

    // For each constraint a -> b ("a leaves before b"), candidate roots r for
    // which the constraint is satisfied are exactly the nodes "on b's side" when
    // the tree is split by the edge on the path from b toward a. Equivalently:
    // r is valid for this constraint iff a is on the path from b to r.
    // We accumulate +1 over the valid region using subtree difference arrays.
    vector<int> mark(N + 2, 0);  // sketch only; full impl uses Euler tour diffs
    // ... fill mark via LCA-based subtree increments ...

    // A node r is a valid "last" iff every constraint marks it -> total = M.
    for (int r = 1; r <= N; ++r)
        cout << (mark[r] == M ? 1 : 0) << "\n";
}

Pitfalls

What Platinum December 2018 was actually testing