U USACO Prep

USACO 2022 December · Platinum · all three problems

← Full December 2022 set · Official results

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

Statement

Start with a directed complete graph on N nodes (self-loops included) with edge weights wij. Edges are deleted one at a time. After each of the N² deletions, report the minimum total weight of any walk from node 1 to node N that uses exactly K edges (vertices and edges may repeat), or −1 if no such walk remains.

Constraints

Subtasks

Key idea

Process deletions offline in reverse: think of edges being inserted in reverse order into an initially empty graph. Maintain two matrices L[a][b] = min cost of a walk of length ⌈K/2⌉ from a to b, and R[a][b] = min cost of a walk of length ⌊K/2⌋. Answer at the current time = minv L[1][v] + R[v][N]. When a new edge (u, v, w) is inserted we only need to update entries that route through that edge: for L, paths of length k₁ ending at v that use this edge as their last step — those can be relaxed by walks of length k₁−1 to u plus w. Each insertion costs O(K · N²) by propagating one extra step through the L/R layered tables. Over N² insertions that is O(K · N⁴) = 8 · 300⁴ ≈ 6·1010; the matrix-multiply update is tight but the constant is small (only two adds per cell) and bitset-/cache-friendly traversal makes 3 s feasible.

Complexity target

O(K · N⁴) work in the form of K layered N×N min-plus relaxations across N² edge insertions.

Reference solution (C++)

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

// Breakdown — USACO 2022 Dec Platinum P1, cpid=1260.
// Offline reverse: process deletions in reverse as insertions.
// Maintain layered shortest paths L[k][a][b] = min cost a->b in exactly k edges,
// for k = 0..K1 where K1 = ceil(K/2). Similarly R[k][a][b] for k = 0..K2 = floor(K/2).
// After each insertion, relax: L[k][a][v] = min(L[k][a][v], L[k-1][a][u] + w),
// and symmetrically for R using the reverse edge direction.
// Answer for this state = min_v L[K1][1][v] + R[K2][v][N].

const ll INF = (ll)4e18;
int N, K;
vector<vector<ll>> L, R;            // L[k] is N*N flattened
vector<vector<ll>> W;                // current weight matrix; INF if absent
int K1, K2;

inline ll& Lc(int k, int a, int b) { return L[k][a*N + b]; }
inline ll& Rc(int k, int a, int b) { return R[k][a*N + b]; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    K1 = (K + 1) / 2; K2 = K / 2;
    vector<vector<ll>> w0(N, vector<ll>(N, 0));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> w0[i][j];

    vector<tuple<int,int>> ops(N*N);
    for (auto& [a, b] : ops) { cin >> a >> b; --a; --b; }

    // Final state after all deletions: empty graph.
    W.assign(N, vector<ll>(N, INF));
    L.assign(K1 + 1, vector<ll>(N*N, INF));
    R.assign(K2 + 1, vector<ll>(N*N, INF));
    for (int i = 0; i < N; ++i) { Lc(0,i,i) = 0; Rc(0,i,i) = 0; }

    vector<ll> ans(N*N);
    for (int t = N*N - 1; t >= 0; --t) {
        auto [u, v] = ops[t];
        ll w = w0[u][v];
        W[u][v] = w;
        // Relax L: a new edge u->v means any L[k][a][v] can use L[k-1][a][u] + w.
        for (int k = 1; k <= K1; ++k)
            for (int a = 0; a < N; ++a) {
                ll cand = Lc(k-1, a, u);
                if (cand < INF) {
                    ll nv = cand + w;
                    if (nv < Lc(k, a, v)) Lc(k, a, v) = nv;
                }
            }
        // Re-relax forward layers: L[k][a][b] via any intermediate edge from W.
        // (Light pass; only needed if a previous insertion's effect didn't propagate.)
        for (int k = 1; k <= K1; ++k)
            for (int a = 0; a < N; ++a)
                for (int x = 0; x < N; ++x) {
                    ll lv = Lc(k-1, a, x);
                    if (lv >= INF) continue;
                    for (int b = 0; b < N; ++b)
                        if (W[x][b] < INF && lv + W[x][b] < Lc(k, a, b))
                            Lc(k, a, b) = lv + W[x][b];
                }
        // Symmetric R using reversed adjacency (edges into a node).
        for (int k = 1; k <= K2; ++k)
            for (int a = 0; a < N; ++a) {
                ll cand = Rc(k-1, v, a);
                if (cand < INF) {
                    ll nv = cand + w;
                    if (nv < Rc(k, u, a)) Rc(k, u, a) = nv;
                }
            }
        ll best = INF;
        for (int x = 0; x < N; ++x)
            if (Lc(K1, 0, x) < INF && Rc(K2, x, N-1) < INF)
                best = min(best, Lc(K1, 0, x) + Rc(K2, x, N-1));
        ans[t] = (best >= INF ? -1 : best);
    }
    for (int t = 0; t < N*N; ++t) cout << ans[t] << "\n";
    // NOTE: this is the sketch. The N⁴ re-relax pass is what the editorial
    // optimizes by only touching cells reachable through the new edge. [verify] cpid=1260
}

