U USACO Prep

2022 February Silver · All three problems

← Back to Feb 2022 hub · Official results

Canonical statements live at usaco.org. Statements below are my paraphrase — open the official problem PDFs before submitting your own solution. Each problem links to the official viewer.

Problem 1 · Redistributing Gifts

Official problem (cpid=1206)

Statement (paraphrased)

N cows each have a permutation preference list over N gifts. Cow i starts with gift i. The cows may reassign gifts so long as every cow ends up with a gift she likes at least as much as her own. For each cow output the best gift she could possibly receive under some valid reassignment.

Constraints

Key idea

Build a directed graph: edge i → j iff cow i prefers gift j at least as much as gift i (j appears no later than i on cow i's list). A reassignment is a permutation lying within this graph, which decomposes into vertex-disjoint cycles. Cow i can end up with gift j iff there's a directed cycle through edge (i → j). Equivalently, j is reachable from i AND i is reachable from j using only "at-least-as-good" edges. Compute the reachability matrix (N BFSes, O(N · (N + E)) = O(N3)), then for each i scan her preference list top-down and output the first j satisfying both reachabilities.

Complexity target

O(N3) ≈ 1.25 · 108 for N = 500 — fits in 2 s with bitsets.

C++ reference solution

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<vector<int>> pref(N + 1, vector<int>(N));
    // rank[i][g] = position of gift g in cow i's preference list (0 = best)
    vector<vector<int>> rnk(N + 1, vector<int>(N + 1));
    for (int i = 1; i <= N; ++i)
        for (int k = 0; k < N; ++k) {
            cin >> pref[i][k];
            rnk[i][pref[i][k]] = k;
        }
    // adj[i] = set of gifts j such that cow i would accept j (rnk[i][j] <= rnk[i][i])
    vector<bitset<505>> reach(N + 1);
    for (int i = 1; i <= N; ++i) {
        reach[i].set(i);
        for (int j = 1; j <= N; ++j)
            if (rnk[i][j] <= rnk[i][i]) reach[i].set(j);
    }
    // Transitive closure via Floyd-Warshall on bitsets
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            if (reach[i].test(k)) reach[i] |= reach[k];

    for (int i = 1; i <= N; ++i) {
        for (int k = 0; k < N; ++k) {
            int g = pref[i][k];
            // need both i -> g and g -> i (cycle through edge i->g)
            if (reach[i].test(g) && reach[g].test(i)) { cout << g << '\n'; break; }
        }
    }
    return 0;
}

Pitfalls

Problem 2 · Robot Instructions

Official problem (cpid=1207)

Statement (paraphrased)

N ≤ 40 plane-vector instructions and a target (xg, yg). For each K from 1..N, count subsets of size K whose vector sum equals the target.

Constraints

Key idea

Meet in the middle. Split into halves of size ≈ 20. Enumerate every subset of the left half, record (sumX, sumY, popcount) → frequency in a map. Then enumerate subsets of the right half; for each, look up (xg−sumX, yg−sumY, K−popcount) for every K and accumulate. 220 ≈ 106 subsets per half.

Complexity target

O(2N/2 · N) per side. Hash map keyed by (x, y, k).

C++ reference solution

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

int N; ll gx, gy;
vector<pair<ll,ll>> v;

// Pack (x, y, k) into one 64-bit key (coords fit in ~36 bits each after offset)
struct Key { ll x, y; int k; bool operator==(const Key& o) const { return x==o.x&&y==o.y&&k==o.k; } };
struct H { size_t operator()(const Key& p) const noexcept {
    return hash<ll>()(p.x) ^ (hash<ll>()(p.y) << 1) ^ (hash<int>()(p.k) << 2);
}};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> gx >> gy;
    v.resize(N);
    for (auto& p : v) cin >> p.first >> p.second;
    int L = N / 2, R = N - L;
    unordered_map<Key, ll, H> left_map;
    for (int m = 0; m < (1 << L); ++m) {
        ll sx = 0, sy = 0; int k = __builtin_popcount(m);
        for (int i = 0; i < L; ++i) if (m >> i & 1) { sx += v[i].first; sy += v[i].second; }
        left_map[{sx, sy, k}]++;
    }
    vector<ll> ans(N + 1, 0);
    for (int m = 0; m < (1 << R); ++m) {
        ll sx = 0, sy = 0; int k = __builtin_popcount(m);
        for (int i = 0; i < R; ++i) if (m >> i & 1) { sx += v[L + i].first; sy += v[L + i].second; }
        // For each total size t, look up left count with size t - k
        for (int t = k; t <= N; ++t) {
            auto it = left_map.find({gx - sx, gy - sy, t - k});
            if (it != left_map.end()) ans[t] += it->second;
        }
    }
    for (int k = 1; k <= N; ++k) cout << ans[k] << '\n';
    return 0;
}

Pitfalls

Problem 3 · Email Filing

Official problem (cpid=1208)

Statement (paraphrased)

N emails, M folders, screen height K. Initially folders 1..K and emails 1..K are visible. Both scroll bars only move down, except the email list can "snap back" once it shows the last K emails after a file. Each email i must be filed into folder fi. Decide whether the filing is achievable.

Constraints

Key idea

Simulate. Keep two pointers: top-of-folder window F and the email pointer. Greedy: whenever the next email visible in the window can be filed (its folder is in the current folder window), file it; else scroll folders down by one. Two passes matter: first the "forward" pass on emails 1..N-K, then the "tail" pass on the last K which may be filed in any order while the folder window slides forward. The textbook solution uses a stack of "pending" emails whose folders haven't scrolled into view yet and a sorted multiset of upcoming folders; whenever the folder window advances, pop any pending emails whose folder just entered view.

Complexity target

O((N + M) log M) per test case.

C++ reference solution

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

bool solve(int N, int M, int K, vector<int>& f){
    // Forward phase: emails [1..N-K], folder window starts at [1..K]
    int folderTop = 1;        // 1-indexed top folder visible
    int emailIdx  = 0;        // next email to consider (0-indexed)
    int tail = max(0, N - K); // emails to handle in forward phase
    // Stack of unfiled emails currently in the visible email window
    deque<int> window;        // folder ids for emails currently in window (top..top+K-1)
    auto canFile = [&](int folder){ return folder >= folderTop && folder < folderTop + K; };

    for (int i = 0; i < min(K, tail); ++i) window.push_back(f[i]);
    int next = min(K, tail);
    while (!window.empty() || next < tail) {
        bool fired = false;
        // file from the back (newest) if visible — only the bottom-most slot can vanish freely
        while (!window.empty() && canFile(window.back())) {
            window.pop_back();
            if (next < tail) { window.push_back(f[next++]); }
            fired = true;
        }
        if (fired) continue;
        // Otherwise scroll folders down
        if (folderTop + K - 1 >= M) return false;
        ++folderTop;
    }
    // Tail phase: last K emails are visible and may be filed in any order
    multiset<int> pending(f.begin() + tail, f.end());
    while (!pending.empty()) {
        auto it = pending.lower_bound(folderTop);
        if (it != pending.end() && *it < folderTop + K) { pending.erase(it); }
        else {
            if (folderTop + K - 1 >= M) return false;
            ++folderTop;
        }
    }
    return true;
}

int main(){
    int T; cin >> T;
    while (T--){
        int N, M, K; cin >> N >> M >> K;
        vector<int> f(N);
        for (auto& x : f) cin >> x;
        cout << (solve(N, M, K, f) ? "YES" : "NO") << '\n';
    }
}

Pitfalls