U USACO Prep

USACO 2020 January · Gold · 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 — Time is Mooney

Statement

A directed graph of N cities with edges (u, v). Visiting city v earns mv mooney. Each traversed edge costs 1 day; at the end of T days Bessie loses C · T² mooney (cost grows quadratically with time). She starts and ends at city 1. Maximize net profit (sum of m at visited cities − C · T²).

Constraints

Key idea

Time T is bounded: best gross profit per day is ≤ max m ≤ 1000, so once C · T > 1000, going further is strictly worse. T_max ≈ 1000. DP: dp[t][v] = max mooney collected after t days ending at v. Transition: dp[t+1][v] = max over (u, v) of dp[t][u] + mv. Answer = max over t of dp[t][1] − C · t².

Complexity target

O(T_max · M) ≈ 1000 · 2000 = 2 · 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, M; ll C;
    cin >> N >> M >> C;
    vector<ll> mv(N);
    for (auto& x : mv) cin >> x;
    vector<pair<int,int>> edges(M);
    for (auto& [u,v] : edges) { cin >> u >> v; --u; --v; }

    const int T = 1001; // T > sqrt(max_m / C) * something; 1000 suffices for the stated bounds
    vector<vector<ll>> dp(T + 1, vector<ll>(N, LLONG_MIN));
    dp[0][0] = 0;
    ll ans = 0;
    for (int t = 0; t < T; ++t) {
        for (auto& [u, v] : edges) {
            if (dp[t][u] == LLONG_MIN) continue;
            ll cand = dp[t][u] + mv[v];
            if (cand > dp[t + 1][v]) dp[t + 1][v] = cand;
        }
        // Bessie must end at city 1 (index 0). Net profit at day t+1 if back home.
        if (dp[t + 1][0] != LLONG_MIN) ans = max(ans, dp[t + 1][0] - C * (ll)(t + 1) * (t + 1));
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Farmer John Solves 3SUM

Statement

Given an array a1..N, define f(i, j) = number of unordered pairs (p, q) with i ≤ p < q ≤ j and ap + aq = 0. Answer Q queries each asking for f(l, r).

Constraints

Key idea

Precompute cnt[i][j] = number of valid pairs entirely inside [i, j]. Iterate j outward and for each j sweep i from j−1 down to 0, adding +1 whenever ai + aj = 0. Then build a 2D prefix sum so cnt[i][j] = cnt[i+1][j] + cnt[i][j−1] − cnt[i+1][j−1] + (ai+aj==0). Each query is O(1). Total O(N²) precomp, O(Q) answer.

Complexity target

O(N² + Q). 2.5 · 107 table cells, each a long long → ~200 MB if naive; use 32-bit pairs or store row-by-row carefully. Most ACs use a vector<vector<long long>> with N = 5000 which is 200 MB — tight but fits with int32.

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, Q; cin >> N >> Q;
    vector<ll> a(N);
    for (auto& x : a) cin >> x;

    // cnt[i][j] = # pairs (p, q), i <= p < q <= j, with a[p] + a[q] = 0.
    // Use long long for the answers (can grow to ~N^2/2 = 1.25e7, fits 32-bit
    // but we'll be safe). Row 0..N-1, col 0..N-1.
    vector<vector<ll>> cnt(N, vector<ll>(N, 0));
    for (int i = N - 1; i >= 0; --i) {
        for (int j = i + 1; j < N; ++j) {
            cnt[i][j] = cnt[i + 1][j] + cnt[i][j - 1] - cnt[i + 1][j - 1];
            if (a[i] + a[j] == 0) ++cnt[i][j];
        }
    }
    while (Q--) {
        int l, r; cin >> l >> r; --l; --r;
        cout << cnt[l][r] << "\n";
    }
}

Pitfalls

Problem 3 — Springboards

Statement

Bessie walks from (0, 0) to (X, Y) on an integer grid using only +x or +y unit moves. There are P springboards; each instantly teleports her from (x1, y1) to (x2, y2) with x2 ≥ x1, y2 ≥ y1 (a free Manhattan jump). Minimize the total Manhattan distance she actually walks (springboard hops are free).

Constraints

Key idea

DP: for each springboard i, let f(i) = min Manhattan distance walked to arrive at springboard i's start (x1i, y1i), then take the springboard to (x2i, y2i). The walked distance is (x1i + y1i) − (x2j + y2j) + g(j), summed over the best predecessor j with x2j ≤ x1i, y2j ≤ y1i. Coordinate-compress y, sort events by x, and maintain a Fenwick tree of "min g(j) − x2 − y2" indexed by y2. Final answer: X + Y − max savings reachable to (X, Y).

Complexity target

O(P log P) after coordinate compression.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

struct Fenw {
    int n; vector<ll> t;
    Fenw(int n) : n(n), t(n + 1, INF) {}
    void upd(int i, ll v) { for (++i; i <= n; i += i & -i) t[i] = min(t[i], v); }
    ll qry(int i) { ll r = INF; for (++i; i > 0; i -= i & -i) r = min(r, t[i]); return r; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int P; ll X, Y;
    cin >> P >> X; // statement order: P first, then X, Y? [verify cpid=995]
    // Common format: first line "P N" where N is the grid (X=Y=N). Adjust as needed.
    Y = X;
    vector<array<ll, 4>> sp(P); // x1, y1, x2, y2
    vector<ll> ys;
    for (auto& s : sp) {
        cin >> s[0] >> s[1] >> s[2] >> s[3];
        ys.push_back(s[1]); ys.push_back(s[3]);
    }
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
    auto yid = [&](ll y){ return (int)(lower_bound(ys.begin(), ys.end(), y) - ys.begin()); };

    // Events: process springboards by (x1, +0) "use as endpoint" then (x2, +1) "register".
    vector<tuple<ll, int, int>> ev; // (x, type 0=use 1=register, idx)
    for (int i = 0; i < P; ++i) {
        ev.push_back({sp[i][0], 0, i});
        ev.push_back({sp[i][2], 1, i});
    }
    sort(ev.begin(), ev.end());

    Fenw fw((int)ys.size());
    // dp[i] = min walked distance to reach end of springboard i (i.e., at (x2_i, y2_i))
    vector<ll> dp(P, INF);

    for (auto& [x, t, i] : ev) {
        if (t == 0) {
            // Arrive at start of springboard i. Best predecessor j has x2_j <= x1_i, y2_j <= y1_i.
            ll best = fw.qry(yid(sp[i][1]));
            ll arr = sp[i][0] + sp[i][1]; // Manhattan from origin via best predecessor
            ll cost = (best == INF) ? arr : best + arr;
            dp[i] = cost; // walked-distance to end of springboard i (springboard hop is free)
        } else {
            // Register springboard i's endpoint.
            if (dp[i] < INF) fw.upd(yid(sp[i][3]), dp[i] - sp[i][2] - sp[i][3]);
        }
    }
    // Answer = X + Y minus max saving to (X, Y). Equivalent formula:
    // best dp[i] + (X - x2_i) + (Y - y2_i) over i (and the option of skipping all boards).
    ll ans = X + Y;
    for (int i = 0; i < P; ++i) if (dp[i] < INF) {
        ans = min(ans, dp[i] + (X - sp[i][2]) + (Y - sp[i][3]));
    }
    cout << ans << "\n";
}

Pitfalls

What Gold January 2020 was actually testing