U USACO Prep

USACO 2020 February · Gold · all three problems

← Full February 2020 set · Official results

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

Statement

N events occur. Event i is initially known to happen no earlier than day si. There are C additional constraints: event b happens at least g days after event a (sb ≥ sa + g). Compute the earliest day for each event consistent with both the lower bounds and the constraints.

Constraints

Key idea

Each constraint is a directed edge a → b of weight g, meaning ans[b] ≥ ans[a] + g. Combined with ans[i] ≥ si, this is a longest-path-on-a-DAG problem. Topologically sort; relax in order: ans[b] = max(ans[b], ans[a] + g). Initial ans[i] = si.

Complexity target

O(N + C). Kahn's algorithm or DFS-based topo sort.

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, C; cin >> N >> C;
    vector<ll> s(N);
    for (auto& x : s) cin >> x;
    vector<vector<pair<int, int>>> g(N);
    vector<int> indeg(N, 0);
    for (int i = 0; i < C; ++i) {
        int a, b, w; cin >> a >> b >> w; --a; --b;
        g[a].push_back({b, w});
        ++indeg[b];
    }
    queue<int> q;
    for (int i = 0; i < N; ++i) if (indeg[i] == 0) q.push(i);
    vector<ll> ans = s;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : g[u]) {
            ans[v] = max(ans[v], ans[u] + w);
            if (--indeg[v] == 0) q.push(v);
        }
    }
    for (ll x : ans) cout << x << "\n";
}

Pitfalls

Problem 2 — Help Yourself

Statement

Given N closed intervals on the real line, for every subset S of intervals let f(S) be the number of connected components of the union of intervals in S (empty subset has 0). Compute the sum of f(S) over all 2N subsets, mod 109+7.

Constraints

Key idea

Sort intervals by left endpoint. The contribution of interval i to ΣF is the number of subsets where it "starts a new component" — i.e. all intervals j < i (in sort order) with rj ≥ li must be absent. If ci = number of earlier intervals overlapping li, then interval i contributes 2N − 1 − ci subsets (the ci overlappers must be excluded; i itself must be present; the other N − 1 − ci are free). Sum these powers of two.

Complexity target

O(N log N) sort + O(N) sweep + O(N) precomputed pow2.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<pair<int, int>> iv(N);
    for (auto& [l, r] : iv) cin >> l >> r;
    sort(iv.begin(), iv.end()); // by l ascending

    // For each i, count c_i = #{ j < i : r_j >= l_i }. Equivalently,
    // among the first i-1 right endpoints, how many are >= l_i.
    // Use a multiset of r-values; remove r's that fell below l_i as we sweep.
    // Easier: sort r's of first i-1 intervals and binary-search. But that's O(N^2).
    // Smarter: process intervals in order of l; maintain a Fenwick/BIT over r-coords,
    // or just use a sorted multiset and binary-search count_above(l_i).
    vector<ll> pw(N + 1, 1);
    for (int i = 1; i <= N; ++i) pw[i] = pw[i - 1] * 2 % MOD;

    multiset<int> rs;
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        auto [l, r] = iv[i];
        // c_i = #{ r in rs : r >= l }.
        int c = distance(rs.lower_bound(l), rs.end());
        ans = (ans + pw[N - 1 - c]) % MOD;
        rs.insert(r);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Delegation

Statement

A tree with N nodes. For each K from 1 to N−1, decide whether the N−1 edges can be partitioned into edge-disjoint paths each of length exactly K. Output an N−1 character string of 0/1.

Constraints

Key idea

Necessary condition: K | (N−1). For each such K, root the tree and at each vertex collect the lengths of "pending" path-stubs from each child subtree. Greedily pair stubs whose lengths sum to K (so they form one complete path through v); each subtree may contribute at most one unpaired stub, which becomes the stub passed up. If at any vertex more than one stub remains unpaired (root: zero must remain), K fails.

Complexity target

O(N log N) per valid K, summed over K | (N−1) is O(N · σ0(N−1) · log N) — well within 2s.

Reference solution (C++)

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

int N;
vector<vector<int>> g;
int K_;

// Returns the unmatched stub length passed up to the parent, or -1 if infeasible.
// "Stub length" includes the edge from this node to its parent (added by caller).
int dfs(int u, int par) {
    multiset<int> lens;
    for (int v : g[u]) if (v != par) {
        int s = dfs(v, u);
        if (s < 0) return -1;
        if (s > 0) lens.insert(s + 1); // add the edge (u,v) to the child's stub
    }
    // Pair stubs: for each s in lens, look for (K_ - s) elsewhere.
    int leftover = -1; // length of the at-most-one unmatched stub
    while (!lens.empty()) {
        int x = *lens.begin(); lens.erase(lens.begin());
        if (x > K_) return -1;
        if (x == K_) continue; // completes a path entirely below u
        auto it = lens.find(K_ - x);
        if (it != lens.end()) { lens.erase(it); continue; }
        // x cannot be paired; must become the leftover passed up.
        if (leftover != -1) return -1;
        leftover = x;
    }
    if (u == 0) return (leftover == -1 ? 0 : -1); // root must have nothing
    return (leftover == -1 ? 0 : leftover);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    g.assign(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);
    }
    string out;
    for (int K = 1; K <= N - 1; ++K) {
        if ((N - 1) % K) { out += '0'; continue; }
        K_ = K;
        out += (dfs(0, -1) == 0 ? '1' : '0');
    }
    cout << out << "\n";
}

Pitfalls

What Gold February 2020 was actually testing