U USACO Prep

USACO 2015 US Open · Silver · all three problems

← Full 2015 US Open set · Official results

Source. Statements paraphrased from usaco.org/index.php?page=open15results and per-problem pages (cpids 549–551).

Problem 1 — Bessie Goes Moo

Statement

Given lists of integer values for variables B, E, S, I, G, O, M (each with up to 500 listed values), count the number of distinct assignments such that the product (B+E+S+S+I+E) · (G+O+E+S) · (M+O+O) is divisible by 7.

Constraints

Key idea

Reduce every value mod 7. The product is 0 mod 7 iff at least one factor is. Enumerate residues: each of the 7 variables has 7 residue buckets, giving 77 ≈ 823 543 tuples — small. For each tuple compute the three factor residues mod 7 and check if any is 0. Multiply the per-variable bucket counts and add to the total. Naively 77 < 106; fast.

Smarter (and how the official editorial usually frames it): split into halves of three or four variables, build a residue distribution for each factor, then combine via a 7-bucket convolution. For 2015 Silver the 77 brute force is well within limits.

Complexity target

O(77) ≈ 8·105 operations.

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;
    map<char,int> id = {{'B',0},{'E',1},{'S',2},{'I',3},{'G',4},{'O',5},{'M',6}};
    ll cnt[7][7] = {{0}};                 // cnt[var][residue mod 7]
    for (int i = 0; i < N; ++i) {
        char v; int x; cin >> v >> x;
        cnt[id[v]][((x % 7) + 7) % 7]++;
    }

    ll ans = 0;
    int r[7];
    // Enumerate residues of (B, E, S, I, G, O, M) = indices 0..6.
    for (r[0] = 0; r[0] < 7; ++r[0])
    for (r[1] = 0; r[1] < 7; ++r[1])
    for (r[2] = 0; r[2] < 7; ++r[2])
    for (r[3] = 0; r[3] < 7; ++r[3])
    for (r[4] = 0; r[4] < 7; ++r[4])
    for (r[5] = 0; r[5] < 7; ++r[5])
    for (r[6] = 0; r[6] < 7; ++r[6]) {
        int F1 = (r[0] + r[1] + r[2] + r[2] + r[3] + r[1]) % 7;     // B+E+S+S+I+E
        int F2 = (r[4] + r[5] + r[1] + r[2]) % 7;                   // G+O+E+S
        int F3 = (r[6] + r[5] + r[5]) % 7;                          // M+O+O
        if (F1 != 0 && F2 != 0 && F3 != 0) continue;
        ll ways = 1;
        for (int i = 0; i < 7; ++i) ways *= cnt[i][r[i]];
        ans += ways;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Trapped in the Haybales (Silver)

Statement

Same setup as Bronze, but now Bessie's position B is fixed and she is currently not trapped. FJ wants to add hay to exactly one bale (any single bale; you choose) to trap her. Output the minimum total hay he must add — or −1 if no single-bale increment suffices.

Constraints

Key idea

Simulate escape on each side independently. To trap Bessie you must block both sides. So you only need to enlarge one bale on one side, plus a separate one on the other? No — exactly one bale total. That means at least one side must already trap her without help; otherwise no single addition works (output −1). So compute: does she currently escape left? right? If both, return −1. Suppose she currently escapes (say) right; she's already trapped left (else she'd escape there). Now binary search the additional size Δ added to some bale on the right side to stop her.

Concretely: for the side where she escapes, simulate her escape and try, for each bale on that side, the minimum Δ that flips the predicate. The minimum across bales is the answer. With sorted bales and N up to 105, a binary search on Δ per candidate bale, with O(N) simulation, is O(N² log V) worst case — fine for N=105? Actually N² is 1010; we need smarter. The standard Silver-difficulty approach: binary-search the single value Δ added to the bale that maximally stops her — i.e., binary search on the answer Δ globally, and per check, simulate escape with Δ added to whichever bale she would currently break (the cheapest spot to upgrade) — total O(N log V).

Complexity target

O(N log V), V = max coordinate (109).

Reference solution (C++)

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

