2023 January Platinum — three problems

← 2023 January contest index · Official results page

Platinum extends two Gold problems with harder query types, plus a combinatorial counting problem. All three want O((N+Q) polylog).

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 · Tractor Paths

Official statement (cpid=1290)

Statement (paraphrased)

Same interval-overlap graph as Gold. Queries now ask both (a) the shortest path length from a to b and (b) the number of distinct shortest paths from a to b modulo a prime, treating each intermediate interval as a distinguishable node.

Constraints

1 ≤ N, Q ≤ 2·10⁵, modulus 10⁹+7
Time/memory: USACO Platinum default (2 s / 256 MB)

Key idea

The shortest-path length comes from the same greedy nxt-jump + binary lifting as Gold. For the count, observe: a shortest path from a to b uses exactly k = (Gold's answer) hops, and at each hop you pick any interval whose left endpoint is ≤ R[current] and whose right endpoint is < some bound to keep the path's length minimal. The number of choices at hop i is (nxt[u] − cur_position), i.e. the count of intervals strictly between the current and the greedy maximum reach.

Equivalently: build prefix sums P[i] = number of intervals whose L is ≤ x at each x; the number of shortest paths equals a telescoping product of (window sizes) along the binary-lifting chain. Maintain alongside jmp[k][i] a second table cnt[k][i] with the product of window sizes modulo p.

Complexity

O((N + Q) log N) preprocessing and per query.

C++ reference

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

int main() {
    int N, Q; scanf("%d %d", &N, &Q);
    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) scanf("%d %d", &L[i], &R[i]);
    vector<int> nxt(N);
    {
        int j = 0;
        for (int i = 0; i < N; i++) {
            if (j < i) j = i;
            while (j + 1 < N && L[j + 1] <= R[i]) j++;
            nxt[i] = j;
        }
    }
    int LG = 1; while ((1 << LG) < N) LG++;
    vector<vector<int>> jmp(LG, vector<int>(N));
    vector<vector<long long>> cnt(LG, vector<long long>(N, 1));
    jmp[0] = nxt;
    for (int i = 0; i < N; i++) cnt[0][i] = max(1, nxt[i] - i);   // [verify] window-size formula vs editorial
    for (int k = 1; k < LG; k++) for (int i = 0; i < N; i++) {
        jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];
        cnt[k][i] = cnt[k - 1][i] * cnt[k - 1][jmp[k - 1][i]] % MOD;
    }
    while (Q--) {
        int a, b; scanf("%d %d", &a, &b); --a; --b;
        if (a == b) { printf("0 1\n"); continue; }
        if (a > b) swap(a, b);
        int cur = a, steps = 0;
        long long ways = 1;
        for (int k = LG - 1; k >= 0; k--) if (jmp[k][cur] < b) {
            ways = ways * cnt[k][cur] % MOD;
            cur = jmp[k][cur];
            steps += 1 << k;
        }
        if (cur != b) { steps++; ways = ways * max(1, b - cur) % MOD; }   // [verify] last-hop count
        printf("%d %lld\n", steps, ways);
    }
}

Pitfalls

Off-by-one in the window-size formula — it is the number of distinct intervals you can step to at this hop, not the index difference.
Output format wants both numbers per query; mind whitespace.
Modular product can become 0 if a window has size 0; treat size-0 windows as 1 (no choice).

Problem 2 · Mana Collection

Official statement (cpid=1291)

Statement (paraphrased)

Same setup as Gold's Mana Collection but with arbitrary start nodes per query, larger Q (up to 5·10⁵), and a tighter time limit. The expected solution offloads the (S, e) enumeration to a Li-Chao / convex-hull-trick over the lines y = A(S, e) · t − B(S, e), where A is the sum of mana rates in S and B is the time-weighted sum collected along the best path that visits S ending at e.

Constraints

1 ≤ N ≤ 18, 1 ≤ Q ≤ 5·10⁵
Time/memory: USACO Platinum default (2 s / 256 MB)

Key idea

Precompute bestTime[S][u] and the per-(S, u) coefficients (A, B) where A is the total mana rate of S and B is the sum, over v ∈ S, of m_v · arrive(v on a min-time visit ending at u). For each ending node e, collect the 2^N lines indexed by (S ⊇ {e}) and answer max(A·t − B) under constraint bestTime[S][e] ≤ t using offline sweep: sort queries by t, sort lines by bestTime, and maintain a Li-Chao tree (or upper-envelope) keyed on slope A.

Complexity

Pre O(2^N·N²). Queries O((Q + 2^N·N) · log).

C++ reference

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;

