U USACO Prep

USACO 2017 December · Silver · all three problems

← Full December 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec17results. 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 — My Cow Ate My Homework

Statement

Bessie has scores s1..sN. For each k = 0..N−2, consider the suffix sk+1..sN: drop its single lowest score, then take the average of the remaining scores. Output every value of k that achieves the maximum such average (smallest k first).

Constraints

Key idea

Process suffixes right-to-left. Maintain running suffix sum S, running minimum M, and suffix length L. For each k (i.e. each starting position from N−1 down to 0), the score after dropping the min is (S − M) / (L − 1). To compare fractions without floats, compare a/b vs c/d via a·d vs c·b in 64-bit. Store all k along with their fractions, find the max fraction, output every k that ties.

Complexity target

O(N) suffix sweep, O(N) compare pass.

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<int> s(N);
    for (auto& x : s) cin >> x;

    // For k = 0..N-2 (suffix starts at index k, must have >= 2 elements).
    vector<pair<ll,ll>> avg(N - 1); // numerator, denominator
    ll sum = 0, mn = LLONG_MAX, len = 0;
    for (int i = N - 1; i >= 0; --i) {
        sum += s[i]; mn = min(mn, (ll)s[i]); ++len;
        if (len >= 2) avg[i] = { sum - mn, len - 1 };
    }
    // Find max fraction.
    pair<ll,ll> best = avg[0];
    for (int k = 1; k < N - 1; ++k)
        if (avg[k].first * best.second > best.first * avg[k].second)
            best = avg[k];
    for (int k = 0; k < N - 1; ++k)
        if (avg[k].first * best.second == best.first * avg[k].second)
            cout << k << "\n";
}

Pitfalls

Problem 2 — Milk Measurement

Statement

There are N cows, each starting at 7 gallons/day. There are M events; each event says on day d, cow c changes production by ±x. After processing events in day order, count the number of days on which the set of top producers changes from the previous day (initial state: all N cows tied at 7).

Constraints

Key idea

A multiset (or map<int,int,greater> of production → count) lets you read off the current max and how many cows hold it in O(log N). Also track for each event-affected cow whether it was a max-holder before and after. The "top set" changes iff (a) the max value itself changed, or (b) the touched cow's membership in the max group flipped. You don't need to enumerate the set; just track its identity hash (max value, count, and whether the touched cow is in it).

Simpler implementation: maintain a sorted multiset of productions. For each event, look at the old max, the old production of cow c, and whether cow c was in the max set. Update, look at the new max and whether cow c is in it. If the (max, count, "is c in?") triple changed, the answer increments.

Complexity target

O((N + M) log N) with a multiset / map.

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, M; cin >> N >> M;
    vector<tuple<int,int,int>> ev(M); // day, cow, delta
    for (auto& [d, c, x] : ev) cin >> d >> c >> x;
    sort(ev.begin(), ev.end());

    unordered_map<int, ll> prod;       // cow -> production (default 7)
    map<ll, int, greater<ll>> freq;    // production -> count of cows
    freq[7] = N;                       // all N cows start at 7

    auto getProd = [&](int c) {
        auto it = prod.find(c);
        return it == prod.end() ? 7LL : it->second;
    };

    int ans = 0;
    for (auto& [d, c, x] : ev) {
        ll oldP = getProd(c);
        ll oldMax = freq.begin()->first;
        int oldCnt = freq.begin()->second;
        bool oldIn = (oldP == oldMax);

        if (--freq[oldP] == 0) freq.erase(oldP);
        ll newP = oldP + x; prod[c] = newP;
        ++freq[newP];

        ll newMax = freq.begin()->first;
        int newCnt = freq.begin()->second;
        bool newIn = (newP == newMax);

        if (oldMax != newMax || oldCnt != newCnt || oldIn != newIn) ++ans;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — The Bovine Shuffle

Statement

N cows stand in positions 1..N. The shuffle is the functional mapping a1..aN (not necessarily a permutation — multiple positions can map to the same target). The shuffle is applied infinitely many times. After enough applications, some positions are guaranteed to be empty and some are guaranteed to remain occupied. Count the positions that remain occupied forever.

Constraints

Key idea

Think of a as a functional graph: directed edge i → a[i]. After enough steps, every walk lands inside a cycle. The positions that stay occupied forever are exactly the nodes that lie on some cycle of the functional graph. Count cycle nodes: repeatedly remove leaves (in-degree 0), and what's left is the union of cycles.

Complexity target

O(N) — a topological-style peel.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(N + 1), indeg(N + 1, 0);
    for (int i = 1; i <= N; ++i) { cin >> a[i]; ++indeg[a[i]]; }

    // Peel nodes with indeg 0; they cannot lie on a cycle.
    queue<int> q;
    for (int i = 1; i <= N; ++i) if (indeg[i] == 0) q.push(i);
    int peeled = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); ++peeled;
        if (--indeg[a[u]] == 0) q.push(a[u]);
    }
    cout << (N - peeled) << "\n";
}

Pitfalls

What Silver December 2017 was actually testing