U USACO Prep

USACO 2019 January · Gold · all three problems

← Full January 2019 set · Official results

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

Statement

Bessie has a permutation a1..N. She is about to perform exactly K "moves", each of which takes any cow currently in the line and re-inserts her anywhere (including the same spot). Count the number of distinct permutations of cows that could end up after exactly K moves, modulo 109+7.

Constraints

Key idea

A permutation is reachable in exactly K moves iff at least N − K of its elements were not moved (i.e. some N − K of the original positions remain in their original relative order). The set of "unmoved" cows forms an increasing subsequence relative to a; counting reachable permutations reduces to a sum over choices of the moved set, with placements of K moved cows into N slots. The closed form combines binomial coefficients: answer = Σj=0..K (−1)j C(N, K−j) · (N − K + j)j · …, computed with precomputed factorials.

Complexity target

O(N log MOD) including modular inverses for binomials; O(N + K) inner loop after factorial precompute.

Reference solution (C++)

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

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, K; cin >> N >> K;
    // (statement uses a permutation as input; for the count itself only N, K matter.)
    for (int i = 0, x; i < N; ++i) cin >> x;

    int M = N + 5;
    vector<ll> fact(M), inv(M);
    fact[0] = 1;
    for (int i = 1; i < M; ++i) fact[i] = fact[i - 1] * i % MOD;
    inv[M - 1] = pw(fact[M - 1], MOD - 2, MOD);
    for (int i = M - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
    auto C = [&](int n, int r) -> ll {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv[r] % MOD * inv[n - r] % MOD;
    };

    // Inclusion-exclusion over the "moved set" of size K (with repetition allowed
    // via choosing which K positions in the final sequence are the moved cows).
    ll ans = 0;
    for (int j = 0; j <= K; ++j) {
        ll term = C(N, K - j) % MOD * pw(N - K + j, j, MOD) % MOD;
        if (j & 1) ans = (ans - term + MOD) % MOD;
        else       ans = (ans + term) % MOD;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Shortcut

Statement

There are N fields connected by M bidirectional paths with travel times. Every evening each cow walks from the barn (field 1) to her own field along a shortest path; FJ knows ci cows live in field i. FJ may add a single zero-time "shortcut" of cost T from the barn to one chosen field; this creates an alternative path that cows will use only if it is at least as short as their current shortest. Choose the destination to maximize total time saved.

Constraints

Key idea

Run Dijkstra from the barn to get shortest distance dist[v] for every field. Among the shortest paths, build a "shortest-path forest" by preferring, for tie-breaking, the path that maximizes the sum of c along it (so we credit each cow's time savings to one specific path). For each field v with dist[v] > T, the saving if we connect v is c-subtree-of-v · (dist[v] − T). Pick the max. Subtree c-sums come from a topological sort over the DAG of shortest-path predecessors (process nodes in decreasing dist order).

Complexity target

O((N + M) log N) for Dijkstra + O(N + M) for the DAG aggregation.

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, M, T; cin >> N >> M >> T;
    vector<ll> c(N + 1);
    for (int i = 1; i <= N; ++i) cin >> c[i];
    vector<vector<pair<int,int>>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<ll> dist(N + 1, LLONG_MAX);
    vector<int> parent(N + 1, 0);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[1] = 0; pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : g[u]) {
            ll nd = d + w;
            // Tie-break: prefer parent with smaller index, deterministic.
            if (nd < dist[v] || (nd == dist[v] && u < parent[v])) {
                dist[v] = nd;
                parent[v] = u;
                pq.push({nd, v});
            }
        }
    }

    // Aggregate c up the shortest-path tree.
    vector<ll> sub = c;
    vector<int> order(N);
    iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(), [&](int a, int b) { return dist[a] > dist[b]; });
    for (int u : order) if (u != 1 && parent[u]) sub[parent[u]] += sub[u];

    ll best = 0;
    for (int v = 2; v <= N; ++v) if (dist[v] > T) best = max(best, sub[v] * (dist[v] - T));
    cout << best << "\n";
}

Pitfalls

Problem 3 — Cow Poetry

Statement

There are N words; word i has si syllables and rhyme class ci. A poem has M lines, each with exactly K syllables, and the lines must follow a given rhyme scheme (e.g. ABBA): lines with the same letter must end on words from the same rhyme class. Count the number of valid poems modulo 109+7.

Constraints

Key idea

(1) Knapsack DP: ways[j] = number of ways to fill a line of exactly j syllables using word multiset (with repetition). For each j with j == K, we know how many lines end on each word — specifically ends[w] = ways[K − sw]. Aggregate endClass[c] = Σ ends[w] for words w with class c. (2) For each rhyme group of size t (number of lines that share a letter), the number of choices is Σc endClass[c]t. The total poem count is the product over rhyme groups of these sums. Multiply, take mod.

Complexity target

O(N · K) knapsack + O((#classes) · log M) for exponentiation per group.

Reference solution (C++)

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, K; cin >> N >> M >> K;
    vector<int> s(N), c(N);
    for (int i = 0; i < N; ++i) cin >> s[i] >> c[i];

    // ways[j] = #ordered sequences of words summing to j syllables
    vector<ll> ways(K + 1, 0);
    ways[0] = 1;
    for (int j = 1; j <= K; ++j)
      for (int i = 0; i < N; ++i) if (s[i] <= j)
        ways[j] = (ways[j] + ways[j - s[i]]) % MOD;

    // endClass[c] = #line-completions ending on a word of class c
    map<int, ll> endClass;
    for (int i = 0; i < N; ++i) if (s[i] <= K)
        endClass[c[i]] = (endClass[c[i]] + ways[K - s[i]]) % MOD;

    // Count group sizes from the rhyme scheme.
    map<char, int> group;
    for (int line = 0; line < M; ++line) { char x; cin >> x; ++group[x]; }

    ll ans = 1;
    for (auto& [letter, t] : group) {
        ll s_ = 0;
        for (auto& [cls, v] : endClass) s_ = (s_ + pw(v, t)) % MOD;
        ans = ans * s_ % MOD;
    }
    cout << ans << "\n";
}

Pitfalls

What Gold January 2019 was actually testing