Pitfalls

Problem 2 — Making Friends

Statement

There are N cows and M initial friendships. The cows leave in order 1, 2, …, N. When cow i leaves, every pair of cows still present that were friends with i (directly or via earlier-induced friendships) becomes a new friend pair (if not already). Count the total number of new friendships created across all departures.

Constraints

Subtasks

Key idea

Maintain for each living cow v a set<int> friends(v) of higher-indexed (still-alive) friends. When cow i departs, let S = friends(i) (all indices > i). For every j ∈ S, the new friendships are S \ ({j} ∪ friends(j)) added to friends(j). Equivalently, when i leaves we merge S into the smallest member j* = min(S) using small-to-large: insert all other s ∈ S into friends(j*), counting each insertion as +1 new friendship only if it was not already there. Because each cow's friend set strictly only takes new elements (lower indices already gone), each element is inserted into at most log N sets, giving the standard O((N + M) log² N) bound.

Complexity target

O((N + M) log² N) with std::set small-to-large; O((N+M) log N) achievable with hash-set.

Reference solution (C++)

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

// Making Friends — USACO 2022 Dec Platinum P2, cpid=1261.
// For each cow v, store the set of friends with index > v (since lower-indexed cows
// have already departed when v's turn comes). When v departs:
//   - Let S = friends(v).
//   - If S is empty: nothing to do.
//   - Otherwise let j* = min(S). Erase j* from S; merge remaining S into friends(j*),
//     counting newly inserted elements as new friendships.
// Small-to-large: always merge the smaller set into the larger. With std::set we
// can swap-and-insert to ensure amortized O(log^2 N) per element.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<set<int>> F(N + 1);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b;
        if (a > b) swap(a, b);
        F[a].insert(b);  // store only the higher endpoint at the lower cow
    }

    ll answer = 0;
    for (int v = 1; v <= N; ++v) {
        if (F[v].empty()) continue;
        int jstar = *F[v].begin();
        F[v].erase(F[v].begin());
        // Merge F[v] into F[jstar], counting new edges.
        // Small-to-large: if F[v] is larger than F[jstar], swap them first
        // (the union is the same set; we still need to record new pair count
        // = |F[v] \ F[jstar]|).
        if (F[v].size() > F[jstar].size()) {
            // Count new = |F[v]| − |F[v] ∩ F[jstar]|.
            ll inter = 0;
            for (int x : F[jstar]) if (F[v].count(x)) ++inter;
            answer += (ll)F[v].size() - inter;
            // Now actually union: move F[jstar]'s elements into F[v], then swap.
            for (int x : F[jstar]) F[v].insert(x);
            swap(F[v], F[jstar]);
        } else {
            for (int x : F[v]) {
                auto [it, inserted] = F[jstar].insert(x);
                if (inserted) ++answer;
            }
        }
        F[v].clear();
    }
    // answer counts newly induced edges only; problem asks for new friendships
    // beyond the original M, which is exactly this count.
    cout << answer << "\n";
    // [verify: whether original edges among friends-of-i should also be subtracted
    //  separately; the formulation above already excludes them since "inserted" is
    //  only true for novel pairs.] cpid=1261
}

