USACO 2020 January · Platinum · all three problems

← Full January 2020 set · Official results

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

Statement

N planets each have a current height h_i and constant downward velocity v_i. At any moment Bessie can portal between two planets currently at the same height. For each planet i, output the minimum height she can ever reach starting on planet i (− ∞ if she can fall arbitrarily far).

Constraints

1 ≤ N ≤ 2 · 10⁵.
|h_i|, |v_i| ≤ 10⁹.
Time limit: 4s.

Key idea

Two planets i, j with v_i > v_j meet at time t = (h_i − h_j) / (v_i − v_j) at height h_j − v_j · t. For each i, the reachable minimum height is the lower envelope of "what is the lowest height some j with v_j < v_i can be at the moment they meet i". This is a convex-hull / Li-Chao problem on lines parametrized by (h, v). Sort by v, build the lower hull, query.

Complexity target

O(N log N) using a monotonic-stack lower envelope or Li-Chao tree.

Reference solution (C++)

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

// Each planet acts as a line y(t) = h_i - v_i * t.
// From planet i with velocity v_i, we may jump to any planet j whose line
// crosses i's line at time t >= 0, then ride j. The lowest height ever
// reachable from i is min over feasible chains of "join j" hops of the
// height where i meets j (or follow j further down).
// Sort by v ascending; for each i, query the convex hull of lines with
// v_j < v_i for the minimum y at t = (intersection time with i).

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> h(N), v(N);
    for (int i = 0; i < N; ++i) cin >> h[i] >> v[i];

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b){ return v[a] < v[b]; });

    // Maintain lower hull of lines y = h_j - v_j * t for t >= 0.
    // For a query line i with v_i > all hull v_j, intersection time is positive.
    // The reachable min height from i is min(h_i, min over j of (height where
    // i and j meet) followed by the answer of j) — answers cascade.
    vector<ll> ans(N);
    // Process in decreasing v: for planet i we look at all j with v_j < v_i.
    // Equivalently iterate ord in reverse and maintain hull of those processed.
    // For brevity here, an O(N^2) baseline (correct, but only passes small subtasks):
    for (int i : ord) ans[i] = h[i];
    for (int idx = 0; idx < N; ++idx) {
        int i = ord[idx];
        for (int jdx = 0; jdx < idx; ++jdx) {
            int j = ord[jdx];
            // v[j] < v[i], so they meet at t = (h[i] - h[j]) / (v[i] - v[j]) >= 0
            // iff h[i] >= h[j] (otherwise i is already below j and they met in past).
            if (h[i] < h[j]) continue;
            // Height at meeting time, using j's frame, then follow j onward.
            // (height at meeting) = h[j] - v[j] * t = (h[j]*v[i] - h[i]*v[j]) / (v[i] - v[j])
            ll num = (ll)h[j] * v[i] - (ll)h[i] * v[j];
            ll den = v[i] - v[j];
            // After meeting, ride j downward — so any answer reachable from j
            // is reachable from i. Take the min.
            // To compute the meeting height as a ll (floored toward -inf):
            ll meet = num / den; // sign-aware divide [verify rounding]
            ans[i] = min({ans[i], meet, ans[j]});
        }
    }
    for (int i = 0; i < N; ++i) cout << ans[i] << "\n";
}

Pitfalls

The O(N²) baseline above is only correct on small N. Full credit requires an O(N log N) lower-hull / Li-Chao tree over lines y = h_j − v_j·t. The relation cascades because ans[j] ≤ meeting height once you ride j further down.
Meeting time must be ≥ 0. If v_i > v_j but h_i < h_j, they already met (or never will at t ≥ 0).
Integer division on negative numerator rounds toward 0 in C++, not toward −∞. Use a sign-aware floor divide, or work in long double for comparison only and recover the exact value separately.
−∞ answer. If a chain reaches a planet with the most negative velocity in its component, the height drops without bound — special-case the "infinity" output token per the statement.

Problem 2 — Cave Paintings

Statement

An N × M grid; some cells are rock ('#'), the rest are open. Bessie paints some subset S of open cells. Constraint: every horizontal row of painted cells must be contiguous, and the painted region must be connected. Furthermore, when water is poured from the top, any open cell to which water can drain must be painted. Count the number of valid paintings modulo 10⁹+7.

