U USACO Prep

USACO 2020 January · Bronze · 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 — Word Processor

Statement

Bessie types an essay of N words with a line width of K characters. She greedily places each word on the current line if it fits (current line length + word length ≤ K), otherwise she starts a new line. Output the essay with words separated by spaces and newlines between filled lines.

Constraints

Key idea

Track the length of the current line. For each incoming word, if (current + word_len) ≤ K, append it with a space; otherwise emit a newline and start a new line with this word. No DP needed — it is the classic greedy line-fill ("first-fit").

Complexity target

O(total characters). N · K ≤ 8000 — trivial.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    int cur = 0; // chars on current line, NOT counting trailing space
    for (int i = 0; i < N; ++i) {
        string w; cin >> w;
        int L = (int)w.size();
        if (cur == 0) {
            cout << w;
            cur = L;
        } else if (cur + 1 + L <= K) {
            // Bessie's rule actually checks cur + L (no separator counted),
            // because spaces are added when printing but width counts letters.
            // The official statement counts only letters toward K.
            cout << ' ' << w;
            cur += L; // spaces are free per statement [verify cpid=987]
        } else {
            cout << '\n' << w;
            cur = L;
        }
    }
    cout << '\n';
}

Pitfalls

Problem 2 — Photoshoot

Statement

The original lineup is a permutation a1..N of 1..N. Farmer John recorded the array bi = ai + ai+1 for i = 1..N−1 but lost the permutation. Given b, reconstruct the lexicographically smallest valid a.

Constraints

Key idea

Once a1 is fixed, the whole permutation is forced: a2 = b1 − a1, a3 = b2 − a2, … Try each candidate a1 from 1 to N in increasing order, generate the implied a, and check that it is a permutation of 1..N (all values in [1,N] and distinct). Output the first that works.

Complexity target

O(N²) candidates × verification — at most 106 ops.

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

    for (int a1 = 1; a1 <= N; ++a1) {
        vector<int> a(N);
        a[0] = a1;
        vector<char> seen(N + 1, 0);
        bool ok = (a1 >= 1 && a1 <= N);
        if (ok) { seen[a1] = 1; }
        for (int i = 1; i < N && ok; ++i) {
            a[i] = b[i - 1] - a[i - 1];
            if (a[i] < 1 || a[i] > N || seen[a[i]]) { ok = false; break; }
            seen[a[i]] = 1;
        }
        if (ok) {
            for (int i = 0; i < N; ++i) cout << a[i] << " \n"[i == N - 1];
            return 0;
        }
    }
}

Pitfalls

Problem 3 — Race

Statement

Bessie runs a race on a 1D track of length K. Her speed starts at 0 and changes by ±1 per second; she must finish at speed 0. She gets a fatigue meter: at every second her speed exceeds a threshold T, fatigue increases. Output, for each query, the minimum total time to finish under the constraints. (The Bronze version asks for simple simulations on a fixed plan.)

Constraints

Key idea

Bessie's velocity profile is a triangle / trapezoid: accelerate from 0 up to some peak v, cruise, then decelerate from v back to 0. Distance under that profile is v(v+1) + cruise · v (in the standard "speed s for one full second" model). For each query, binary-search or close-form the peak v that exactly uses the fatigue budget, then compute the cruise length so total distance ≥ K.

Complexity target

O(N · log K) using binary search on the peak speed.

Reference solution (C++)

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

// Distance traveled if Bessie peaks at speed v with f fatigue-burning seconds at speed v.
// Accelerate 1..v (v seconds, distance v(v+1)/2), cruise at v for c seconds,
// decelerate v..1 (v seconds, distance v(v+1)/2). Total = v(v+1) + c*v.
// Fatigue spent at speeds > T: count seconds with speed in (T, v].

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll K; int N;
    cin >> K >> N;
    while (N--) {
        ll T, F; cin >> T >> F; // cruise threshold, fatigue budget
        // Try peak v: fatigue spent = max(0, v - T)*2 + cruise_seconds * max(0, [v > T])
        // ... (problem-specific formula; this is a sketch — verify against statement)
        ll lo = 1, hi = (ll)2e9, best = 1;
        auto feasible = [&](ll v) -> bool {
            // Minimal time to cover K with peak v and zero cruise above T:
            // accel + decel distance = v*(v+1). If >= K we're fine without cruising over T.
            ll triangle = v * (v + 1);
            if (triangle >= K) return true;
            // Otherwise cruise. Cruising at v > T burns fatigue every second.
            ll need = K - triangle;
            ll cruise = (need + v - 1) / v;
            ll fatigue = (v > T) ? cruise + 2 * (v - T) : 0;
            return fatigue <= F;
        };
        while (lo <= hi) {
            ll m = (lo + hi) / 2;
            if (feasible(m)) { best = m; hi = m - 1; } else lo = m + 1;
        }
        // Total time = 2*best + cruise.
        ll triangle = best * (best + 1);
        ll cruise = (triangle >= K) ? 0 : (K - triangle + best - 1) / best;
        cout << (2 * best + cruise) << "\n";
    }
}

Pitfalls

What Bronze January 2020 was actually testing