U USACO Prep

USACO 2021 January · Gold · all three problems

← Full January 2021 set · Official results

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

Statement

Same setup as Bronze: Mildred recites a cowphabet (a permutation of 26 letters) repeatedly, and Farmer Nhoj records the heard string T. But here the cowphabet is NOT given — we choose it adversarially to minimize the number of complete recitations consistent with T. Output that minimum.

Constraints

Key idea

Walk T left to right. At position i with letter T[i], we must start a new recitation if and only if the pair (T[i−1], T[i]) is forced to occur "in this order" within a cowphabet AND the cowphabet has already placed T[i] before T[i−1]. Equivalently: we need to count the minimum number of recitations such that the multiset of ordered adjacent pairs (T[i−1], T[i]) in T can be consistent with one global ordering. Concretely, consider directed adjacency edges T[i−1] → T[i]. We start a new recitation exactly when we encounter a pair (a, b) such that we've already committed b → a elsewhere — i.e., the directed graph of "must precede" relations would otherwise contain a cycle. Greedy answer: scan T and count positions i where we've already seen the pair (T[i], prev) in some earlier recitation. The total minimum is 1 + (number of forced restarts).

Complexity target

O(|T| · 26) using a 26×26 boolean "seen forward edge" table.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string t; cin >> t;
    int n = (int)t.size();
    if (n == 0) { cout << 0 << "\n"; return 0; }

    // seen[a][b] = true iff we've committed "a before b" in the current
    // (still-open) cowphabet recitation. A new recitation lets us pick a
    // fresh ordering, so seen resets to "the current recitation's edges so far".
    // We accumulate the GLOBAL precedence graph in "forced"; if adding
    // T[i-1] -> T[i] would close a cycle with already-forced edges in the
    // SAME recitation, we open a new recitation.
    bool forced[26][26] = {};   // forced[a][b] = a must come before b
    auto reaches = [&](int a, int b) {
        // BFS in the 26-node DAG to check if b is reachable from a.
        bool vis[26] = {}; vis[a] = true;
        queue<int> q; q.push(a);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == b) return true;
            for (int v = 0; v < 26; ++v)
                if (forced[u][v] && !vis[v]) { vis[v] = true; q.push(v); }
        }
        return false;
    };

    int recitations = 1;
    auto resetForCurrent = [&]() {
        for (int i = 0; i < 26; ++i)
            for (int j = 0; j < 26; ++j)
                forced[i][j] = false;
    };

    int prev = t[0] - 'a';
    for (int i = 1; i < n; ++i) {
        int c = t[i] - 'a';
        if (c == prev) {            // same letter twice in a row -> new recitation
            ++recitations; resetForCurrent();
        } else if (reaches(c, prev)) {
            // c must come before prev (forced), but we need prev -> c now -> new recitation.
            ++recitations; resetForCurrent();
        } else {
            forced[prev][c] = true;
        }
        prev = c;
    }
    cout << recitations << "\n";
}

Pitfalls

Problem 2 — Telephone

Statement

N cows stand in a line at positions 1..N; cow i has breed bi ∈ [1, K]. A K × K compatibility matrix S has Sij ∈ {0,1} indicating whether breed i can pass a message directly to breed j. Transmission from cow i to cow j (with Sbi, bj = 1) costs |i − j|. Find the minimum total cost to relay a message from cow 1 to cow N, or −1 if impossible.

Subtask structure

Constraints

Key idea

N up to 5 · 104 means N² ≈ 2.5 · 109 edges — too many. Reduce edges by noting that for each cow i and each "destination breed" b', the best handoff is always to the nearest cow of breed b'. So build, for each position i and each breed c with Sbi, c = 1, edges i → (nearest cow of breed c to left) and i → (nearest cow of breed c to right). This gives O(N · K) edges. Run 0-1-style Dijkstra (or just plain Dijkstra) from cow 1.

Complexity target