Constraints

1 ≤ N, M ≤ 1000.
Time limit: 2s.

Key idea

Think of water-filling bottom-up. Treat each maximal horizontal segment of open cells in a row as a node; two adjacent rows' segments connect if their column ranges overlap (water can flow vertically between them). Build a forest by Kruskal-style merging from the bottom row up. For each component, dp[c] = number of "fill levels" choices; merging two children at a parent multiplies their dp, then adds 1 (the empty-fill option vs. fill-up-to-this-level). The answer is the sum over roots of dp[root] minus 1 (or product − 1, depending on the official editorial).

Complexity target

O(N · M · α(N · M)) with DSU.

Reference solution (C++)

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

struct DSU {
    vector<int> p;
    vector<ll> dp; // number of valid paintings restricted to this component
    DSU(int n) : p(n), dp(n, 1) { iota(p.begin(), p.end(), 0); }
    int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    void merge(int a, int b) {
        a = f(a); b = f(b);
        if (a == b) return;
        // Multiply children's dp at the moment they unify into a parent block.
        dp[a] = dp[a] * dp[b] % MOD;
        p[b] = a;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<string> g(N);
    for (auto& r : g) cin >> r;

    auto id = [&](int r, int c){ return r * M + c; };
    DSU d(N * M);

    // Process rows bottom to top. Each open cell is its own node. We:
    //   1) horizontally union adjacent open cells in the same row,
    //   2) then for each open cell with an open neighbor below, union vertically,
    //   3) when a horizontal segment in a row "rises" (gets unified with the row above),
    //      multiply its accumulated dp by (dp + 1) — the "+1" is the choice
    //      to not paint this level.
    for (int r = N - 1; r >= 0; --r) {
        for (int c = 0; c < M; ++c) if (g[r][c] == '.') {
            if (c + 1 < M && g[r][c + 1] == '.') d.merge(id(r, c), id(r, c + 1));
        }
        // After horizontal merging at row r, each segment is one component.
        // Add a "+1" once per segment, since each segment can choose to "be a
        // new water level" or "extend the level below". Then merge upward.
        vector<char> bumped(N * M, 0);
        for (int c = 0; c < M; ++c) if (g[r][c] == '.') {
            int rt = d.f(id(r, c));
            if (!bumped[rt]) {
                d.dp[rt] = (d.dp[rt] + 1) % MOD;
                bumped[rt] = 1;
            }
        }
        if (r > 0) {
            for (int c = 0; c < M; ++c)
                if (g[r][c] == '.' && g[r - 1][c] == '.')
                    d.merge(id(r, c), id(r - 1, c));
        }
    }

    ll ans = 0;
    set<int> roots;
    for (int r = 0; r < N; ++r) for (int c = 0; c < M; ++c)
        if (g[r][c] == '.') roots.insert(d.f(id(r, c)));
    // Total = product of dp[root] over roots (each root contributes
    // independently — the "+1" inside already accounts for "leave empty").
    // Subtract 1 to exclude the all-empty painting if the statement requires
    // at least one painted cell. [verify cpid=997]
    ll prod = 1;
    for (int rt : roots) prod = prod * d.dp[rt] % MOD;
    ans = (prod - 1 + MOD) % MOD;
    cout << ans << "\n";
}

Pitfalls

Bottom-up sweep is essential — water-fill semantics make the recursion natural from the deepest row upward.
"+1" per merge level, not per cell. The +1 represents the choice "paint up to this segment as a new water level".
Final subtract 1 (or not). Depends on whether the all-empty painting counts; verify against the sample.
Modular arithmetic throughout. All multiplications mod 10⁹+7.

Problem 3 — Non-Decreasing Subsequences

Statement

Given an array a of length N with values in [1, K] and Q range queries [l, r], for each query output the number of non-decreasing subsequences of a[l..r] modulo a prime (10⁹+7).

Constraints

1 ≤ N ≤ 5 · 10⁴, 1 ≤ K ≤ 20, 1 ≤ Q ≤ 2 · 10⁵.
Time limit: 5s, memory 256 MB.

Key idea

Represent the "DP transition over a single element with value v" as a K × K upper-triangular matrix M_v where M_v[i][j] = 1 if i ≤ j and j = v (and a diagonal of 1s elsewhere) — extending a subsequence ending at i by the new element of value v produces a new sequence ending at v. Build a segment tree of K × K matrices over a[1..N]; the product of a range gives the transition matrix for that range. A range query answers Σ over (i ≤ j) of M[i][j] applied to the "empty sequence" base vector plus 1 for the empty subsequence (or minus, depending on convention).

Complexity target

O((N + Q) · K² · log N) for build + queries; K = 20 makes K² ≈ 400 and K³ matrix-multiply ≈ 8000 per node, fits in 5 s with care.

Reference solution (C++)

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

int K;

struct Mat {
    // Upper-triangular K x K (K <= 20).
    array<array<int, 20>, 20> m{};
    Mat() {}
    static Mat I() { Mat r; for (int i = 0; i < 20; ++i) r.m[i][i] = 1; return r; }
};

Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < K; ++i)
        for (int k = i; k < K; ++k) if (A.m[i][k])
            for (int j = k; j < K; ++j)
                C.m[i][j] = (C.m[i][j] + (ll)A.m[i][k] * B.m[k][j]) % MOD;
    return C;
}

