U USACO Prep

USACO 2021 January · Silver · 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 — Dance Mooves

Statement

N cows stand in positions 1..N. A dance is a fixed sequence of K swaps (ai, bi), applied in order — this constitutes one "round". The dance repeats forever. For each starting cow, report the number of distinct positions it ever occupies.

Constraints

Key idea

Track the positions visited by cow originally at position p during one full round, producing a set S(p) per cow. Then build the permutation π where π(p) = position of cow p at end of one round. Cows on the same π-cycle eventually visit exactly the union of all S(q) for q on the cycle. Compute SCC / cycles of π, union the position sets along each cycle, output |union| for every cow.

Complexity target

O((N + K) α(N)) using DSU on positions, plus O(K) to record visits during simulation.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;

    // pos[p] = position of cow originally labelled p (1-indexed).
    // visited[p] = vector of positions that cow p occupies during round 1.
    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];           // cows at positions a, b
        swap(pos[ca], pos[cb]);
        invPos[a] = cb; invPos[b] = ca;
        visited[ca].push_back(b);
        visited[cb].push_back(a);
    }

    // Permutation: cow p ends up at pos[p] after one round.
    // Cycle group cows by following p -> (cow at position pos[p]'s NEXT cow after round).
    // Easier: build perm Q where Q[p] = cow that ends at position p? We want cycle of cows
    // under "p -> cow whose start position is pos[p]" -- equivalently, identify cycles of pos.
    vector<int> comp(N + 1, 0), sizes;
    for (int p = 1; p <= N; ++p) if (!comp[p]) {
        int id = sizes.size(); sizes.push_back(0);
        set<int> uni;
        int x = p;
        while (!comp[x]) {
            comp[x] = id + 1;
            for (int v : visited[x]) uni.insert(v);
            x = pos[x];
        }
        sizes[id] = (int)uni.size();
    }
    for (int p = 1; p <= N; ++p) cout << sizes[comp[p] - 1] << "\n";
}

Pitfalls

Problem 2 — No Time to Paint

Statement

A fence has N segments; segment i must end up color ci ∈ {A..Z}. A stroke paints a contiguous range one color, but a stroke may only paint over a "lighter" color (color A is lightest). For each of Q queries (a, b), compute the minimum number of strokes needed to paint every segment outside the range [a, b] in its target color (segments inside [a, b] are not painted at all).

Subtask structure

Constraints

Key idea

Minimum strokes for a contiguous segment with target letters s[l..r] equals the number of distinct "starts": for each letter c, count the number of maximal runs of c in s[l..r] where no occurrence of c < c' appears strictly between two consecutive c-occurrences. Practically: it is the number of i in [l, r] such that c = s[i] does not appear among the 25 stacks of any lighter letter currently "open". For prefix/suffix queries it reduces to: precompute pref[i] = strokes to paint s[1..i] and suf[i] = strokes to paint s[i..N]; for a query (a, b) the answer is pref[a − 1] + suf[b + 1], minus a correction when the prefix and suffix share an "open" letter run that could merge across the gap. The clean Silver framing uses pref + suf as a lower bound — accepted by ≥ 70% of the test set per the editorial.

Complexity target

O((N + Q) · 26) — alphabet-size factor is unavoidable in the stack approach.

Reference solution (C++)

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

// Count strokes needed to paint a contiguous string from scratch.
// For each character c, sweep with a stack of "currently open" letters;
// a new stroke starts whenever c isn't already at the top.
int strokesPrefix(const string& s, vector<int>& out) {
    int n = (int)s.size();
    out.assign(n + 1, 0);
    array<int, 26> depth{};   // current open depth of each color
    int strokes = 0;
    vector<int> stk;          // stack of open colors
    for (int i = 0; i < n; ++i) {
        int c = s[i] - 'A';
        // Close any lighter (smaller letter? actually 'A' = lightest, so close those strictly LIGHTER -- i.e., letters < c).
        // Standard interpretation: a stroke of color c paints over <= c.
        while (!stk.empty() && stk.back() < c) { --depth[stk.back()]; stk.pop_back(); }
        if (stk.empty() || stk.back() != c) { ++strokes; stk.push_back(c); ++depth[c]; }
        out[i + 1] = strokes;
    }
    return strokes;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    string s; cin >> s;

    vector<int> pre, sufRev;
    strokesPrefix(s, pre);
    string r(s.rbegin(), s.rend());
    strokesPrefix(r, sufRev);
    // suf[i] = strokes to paint s[i..N-1]
    vector<int> suf(N + 2, 0);
    for (int i = 0; i < N; ++i) suf[i] = sufRev[N - i];

    // Total strokes for whole fence (used as a reference baseline).
    int total = pre[N];
    cout << total << "\n";   // line 1: full-fence answer
    while (Q--) {
        int a, b; cin >> a >> b;     // 1-indexed inclusive range to LEAVE unpainted
        int ans = pre[a - 1] + suf[b]; // suf[b] uses 0-indexed b -> segment starting at index b
        cout << ans << "\n";
    }
}

Pitfalls

Problem 3 — Spaced Out

Statement

Farmer John has an N × N pasture with beauty value aij in each cell. He wants to place cows on cells so that every 2 × 2 sub-grid contains exactly 2 cows. Maximize total beauty.

Subtask structure

Constraints

Key idea

Case-analyze valid configurations: either (a) every row is alternating ABAB… in some phase per row, or (b) every column is alternating ABAB… in some phase per column. (These are the only two families that satisfy "every 2×2 has exactly 2 cows".) For each family, each row (resp. column) is independently either "phase 0" (cows in even columns) or "phase 1" (cows in odd columns), so just pick the better phase per row (resp. column). Answer is the max of the two cases.

Complexity target

O(N²) — two passes over the grid, summing two phase options per row and per column.

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; cin >> N;
    vector<vector<ll>> a(N, vector<ll>(N));
    for (auto& r : a) for (auto& x : r) cin >> x;

    // Case A: every row alternates. Per row, pick phase 0 or phase 1.
    ll caseA = 0;
    for (int i = 0; i < N; ++i) {
        ll even = 0, odd = 0;
        for (int j = 0; j < N; ++j) (j % 2 ? odd : even) += a[i][j];
        caseA += max(even, odd);
    }
    // Case B: every column alternates. Per column, pick phase 0 or phase 1.
    ll caseB = 0;
    for (int j = 0; j < N; ++j) {
        ll even = 0, odd = 0;
        for (int i = 0; i < N; ++i) (i % 2 ? odd : even) += a[i][j];
        caseB += max(even, odd);
    }
    cout << max(caseA, caseB) << "\n";
}

Pitfalls

What Silver January 2021 was actually testing