int N;
ll B;
vector<pair<ll,ll>> bale;            // sorted by position: (pos, size)

// Can Bessie escape to the right when one bale (index addIdx, -1 = none) has +delta size?
bool escapesRight(int addIdx, ll delta) {
    // Find first bale strictly right of B.
    int i = upper_bound(bale.begin(), bale.end(), make_pair(B, LLONG_MAX)) - bale.begin();
    ll pos = B;
    while (i < N) {
        ll sz = bale[i].second + (i == addIdx ? delta : 0);
        ll D = bale[i].first - pos;
        if (D > sz) { pos = bale[i].first; i++; } else return false;
    }
    return true;
}
bool escapesLeft(int addIdx, ll delta) {
    int i = (int)(lower_bound(bale.begin(), bale.end(), make_pair(B, 0LL)) - bale.begin()) - 1;
    ll pos = B;
    while (i >= 0) {
        ll sz = bale[i].second + (i == addIdx ? delta : 0);
        ll D = pos - bale[i].first;
        if (D > sz) { pos = bale[i].first; i--; } else return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> B;
    bale.resize(N);
    for (auto& p : bale) cin >> p.second >> p.first;
    sort(bale.begin(), bale.end());

    bool eR = escapesRight(-1, 0);
    bool eL = escapesLeft(-1, 0);
    // To trap with a single bale enlargement, one side must already block her.
    if (eR && eL) { cout << -1 << "\n"; return 0; }
    if (!eR && !eL) { cout << 0 << "\n"; return 0; }    // already trapped

    // She currently escapes exactly one side; pick the right helper.
    bool toRight = eR;
    ll best = LLONG_MAX;
    // For each bale on that side, binary search the min delta to stop her.
    int lo, hi;
    if (toRight) {
        lo = upper_bound(bale.begin(), bale.end(), make_pair(B, LLONG_MAX)) - bale.begin();
        hi = N - 1;
    } else {
        lo = 0;
        hi = (int)(lower_bound(bale.begin(), bale.end(), make_pair(B, 0LL)) - bale.begin()) - 1;
    }
    for (int idx = lo; idx <= hi; ++idx) {
        ll l = 0, r = (ll)2e9, ans = -1;
        while (l <= r) {
            ll m = l + (r - l) / 2;
            bool esc = toRight ? escapesRight(idx, m) : escapesLeft(idx, m);
            if (!esc) { ans = m; r = m - 1; } else l = m + 1;
        }
        if (ans != -1) best = min(best, ans);
    }
    cout << (best == LLONG_MAX ? -1 : best) << "\n";
}

Pitfalls

Problem 3 — Bessie's Birthday Buffet

Statement

A row of N grass patches has qualities q1..qN (all distinct). Bessie can start at any patch and move between adjacent patches at a cost of E energy per step. She may eat any patch she visits, gaining its quality in energy — but once she eats quality v, she may never again eat a patch of quality ≤ v. (She can walk through any patch without eating.) Maximize her total energy.

Constraints

Key idea

Sort patches by quality ascending; the sequence of eaten patches must be a subsequence of this sorted order. DP: dp[i] = max energy when the last patch eaten is sorted-rank i. Transition: dp[i] = q[i] + max(0, max over j < i of dp[j] − E · |pos[i] − pos[j]|). Answer is max dp[i]. N = 1000 makes the O(N²) DP trivially fast.

Complexity target

O(N²) ≈ 106.

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; ll E; cin >> N >> E;
    vector<pair<ll,int>> a(N);          // (quality, original index)
    for (int i = 0; i < N; ++i) { cin >> a[i].first; a[i].second = i; }
    sort(a.begin(), a.end());            // ascending by quality

    vector<ll> dp(N, 0);
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        ll best = 0;                     // option: start here (eat only i)
        for (int j = 0; j < i; ++j) {
            ll travel = E * (ll)abs(a[i].second - a[j].second);
            ll cand = dp[j] - travel;
            if (cand > best) best = cand;
        }
        dp[i] = a[i].first + best;
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
}

Pitfalls

What Silver 2015 US Open was actually testing