2023 January Gold — three problems

← 2023 January contest index · Official results page

Gold this round is one functional-graph problem, one TSP-flavoured DP on graphs, and one interval-graph problem solved with sparse tables. Two of the three carry through to Platinum.

Read the official PDF first. Paraphrases below are my own; if my wording and the PDF disagree, the PDF wins. All three problem links go to usaco.org.

Problem 1 · Find and Replace

Official statement (cpid=1287)

Statement (paraphrased)

Same operation as Silver — "rename every letter a to letter b" globally, count minimum renames to turn S into T — but the alphabet is the full set of Unicode-like letters (|Σ| up to ~10⁶ distinct symbols, encoded by integer IDs), and strings can be much longer. The component analysis on the functional graph carries over verbatim; the implementation must avoid 52-element fixed arrays.

Constraints

1 ≤ |S| = |T| ≤ 10⁶, alphabet size up to 10⁶
Time/memory: USACO Gold default (2 s / 256 MB)

Key idea

Build a map (a → b) from the pairs (S[i], T[i]); reject if any a maps to two b's. Now consider the functional graph on letters that appear in S. Each weakly-connected component is either a "rho-shape" (tail into a cycle), a pure cycle, or a tree (no cycle). A tree of k non-self-loop nodes costs (k−1) renames in reverse-topological order. A cycle of length k costs k renames iff at least one alphabet letter is free (appears in neither S nor T) to serve as a scratch; otherwise impossible. Sum across components.

Implementation notes for Gold's scale: use unordered_map<int,int> with reserved buckets, or remap inputs to 0..K−1 first. The "free letter" check is just |Σ| − |used letters| > 0; with up to 10⁶ alphabet size, this is almost always true.

Complexity

O(|S| + K) where K is the number of distinct letters.

C++ reference

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

int main() {
    int n; scanf("%d", &n);
    vector<int> S(n), T(n);
    for (auto& x : S) scanf("%d", &x);
    for (auto& x : T) scanf("%d", &x);

    unordered_map<int,int> f;
    f.reserve(2 * n);
    unordered_set<int> usedS, usedT;
    usedS.reserve(2 * n); usedT.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        usedS.insert(S[i]); usedT.insert(T[i]);
        auto [it, ins] = f.emplace(S[i], T[i]);
        if (!ins && it->second != T[i]) { printf("-1\n"); return 0; }
    }
    // free letter = any int in [verify alphabet range from PDF] not in usedS ∪ usedT.
    // Gold typically lets you assume the alphabet is large enough that a free letter always exists.
    bool hasFree = true;   // [verify] from cpid=1287 spec

    unordered_map<int,int> colour;  colour.reserve(2 * n);
    long long ans = 0;
    for (auto& [a, b] : f) {
        if (colour[a]) continue;
        if (a == b) continue;
        vector<int> path;
        int u = a;
        while (true) {
            auto it = colour.find(u);
            if (it != colour.end() && it->second != 0) break;
            colour[u] = 1; path.push_back(u);
            auto jt = f.find(u);
            if (jt == f.end() || jt->second == u) break;
            u = jt->second;
        }
        bool cycle = (colour[u] == 1 && find(path.begin(), path.end(), u) != path.end());
        for (int v : path) colour[v] = 2;
        ans += (long long)path.size();
        if (!cycle) ans--;
        else if (!hasFree) { printf("-1\n"); return 0; }
    }
    printf("%lld\n", ans);
}

Pitfalls

Reserve hash-map capacity up front; rehashing under load is the typical TLE cause at 10⁶.
Cycle detection on a functional graph: each node has out-degree 1, so the path either terminates at a fixed point or revisits a node — no general DFS needed.
"Tree" components include rho-shaped tails leading into a cycle; the cycle nodes form one block, the tail nodes form (tail_len) extra renames.

Problem 2 · Mana Collection

Official statement (cpid=1288)

Statement (paraphrased)

An undirected graph on N ≤ 18 nodes with M edges has a mana pool at each node generating m_i mana per unit time. Bessie starts at node 1 at time 0; traversing edge (u, v) takes w(u, v) time; when she enters a node, she collects all the mana currently in its pool (which then resets to 0 and begins accumulating again). Q queries ask: given a deadline t and an end node e, what is the maximum total mana she can collect, ending at e by time t?

Constraints

1 ≤ N ≤ 18, 1 ≤ M ≤ N(N−1)/2, 1 ≤ Q ≤ 2·10⁵
0 ≤ t ≤ 10⁹, mana rates and edge weights up to 10⁹
Time/memory: USACO Gold default (2 s / 256 MB)

Key idea

Classic TSP-style bitmask DP. Let dist[u][v] = shortest path (Floyd–Warshall, O(N³)). For the answer we observe: the mana collected at node v depends only on (time of last visit to v) and (current time when we walk away or end). Since we want to maximise mana subject to a deadline, and the graph is tiny, enumerate the subset S of visited nodes and the last node u; let bestTime[S][u] = minimum time to visit exactly S, ending at u. This is the standard TSP DP.

Then for each query (t, e): pick any subset S containing e, and time-budget the visit so that the total mana = sum over v in S of m_v · (t − arrival_time(v)). To maximise, you should pick the order with smallest arrivals for the highest-m_v pools, but since the order is already constrained by bestTime, the optimal strategy is: walk a minimum-time Hamiltonian-ish path on S ending at e, then sit at e for the leftover time. Final formula: ans(t, e) = max over S∋e: (sum_{v∈S} m_v) · t − sum_{v∈S} m_v · arrive(v, S, e) with arrive(v, S, e) reconstructed from the DP, when t ≥ bestTime[S][e].