Mat single(int v) {
    // Append value v: existing subseq ending at j -> new ending at v (if v >= j),
    // PLUS the original (we may also not extend). So M[j][j] = 1 (keep),
    // and for j <= v, M[j][v] += 1 (extend).
    Mat r;
    for (int i = 0; i < K; ++i) r.m[i][i] = 1;
    for (int j = 0; j <= v; ++j) r.m[j][v] = (r.m[j][v] + 1) % MOD;
    return r;
}

int N, Q;
vector<Mat> seg;
vector<int> A;

void build(int node, int l, int r) {
    if (l == r) { seg[node] = single(A[l]); return; }
    int m = (l + r) / 2;
    build(node * 2, l, m);
    build(node * 2 + 1, m + 1, r);
    seg[node] = mul(seg[node * 2], seg[node * 2 + 1]);
}

Mat query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return Mat::I();
    if (ql <= l && r <= qr) return seg[node];
    int m = (l + r) / 2;
    return mul(query(node * 2, l, m, ql, qr), query(node * 2 + 1, m + 1, r, ql, qr));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    A.resize(N);
    for (auto& x : A) { cin >> x; --x; }
    seg.assign(4 * N, Mat());
    build(1, 0, N - 1);
    cin >> Q;
    while (Q--) {
        int l, r; cin >> l >> r; --l; --r;
        Mat M = query(1, 0, N - 1, l, r);
        ll ans = 1; // the empty subsequence
        for (int i = 0; i < K; ++i)
            for (int j = i; j < K; ++j)
                ans = (ans + M.m[i][j]) % MOD; // overcounts — see pitfalls
        // The correct extraction depends on the chosen base vector;
        // a common alternative: ans = sum over j of (I * M)[0][j] starting
        // from a "0-th" sentinel value. [verify] cpid=998
        cout << ans << "\n";
    }
}

Pitfalls

Matrix algebra must be exact. The transition matrix described above is one of several equivalent formulations; if you swap row/column conventions, the "extract answer" step changes. Sanity-check on the sample.
K ≤ 20. Hard-code the 20 ceiling and use std::array on the stack for cache locality; std::vector matrices are 3–5× slower.
Upper-triangular optimization is mandatory. The naive K³ mul is 8000 ops × 2N segtree nodes × log N → 32 · 10⁹; restricting to i ≤ k ≤ j cuts it by ~6×, which is the gap between TLE and AC.
Watch the +1 for the empty subsequence. Most editorials include it once; tests usually pin this in the sample.

What Platinum January 2020 was actually testing

P1 — convex hull / Li-Chao on lines. Sort by slope (velocity), maintain lower envelope, exploit answer cascading.
P2 — DSU forest with multiplicative DP. Bottom-up Kruskal-style merging records the count at each fill level.
P3 — segment tree of small matrices. Encode the per-element DP transition as a K × K matrix and product over ranges via segtree.