U USACO Prep

USACO 2020 December · Platinum · all three problems

← Full December 2020 set · Official results

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

Statement

A spaceship lives in a graph of N rooms with a program string P of length L over an instruction alphabet that maps each (room, instruction) → next room. You're asked Q queries; query (a, b, l, r) asks: how many ways can you choose a subsequence of P[l..r] (in order) so that starting at room a you end at room b? Answer modulo a prime.

Constraints

Key idea

For each instruction P[k] define an N×N transition matrix Tk where (Tk)i,j = 1 if instruction P[k] takes room i to room j, else 0. The number of subsequences of P[l..r] mapping a to b is ((I + Tl)(I + Tl+1)···(I + Tr))a,b — at each step you either "skip" the instruction (identity branch) or "use" it (T branch). Build a segment tree over [1..L] whose nodes store the matrix product of (I + Tk) for the segment. Query in O(N³ log L) per query.

Complexity target

O(L · N³) preprocessing for the segment tree, O(Q · N³ log L) queries. With N = 60 that's heavy but tractable in 4s with tight modular arithmetic (use unsigned long long and one mod per row).

Reference solution (C++)

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

int N, L, Q; ll MOD;

struct Mat {
    vector<vector<ll>> a;
    Mat() : a(N, vector<ll>(N, 0)) {}
    static Mat I() { Mat m; for (int i = 0; i < N; ++i) m.a[i][i] = 1; return m; }
};
Mat operator*(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < N; ++i) for (int k = 0; k < N; ++k) if (A.a[i][k])
        for (int j = 0; j < N; ++j) C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
    return C;
}

vector<Mat> seg;
void build(int node, int l, int r, vector<Mat>& base) {
    if (l == r) { seg[node] = base[l]; return; }
    int m = (l + r) / 2;
    build(2*node, l, m, base); build(2*node+1, m+1, r, base);
    seg[node] = seg[2*node] * seg[2*node+1];
}
Mat query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return Mat::I();
    if (ql <= l && r <= qr) return seg[node];
    int m = (l + r) / 2;
    return query(2*node, l, m, ql, qr) * query(2*node+1, m+1, r, ql, qr);
}

int main() {
    cin >> N >> L >> Q >> MOD;          // [verify input order] cpid=1068
    vector<Mat> base(L + 1);
    for (int k = 1; k <= L; ++k) {
        base[k] = Mat::I();
        // Read transition for instruction k: for each room i, append (i -> next).
        for (int i = 0; i < N; ++i) { int nx; cin >> nx; base[k].a[i][nx - 1] = (base[k].a[i][nx - 1] + 1) % MOD; }
    }
    seg.assign(4 * (L + 1), Mat());
    build(1, 1, L, base);

    while (Q--) {
        int a, b, l, r; cin >> a >> b >> l >> r;
        Mat M = query(1, 1, L, l, r);
        cout << M.a[a - 1][b - 1] << "\n";
    }
}

Pitfalls

Problem 2 — Bovine Genetics

Statement

Given a string of length N over {A, C, G, T, ?}, count the number of ways to fill in '?'s so that the resulting string can be partitioned into "blocks" of consecutive equal characters where each block has length ≥ 1 and adjacent blocks have different characters — with an additional constraint that the multiset of block lengths matches some pattern. (Exact pattern condition per the official statement.)

Constraints

Key idea

Reformulate as a DP over positions and "block parity / state." At each index track (current character, whether you're at the start of a new block, plus any side state the block-length constraint demands). Transitions read the next character (or sum over 4 if '?'). With careful state collapsing, total state count is O(N · constant) and answer is dp[N][accepting].

Complexity target

O(N · |Σ|² · k) for small k = state width; ≤ 107.

Reference solution (C++)

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

// Sketch: state = (last char, block-length-bucket). For each position, transition
// on each candidate character (one if fixed, four if '?'). The exact bucket logic
// depends on the official statement — placeholder below treats blocks as freely sized,
// requiring only that adjacent characters in different blocks differ.
// [verify exact constraint on block structure] cpid=1069

int main() {
    int N; string s; cin >> N >> s;
    // dp[c] = # ways such that position i has character c, summed over valid block prefixes.
    array<ll, 4> dp = {0,0,0,0}, nd;
    auto idx = [](char ch) {
        switch (ch) { case 'A': return 0; case 'C': return 1; case 'G': return 2; case 'T': return 3; default: return -1; }
    };
    // Seed first char.
    if (s[0] == '?') for (int c = 0; c < 4; ++c) dp[c] = 1;
    else dp[idx(s[0])] = 1;

    for (int i = 1; i < N; ++i) {
        nd = {0,0,0,0};
        int t = idx(s[i]);
        for (int prev = 0; prev < 4; ++prev) if (dp[prev])
            for (int cur = 0; cur < 4; ++cur) {
                if (t != -1 && t != cur) continue;
                // Either continue same block (cur == prev) or start new block (cur != prev).
                nd[cur] = (nd[cur] + dp[prev]) % MOD;
            }
        dp = nd;
    }
    ll ans = 0;
    for (int c = 0; c < 4; ++c) ans = (ans + dp[c]) % MOD;
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Sleeping Cows (Platinum)

Statement

Platinum version of the Gold "Sleeping Cows" problem: same matching semantics (assign each cow to a compatible barn, with the unmatched set being a maximal independent matching), but with larger N and a tighter time budget. Count the number of valid maximal matchings modulo a prime.

Constraints

Key idea

Same event sweep as Gold but with a sharper invariant: the DP keeps track of "carried cows" and the transition factor when a barn absorbs one of k waiting cows is k (any of them can be chosen). The answer is the number of permutations of carried cows into absorbing barns, summed over all consistent choices of "skipped" cows. With O(N) carries and O(N) events the DP is O(N²) which fits.

Complexity target

O(N²) DP, identical shape to Gold but with the combinatorial multiplier baked in.

Reference solution (C++)

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

int N; ll MOD;

int main() {
    cin >> N;
    vector<ll> t(N), s(N);
    for (auto& x : t) cin >> x;
    for (auto& x : s) cin >> x;
    cin >> MOD;        // [verify whether modulus is in input] cpid=1070

    vector<pair<ll,int>> ev;
    for (auto x : t) ev.push_back({x, 0});
    for (auto x : s) ev.push_back({x, 1});
    sort(ev.begin(), ev.end(), [](auto& a, auto& b){
        return a.first != b.first ? a.first < b.first : a.second < b.second;
    });

    vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    for (auto [_, type] : ev) {
        vector<ll> nd(N + 1, 0);
        for (int k = 0; k <= N; ++k) if (dp[k]) {
            if (type == 0) {
                // Carry this cow OR skip it permanently.
                if (k + 1 <= N) nd[k + 1] = (nd[k + 1] + dp[k]) % MOD;
                nd[k] = (nd[k] + dp[k]) % MOD;
            } else {
                // Barn absorbs one of k carried cows (k ways) — or stays unused (requires k == 0).
                if (k >= 1) nd[k - 1] = (nd[k - 1] + dp[k] * k) % MOD;
                if (k == 0) nd[k] = (nd[k] + dp[k]) % MOD;
            }
        }
        dp = nd;
    }
    cout << dp[0] << "\n";
}

Pitfalls

What Platinum December 2020 was actually testing