U USACO Prep

USACO 2019 February · Platinum · all three problems

← Full February 2019 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=feb19results. 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 — Cow Dating

Statement

Bessie has N candidate bulls, each independently accepting with probability pi. She picks a contiguous interval [l, r] and contacts those bulls. Output the maximum over all intervals of the probability that exactly one bull in the interval accepts. Print the answer multiplied by 106, floored.

Constraints

Key idea

For an interval [l, r], the probability of exactly one acceptance is f(l, r) = (Σi pi/(1−pi)) · Πi(1 − pi), where products and sums run over i ∈ [l, r]. Fix l; as r grows, the function is unimodal (single peak) — adding a bull helps while expected count is < 1 and hurts after. Two-pointer: for each l, advance r as long as f(l, r+1) ≥ f(l, r). Each pointer moves at most N total times, so O(N). The peak position is monotone in l, giving the two-pointer structure.

Complexity target

O(N) two-pointer with running product and sum.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<double> p(N);
    for (auto& x : p) { long long v; cin >> v; x = v / 1e6; }

    // f([l..r]) = sum_i (p_i / (1 - p_i)) * prod_i (1 - p_i)
    double best = 0;
    double sumRatio = 0, prodNeg = 1;
    int r = -1;
    for (int l = 0; l < N; ++l) {
        if (r < l - 1) { r = l - 1; sumRatio = 0; prodNeg = 1; }
        // Grow r while it improves.
        while (r + 1 < N) {
            double s2 = sumRatio + p[r + 1] / (1 - p[r + 1]);
            double pr2 = prodNeg * (1 - p[r + 1]);
            double next = s2 * pr2;
            double cur  = sumRatio * prodNeg;
            if (next >= cur) { sumRatio = s2; prodNeg = pr2; ++r; }
            else break;
        }
        best = max(best, sumRatio * prodNeg);
        // Drop l from the running window.
        if (r >= l) {
            prodNeg /= (1 - p[l]);
            sumRatio -= p[l] / (1 - p[l]);
        }
    }
    cout << (long long)floor(best * 1e6) << "\n";
}

Pitfalls

Problem 2 — Moorio Kart

Statement

A forest has N meadows and M edges with weights. A "farm" is a connected component with ≥ 2 nodes; let K be the number of farms. A valid track is a cycle that visits all K farms, entering and exiting each farm once at some pair of distinct meadows in that farm, with the K inter-farm edges each having length X. The length of a track is the sum of intra-farm path lengths plus K · X. Count, modulo 109+7, the number of tracks (over all orderings and entry/exit choices) whose length is ≥ Y.

Constraints

Key idea

For each farm, run all-pairs BFS/DFS to enumerate every ordered pair (u, v) of distinct nodes inside it; the entry/exit path length is dist(u, v). Bucket the multiset of farm path-lengths per farm. Convolve farm bucket counts to get a distribution over total intra-farm length sums. Each track contributes a factor of K!/2 (ordering of farms in the cycle) because rotations and the single reflection are equivalent. Final answer: sum over sums S where S + K·X ≥ Y of count(S) · (K! / (2·K)), modulo 109+7. Length bound: max total ≈ K · 2500 + 2500 ≈ 4·106, so cap convolution at max(Y, ...) — accumulate "> Y" into a single overflow bucket to keep DP size O(Y).

Complexity target

O(K · Y + N²) ≈ a few · 106. The all-pairs distances cost O(N · (N + M)) = O(N²).

Reference solution (C++)

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

int N, M, X, Y;
vector<pair<int,int>> g[1505];                  // (neighbor, weight)
int comp[1505]; vector<int> members[1505]; int nC = 0;

void dfs(int u, int c) {
    comp[u] = c; members[c].push_back(u);
    for (auto [v, w] : g[u]) if (comp[v] == -1) dfs(v, c);
}

long long pw(long long b, long long e, long long m) {
    long long r = 1; b %= m;
    while (e) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; }
    return r;
}

int main() {
    cin >> N >> M >> X >> Y;
    for (int i = 0; i < M; ++i) {
        int a, b, w; cin >> a >> b >> w;
        g[a].push_back({b, w}); g[b].push_back({a, w});
    }
    memset(comp, -1, sizeof comp);
    for (int i = 1; i <= N; ++i) if (comp[i] == -1) dfs(i, nC++);

    // Collect farms (components with size >= 2) and their multiset of pair distances.
    vector<vector<long long>> perFarm;            // perFarm[k][len] = count of unordered pairs (u<v)
    int CAP = Y + 1;                              // values >= Y all bucket-aliased to CAP-1
    for (int c = 0; c < nC; ++c) {
        if ((int)members[c].size() < 2) continue;
        vector<long long> cnt(CAP, 0);
        for (int u : members[c]) {
            // BFS/DFS distances from u within component.
            vector<long long> dist(N + 1, -1);
            dist[u] = 0;
            stack<int> st; st.push(u);
            while (!st.empty()) {
                int x = st.top(); st.pop();
                for (auto [v, w] : g[x]) if (dist[v] < 0) { dist[v] = dist[x] + w; st.push(v); }
            }
            for (int v : members[c]) if (v > u)
                cnt[min<long long>(dist[v], CAP - 1)] = (cnt[min<long long>(dist[v], CAP - 1)] + 1) % MOD;
        }
        perFarm.push_back(cnt);
    }
    int K = perFarm.size();
    if (K == 0) { cout << 0 << "\n"; return 0; }

    // Convolve all farm distributions, capping the running sum at CAP-1.
    vector<long long> dp(CAP, 0); dp[0] = 1;
    for (auto& f : perFarm) {
        vector<long long> nd(CAP, 0);
        for (int s = 0; s < CAP; ++s) if (dp[s])
            for (int t = 0; t < CAP; ++t) if (f[t]) {
                int ns = min(s + t, CAP - 1);
                nd[ns] = (nd[ns] + dp[s] * f[t]) % MOD;
            }
        dp = nd;
    }

    // Multiply by K!/2 (cycle arrangements) and 2 (entry/exit per farm is unordered pair so already / 2).
    long long ways = 1;
    for (int i = 2; i <= K; ++i) ways = ways * i % MOD;
    ways = ways * pw(2, MOD - 2, MOD) % MOD;

    // Sum lengths whose total intra-farm length + K*X >= Y.
    long long ans = 0, threshold = max(0, Y - K * X);
    for (int s = 0; s < CAP; ++s) if (s >= threshold) ans = (ans + dp[s]) % MOD;
    cout << ans * ways % MOD << "\n";
}

