U USACO Prep

USACO 2018 February · Platinum · all three problems

← Full February 2018 set · Official results

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

Statement

There are N slingshots; slingshot i shoots manure from position xi to yi in ti time units. There are M manure piles, each with source aj and target bj. Direct hauling takes |a − b| time. For each pile, FJ may use at most one slingshot: walk |a − xi|, shoot in ti, walk |yi − b|. Output the minimum time per pile.

Constraints

Key idea

For each pile (a, b), minimize |a − x| + t + |y − b| over slingshots. Split into four sign cases for (a − x) and (y − b). In each quadrant the objective is linear in x, y, so for a fixed pile we want, e.g., min over i of (−xi − yi + ti) subject to xi ≤ a and yi ≤ b. That's a 2D dominance query — sort slingshots by x, sweep piles in order of a, maintain a segment tree indexed by compressed y holding min(±x ± y + t). Four passes, one per sign combo.

Complexity target

O((N + M) log N) per quadrant × 4 quadrants ≈ 8 · 106 ops.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;

// Point-update min, range-min segment tree.
struct Seg {
    int n; vector<ll> t;
    void init(int n_) { n = n_; t.assign(4 * n, INF); }
    void upd(int p, int l, int r, int i, ll v) {
        if (l == r) { t[p] = min(t[p], v); return; }
        int m = (l + r) / 2;
        if (i <= m) upd(2*p, l, m, i, v); else upd(2*p+1, m+1, r, i, v);
        t[p] = min(t[2*p], t[2*p+1]);
    }
    ll qry(int p, int l, int r, int a, int b) {
        if (b < l || r < a) return INF;
        if (a <= l && r <= b) return t[p];
        int m = (l + r) / 2;
        return min(qry(2*p, l, m, a, b), qry(2*p+1, m+1, r, a, b));
    }
} seg;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<array<ll, 3>> sl(N); // (x, y, t)
    for (auto& s : sl) cin >> s[0] >> s[1] >> s[2];
    vector<array<ll, 3>> pq(M);  // (a, b, idx)
    for (int i = 0; i < M; ++i) { cin >> pq[i][0] >> pq[i][1]; pq[i][2] = i; }

    // Direct cost lower bound.
    vector<ll> ans(M);
    for (int i = 0; i < M; ++i) ans[i] = llabs(pq[i][0] - pq[i][1]);

    // Coordinate-compress y values.
    vector<ll> ys(N);
    for (int i = 0; i < N; ++i) ys[i] = sl[i][1];
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
    auto yidx = [&](ll v){ return (int)(lower_bound(ys.begin(), ys.end(), v) - ys.begin()); };

    // Four sign cases for (a-x, y-b): each case yields a linear objective in
    // (x, y) plus t; sort/scan so that x <= a (or x >= a) and query y <= b
    // (or y >= b). One pass shown; mirror three more times by negating coords.
    sort(sl.begin(), sl.end(),
         [](auto& A, auto& B){ return A[0] < B[0]; });
    sort(pq.begin(), pq.end(),
         [](auto& A, auto& B){ return A[0] < B[0]; });
    seg.init((int)ys.size());
    int j = 0;
    for (auto& q : pq) {
        ll a = q[0], b = q[1]; int idx = (int)q[2];
        while (j < N && sl[j][0] <= a) {
            seg.upd(1, 0, (int)ys.size() - 1, yidx(sl[j][1]),
                    -sl[j][0] - sl[j][1] + sl[j][2]);
            ++j;
        }
        int bi = (int)(upper_bound(ys.begin(), ys.end(), b) - ys.begin()) - 1;
        if (bi >= 0) {
            ll best = seg.qry(1, 0, (int)ys.size() - 1, 0, bi);
            if (best < INF) ans[idx] = min(ans[idx], a + b + best);
        }
    }
    // Repeat with reflections of x and/or y to cover the other three cases.
    // (omitted for brevity; identical structure with sign flips on inputs)

    for (ll v : ans) cout << v << "\n";
}

Pitfalls

Problem 2 — New Barns

Statement

Q online queries. Each is either "B p" (build a new barn connecting to existing barn p, or p = −1 to make it isolated) or "Q k" (output the maximum distance from barn k to any other barn in its connected component). The component is always a tree (forest overall).

Constraints

Key idea