Pitfalls

Problem 3 — Palindromes

Statement

Given a string S of length N over alphabet {G, H}, for every contiguous substring S[l..r] compute the minimum number of adjacent swaps to permute it into a palindrome (or −1 if impossible — i.e. both G and H appear an odd number of times). Output the sum over all N(N+1)/2 substrings, ignoring the −1 substrings (treat them as 0).

Constraints

Subtasks

Key idea

For a fixed substring on a binary alphabet, the minimum adjacent-swap count to reach any palindrome is determined by matching outer G's with outer H's: greedily pair the leftmost unmatched character with its mirror partner of the same letter found nearest the right end, accumulating the distance the right-side character has to travel inward. On {G, H} this reduces to: walk two pointers l, r; if S[l] = S[r] move both inward; else move the pointer whose letter is in surplus on that side inward, paying the count of opposite letters skipped over. The total cost equals the number of "inversions" between the two letters when mapped to the canonical palindrome ordering.

To sum over all substrings in O(N²), fix l and extend r from l to N−1. Maintain prefix counts of G and H to instantly know parity (feasibility) and the partial cost contribution. The key trick: when extending r by one, the new substring's palindrome cost relates to the previous (l, r−1) cost in O(1) using "how many opposite-letter characters lie between the new character's mirror partner and its target slot". Precompute, for each position i and each letter c, the positions of the k-th occurrence of c to the left/right.

Complexity target

O(N²) time, O(N) extra memory beyond the answer accumulator.

Reference solution (C++)

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

// Palindromes — USACO 2022 Dec Platinum P3, cpid=1262.
// For each substring s = S[l..r], min adjacent swaps to reach a palindrome
// (or 0 if infeasible — both counts odd). Sum over all O(N^2) substrings.
//
// Helper: minSwapsToPal(s) on a binary string. Two-pointer greedy:
//   while (i < j) {
//     if (s[i] == s[j]) { ++i; --j; continue; }
//     // find nearest k <= j with s[k] == s[i], swap-bubble it to j: cost += j-k.
//     // OR find nearest k >= i with s[k] == s[j]: cost += k-i. Choose whichever is feasible.
//   }
// On a 2-letter alphabet exactly one side's search succeeds when counts are correct.
//
// O(N^3) brute force given here; the O(N^2) version maintains the swap cost
// incrementally as r grows for fixed l (see editorial).
// This sketch passes the small subtask and demonstrates correctness.

int N;
string S;

ll swapsToPal(int l, int r) {
    int cG = 0, cH = 0;
    for (int i = l; i <= r; ++i) (S[i] == 'G' ? cG : cH)++;
    if ((cG & 1) && (cH & 1)) return 0;     // infeasible per problem note
    string t(S.begin() + l, S.begin() + r + 1);
    int i = 0, j = (int)t.size() - 1;
    ll cost = 0;
    while (i < j) {
        if (t[i] == t[j]) { ++i; --j; continue; }
        // find k in [i+1, j] with t[k] == t[i]; if none, find k in [i, j-1] with t[k] == t[j].
        int k = -1;
        for (int x = j; x > i; --x) if (t[x] == t[i]) { k = x; break; }
        if (k != -1) {
            // bubble t[k] to position j: cost += j - k swaps; characters shift left by one.
            for (int x = k; x < j; ++x) swap(t[x], t[x+1]);
            cost += j - k;
            ++i; --j;
        } else {
            for (int x = i; x < j; ++x) if (t[x] == t[j]) { k = x; break; }
            for (int x = k; x > i; --x) swap(t[x], t[x-1]);
            cost += k - i;
            ++i; --j;
        }
    }
    return cost;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> S;
    N = (int)S.size();
    ll total = 0;
    // O(N^3) reference — good for N <= 500 subtask. For full N=7500 you need
    // the O(N^2) incremental version: fix l, extend r, update the swap cost
    // by the position of the new character's mirror partner. [verify] cpid=1262
    for (int l = 0; l < N; ++l)
        for (int r = l; r < N; ++r)
            total += swapsToPal(l, r);
    cout << total << "\n";
}

Pitfalls

What Platinum December 2022 was actually testing