USACO 2020 February · Platinum · all three problems

← Full February 2020 set · Official results

Problem 1 — Delegation

Statement

Platinum upgrade of Gold Delegation. Given a tree with N nodes, output the largest K such that the edges can be partitioned into vertex-disjoint paths of length exactly K (or determine for which K feasibility holds — phrasing varies; the constraint pool tests max K).

Constraints

• 1 ≤ N ≤ 10⁵.
• Time limit: 2s.

Key idea

Same multiset-pair-on-subtree greedy as Gold, but now we need to handle all divisors of N−1 efficiently. Observation: a candidate K must divide N−1. For each candidate, run the Gold dfs. The total work is bounded by N · d(N−1) where d is the number of divisors of N−1, but with care (early termination when a subtree has too many stubs > K) the amortised cost per K is much less and the harmonic-style bound makes the whole sum O(N log² N) in practice.

Complexity target

O(N log² N) total across all candidate K's, using multiset pairing per subtree.

Reference solution (C++)

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

int N;
vector<vector<int>> g;
int K_;
bool ok_;

// Iterative post-order DFS over the rooted tree.
// stub[u] = the (at most one) unmatched stub length passed up from u, or -1 if u fails.
vector<int> stub;

void run(int K) {
    K_ = K; ok_ = true;
    stub.assign(N, 0);
    // Iterative post-order
    vector<int> order; order.reserve(N);
    vector<int> par(N, -1);
    vector<int> stk = {0};
    vector<char> vis(N, 0); vis[0] = 1;
    while (!stk.empty()) {
        int u = stk.back(); stk.pop_back();
        order.push_back(u);
        for (int v : g[u]) if (!vis[v]) { vis[v] = 1; par[v] = u; stk.push_back(v); }
    }
    for (int i = (int)order.size() - 1; i >= 0 && ok_; --i) {
        int u = order[i];
        multiset<int> lens;
        for (int v : g[u]) if (v != par[u]) {
            if (stub[v] > 0) lens.insert(stub[v] + 1);
        }
        int leftover = -1;
        while (!lens.empty() && ok_) {
            int x = *lens.begin(); lens.erase(lens.begin());
            if (x > K) { ok_ = false; break; }
            if (x == K) continue;
            auto it = lens.find(K - x);
            if (it != lens.end()) { lens.erase(it); continue; }
            if (leftover != -1) { ok_ = false; break; }
            leftover = x;
        }
        if (!ok_) break;
        if (u == 0) { if (leftover != -1) ok_ = false; stub[u] = 0; }
        else stub[u] = (leftover == -1 ? 0 : leftover);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    g.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        g[a].push_back(b); g[b].push_back(a);
    }
    int best = 1;
    for (int K = 1; K <= N - 1; ++K) {
        if ((N - 1) % K) continue;
        run(K);
        if (ok_) best = K;
    }
    cout << best << "\n";
}

Pitfalls

• Iterative DFS — recursion at N = 10⁵ often stack-overflows on the USACO judge.
• Multiset pairing is O(deg log deg) per node. Across the whole tree that's O(N log N) per K. Sum over divisors → O(N · d(N−1) · log N).
• Edge cases: N = 1 (trivial), N − 1 prime (only K = 1 and K = N − 1 candidates).
• Stub passed up includes the parent edge. Same gotcha as Gold.

Problem 2 — Equilateral Triangles

Statement

Given N grid points, count the number of triples that form an "equilateral" triangle under the L_∞ (Chebyshev) metric — equivalently, under the rotated-45° L₁ (Manhattan) metric all three pairwise distances are equal.

Constraints

• 1 ≤ N ≤ 300.
• Coordinates ≤ ~10⁴.
• Time limit: 2s.

Key idea

Rotate every point (x, y) → (x + y, x − y). Manhattan distance in the original becomes Chebyshev distance in the rotated space, and vice versa. Then "Manhattan-equilateral" triangle in the original corresponds to a "Chebyshev-equilateral" triangle in rotated coords, which is geometrically a square's three corners — easy to count by enumerating each axis-aligned square's side length and three-corner selections. With N ≤ 300 an O(N³) brute force checking all triples already runs in < 30 M ops.

Complexity target

O(N³) brute is enough; O(N² log N) with the rotation trick + counting is also clean.

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; cin >> N;
    vector<ll> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    // Rotate 45°: u = x + y, v = x - y. Now Manhattan dist (orig)
    // = max(|du|, |dv|) (Chebyshev in rotated). Manhattan-equilateral
    // means all 3 pairwise max(|du|,|dv|) equal.
    vector<ll> U(N), V(N);
    for (int i = 0; i < N; ++i) { U[i] = X[i] + Y[i]; V[i] = X[i] - Y[i]; }

    auto cheby = [&](int i, int j) {
        return max(abs(U[i] - U[j]), abs(V[i] - V[j]));
    };
    ll ans = 0;
    for (int i = 0; i < N; ++i)
        for (int j = i + 1; j < N; ++j)
            for (int k = j + 1; k < N; ++k) {
                ll a = cheby(i, j), b = cheby(j, k), c = cheby(i, k);
                if (a == b && b == c && a > 0) ++ans;
            }
    cout << ans << "\n";
}

