U USACO Prep

2022 January Gold — three problems

← 2022 January contest index · Official results page

Gold 2022-Jan is a counting DP (Drought), an offline reverse-time DSU (Farm Updates), and a constructive reasoning problem (Tests for Haybales).

Read the official PDF first. Paraphrases below are my own; if my wording and the PDF disagree, the PDF wins. All three problem links go to usaco.org.

Problem 1 · Drought

Official statement (cpid=1185)

Statement (paraphrased)

Count N-tuples (h1,…,hN) with 0 ≤ hi ≤ Hi such that FJ can equalise the array using the Bronze operation (pick two adjacent cows, decrease both by 1). Output the count mod 109+7.

Constraints

Key idea

From Bronze: feasibility for N ≥ 3 is equivalent to "greedy left-to-right with target = min(h) ends at target". Reformulate: fix the target t = min(h). Walking left to right, the carry ci = hi − t accumulates and gets passed forward; the constraint is ci ≥ 0 at every prefix and the final hN after applying carry equals t. After algebra this reduces to a 2-D DP over (position i, current carry c) with c bounded by max Hi. For each target t (0..max H), run the DP over remaining capacity. Sum results carefully to avoid double counting min(h) = t for several t's simultaneously — use inclusion–exclusion ("≥ t" minus "≥ t+1") or fix t as exactly the minimum by forcing some i with hi = t.

Complexity per t: O(N · maxH). Total: O(N · maxH2) ≈ 108, borderline but fits.

Complexity

O(N · maxH2).

C++ reference

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int N;
vector<int> H;

// count arrays with h_i in [t, H_i] s.t. greedy left-to-right (target t) ends with 0 carry.
long long countGE(int t) {
    // dp[c] = number of ways, c = current carry (excess pushed from previous position)
    int maxC = *max_element(H.begin(), H.end()) - t + 1;
    if (maxC <= 0) return 0;
    vector<long long> dp(maxC, 0), nd(maxC, 0);
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        fill(nd.begin(), nd.end(), 0);
        int hi = H[i] - t;
        if (hi < 0) return 0;
        // choose h_i' = h_i - t in [0, hi]; new carry = old carry + h_i' (last position must end at 0)
        for (int c = 0; c < maxC; c++) if (dp[c]) {
            for (int v = 0; v <= hi && c + v < maxC; v++) {
                int nc = (i == N - 1) ? (c + v == 0 ? 0 : -1) : c + v;
                if (nc < 0) continue;
                nd[nc] = (nd[nc] + dp[c]) % MOD;
            }
        }
        swap(dp, nd);
    }
    return dp[0];
}

int main() {
    scanf("%d", &N); H.resize(N);
    int mxH = 0;
    for (int i = 0; i < N; i++) { scanf("%d", &H[i]); mxH = max(mxH, H[i]); }
    // inclusion-exclusion: countGE(t) - countGE(t+1) gives those with min exactly t
    long long ans = 0;
    for (int t = 0; t <= mxH; t++) {
        long long a = countGE(t), b = countGE(t + 1);
        ans = (ans + (a - b + MOD)) % MOD;
    }
    printf("%lld\n", ans);
}

Note: the DP above is illustrative; the real submission needs the inner loop optimised with prefix sums to fit in time.

Pitfalls

Problem 2 · Farm Updates

Official statement (cpid=1186)

Statement (paraphrased)

N farms, all initially active and isolated. Q ops follow: (A x y) add an edge x–y; (R e) remove the e-th-added edge; (D x) deactivate farm x. A farm is "relevant" at time t if it is active or reachable through current edges from some still-active farm. For each farm, output the largest t (0..Q) at which it is still relevant.

Constraints

Key idea

Process operations in reverse. Going backwards: a (D x) becomes "x becomes active", an (R e) becomes "add edge e back", an (A x y) becomes "remove edge x–y". DSU naturally handles add-only edges, so we want the reverse stream to be add-only — and it is, modulo the (A …) reversals, but those (A) edges could have already been removed by an (R) before reversal; net edges that exist at the end of the timeline are exactly the edges never (R)'d. Build the final graph (after all Q ops), then sweep the timeline in reverse, with a DSU that supports "this component contains an active farm?" as component metadata. Whenever a farm becomes active (we just reversed its D), mark its component as active-touched and set its answer to "current time t"; whenever an edge addition (reverse of A) connects an active-touched component to a previously dead one, the dead side just became relevant at time t, so set ans = t for everyone in it. Use small-to-large or DSU-with-component-lists; or use the "answer = first time t (going backward) at which this farm sits in an active-touched component" formulation.

