U USACO Prep

2023 January Silver — three problems

← 2023 January contest index · Official results page

Silver pivots toward the letter-mapping graph in Find and Replace, plus a bigger Air Cownditioning that wants real DP.

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 · Air Cownditioning II

Official statement (cpid=1284)

Statement (paraphrased)

Same setup as Bronze: N stalls with cooling demands, M air conditioners each covering a range with a power and a cost. Choose a subset minimising total cost while satisfying every stall. Silver lifts the bounds so 2M brute force no longer fits — but M is still small enough for bitmask DP on the set of chosen ACs.

Constraints

Key idea

Bitmask over ACs is still the cleanest framing: 220 ≈ 106 subsets. For each subset, build per-stall cooling with a difference array (O(M)) and total cost; check feasibility in O(N). Total roughly 2M · (N + M) ≈ 108 — tight but acceptable in C++ with arrays not vectors. If M is larger in the real PDF, fall back to ILP-style branch-and-bound or DP on stall index with the set of ACs ending at or after the current stall.

Complexity

O(2M · (N + M)) with bitmask. Memory O(N).

C++ reference

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

int N, M;
int d[105];
int s[25], t[25], p[25], m[25];
int diffArr[110];

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) scanf("%d", &d[i]);
    for (int i = 0; i < M; i++) scanf("%d %d %d %d", &s[i], &t[i], &p[i], &m[i]);

    int best = INT_MAX;
    for (int mask = 0; mask < (1 << M); mask++) {
        memset(diffArr, 0, sizeof(int) * (N + 2));
        long long cost = 0;
        for (int i = 0; i < M; i++) if (mask >> i & 1) {
            diffArr[s[i]] += p[i];
            diffArr[t[i] + 1] -= p[i];
            cost += m[i];
            if (cost >= best) goto skip;
        }
        {
            int cool = 0;
            for (int j = 1; j <= N; j++) { cool += diffArr[j]; if (cool < d[j]) goto skip; }
            best = (int)cost;
        }
        skip:;
    }
    printf("%d\n", best);
}

Pitfalls

Problem 2 · Spelling Bee

Official statement (cpid=1285)

Statement (paraphrased)

Given a target string T of length n, and Q query strings, decide for each query whether it can be reduced to T by repeatedly applying the rule: collapse two adjacent equal characters into one of the same character (or some similar "stack reduction" rule).

Constraints

Key idea

Reduce each query with a stack: push next char if it differs from the stack top, else (if the rule collapses equal pairs) pop or merge. The final stack is the canonical reduced form. Compare against the canonical reduction of T.

Complexity

O(sum of |query|) total.

C++ reference

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

// [verify] exact reduction rule against cpid=1285. Below assumes "collapse two equal
// adjacent characters into one" until no two adjacent characters are equal.
string reduce(const string& s) {
    string st;
    for (char c : s) {
        if (!st.empty() && st.back() == c) {
            // merge: leave one copy on the stack (idempotent)
            continue;
        }
        st.push_back(c);
    }
    return st;
}

int main() {
    string T; cin >> T;
    int Q; cin >> Q;
    string canon = reduce(T);
    while (Q--) {
        string q; cin >> q;
        cout << (reduce(q) == canon ? "YES" : "NO") << "\n";
    }
}

Pitfalls

Problem 3 · Find and Replace

Official statement (cpid=1286)

Statement (paraphrased)

Given strings S and T of equal length over an alphabet Σ, in one operation you pick a letter a and a letter b and globally replace every a in the current string with b. Find the minimum number of operations to turn S into T, or report it is impossible. Silver uses a small alphabet (uppercase + lowercase letters, |Σ| ≤ 52).

Constraints

Key idea

Build a function f : Σ → Σ where f(c) is what every occurrence of c in S must eventually become according to T. If S has an a that maps to two different targets, output −1. Otherwise look at the functional graph of f restricted to letters that actually appear in S. Each weakly-connected component contributes (size − 1) operations if it is a tree, and (size) operations if it contains a cycle — and a cycle additionally requires a "temporary" letter from Σ that is currently unused, costing one extra rename if no such letter exists.

Complexity

O(|S| + |Σ|).

C++ reference

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

int idx(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    return 26 + (c - 'A');
}

int main() {
    string S, T; cin >> S >> T;
    if (S.size() != T.size()) { cout << -1; return 0; }
    const int K = 52;
    vector<int> f(K, -1);
    vector<bool> usedInS(K, false), usedInT(K, false);
    for (size_t i = 0; i < S.size(); i++) {
        int a = idx(S[i]), b = idx(T[i]);
        usedInS[a] = true; usedInT[b] = true;
        if (f[a] != -1 && f[a] != b) { cout << -1; return 0; }
        f[a] = b;
    }
    bool hasFree = false;
    for (int c = 0; c < K; c++) if (!usedInS[c] && !usedInT[c]) { hasFree = true; break; }

    // walk components in the functional graph of f over letters with f[c] != -1 and f[c] != c
    vector<int> colour(K, 0);   // 0 unseen, 1 in-stack, 2 done
    int ans = 0;
    for (int start = 0; start < K; start++) {
        if (colour[start] != 0 || f[start] == -1 || f[start] == start) continue;
        // walk path from start, detect cycle in this component
        vector<int> path;
        int u = start;
        while (u != -1 && colour[u] == 0) { colour[u] = 1; path.push_back(u); u = f[u]; }
        bool cycle = (u != -1 && colour[u] == 1);   // returned into this path
        for (int v : path) colour[v] = 2;
        ans += (int)path.size();
        if (!cycle) ans--;   // tree: size - 1 renames
        else if (!hasFree) { cout << -1; return 0; }   // [verify] cycles need a scratch letter
    }
    cout << ans;
}

Pitfalls