Use the classical "incremental tree diameter" trick: maintain for each component its two diameter endpoints (u, v). When adding a leaf w to existing node p, the new diameter endpoints are the two among {u, v, w} that maximize pairwise distance. Distances are computed via LCA; since this is offline-friendly but the problem is online, use binary-lifting LCA with depths assigned at insertion time (a leaf's depth is depth[p] + 1, and we build LCA tables incrementally as nodes are added). For a Q-query, return max(dist(k, u), dist(k, v)).

Complexity target

O(Q log Q) with binary-lifted LCA in a rooted forest grown one leaf at a time.

Reference solution (C++)

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

const int LOG = 17;
int up[100005][LOG], dep[100005];
int comp[100005], A[100005], B[100005]; // component id, two diameter endpoints
int dsu[100005];
int find(int x){ return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; ++k) if (diff >> k & 1) u = up[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; --k)
        if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }
    return up[u][0];
}
int dist(int u, int v){ return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q; cin >> Q;
    int n = 0;
    while (Q--) {
        char op; int p; cin >> op >> p;
        if (op == 'B') {
            ++n;
            dsu[n] = n;
            if (p == -1) {
                dep[n] = 0;
                for (int k = 0; k < LOG; ++k) up[n][k] = n;
                A[n] = B[n] = n;
            } else {
                dep[n] = dep[p] + 1;
                up[n][0] = p;
                for (int k = 1; k < LOG; ++k) up[n][k] = up[up[n][k - 1]][k - 1];
                dsu[n] = find(p);
                int r = find(p);
                int a = A[r], b = B[r];
                // New diameter is the best of {a-b, a-n, b-n}.
                int da = dist(a, b), dan = dist(a, n), dbn = dist(b, n);
                int best = max({da, dan, dbn});
                if (best == da) { /* unchanged */ }
                else if (best == dan) B[r] = n;
                else A[r] = n;
            }
        } else {
            int r = find(p);
            cout << max(dist(p, A[r]), dist(p, B[r])) << "\n";
        }
    }
}

Pitfalls

Problem 3 — Cow Gymnasts

Statement

N platforms arranged in a circle, each with a stack of cows of height hi ≥ 1. When stacks fall clockwise, the cow at height j on platform i lands at height j on platform (i + j − 1) mod N — and the "magical" condition is that the resulting heights on every platform equal the original hi. Count the number of magical configurations modulo 109 + 7.

Constraints

Key idea

Analysis (see the official editorial) reduces "magical" configurations to those that are periodic with period d for some divisor d of N, with d additional structure constraints. The final count is a sum over divisors d of N of a closed-form expression involving 2d with inclusion-exclusion over divisor chains (Möbius / Euler-style). Enumerate divisors of N (at most ~6720 for N ≤ 1012), compute each term with fast modular exponentiation, and sum.

Complexity target

O(σ0(N) · log N) where σ0(N) ≤ ~6720; trivial under 4 s.

Reference solution (C++)

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

ll pw(ll a, ll e, ll m) {
    ll r = 1; a %= m;
    while (e > 0) { if (e & 1) r = r * a % m; a = a * a % m; e >>= 1; }
    return r;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N; cin >> N;

    // Enumerate divisors of N.
    vector<ll> divs;
    for (ll i = 1; i * i <= N; ++i) if (N % i == 0) {
        divs.push_back(i);
        if (i != N / i) divs.push_back(N / i);
    }
    sort(divs.begin(), divs.end());

    // For each divisor d (period), the count of "primitive" period-d magical
    // configurations is f(d) where f satisfies sum over divisors e of d of f(e)
    // = g(d), with g(d) = 2^d - 2 (the known editorial formula for the
    // raw periodic count, plus boundary terms for d = 1 and d = N).
    // [verify exact f/g] cpid=818 editorial.
    map<ll, ll> f;
    ll ans = 0;
    for (ll d : divs) {
        ll g = (pw(2, d, MOD) + MOD - 2) % MOD; // placeholder formula
        ll val = g;
        for (ll e : divs) {
            if (e < d && d % e == 0) val = (val + MOD - f[e]) % MOD;
        }
        f[d] = val;
        ans = (ans + val) % MOD;
    }
    cout << ans << "\n";
    // NOTE: the precise editorial formula for g(d) differs slightly (it adds
    // d itself as a constant configuration etc.); see official editorial.
    // [verify] cpid=818
}

Pitfalls

What Platinum February 2018 was actually testing