U USACO Prep

USACO 2021 February · Platinum · all three problems

← Full February 2021 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=feb21results. 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 — No Time to Dry

Statement

Bessie has a 1D canvas of N segments with desired colours c1..cN (1 to N, lighter is smaller). A stroke paints a contiguous range with a single colour, but she cannot paint a lighter colour over a darker one. For each of Q queries [a, b], find the minimum number of strokes needed to paint segments a..b to their target colours (segments outside [a, b] don't matter).

Constraints

Key idea

The answer for [a, b] equals the number of distinct colours that appear in c[a..b] with the twist that runs of the same colour can be painted in one stroke — but only when there is no strictly smaller (lighter) colour strictly between two equal-colour positions. Formally, define next[i] = smallest j > i with c[j] = c[i], provided min(c[i+1..j-1]) ≥ c[i]; else next[i] = ∞. Then the answer = (b − a + 1) − #{i ∈ [a, b−1] : c[i] == c[i+1] or next[i] ≤ b with all values in (i, next[i]] ≥ c[i]}. Offline sweep with a segment tree of "active prev-pointers" and Mo-style answering, or directly: sort queries by b, scan i = 1..N maintaining a Fenwick of indicator-at-prev[i] when prev[i] is "still mergeable", and answer each query b by range-sum on [a, b]. Standard O((N + Q) log N).

Complexity target

O((N + Q) log N) with a Fenwick tree.

Reference solution (C++)

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

struct BIT {
    int n; vector<int> f;
    BIT(int n) : n(n), f(n + 2, 0) {}
    void upd(int i, int v) { for (++i; i <= n; i += i & -i) f[i] += v; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += f[i]; return s; }
    int range(int l, int r) { return sum(r) - (l ? sum(l - 1) : 0); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vector<int> c(N);
    for (auto& x : c) cin >> x;

    // prev[i] = largest j < i with c[j] == c[i] and min(c[j+1..i-1]) >= c[i]; else -1.
    // We compute it by sweeping with a monotonic stack per colour.
    vector<int> prev(N, -1);
    vector<int> lastIdx(N + 1, -1);
    // Stack of indices with strictly increasing colour values; while top has
    // colour > c[i], pop (those can no longer reach a same-colour predecessor
    // because c[i] sits between them as a smaller value).
    stack<int> st;
    for (int i = 0; i < N; ++i) {
        while (!st.empty() && c[st.top()] > c[i]) {
            lastIdx[c[st.top()]] = -1;   // invalidate same-colour bookkeeping
            st.pop();
        }
        if (lastIdx[c[i]] != -1 && (st.empty() || c[st.top()] >= c[i]))
            prev[i] = lastIdx[c[i]];
        lastIdx[c[i]] = i;
        st.push(i);
    }

    // Offline: sort queries by right endpoint, answer with Fenwick on prev[].
    vector<tuple<int,int,int>> qs(Q);
    for (int i = 0; i < Q; ++i) { int a, b; cin >> a >> b; --a; --b; qs[i] = {b, a, i}; }
    sort(qs.begin(), qs.end());

    BIT bit(N);
    vector<int> ans(Q);
    int idx = 0;
    for (auto [b, a, qi] : qs) {
        while (idx <= b) {
            if (prev[idx] != -1) bit.upd(prev[idx], 1);
            ++idx;
        }
        int mergeable = bit.range(a, b);
        ans[qi] = (b - a + 1) - mergeable;
    }
    for (int v : ans) cout << v << "\n";
}
// [verify edge cases on prev[] when equal colours surround a smaller value]
//   https://usaco.org/index.php?page=viewproblem2&cpid=1116

Pitfalls

Problem 2 — Minimizing Edges

Statement

Given a connected undirected graph G on N vertices, define fG(a, b) = true iff there is a walk from vertex 1 to vertex a using exactly b edges (with repetition allowed; self-loops permitted, no parallel edges). Build a graph G' on the same vertex set with fG' ≡ fG, minimising the number of edges of G'. Output that minimum count.

Constraints

Key idea

fG(a, b) depends only on (i) the BFS distance d(1, a) from vertex 1 and (ii) whether the component containing a has an odd cycle reachable on or before reaching a (parity-mixing). Hence the minimum G' is built from BFS layers L0, L1, … from vertex 1: for every vertex v ∈ Lk (k ≥ 1) add one edge to some vertex in Lk−1 — that's N−1 edges, the BFS tree. Then for each vertex a where odd-walks of length d(1, a) + 1, d(1, a) + 3, … must also be achievable, add a self-loop at some vertex in Lk (or an intra-layer edge) iff the original component had an odd cycle reachable to that layer. The bookkeeping is BFS + parity check; the count of required odd-loops is the number of distinct "odd-reachable layer regions".

Complexity target

O(N + M) per test using BFS and a single parity-flag DSU/scan.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        vector<vector<int>> g(N + 1);
        bool hasSelfLoop = false;
        for (int i = 0; i < M; ++i) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            if (u != v) g[v].push_back(u);
            else hasSelfLoop = true;
        }
        // BFS from 1 to compute layers; detect odd cycles by finding an edge
        // joining two vertices in the same layer.
        vector<int> dist(N + 1, -1);
        dist[1] = 0;
        queue<int> q; q.push(1);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
        // Count "earliest odd-mix depth": smallest layer that admits an odd walk.
        int firstOddLayer = INT_MAX;
        for (int u = 1; u <= N; ++u)
            for (int v : g[u])
                if (u == v) firstOddLayer = min(firstOddLayer, dist[u]);
                else if (dist[u] == dist[v]) firstOddLayer = min(firstOddLayer, dist[u]);

        // Minimum edges = (N - 1) BFS-tree edges, plus 1 self-loop if any odd
        // cycle is reachable from vertex 1 at all.
        long long answer = (long long)(N - 1);
        if (firstOddLayer != INT_MAX) answer += 1;
        cout << answer << "\n";
    }
}
// [verify the "single self-loop suffices" claim for all reachable a;
//  the editorial discusses cases where intra-layer edges are mandatory]
//   https://usaco.org/index.php?page=viewproblem2&cpid=1117

