U USACO Prep

2024 January Platinum — three problems

← 2024 January contest index · Official results page

Platinum is well above my current target. I'm logging the subtask structure, the algorithmic family, and a skeleton solution per problem so I have something to come back to.

These are reading exercises for me. Code below is a faithful sketch of the editorial's approach, not a guaranteed full-credit submission — partial credit on the listed subtasks is the realistic goal.

Problem 1 · Island Vacation

Official statement (cpid=1380)

Statement (paraphrased)

A connected graph on N islands has at most ⌊3(N−1)/2⌋ edges; each edge lies in at most one simple cycle. Bessie starts at island 1. At every island i she terminates with probability pi (given as a fraction mod 1e9+7), else she picks a uniformly random unvisited bridge and crosses it. Output, for each island, the probability she terminates there (mod 1e9+7).

Subtasks

Constraints

Key idea

The "each edge in ≤ 1 cycle" condition makes the graph a cactus. Build the block-cut tree: each block is either a bridge or a simple cycle. DP over the block-cut tree. Tree case: standard per-edge probability propagation (probability of not having returned multiplied by 1/deg). Cycle case: walk around the cycle in both directions and sum over which side we eventually traverse; account for the fact that once we enter a cycle node and pick a direction, both edges out of that node are still unvisited initially.

Complexity

O((N + M) log MOD) for modular inverses; the block-cut tree DP itself is linear.

C++ reference (skeleton)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL;

ll pw(ll a, ll b) { ll r = 1; a %= MOD; while (b){ if(b&1) r = r*a%MOD; a = a*a%MOD; b >>= 1; } return r; }
ll inv(ll a) { return pw(a, MOD - 2); }

// Skeleton: build block-cut tree of a cactus, then DFS it propagating arrival probability.
// [verify] block-cut construction and cycle-block DP against editorial cpid=1380
int N, M;
vector<pair<int,int>> g[10005];   // (neighbour, edge_id)
ll prob[10005];                    // p_i mod
ll endProb[10005];                 // answer per island

// stub: BCC into bridges and simple cycles, build forest of blocks,
// DFS root=island 1, accumulate endProb[v] += arrive[v] * prob[v].
void solve() {
    // ... omitted skeleton; the meaningful work is the cactus DP.
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) { ll num, den; scanf("%lld %lld", &num, &den); prob[i] = num * inv(den) % MOD; }
    for (int i = 0; i < M; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back({v, i}); g[v].push_back({u, i}); }
    solve();
    for (int i = 1; i <= N; i++) printf("%lld\n", endProb[i]);
}

Pitfalls

Problem 2 · Merging Cells

Official statement (cpid=1381)

Statement (paraphrased)

N cells in a row with sizes s1..sN and labels 1..N. Repeatedly pick a uniformly random adjacent pair and merge them: the merged cell takes the sum of sizes and the label of the strictly larger cell (ties → the larger label). After N−1 merges one cell remains. Output the probability each original label is the final label, mod 109+7.

Subtasks

Constraints

Key idea

For each label k, compute P[k] = probability label k survives. Condition on the final interval [l, r] that label k "absorbs": survival happens iff (a) the merge tree contracts [l, r] before merging with the outside, and (b) within [l, r] label k always sits on the side of the larger sum at every merge. The probability of a particular contraction order on N cells is a classical Catalan-number / random binary tree quantity; let f(l, r) = probability that the random process first reduces [l, r] to a single cell before ever merging cell l with l−1 or cell r with r+1.

f satisfies an O(N3) DP that's tight at N = 5000; with the right reformulation (counting orderings by which adjacency is collapsed last) it tightens to O(N2) — which is what fits in 2 s.

Complexity

O(N2) for the full subtask.

C++ reference (skeleton)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL;

ll pw(ll a, ll b) { ll r = 1; a %= MOD; while (b){ if(b&1) r = r*a%MOD; a = a*a%MOD; b >>= 1; } return r; }
ll inv(ll a) { return pw(a, MOD - 2); }

int N;
ll s[5005], pref[5005];
ll ans[5005];

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) { scanf("%lld", &s[i]); pref[i] = pref[i-1] + s[i]; }
    // f[l][r] = probability the interval [l, r] is fully contracted before merging across either boundary.
    // Recurrence: f[l][r] = sum over the LAST merge inside [l, r] of (probability that merge happens last)
    //            weighted by f[l][k] * f[k+1][r].   [verify] full recurrence against editorial cpid=1381
    // For each label k, walk outward from cell k and sum f[l][r] * (prob label k wins inside [l, r]).
    // Skeleton — the O(N^2) reformulation is the trick.
    for (int i = 1; i <= N; i++) ans[i] = 0;     // placeholder
    for (int i = 1; i <= N; i++) printf("%lld\n", ans[i]);
}

Pitfalls

Problem 3 · Mooball Teams III

Official statement (cpid=1382)

Statement (paraphrased)

N cows at points (xi, yi) with both x and y coordinates being permutations of 1..N. Assign each cow to RED, BLUE, or NEITHER such that (1) both teams are non-empty and (2) the two coloured sets are separable by a single axis-aligned line at a non-integer coordinate. Count the assignments mod 109+7.

Subtasks

Constraints

Key idea

Inclusion–exclusion over the axis. Fix a vertical split at x = k + ½ separating left set L (size k) from right set R (size N−k). Each cow in L is RED, NEITHER, or doesn't exist for this split; symmetric for R as BLUE. Counting assignments where L is non-empty RED and R is non-empty BLUE: (2k−1)(2N−k−1). Sum over k = 1..N−1 for the vertical line case, double for horizontal, then subtract the overlap (assignments separable by both lines simultaneously) using a 2-D scan with a Fenwick tree.

Complexity

O(N log N) for the overlap count, O(N) for the two single-axis counts.

C++ reference (skeleton)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL;

ll pw(ll a, ll b) { ll r = 1; a %= MOD; while (b){ if(b&1) r = r*a%MOD; a = a*a%MOD; b >>= 1; } return r; }

int N;
int yof[200005];

// Fenwick over y for the overlap count.
ll bit[200005];
void upd(int i, ll v) { for (; i <= N; i += i & -i) bit[i] = (bit[i] + v) % MOD; }
ll qry(int i) { ll r = 0; for (; i > 0; i -= i & -i) r = (r + bit[i]) % MOD; return r; }

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) { int x, y; scanf("%d %d", &x, &y); yof[x] = y; }

    ll pow2[200005]; pow2[0] = 1;
    for (int i = 1; i <= N; i++) pow2[i] = pow2[i-1] * 2 % MOD;

    // Vertical-only: sum_{k=1}^{N-1} (2^k - 1)(2^{N-k} - 1)
    ll vert = 0;
    for (int k = 1; k < N; k++) vert = (vert + (pow2[k] - 1 + MOD) % MOD * ((pow2[N-k] - 1 + MOD) % MOD)) % MOD;
    ll horiz = vert;       // by symmetry of permutations

    // Both-line separable: sweep x left-to-right, for each split count how many cows are "above"
    // vs "below" the chosen y-cut on each side. Use Fenwick on y.
    // [verify] overlap formula and inclusion-exclusion sign against editorial cpid=1382
    ll both = 0;
    for (int x = 1; x < N; x++) {
        upd(yof[x], 1);
        // contribution roughly (#left-below)(#left-above)(#right-below)(#right-above)
        // packaged through the (2^a - 1) terms — skeleton only.
    }

    ll ans = ((vert + horiz - both) % MOD + MOD) % MOD;
    printf("%lld\n", ans);
}

Pitfalls