U USACO Prep

USACO 2016 December · Silver · all three problems

← Full December 2016 set · Official results

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

Statement

Farmer John has N haybales at integer positions on a 1D road. Answer Q queries: for each [A, B], output the number of haybales x with A ≤ x ≤ B.

Constraints

Key idea

Sort the haybale positions once. For a query [A, B] the answer is upper_bound(B) − lower_bound(A) on the sorted array — i.e. the count of indices i with pos[i] ∈ [A, B].

Complexity target

O((N + Q) log N): one sort, two binary searches per query.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vector<int> pos(N);
    for (auto& x : pos) cin >> x;
    sort(pos.begin(), pos.end());

    while (Q--) {
        int a, b; cin >> a >> b;
        auto lo = lower_bound(pos.begin(), pos.end(), a);
        auto hi = upper_bound(pos.begin(), pos.end(), b);
        cout << (hi - lo) << "\n";
    }
}

Pitfalls

Problem 2 — Cities and States

Statement

N cities are given, each with a name (≥ 2 letters) and a 2-letter state code. Two cities (Ci, Si) and (Cj, Sj) form a "special pair" if the first two letters of Ci equal Sj, the first two letters of Cj equal Si, and the states are different (Si ≠ Sj). Count unordered special pairs.

Constraints

Key idea

Reduce each city to the ordered pair (prefix2, state). Two cities (Pi, Si) and (Pj, Sj) form a special pair iff Pi = Sj, Pj = Si, and Si ≠ Sj. Bucket cities by (prefix2, state) in a hashmap. For each city in bucket (P, S) the number of partners is the count of bucket (S, P) — except we must exclude entries where the partner has the same state (i.e. S = P, which would also kill the different-state condition; equivalently subtract the count of bucket (P, P) when P = S). Sum and divide by 2 for unordered pairs.

Complexity target

O(N) using an unordered_map keyed by a 4-character code (encode as a 32-bit int).

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;
    // Encode (prefix2, state) as a 4-letter code -> integer.
    auto enc = [](const string& a, const string& b) {
        return ((a[0] - 'A') * 26 + (a[1] - 'A')) * 676
             + ((b[0] - 'A') * 26 + (b[1] - 'A'));
    };

    vector<int> codes(N), prefkey(N), statekey(N);
    unordered_map<int, int> cnt;
    cnt.reserve(N * 2);
    for (int i = 0; i < N; ++i) {
        string c, s; cin >> c >> s;
        string p = c.substr(0, 2);
        codes[i]   = enc(p, s);
        cnt[codes[i]]++;
        // Save P and S as 0..675 integers for the swap lookup.
        prefkey[i]  = (p[0] - 'A') * 26 + (p[1] - 'A');
        statekey[i] = (s[0] - 'A') * 26 + (s[1] - 'A');
    }

    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        if (prefkey[i] == statekey[i]) continue;          // P == S can't pair (same-state)
        int swapped = statekey[i] * 676 + prefkey[i];     // bucket (S, P)
        auto it = cnt.find(swapped);
        if (it != cnt.end()) ans += it->second;
    }
    cout << (ans / 2) << "\n";
}

Pitfalls

Problem 3 — Moocast

Statement

N cows have walkie-talkies with individual transmission powers Pi. Cow i can directly send a message to cow j if the Euclidean distance between them is at most Pi (one-way, since Pj may be smaller). Messages can be relayed. For each cow as the originator, find how many cows the message can reach; output the maximum over all starting cows.

Constraints

Key idea

Build a directed reachability graph: edge i → j iff dist²(i, j) ≤ Pi². With N ≤ 200 the graph has at most 40 000 edges. For each source run BFS/DFS and count reached nodes; report the maximum. Compare squared distances to avoid floating point.

Complexity target

O(N · (N + E)) = O(N³) ≈ 8 · 106. Plenty of room.

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<ll> x(N), y(N), p(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> p[i];

    // adj[i] = cows j such that cow i can directly send to j (dist^2 <= p[i]^2).
    vector<vector<int>> adj(N);
    for (int i = 0; i < N; ++i) {
        ll P2 = p[i] * p[i];
        for (int j = 0; j < N; ++j) if (j != i) {
            ll dx = x[i] - x[j], dy = y[i] - y[j];
            if (dx * dx + dy * dy <= P2) adj[i].push_back(j);
        }
    }
    int best = 0;
    for (int s = 0; s < N; ++s) {
        vector<char> seen(N, 0);
        queue<int> q; q.push(s); seen[s] = 1;
        int cnt = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop(); ++cnt;
            for (int v : adj[u]) if (!seen[v]) { seen[v] = 1; q.push(v); }
        }
        best = max(best, cnt);
    }
    cout << best << "\n";
}

Pitfalls

What Silver December 2016 was actually testing