Pitfalls

Problem 3 — Counting Graphs

Statement

With the same fG(a, b) as in Problem 2, count the number of distinct simple graphs G' on the same N vertices (self-loops permitted, no parallel edges) such that fG' ≡ fG, modulo 109+7.

Constraints

Key idea

From Problem 2 we know G' is parameterised by: a BFS-tree (each non-root vertex picks any parent one layer higher) plus optional intra-layer / self-loop edges that don't change parity-reachability. Group vertices by (layer, parity-of-odd-reachability). For each non-root vertex of layer k, count the number of choices of "edges into layer k−1 or k" that preserve f. With layer sizes s0, s1, … and odd-reach pattern, the answer factorises as a product over layers of (combinatorial factors involving 2sk·sk-1 minus invalid subsets). Compute modulo 109+7.

Complexity target

O(N² + M) per test, dominated by layer-pair enumeration.

Reference solution (C++)

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

ll powmod(ll a, ll e, ll m = MOD) {
    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 T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        vector<vector<int>> g(N + 1);
        for (int i = 0; i < M; ++i) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            if (u != v) g[v].push_back(u);
        }
        // BFS layers from vertex 1.
        vector<int> dist(N + 1, -1);
        dist[1] = 0;
        queue<int> q; q.push(1);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
        }
        // Layer sizes.
        int maxL = 0;
        for (int i = 1; i <= N; ++i) maxL = max(maxL, dist[i]);
        vector<int> sz(maxL + 1, 0);
        for (int i = 1; i <= N; ++i) ++sz[dist[i]];

        // Sketch product: each layer-k vertex chooses a nonempty subset of layer
        // (k-1) parents — (2^{sz[k-1]} - 1)^{sz[k]} — times the free choice of
        // intra-layer / odd-loop edges consistent with f. This is the structural
        // skeleton; the precise factor needs the per-layer odd-parity flag.
        ll ans = 1;
        for (int k = 1; k <= maxL; ++k) {
            ll base = (powmod(2, sz[k - 1]) - 1 + MOD) % MOD;
            ans = ans * powmod(base, sz[k]) % MOD;
        }
        cout << ans << "\n";
    }
}
// NOTE: this is a structural template. The full solution multiplies by extra
// factors that account for intra-layer edges and odd-cycle-injection points.
// See editorial. [verify] cpid=1118

Pitfalls

What Platinum February 2021 was actually testing