U USACO Prep

USACO 2018 January · Gold · all three problems

← Full January 2018 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan18results. 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 — MooTube (Gold)

Statement

Same setup as Silver MooTube — N videos forming a tree with weighted edges; two videos are K-similar if every edge on the path between them has weight ≥ K. Queries (K, v) ask for the count of videos K-similar to v. The Gold version raises N and Q substantially.

Constraints

Key idea

The Gold solution is the same offline DSU sweep as Silver: sort edges and queries by K descending, union endpoints whose weight ≥ current K, answer = component size of v minus 1. The Gold "twist" is mainly raised bounds, which kills any BFS-per-query approach (O(NQ) is 1010) and forces an O((N+Q) log (N+Q)) sweep.

Complexity target

O((N + Q) log (N + Q)).

Reference solution (C++)

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
    int f(int x) { while (x != p[x]) x = p[x] = p[p[x]]; return x; }
    void u(int a, int b) {
        a = f(a); b = f(b); if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a; sz[a] += sz[b];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vector<tuple<int,int,int>> edges(N - 1);  // (w, a, b)
    for (auto& [w,a,b] : edges) { cin >> a >> b >> w; --a; --b; }
    sort(edges.begin(), edges.end(), greater<>());

    vector<tuple<int,int,int>> qs(Q);          // (K, v, idx)
    for (int i = 0; i < Q; ++i) {
        int k, v; cin >> k >> v; --v;
        qs[i] = {k, v, i};
    }
    sort(qs.begin(), qs.end(), greater<>());

    DSU dsu(N);
    vector<int> ans(Q);
    int ei = 0;
    for (auto& [k, v, idx] : qs) {
        while (ei < (int)edges.size() && get<0>(edges[ei]) >= k) {
            dsu.u(get<1>(edges[ei]), get<2>(edges[ei]));
            ++ei;
        }
        ans[idx] = dsu.sz[dsu.f(v)] - 1;
    }
    for (int x : ans) cout << x << "\n";
}

Pitfalls

Problem 2 — Cow at Large (Gold)

Statement

The farm is a tree of N nodes; leaves are barn exits. Bessie starts at a given node s and tries to reach any leaf. Farmer John must place some number of farmers at nodes; every step, Bessie moves to an adjacent node and every farmer also moves to an adjacent node. Farmer John wins if some farmer occupies Bessie's node before she reaches a leaf (or simultaneously). Compute the minimum number of farmers needed.

Constraints

Key idea

Root the tree at s. For each node v, let ds(v) be its depth from s, and dL(v) be its distance to the nearest leaf in its subtree (computed by a leaf-distance BFS, then a tree pass). Bessie is intercepted at v if some farmer reaches v no later than Bessie does — equivalently the closest leaf strictly below v is at distance ≥ ds(v): farmers can sit on the leaf and walk up. So the "fatal" set is { v : dL(v) ≤ ds(v) }. The minimum number of farmers is the number of topmost such nodes — those v in the fatal set whose parent is not. Sum over the rooted tree.

Complexity target

O(N) BFS + one DFS / BFS.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, s; cin >> N >> s; --s;
    vector<vector<int>> g(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        g[a].push_back(b); g[b].push_back(a);
    }

    // Multi-source BFS from leaves: dL[v] = distance to nearest leaf.
    vector<int> dL(N, INT_MAX), parent(N, -1), dS(N, 0), order;
    queue<int> q;
    for (int i = 0; i < N; ++i) if ((int)g[i].size() <= 1) { dL[i] = 0; q.push(i); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (dL[v] > dL[u] + 1) { dL[v] = dL[u] + 1; q.push(v); }
    }

    // BFS from s to fix parent + dS.
    vector<char> seen(N, 0);
    q.push(s); seen[s] = 1; parent[s] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : g[u]) if (!seen[v]) {
            seen[v] = 1; parent[v] = u; dS[v] = dS[u] + 1; q.push(v);
        }
    }

    // Count "topmost fatal" nodes.
    long long ans = 0;
    for (int u : order) {
        if (u == s) continue;
        bool fatal = (dL[u] <= dS[u]);
        bool parentFatal = (parent[u] != s && parent[u] != -1) ? (dL[parent[u]] <= dS[parent[u]]) : false;
        // If s itself is "fatal" (a leaf), Bessie already caught — but problem
        // assumes s is not a leaf; otherwise answer is 0.
        if (fatal && !parentFatal) ++ans;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Stamp Painting

Statement

A length-N canvas starts blank. Bessie has K colors and a length-M stamp; each stamp paints a contiguous length-M run of one color on top of whatever is there (later stamps overwrite earlier). A final coloring c1,…,cN is "reachable" iff there is some sequence of stamps producing it. Output the number of reachable colorings modulo 109+7.

Constraints

Key idea

Claim: a coloring is reachable iff it has at least one run of M consecutive equal colors. (Sketch: if it does, that run was the last stamp; peel and induct. If it doesn't, the last stamp would have left an M-run.) Count complement: strings of length N over K colors with no run ≥ M. Let f(n) be that count. f(n) = Kn for n < M; for n ≥ M, f(n) = (K−1)·(f(n−1) + f(n−2) + … + f(n−M+1)). (Pick a run length 1..M−1 at the end with a fresh color.) Maintain a window sum in O(1) per step. Answer = KN − f(N) (mod p).

Complexity target

O(N), with O(M) initial window.

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 % m; a %= m; while (e) { 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);
    int N, M, K; cin >> N >> M >> K;

    // f(n) = strings of length n over K colors with NO run of length >= M.
    // For n < M: f(n) = K^n.
    // For n >= M: f(n) = (K-1) * (f(n-1) + f(n-2) + ... + f(n-M+1)).
    vector<ll> f(N + 1, 0);
    f[0] = 1 % MOD;
    ll windowSum = f[0];        // sum of f over last (M-1) entries we'll need
    // We'll keep windowSum = f[n-1] + ... + f[n-M+1] for the next computation.
    for (int n = 1; n <= N; ++n) {
        if (n < M) {
            f[n] = f[n - 1] * (K % MOD) % MOD;
        } else {
            f[n] = (K - 1 + MOD) % MOD * windowSum % MOD;
        }
        // Update windowSum: it should hold f[n] + f[n-1] + ... + f[n - M + 2]
        // (length M-1, ending at n) for the next iteration.
        windowSum = (windowSum + f[n]) % MOD;
        int drop = n - (M - 1);  // index to drop so window length stays M-1
        if (drop >= 0) windowSum = (windowSum - f[drop] + MOD) % MOD;
    }

    ll total = pw(K, N, MOD);
    ll ans = (total - f[N] + MOD) % MOD;
    cout << ans << "\n";
}

Pitfalls

What Gold January 2018 was actually testing