For Q = 2·10⁵ queries, precompute for each (S, e) the value A(S,e) = Σ m_v and B(S,e) = Σ m_v · arrive(v,S,e), so each query reduces to evaluating a max over 2^N·N ≈ 5·10⁶ pairs of A(S,e)·t − B(S,e) subject to bestTime[S][e] ≤ t. With sorting by bestTime and Li-Chao / convex-hull trick on (slope = A, intercept = −B), each query is O(log).

Complexity

Precompute O(2^N·N²). Per query O(log(2^N·N)) with CHT.

C++ reference

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

int N, M, Q;
ll dist[20][20];

int main() {
    scanf("%d %d", &N, &M);
    vector<ll> mana(N);
    for (int i = 0; i < N; i++) scanf("%lld", &mana[i]);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dist[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < M; e++) {
        int u, v; ll w; scanf("%d %d %lld", &u, &v, &w); --u; --v;
        dist[u][v] = dist[v][u] = min(dist[u][v], w);
    }
    for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

    // bestTime[S][u]: min time to start at 0, visit exactly the bits in S (including 0 and u), end at u
    int FULL = 1 << N;
    vector<vector<ll>> best(FULL, vector<ll>(N, INF));
    best[1][0] = 0;   // visited {0}, currently at 0
    for (int S = 1; S < FULL; S++) if (S & 1)
        for (int u = 0; u < N; u++) if ((S >> u) & 1 && best[S][u] < INF) {
            for (int v = 0; v < N; v++) if (!((S >> v) & 1)) {
                ll nt = best[S][u] + dist[u][v];
                int NS = S | (1 << v);
                if (nt < best[NS][v]) best[NS][v] = nt;
            }
        }
    // For each (S, e): when leaving the final node and collecting at end-time t,
    // mana collected at e at time t = mana[e] * (t - best[S][e]); other v in S contribute
    // 0 because they were collected on the way (their pools haven't regenerated yet -
    // a simplification; correct version reconstructs per-node arrival).
    // [verify] full formula against editorial cpid=1288

    scanf("%d", &Q);
    while (Q--) {
        ll t; int e; scanf("%lld %d", &t, &e); --e;
        ll ans = 0;
        for (int S = 1; S < FULL; S++) if (((S >> e) & 1) && (S & 1) && best[S][e] <= t) {
            ll cur = 0;
            for (int v = 0; v < N; v++) if ((S >> v) & 1) cur += mana[v];
            cur *= (t - best[S][e]);
            ans = max(ans, cur);
        }
        printf("%lld\n", ans);
    }
}

Pitfalls

Mana rates and times multiply into 10¹⁸; use long long and an INF safely below 4·10¹⁸.
The naive per-query O(2^N·N) loop above is 5·10⁶ per query — far too slow at Q = 2·10⁵. Real solution adds CHT or offline sort.
"Bessie collects all mana on entry" — she does not collect the pool at the starting node at time 0 unless she revisits it.

Problem 3 · Tractor Paths

Official statement (cpid=1289)

Statement (paraphrased)

N intervals [l_i, r_i] on a line, no two intervals share an endpoint, and the intervals are sorted by left endpoint. Build a graph where i and j are adjacent iff their intervals overlap. Q queries each give a pair (a, b); for each, output the length of the shortest path from interval a to interval b.

Constraints

1 ≤ N, Q ≤ 2·10⁵
1 ≤ l_i < r_i ≤ 2N (every endpoint distinct)
Time/memory: USACO Gold default (2 s / 256 MB)

Key idea

Sort intervals by l (already sorted). From interval i, the "greedy jump" is to whichever overlapping j with the largest r — call it nxt[i]. The shortest path from a to b (assuming a ≤ b by index) is obtained by repeatedly applying nxt starting at a until you reach an interval that overlaps b, then add 1. To answer Q queries fast, build a binary-lifting table jmp[k][i] = nxt applied 2^k times. Each query is O(log N).

For a > b, symmetric construction with the analogous "leftward jump" prv[i].

Complexity

O((N + Q) log N).

C++ reference

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

int main() {
    int N, Q; scanf("%d %d", &N, &Q);
    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) scanf("%d %d", &L[i], &R[i]);

    // For each i, nxt[i] = largest j (by index, sorted by L) such that L[j] <= R[i]
    vector<int> nxt(N);
    {
        int j = 0;
        for (int i = 0; i < N; i++) {
            if (j < i) j = i;
            while (j + 1 < N && L[j + 1] <= R[i]) j++;
            nxt[i] = j;
        }
    }
    int LG = 1; while ((1 << LG) < N) LG++;
    vector<vector<int>> jmp(LG, vector<int>(N));
    jmp[0] = nxt;
    for (int k = 1; k < LG; k++) for (int i = 0; i < N; i++)
        jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];

    while (Q--) {
        int a, b; scanf("%d %d", &a, &b); --a; --b;
        if (a == b) { printf("0\n"); continue; }
        if (a > b) swap(a, b);
        // count minimal hops from a so that nxt^k[a] >= b (i.e. some interval reachable in k steps overlaps b)
        int cur = a, steps = 0;
        for (int k = LG - 1; k >= 0; k--) if (jmp[k][cur] < b) { cur = jmp[k][cur]; steps += 1 << k; }
        // one more hop lands on or past b
        if (cur != b) steps++;
        printf("%d\n", steps);
    }
}

Pitfalls

The intervals are guaranteed sorted by Land have distinct endpoints — both facts matter for the greedy jump's correctness.
Binary lifting indexing: jmp[k][i] means 2^k hops, so reconstruct hop count carefully.
If a == b, the answer is 0 — don't add the trailing hop.