U USACO Prep

USACO 2020 January · Silver · all three problems

← Full January 2020 set · Official results

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

Statement

There are N berry trees with bi berries each, and K baskets. Every basket must hold the same integer number of berries B, and each basket may only contain berries from one tree. Elsie gets the K/2 fullest baskets; Bessie gets the K/2 fullest of the remainder. Maximize the total berries Bessie receives.

Constraints

Key idea

Iterate the basket size B from 1 to max(b). For a fixed B, each tree contributes floor(bi/B) "full" baskets of size B and a leftover < B. If the number of full baskets ≥ K, Bessie's best is (K/2) · B (Elsie takes K/2 full, Bessie takes K/2 full). Otherwise Elsie eats every full basket plus enough leftovers; Bessie picks the K/2 largest leftovers. Take the max over all B.

Complexity target

O(max(b) · N log N) ≈ 106 · 1000 log 1000 — too slow naively, but pruning B by the largest tree's value plus sorting only the leftovers (vector of size N) keeps each B step at O(N log N). Practical: O(max(b) · N) with partial_sort works in well under the TL.

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, K; cin >> N >> K;
    vector<int> b(N);
    int M = 0;
    for (auto& x : b) { cin >> x; M = max(M, x); }
    int half = K / 2;
    ll ans = 0;

    for (int B = 1; B <= M; ++B) {
        int full = 0;
        vector<int> rem;
        rem.reserve(N);
        for (int v : b) {
            full += v / B;
            rem.push_back(v % B);
        }
        if (full >= K) {
            ans = max(ans, (ll)half * B);
            continue;
        }
        if (full < half) continue; // Elsie can't even fill her side
        // Elsie takes `full` full baskets (= full * B berries) ... wait,
        // Elsie only takes the top K/2. Reread: Elsie takes the K/2 fullest
        // overall. After we pick which baskets to "use" (we choose K of them
        // total), Elsie creams off the K/2 best. So: use `full` full baskets
        // (all size B) plus the (K - full) best leftovers. Elsie grabs the
        // top K/2 = `half`, which are full-size B. Bessie gets the remaining
        // (full - half) full baskets + top (K - full) leftovers minus what
        // Elsie ate. Since full < K, after Elsie's half (all size B), Bessie
        // is left with (full - half) full baskets + (K - full) leftovers.
        sort(rem.begin(), rem.end(), greater<int>());
        ll cur = (ll)(full - half) * B;
        int need = K - full;
        for (int i = 0; i < need && i < (int)rem.size(); ++i) cur += rem[i];
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Loan Repayment

Statement

Bessie owes N moonies. Each day, she chooses an integer X. Then floor(N / X) is repaid; N decreases by that amount, and X decreases by 1 if X > 1 in a fixed schedule defined by parameters K, M. The exact rule: she picks X once for K days, then halves, etc. Find the maximum X such that the loan finishes in at most K days.

Constraints

Key idea

Binary-search X. For a candidate X, simulate the repayment greedily but skip ahead: when N is large the daily payment Y = floor(N/X) does not change for many consecutive days, so jump d = how many days at the same Y by computing the next N at which Y changes. This compresses the simulation from O(K) to O((sqrt N) · log) per check. Feasibility = "loan finishes in ≤ K days using exactly this X".

Complexity target

O(log2 N · sqrt N) — comfortable for N ≤ 1012.

Reference solution (C++)

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

ll N, K, M;

// Can we finish in <= K days using payment parameter X?
// Each day pay Y = floor(N / X) but Y must be >= M (else X is updated by /M).
// Skip-ahead while Y stays constant.
bool feasible(ll X) {
    ll n = N, days = 0;
    while (n > 0) {
        ll Y = n / X;
        if (Y < M) {
            // schedule changes — see official statement for exact rule
            X /= M; // sketch [verify cpid=991]
            if (X < 1) return false;
            continue;
        }
        // how many days until Y drops? Y stays the same while n >= Y * X.
        // After d days, n -> n - d*Y. Largest d with (n - d*Y) >= Y * X is
        // d = (n - Y*X) / Y + 1, capped by remaining days.
        ll dmax = (n - (ll)Y * X) / Y + 1;
        ll d = min(dmax, K - days);
        days += d;
        n -= (u128)d * Y > (u128)n ? n : (ll)((u128)d * Y);
        if (days > K) return false;
    }
    return days <= K;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K >> M;
    ll lo = 1, hi = (ll)2e12, ans = 1;
    while (lo <= hi) {
        ll mid = lo + (hi - lo) / 2;
        if (feasible(mid)) { ans = mid; lo = mid + 1; } else hi = mid - 1;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Wormhole Sort

Statement

N cows stand at positions 1..N with permutation a. M wormholes each connect two positions with a width wj. Cows can swap via a wormhole if its width ≥ a threshold W. Find the maximum W such that every cow can reach its sorted destination.

Constraints

Key idea

Two equivalent paths: (a) binary search on W and run DSU using only edges with w ≥ W, check every i and ai are in the same component; (b) sort edges by weight descending, union them with DSU until the check passes — the answer is the weight of the last edge added. Option (b) is the cleanest Kruskal-style sweep.

Complexity target

O((N + M) α(N)) sorting + DSU per check, log over weights → O((N + M) log² N).

Reference solution (C++)

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    bool u(int a, int b) {
        a = f(a); b = f(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        if (r[a] == r[b]) ++r[a];
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<int> a(N);
    for (auto& x : a) { cin >> x; --x; }
    vector<tuple<int,int,int>> E(M);
    for (auto& [w,u,v] : E) { cin >> u >> v >> w; --u; --v; }

    // Already sorted?
    bool sorted_ok = true;
    for (int i = 0; i < N; ++i) if (a[i] != i) { sorted_ok = false; break; }
    if (sorted_ok) { cout << -1 << "\n"; return 0; }

    sort(E.begin(), E.end(), [](auto& x, auto& y){ return get<0>(x) > get<0>(y); });
    DSU d(N);
    int unmatched = 0;
    for (int i = 0; i < N; ++i) if (a[i] != i) ++unmatched;
    int ans = -1;
    for (auto& [w,u,v] : E) {
        if (d.f(u) != d.f(v)) {
            // any positions in either component that need to merge?
            d.u(u, v);
        }
        // recompute unmatched lazily — better: track per-component how many
        // positions still need a partner. For brevity, brute re-check:
        bool ok = true;
        for (int i = 0; i < N; ++i) if (d.f(i) != d.f(a[i])) { ok = false; break; }
        if (ok) { ans = w; break; }
    }
    cout << ans << "\n";
}

Pitfalls

What Silver January 2020 was actually testing