U USACO Prep

USACO 2017 January · Silver · all three problems

← Full January 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan17results. 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 — Cow Dance Show

Statement

N cows each have a dance duration di. The stage holds K cows at once. Cow 1..K start at time 0; whenever a cow finishes, the next cow in order steps onto the stage and dances for her own duration. The whole show must complete within Tmax time units. Find the minimum stage size K for which this is possible. K = N is always sufficient.

Constraints

Key idea

Binary search on K. For a candidate K, simulate with a min-heap of finish times: seed with the first K durations, then for each remaining cow pop the earliest finish e and push e + di. The total show time is the maximum heap value at the end. The "feasible" predicate (show time ≤ Tmax) is monotone in K, so binary search over [1, N] finds the minimum.

Complexity target

O(N log N log N): outer log N binary search, inner O(N log K) heap simulation. ~10⁵·14 ≈ 10⁶ ops.

Reference solution (C++)

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

int N; ll Tmax;
vector<ll> d;

bool feasible(int K) {
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int i = 0; i < K; ++i) pq.push(d[i]);
    ll done = 0;
    for (int i = K; i < N; ++i) {
        ll e = pq.top(); pq.pop();
        done = max(done, e);
        if (e + d[i] > Tmax) return false;  // early out
        pq.push(e + d[i]);
    }
    while (!pq.empty()) { done = max(done, pq.top()); pq.pop(); }
    return done <= Tmax;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> Tmax;
    d.assign(N, 0);
    for (auto& x : d) cin >> x;

    int lo = 1, hi = N, ans = N;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (feasible(mid)) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Hoof, Paper, Scissors

Statement

Bessie plays N rounds against Farmer John, and she knows his entire H/P/S sequence in advance. She is lazy and will switch her own gesture at most once over the whole game (zero switches is also allowed). Compute the maximum number of rounds Bessie can win.

Constraints

Key idea

For each gesture g ∈ {H, P, S}, let wg(i) = number of rounds in FJ's prefix of length i that Bessie wins by playing g constantly. Compute the three prefix arrays in O(N). The answer is max over (g1, g2) pairs and split index i of wg1(i) + (wg2(N) − wg2(i)), i.e., play g1 for the first i rounds and g2 for the rest. Try all 9 (g1, g2) pairs (g1 = g2 covers the "no switch" case) and all N + 1 split points.

Complexity target

O(N · 9) = O(N). Comfortable.

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

    // wins[g][i] = wins in the first i rounds if Bessie plays gesture g.
    // Encode H=0, P=1, S=2. Winning move vs FJ: H<-S, P<-H, S<-P.
    auto beats = [](char fj) -> int {
        if (fj == 'S') return 0; // H beats S
        if (fj == 'H') return 1; // P beats H
        return 2;                // S beats P
    };
    vector<vector<int>> w(3, vector<int>(N + 1, 0));
    for (int i = 0; i < N; ++i) {
        int b = beats(s[i]);
        for (int g = 0; g < 3; ++g)
            w[g][i + 1] = w[g][i] + (g == b ? 1 : 0);
    }

    int best = 0;
    for (int g1 = 0; g1 < 3; ++g1)
        for (int g2 = 0; g2 < 3; ++g2)
            for (int i = 0; i <= N; ++i)
                best = max(best, w[g1][i] + (w[g2][N] - w[g2][i]));

    cout << best << "\n";
}

Pitfalls

Problem 3 — Secret Cow Code

Statement

Define F(s) = s concatenated with s rotated one character to the right (last char becomes new first char). Starting from a seed string s of length L ≤ 30, repeatedly apply F to get an infinite string; each step doubles the length. Given a 1-indexed position N ≤ 1018, output the character at position N.

Constraints

Key idea

Let L be the initial length. Find the smallest power-of-2 multiple H = L · 2k that is ≥ N. If N is in the first half (N ≤ H/2 in the current expansion), recurse on N within the previous-level string of length H/2. Otherwise N is in the right half, which is the previous-level string rotated right by one: the character at position N in the right half is the character at position ((N − H/2) − 1 + (H/2) − 1) mod (H/2) + 1 in the left half — i.e., N' = N − H/2 − 1, and if N' == 0 the answer comes from position H/2 of the left half, else position N'. Halve H and repeat until N ≤ L; index into s.

Complexity target

O(log N) recursion steps, each O(1). Up to ~60 iterations for N = 1018.

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);
    string s; ll N; cin >> s >> N;
    ll L = (ll)s.size();

    // Find smallest H = L * 2^k with H >= N.
    ll H = L;
    while (H < N) H *= 2;

    // Walk back down. At each level the string has length H built from
    // (left half = previous level) ++ (previous level rotated right by 1).
    while (H > L) {
        ll half = H / 2;
        if (N > half) {
            // Right half: position N corresponds to position (N - half) in the
            // rotated copy. Rotation-right-by-1 maps left-position p to
            // right-position p+1 for p < half, and left-position half to
            // right-position 1. So to invert: right-position 1 -> left half,
            // right-position p > 1 -> left-position p - 1.
            ll r = N - half;
            N = (r == 1) ? half : r - 1;
        }
        H = half;
    }
    cout << s[N - 1] << "\n";
}

Pitfalls

What Silver January 2017 was actually testing