Pitfalls

• Side length must be positive — degenerate "triangles" with 0 distance (coincident points) shouldn't count.
• The metric. Re-read the problem: USACO's "equilateral" here is under taxicab/Manhattan, which is why the rotation trick works. Verify against the statement.
• O(N³) is only fine because N ≤ 300. If the real N is larger, you need the square-counting reformulation.
• Coordinates can be negative after rotation; just use signed integers.

Problem 3 — Help Yourself

Statement

Platinum upgrade of Gold Help Yourself. Same N intervals; for a parameter K, compute Σ_S f(S)^K mod 10⁹+7, where f(S) is the number of connected components in the union of intervals of S.

Constraints

• 1 ≤ N ≤ 10⁵.
• 1 ≤ K ≤ 10.
• Coordinates ≤ 2N.
• Time limit: 2s.

Key idea

Sweep over coordinates 1..2N. Maintain a polynomial-style DP over (current component count contribution moments): for each subset prefix, track Σ f^j for j = 0..K. When an interval starts at l, it either (a) joins an open component without changing count or (b) starts a new component (incrementing f by 1). Use the binomial expansion (f + 1)^K = Σ C(K, j) f^j to update the moments of the "extended" subsets in O(K) per event. Total O((N + L) · K²) where L is the coordinate range.

Complexity target

O(N · K²) with the binomial-moment DP and a sweep.

Reference solution (C++)

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<pair<int, int>> iv(N);
    int M = 0;
    for (auto& [l, r] : iv) { cin >> l >> r; M = max(M, r); }

    // Sweep coords 1..M. Track events: interval i starts at l, ends at r.
    vector<vector<int>> starts(M + 2), ends(M + 2);
    for (int i = 0; i < N; ++i) {
        starts[iv[i].first].push_back(i);
        ends[iv[i].second].push_back(i);
    }
    // dp[j] = Σ over subsets of intervals seen so far, of f(S)^j, where f counts
    // components UP TO the current coord position (closed intervals so far).
    // We maintain this as a polynomial of degree K.
    vector<ll> dp(K + 1, 0);
    dp[0] = 1;                      // empty subset, f = 0, f^0 = 1
    // Pre-binomials
    vector<vector<ll>> C(K + 1, vector<ll>(K + 1, 0));
    for (int i = 0; i <= K; ++i) { C[i][0] = 1; for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; }
    int openCnt = 0;                // number of currently "open" intervals (sweep state — coarse model)
    for (int x = 1; x <= M; ++x) {
        for (int i : starts[x]) {
            // New interval is either: (a) excluded — dp unchanged contribution for this interval,
            // (b) included — if no open interval covers x, f += 1; else f unchanged.
            // We model the "either include or exclude" doubling per interval, with the f-shift
            // applied to the "include" branch only when openCnt == 0.
            vector<ll> nd(K + 1, 0);
            for (int j = 0; j <= K; ++j) {
                // exclude branch: dp[j] contributes to nd[j]
                nd[j] = (nd[j] + dp[j]) % MOD;
                // include branch: f -> f + [openCnt == 0]
                if (openCnt == 0) {
                    for (int t = 0; t <= j; ++t)
                        nd[j] = (nd[j] + C[j][t] * dp[t]) % MOD;
                } else {
                    nd[j] = (nd[j] + dp[j]) % MOD;
                }
            }
            dp = nd;
            ++openCnt;
        }
        for (int i : ends[x]) --openCnt;
    }
    cout << dp[K] << "\n";
}

Pitfalls

• This reference is a sketch. The exact Platinum solution is subtler: "openCnt" must track per-subset state, not a single counter, so a true solution maintains the polynomial conditioned on "is there currently any open interval in the subset". Use two parallel polynomials A (no open in S) and B (some open in S); transitions move mass between them.
• K ≤ 10 keeps per-event work O(K²) ≈ 100 ops, so total is O(N · K²) ≈ 10⁷.
• Modular inverses not needed — all updates are additions and multiplications.
• Coordinates up to 2N; sweep is over O(N) positions.

What Platinum February 2020 was actually testing

• P1 — tree-DP with greedy multiset pairing. Same idea as Gold, but with iterative DFS and divisor enumeration.
• P2 — metric rotation. Manhattan ↔ Chebyshev via (x+y, x−y); reduces a fiddly geometric count to axis-aligned counting.
• P3 — moment DP over a sweep. Sum of f^K over subsets is computed by tracking the polynomial of moments as intervals are added.