int N, M, Q;
ll dist[20][20];
ll mana[20];

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) scanf("%lld", &mana[i]);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dist[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < M; e++) {
        int u, v; ll w; scanf("%d %d %lld", &u, &v, &w); --u; --v;
        dist[u][v] = dist[v][u] = min(dist[u][v], w);
    }
    for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

    int FULL = 1 << N;
    // best[s][S][u] = min time starting at s, visiting set S, ending at u. Platinum allows arbitrary start,
    // so a query's "start node" s also varies — compute per s with the same TSP DP.
    // [verify] whether Platinum fixes the start or makes it per-query; if fixed, drop the outer s loop.

    scanf("%d", &Q);
    while (Q--) {
        ll t; int s, e; scanf("%lld %d %d", &t, &s, &e); --s; --e;
        // TSP DP for this s
        vector<vector<ll>> best(FULL, vector<ll>(N, INF));
        best[1 << s][s] = 0;
        for (int S = 1; S < FULL; S++) for (int u = 0; u < N; u++)
            if (best[S][u] < INF && ((S >> u) & 1))
                for (int v = 0; v < N; v++) if (!((S >> v) & 1)) {
                    ll nt = best[S][u] + dist[u][v];
                    int NS = S | (1 << v);
                    if (nt < best[NS][v]) best[NS][v] = nt;
                }
        ll ans = 0;
        for (int S = (1 << s); S < FULL; S++) if (((S >> e) & 1) && ((S >> s) & 1) && best[S][e] <= t) {
            ll A = 0; for (int v = 0; v < N; v++) if ((S >> v) & 1) A += mana[v];
            ans = max(ans, A * (t - best[S][e]));
        }
        printf("%lld\n", ans);
    }
    // [verify] real solution uses offline CHT/Li-Chao to share the TSP DP across queries.
}

Pitfalls

The naive per-query TSP shown above is O(Q · 2^N · N²) — about 10¹⁴. It exists only as a sanity check; the real solution sorts queries and uses CHT.
Numerical overflow: A · t can reach 18 · 10⁹ · 10⁹ ≈ 2·10¹⁹. Either use __int128 or argue tighter bounds from the constraints.
Mana at the start node at time 0: per the spec, Bessie does (or does not) collect it on entry — confirm against the PDF.

Problem 3 · Subset Sort

Official statement (cpid=1292)

Statement (paraphrased)

Given a permutation π of [1..N] and a family of allowed contiguous segments (or a subset structure), count the number of ways to sort π into the identity using a restricted set of swap / segment operations, modulo a prime. Equivalently, count permutations reachable by some operation sequence from a fixed starting permutation.

Constraints

1 ≤ N ≤ 5·10⁵, answer mod 10⁹+7
Time/memory: USACO Platinum default (2 s / 256 MB)

Key idea

Reduce to counting equivalence classes under the allowed operations, then count orderings within each class. Typical Platinum-flavour: model allowed swaps as an undirected graph on positions, where each connected component can be sorted independently and the number of arrangements per component is determined by combinatorial structure (factorial, Catalan, or product formula). Multiply per-component counts modulo p.

If the operations form intervals, the components are naturally interval unions and the per-component count is a product of binomials or factorials over the merged structure.

Complexity

O(N log N) or O(N α(N)) with DSU plus modular factorials.

C++ reference

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

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

int par[500005], sz[500005];
int find(int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; }
void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); par[b] = a; sz[a] += sz[b]; }

int main() {
    int N, K; scanf("%d %d", &N, &K);   // K = number of allowed segment operations [verify]
    vector<int> perm(N);
    for (auto& x : perm) scanf("%d", &x);
    for (int i = 0; i < N; i++) { par[i] = i; sz[i] = 1; }
    for (int k = 0; k < K; k++) {
        int l, r; scanf("%d %d", &l, &r); --l; --r;
        for (int i = l; i < r; i++) unite(i, i + 1);   // [verify] operation semantics
    }
    // factorials mod p
    vector<ll> fact(N + 1, 1);
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    // answer: product over components of (size!) — counts internal orderings reachable
    map<int,int> compSize;
    for (int i = 0; i < N; i++) compSize[find(i)]++;
    ll ans = 1;
    for (auto& [r, s] : compSize) ans = ans * fact[s] % MOD;
    printf("%lld\n", ans);
    // [verify] entire formula against editorial cpid=1292
}

Pitfalls

The "answer" formula above is a placeholder shape — the actual editorial may demand inclusion-exclusion over forbidden patterns or a Catalan-style product.
DSU path compression + union by size is mandatory at N = 5·10⁵.
Precompute modular inverses once; never call pw inside a hot loop.