Pitfalls

Problem 3 — Mowing Mischief

Statement

Two cows walk monotone-up-right from (0, 0) to (T, T), each at their own pace; together they enclose a region whose area is to be minimized. Bessie picks a maximum-sized subset S of N flowers such that S lies on a monotone-increasing chain from (0,0) to (T,T) (so |S| is the length of the longest-increasing-chain). Both cows must touch every flower in S. The "area cut" is the sum of rectangle areas between consecutive flowers along the two routes. Output the minimum total area.

Constraints

Key idea

Compute the LIS (in x-sorted order, by y) and group flowers by their LIS layer (longest-chain depth). The required subset S is exactly the flowers in the maximum layer; consecutive flowers in S along the chain bound a rectangle. The cost between consecutive flowers (a, b) in S equals (b.x − a.x) · (b.y − a.y) minus the area saved by visiting an intermediate flower in the previous LIS layer. DP: layer-by-layer, compute the minimum total area for each flower in layer L as f(b) = min over a in layer L−1 with a.x < b.x, a.y < b.y of f(a) + (b.x − a.x)(b.y − a.y). The min transition is a Monge/concave DP solvable with divide-and-conquer optimization in O(N log N) per layer.

Complexity target

O(N log N) per LIS layer via D&C DP optimization; O(N log² N) overall.

Reference solution (C++)

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

int N, T;
struct F { int x, y; };
vector<F> flowers;
vector<vector<int>> layer;                      // layer[L] = indices in LIS layer L
vector<ll> dp;

// D&C optimization for min f(b) = min_{a in prev} f(a) + (b.x-a.x)*(b.y-a.y),
// where opt(b) is monotone in b across sorted prev/curr by x.
void solve(int lo, int hi, int plo, int phi,
           const vector<int>& cur, const vector<int>& prev,
           vector<ll>& ndp) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    int b = cur[mid];
    ll best = LLONG_MAX; int bestIdx = plo;
    for (int i = plo; i <= phi; ++i) {
        int a = prev[i];
        if (flowers[a].x >= flowers[b].x || flowers[a].y >= flowers[b].y) continue;
        ll cost = dp[a] + (ll)(flowers[b].x - flowers[a].x) * (flowers[b].y - flowers[a].y);
        if (cost < best) { best = cost; bestIdx = i; }
    }
    ndp[mid] = best;
    solve(lo, mid - 1, plo, bestIdx, cur, prev, ndp);
    solve(mid + 1, hi, bestIdx, phi, cur, prev, ndp);
}

int main() {
    cin >> N >> T;
    flowers.resize(N);
    for (auto& f : flowers) cin >> f.x >> f.y;
    sort(flowers.begin(), flowers.end(), [](auto& a, auto& b){ return a.x < b.x; });

    // LIS layers by y (patience sort piles).
    vector<int> piles; vector<int> lay(N);
    for (int i = 0; i < N; ++i) {
        int p = lower_bound(piles.begin(), piles.end(), flowers[i].y) - piles.begin();
        if (p == (int)piles.size()) piles.push_back(flowers[i].y);
        else piles[p] = flowers[i].y;
        lay[i] = p;
    }
    int L = piles.size();
    layer.assign(L, {});
    for (int i = 0; i < N; ++i) layer[lay[i]].push_back(i);

    dp.assign(N, 0);
    // Layer 0 dp = (x to 0)*(y to 0). Or seed with implicit (0,0).
    for (int i : layer[0]) dp[i] = (ll)flowers[i].x * flowers[i].y;
    for (int L1 = 1; L1 < L; ++L1) {
        auto& cur = layer[L1]; auto& prev = layer[L1 - 1];
        vector<ll> ndp(cur.size(), LLONG_MAX);
        solve(0, (int)cur.size() - 1, 0, (int)prev.size() - 1, cur, prev, ndp);
        for (int i = 0; i < (int)cur.size(); ++i) dp[cur[i]] = ndp[i];
    }
    // Final hop to (T, T).
    ll ans = LLONG_MAX;
    for (int i : layer[L - 1])
        ans = min(ans, dp[i] + (ll)(T - flowers[i].x) * (T - flowers[i].y));
    cout << ans << "\n";
}

Pitfalls

What Platinum February 2019 was actually testing