Complexity

O((N + Q) α(N)) with DSU + lazy component bookkeeping.

C++ reference

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

struct DSU {
    vector<int> p, sz;
    vector<char> alive;       // component contains an active farm
    vector<int> ansTime;      // for each component, the time at which it became "touched"
    DSU(int n) : p(n), sz(n, 1), alive(n, 0), ansTime(n, -1) { iota(p.begin(), p.end(), 0); }
    int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    void unite(int a, int b, int t, vector<int>& ans) {
        a = f(a); b = f(b); if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        // before merge: if exactly one side is alive, the other side just became relevant at time t.
        // Walking forward we'd have to flood the answer; in reverse-time we set ans on first touch.
        p[b] = a; sz[a] += sz[b];
        alive[a] = alive[a] || alive[b];
    }
};

int main() {
    // Skeleton: parse ops, identify edges that survive to time Q, build final graph,
    // then sweep ops reverse, updating DSU + answers.
    // Full implementation omitted for brevity.
    // [verify] full reverse-sweep correctness against editorial cpid=1186
    return 0;
}

Pitfalls

Problem 3 · Tests for Haybales

Official statement (cpid=1187)

Statement (paraphrased)

You are given an integer N and an array j1,…,jN where ji is the largest index with xji ≤ xi + K, for some sorted non-decreasing array x1 ≤ … ≤ xN and some K. Construct any valid (x, K) consistent with the j's. A solution is guaranteed to exist.

Constraints

Key idea

Each constraint says xji − xi ≤ K (tight: making ji+1 cross the K boundary) and xji+1 − xi > K (so xji+1 − xi ≥ K + 1). Pick K = N (or any large enough power). The system becomes a set of difference constraints on the xi's; solve via shortest-paths on a constraint graph (Bellman–Ford for small N, or a careful topological argument that the j array is monotone non-decreasing → segment-tree friendly). For the simpler half (N ≤ 5000), Bellman–Ford in O(N2) edges is fine. For the full version, exploit monotonicity of ji to process constraints in order and maintain a running x via two pointers + a segment tree of max-distance from a virtual source.

Complexity

O(N2) Bellman–Ford for partial credit; O(N log N) with segment tree for full.

C++ reference

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

// Partial-credit Bellman-Ford skeleton: edges
//   x[j[i]]   - x[i] <= K       (i -> j[i], weight +K)
//   x[i]      - x[j[i]+1] <= -(K+1)  (j[i]+1 -> i, weight -(K+1)) if j[i]+1 <= N
//   x[i+1]    - x[i] >= 0       (i -> i+1, weight 0 in the ">=" direction)
// Solve via Bellman-Ford from a virtual source connected with weight 0 to every node;
// x[i] = -dist[i] gives a feasible assignment.

int main() {
    int N; scanf("%d", &N);
    vector<int> j(N + 2);
    for (int i = 1; i <= N; i++) scanf("%d", &j[i]);
    const ll K = (ll)N + 5;
    vector<tuple<int,int,ll>> E;   // (u, v, w): dist[v] <= dist[u] + w
    for (int i = 1; i <= N; i++) {
        E.push_back({i, j[i], K});
        if (j[i] + 1 <= N) E.push_back({j[i] + 1, i, -(K + 1)});
        if (i < N) E.push_back({i, i + 1, 0});   // x_{i+1} >= x_i  i.e. dist_{i+1} <= dist_i + 0... [verify sign]
    }
    vector<ll> dist(N + 2, 0);    // virtual source: dist 0 everywhere
    for (int it = 0; it < N; it++) {
        bool ch = false;
        for (auto& [u, v, w] : E)
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; ch = true; }
        if (!ch) break;
    }
    // x[i] = dist[i] - min(dist) to keep non-negative
    ll mn = *min_element(dist.begin() + 1, dist.begin() + N + 1);
    printf("%lld\n", K);
    for (int i = 1; i <= N; i++) printf("%lld%c", dist[i] - mn, " \n"[i == N]);
}

Pitfalls