O(N · K · log(N · K)) ≈ 5 · 104 · 50 · 22 ≈ 5.5 · 107.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<string> S(K);
    for (auto& r : S) cin >> r;
    vector<int> b(N);
    for (int i = 0; i < N; ++i) { int x; cin >> x; b[i] = x - 1; }

    // For each breed c, list positions in order.
    vector<vector<int>> byBreed(K);
    for (int i = 0; i < N; ++i) byBreed[b[i]].push_back(i);

    // Build adjacency lazily inside Dijkstra: for each i, for each breed c
    // compatible (S[b[i]][c] == '1'), the only useful edges are to the two
    // nearest cows of breed c -- left neighbor and right neighbor.
    vector<ll> dist(N, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[0] = 0; pq.push({0, 0});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        if (u == N - 1) break;
        for (int c = 0; c < K; ++c) if (S[b[u]][c] == '1') {
            auto& v = byBreed[c];
            auto it = lower_bound(v.begin(), v.end(), u);
            for (int delta : {-1, 0}) {           // candidate right (it+0) and left (it-1)
                auto jt = it + delta;
                if (jt < v.begin() || jt >= v.end()) continue;
                int w = *jt;
                if (w == u) continue;
                ll nd = d + abs(w - u);
                if (nd < dist[w]) { dist[w] = nd; pq.push({nd, w}); }
            }
        }
    }
    cout << (dist[N - 1] >= INF ? -1 : dist[N - 1]) << "\n";
}

Pitfalls

Problem 3 — Dance Mooves (Gold)

Statement

Same as Silver Dance Mooves but the number of full rounds is M, where M can be up to 1018. For each cow output the number of distinct positions it occupies during M rounds.

Constraints

Key idea

Same machinery as Silver: simulate one round, record visited[p] (positions cow p touches in round 1), and build the end-of-round permutation π. Cows on the same π-cycle of length L will revisit each other's visited[·] sets. With M rounds, cow p touches the union of visited[q] for the first min(M, L) cows on its cycle, starting at p. If M ≥ L, that's the whole cycle's union. If M < L, use a sliding window of length M over the cyclically-ordered visited[·] lists. Answer = size of the window's union. Use offline frequency counters over a doubled cycle and add/remove events.

Complexity target

O((N + K) log N) — sliding-window union over each cycle.

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, K; ll M; cin >> N >> K >> M;

    vector<int> pos(N + 1), invPos(N + 1);
    iota(pos.begin(), pos.end(), 0);
    iota(invPos.begin(), invPos.end(), 0);
    vector<vector<int>> visited(N + 1);
    for (int p = 1; p <= N; ++p) visited[p].push_back(p);

    for (int i = 0; i < K; ++i) {
        int a, b; cin >> a >> b;
        int ca = invPos[a], cb = invPos[b];
        swap(pos[ca], pos[cb]);
        invPos[a] = cb; invPos[b] = ca;
        visited[ca].push_back(b);
        visited[cb].push_back(a);
    }

    // Permutation P[p] = cow whose "starting position" gets cow p's role next round.
    // Standard trick: cow p ends at position pos[p]; the cow whose ORIGINAL position
    // equals pos[p] is just (label) pos[p] -- so P[p] = pos[p] is wrong; we want
    // the cow that will, next round, be in cow p's current spot -- but for counting
    // we only need the cycle structure of p -> pos[p].
    vector<int> ans(N + 1, 0);
    vector<int> visIdx(N + 1, -1);     // which cycle position
    vector<int> cycId(N + 1, -1);

    for (int s = 1; s <= N; ++s) if (cycId[s] == -1) {
        // Collect the cycle starting at s.
        vector<int> cyc;
        int x = s;
        while (cycId[x] == -1) { cycId[x] = s; visIdx[x] = (int)cyc.size(); cyc.push_back(x); x = pos[x]; }
        int L = (int)cyc.size();
        ll W = min<ll>(M, (ll)L);    // sliding window length

        // If window covers the cycle entirely, answer is the union of visited[*] over the cycle.
        if (W == L) {
            unordered_set<int> uni;
            for (int q : cyc) for (int v : visited[q]) uni.insert(v);
            int sz = (int)uni.size();
            for (int q : cyc) ans[q] = sz;
            continue;
        }

        // Sliding window of length W over the doubled cycle [cyc, cyc].
        // freq[v] = how many times position v appears in current window.
        unordered_map<int,int> freq;
        int unionSize = 0;
        auto add = [&](int q) {
            for (int v : visited[q]) if (freq[v]++ == 0) ++unionSize;
        };
        auto rem = [&](int q) {
            for (int v : visited[q]) if (--freq[v] == 0) --unionSize;
        };

        for (int i = 0; i < (int)W; ++i) add(cyc[i]);
        ans[cyc[0]] = unionSize;
        for (int i = 1; i < L; ++i) {
            rem(cyc[i - 1]);
            add(cyc[(i + (int)W - 1) % L]);
            ans[cyc[i]] = unionSize;
        }
    }
    for (int p = 1; p <= N; ++p) cout << ans[p] << "\n";
}

Pitfalls

What Gold January 2021 was actually testing