U USACO Prep

2022 January Platinum — three problems

← 2022 January contest index · Official results page

Platinum 2022-Jan is two haybale data-structure problems and a convex-hull geometry/optimisation. P1 is the deepest: a clever segment-tree argument over a "reachability under threshold K" relation.

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 · Minimizing Haybales

Official statement (cpid=1188)

Statement (paraphrased)

N stacks with heights hi. You may repeatedly swap two adjacent stacks whose heights differ by at most K. Output the lexicographically smallest sequence reachable.

Constraints

Key idea

Two stacks at positions i < j can swap (transitively) iff every stack between them is within K of both — equivalently, iff no stack between them blocks them (a "blocker" between values a and b is a stack whose height is < min(a,b) − K or > max(a,b) + K). Process stacks left to right, inserting each into a result list at the leftmost position not blocked by a "barrier" — a previously inserted stack whose height differs from the new one by more than K. This becomes a segment-tree / ordered-set problem: for the new element x, find the latest barrier (highest index where |y − x| > K), and insert just after it. Implement with a Fenwick / segment tree on insertion positions, plus a structure that, given x, finds the rightmost previously-inserted element with height < x − K OR > x + K.

Complexity

O(N log2 N) or O(N log N) with careful implementation.

C++ reference

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

// Segment tree over insertion positions (implicit) is heavy to write; here is the O(N^2)
// brute-force that scores partial credit on subtasks 1+2.
int main() {
    int N; long long K; scanf("%d %lld", &N, &K);
    vector<long long> h(N);
    for (int i = 0; i < N; i++) scanf("%lld", &h[i]);

    vector<long long> res;   // current ordered sequence
    for (int i = 0; i < N; i++) {
        // find latest position p in res such that |res[p] - h[i]| > K; insert at p+1.
        int p = (int)res.size() - 1;
        while (p >= 0 && llabs(res[p] - h[i]) <= K) p--;
        res.insert(res.begin() + (p + 1), h[i]);
    }
    for (int i = 0; i < (int)res.size(); i++) printf("%lld\n", res[i]);
    // [verify] full O(N log N) version against editorial cpid=1188
}

Pitfalls

Problem 2 · Counting Haybales

Official statement (cpid=1189)

Statement (paraphrased)

N stacks of haybales in a row. Operation: take the top bale of a taller stack and place it on an adjacent stack iff the two stacks differ in height by exactly 1. Repeat until no moves remain. Count distinct reachable final configurations mod 109 + 7.

Constraints

Key idea

The operation is highly local and reversible in a Tetris-like sense; the reachable configurations are characterised by a 1-D DP. Sort by the "potential" Σ hi·i and observe that valid final configs are those where no two adjacent stacks differ by > 1 (otherwise a move is still available). DP over position with state (current height) — heights are bounded by max h in input, but compressed using the observation that final heights stay within a small window around their starting profile. Concretely: let dp[i][k] = number of valid final configs of the prefix ending at position i with stack i having height k; transitions enforce |k − k'| ≤ 1 for adjacent stacks plus the total-mass conservation.

This is a Platinum-grade DP; the precise state often needs an extra index for "leftover mass to distribute". Editorial uses an N2-state DP with O(1) transitions.

Complexity

O(N2) per test case.

C++ reference

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

// Skeleton only: the precise DP transition and state design follow the editorial.
// State: dp[i][k] = ways to assemble a valid prefix of length i with stack i having height k,
//        using a total mass of (sum of first i input heights).
// Transition: dp[i+1][k'] += dp[i][k] over all k' with |k' - k| <= 1 and feasibility constraints.
// [verify] exact DP recurrence and feasibility filter against editorial cpid=1189

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        vector<long long> h(N);
        long long S = 0, mx = 0;
        for (int i = 0; i < N; i++) { scanf("%lld", &h[i]); S += h[i]; mx = max(mx, h[i]); }
        // Placeholder: print 1, since the empty/single-stack config is always reachable.
        // A real solve fills dp as described above.
        printf("%d\n", 1);
    }
}

Pitfalls

Problem 3 · Multiple Choice Test

Official statement (cpid=1190)

Statement (paraphrased)

N groups of 2-D integer vectors. Choose exactly one vector from each group; let s be the sum. Maximise |s|2 = s.x2 + s.y2. Output the maximum squared distance.

Constraints

Key idea

Classic result: the maximum of |s|2 over a Minkowski sum of finite point sets is attained at an extreme point of the Minkowski sum, which equals the sum of one extreme point from each set in some common direction. Compute the convex hull of each group, then the Minkowski sum of N convex polygons. The Minkowski sum of convex polygons with total k vertices can be built in O(k log k) by merging edges sorted by angle. After building the final polygon, scan all hull vertices and take the maximum squared distance to the origin.

Complexity

O((Σ |groupi|) log (Σ |groupi|)).

C++ reference

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct P { ll x, y; };
ll cross(P o, P a, P b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }

vector<P> hull(vector<P> v) {
    sort(v.begin(), v.end(), [](P a, P b){ return a.x != b.x ? a.x < b.x : a.y < b.y; });
    int n = v.size(), k = 0; vector<P> H(2 * n);
    for (int i = 0; i < n; i++) { while (k >= 2 && cross(H[k-2], H[k-1], v[i]) <= 0) k--; H[k++] = v[i]; }
    for (int i = n - 2, t = k + 1; i >= 0; i--) { while (k >= t && cross(H[k-2], H[k-1], v[i]) <= 0) k--; H[k++] = v[i]; }
    H.resize(k - 1); return H;
}

// Minkowski sum of two convex polygons (assumed CCW, lowest point first).
vector<P> mink(vector<P> A, vector<P> B) {
    auto rot = [](vector<P>& v) {
        int idx = 0;
        for (int i = 1; i < (int)v.size(); i++)
            if (make_pair(v[i].y, v[i].x) < make_pair(v[idx].y, v[idx].x)) idx = i;
        rotate(v.begin(), v.begin() + idx, v.end());
    };
    rot(A); rot(B);
    vector<P> R; R.reserve(A.size() + B.size() + 2);
    A.push_back(A[0]); A.push_back(A[1]); B.push_back(B[0]); B.push_back(B[1]);
    int i = 0, j = 0;
    while (i < (int)A.size() - 2 || j < (int)B.size() - 2) {
        R.push_back({A[i].x + B[j].x, A[i].y + B[j].y});
        ll c = cross({0,0}, {A[i+1].x - A[i].x, A[i+1].y - A[i].y},
                            {B[j+1].x - B[j].x, B[j+1].y - B[j].y});
        if (c >= 0 && i < (int)A.size() - 2) i++;
        if (c <= 0 && j < (int)B.size() - 2) j++;
    }
    return R;
}

int main() {
    int N; scanf("%d", &N);
    vector<P> cur;
    for (int g = 0; g < N; g++) {
        int k; scanf("%d", &k);
        vector<P> pts(k);
        for (int i = 0; i < k; i++) scanf("%lld %lld", &pts[i].x, &pts[i].y);
        vector<P> h = hull(pts);
        cur = g == 0 ? h : mink(cur, h);
    }
    ll best = 0;
    for (auto& p : cur) best = max(best, p.x * p.x + p.y * p.y);
    printf("%lld\n", best);
}

Pitfalls