2022 February Platinum · All three problems

← Back to Feb 2022 hub · Official results

Canonical statements live at usaco.org. Statements below are my paraphrase — open the official problem PDFs before submitting your own solution. Each problem links to the official viewer.

Problem 1 · Paint by Rectangles

Official problem (cpid=1212)

Statement (paraphrased)

N axis-aligned rectangles in general position (all 2N x-coordinates form a permutation of 1..2N, same for y). They induce a planar subdivision two-colourable in black/white with the outside white. For T=1 output total region count; for T=2 output (white, black) region counts.

Constraints

1 ≤ N ≤ 10⁵. T ∈ {1, 2}.
Time / memory: 4 s, 256 MB (2× default).

Key idea

Euler formula on the planar graph: V − E + F = 1 + C (one for outer face plus connected components). Vertices are rectangle corners and edge intersections. With the "no two collinear" guarantee, vertical edges only intersect horizontal edges. Count intersections via a sweep over x: maintain a Fenwick tree over y. When a rectangle's left edge appears, mark its top and bottom y; at its right edge, query the count of active vertical lines that cross — each horizontal edge of the rectangle accumulates that count. For T=2, also two-colour by a parity argument over depth: a point's colour = parity of rectangles containing it.

Complexity target

O(N log N) via BIT sweep.

C++ reference solution

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

// Sketch only: full solution needs BIT, sweep events, DSU for connected components, and parity tagging.
// This stub shows the event/sweep skeleton; consult the official editorial for the full T=2 path.
// [verify] full impl: https://usaco.org/current/data/sol_prob1_platinum_feb22.html

struct BIT { vector<int> t; int n;
    BIT(int n):n(n),t(n+2,0){}
    void upd(int i,int v){ for(++i; i<=n; i+=i&-i) t[i]+=v; }
    int qry(int i){ int s=0; for(++i; i>0; i-=i&-i) s+=t[i]; return s; }
    int rng(int l,int r){ return qry(r) - (l? qry(l-1):0); }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N, T; cin >> N >> T;
    vector<array<int,4>> R(N); // x1,y1,x2,y2
    for (auto& r : R) cin >> r[0] >> r[1] >> r[2] >> r[3];

    // Sweep x = 1..2N. Maintain BIT over y of "active vertical-edge endpoints".
    // Events: at x = x1 add (y1, y2) to active; at x = x2 remove.
    // Crossings of this rect's bottom (y = y1) and top (y = y2) with active vertical edges
    // accumulate to total intersections.
    vector<vector<pair<int,int>>> open(2*N+2), close(2*N+2);
    for (auto& r : R) { open [r[0]].push_back({r[1], r[3]}); close[r[2]].push_back({r[1], r[3]}); }

    BIT bit(2*N + 2);
    ll inter = 0;
    auto crossesAt = [&](int y){ return bit.qry(y) - (y? bit.qry(y-1):0); }; // count active starting at exact y
    (void)crossesAt; // placeholder — real impl tracks segment counts intersecting horizontal lines.
    // Implementation continues with proper segment-active counters; see editorial.

    // V = 4N + intersections; E = 2N*2 vertical segments + 2N*2 horizontal segments split by intersections; etc.
    // Components C via DSU on rectangles that share a corner or boundary intersection.

    // Final output stub:
    if (T == 1) cout << "[regions]" << '\n';
    else        cout << "[white] [black]" << '\n';
    return 0;
}

Pitfalls

This is the hardest Platinum 1 of 2022; my snippet is only the sweep skeleton — see the editorial for the full Euler-formula bookkeeping and DSU-for-components step [verify] https://usaco.org/current/data/sol_prob1_platinum_feb22.html.
Two-colouring exploits the parity-of-containment invariant: any point's colour equals (number of rectangles containing it) mod 2.
Coordinate-compression is free because x and y are already permutations of 1..2N.

Problem 2 · Sleeping in Class

Official problem (cpid=1213)

Statement (paraphrased)

Platinum version: same log a₁,…,a_N (values up to 10¹⁸, total sum ≤ 10¹⁸) but now Elsie can either merge adjacent entries or split an entry into two non-negative pieces summing to it. For each of Q queries q answer the minimum number of operations so every entry equals q.

Constraints

2 ≤ N ≤ 10⁵; 1 ≤ Q ≤ 10⁵; a_i, q_i ≤ 10¹⁸; Σa ≤ 10¹⁸.
Time / memory: 2 s, 256 MB (default).

Key idea

First, q must divide S = Σa (else output −1). For a fixed q the optimum is: scan prefixes; let p_i be the prefix sum mod q · q ... actually, walk through and greedily cut whenever the running prefix is a multiple of q. Each "cut" we insert is free if the prefix lands exactly on a multiple; otherwise we pay 1 merge to absorb the overshoot, then maybe 1 split. Let k = number of multiples-of-q hit by the prefix sums (excluding 0 and S). Then merges = (N − 1) − k counts how many block boundaries we need to delete; the number of splits we add is (S/q − 1) − k. Total ops = (N − 1) + (S/q − 1) − 2k. So precompute the prefix-sum multiset; for each query q find S/q, count how many prefix-sums are multiples of q.

Complexity target

O((N + Q) · √(S/q) worst, or better with divisor-bucketing). Editorial uses O((N + Q) · d(S)) [verify] https://usaco.org/current/data/sol_prob2_platinum_feb22.html.

C++ reference solution

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> a(N), pref(N + 1, 0);
    for (auto& x : a) cin >> x;
    for (int i = 0; i < N; ++i) pref[i+1] = pref[i] + a[i];
    ll S = pref[N];
    vector<ll> P(pref.begin() + 1, pref.end() - 1); // interior prefix sums

    int Q; cin >> Q;
    while (Q--) {
        ll q; cin >> q;
        if (S % q != 0) { cout << -1 << '\n'; continue; }
        ll blocks = S / q;
        // Count interior prefix sums divisible by q. O(N) per query — TLE for max input.
        // For 10^5 * 10^5 you need offline divisor processing; see editorial.
        ll k = 0;
        for (ll v : P) if (v % q == 0) ++k;
        ll ops = (ll)(N - 1) + (blocks - 1) - 2 * k;
        cout << ops << '\n';
    }
    return 0;
}

Pitfalls

The O(N·Q) version above is correct but TLEs on max input. The editorial groups queries by divisors of S and uses a sieve over divisors of each prefix sum to count k in aggregate O((N + Q) · d(S)) [verify] https://usaco.org/current/data/sol_prob2_platinum_feb22.html.
Output −1 when q ∤ S; the merge-split duality forces total-sum preservation.
Use 128-bit or be careful: S up to 10¹⁸ just barely fits in long long.

Problem 3 · Phone Numbers

Official problem (cpid=1214)

Statement (paraphrased)

Bessie's 3×3 keypad: a press is a single digit, a side-adjacent pair, or a 2×2 square. A press outputs its digits in any order. Given the typed string s of digits 1–9, count the number of intended digit sequences that could have produced s, modulo 10⁹+7.

Constraints

1 ≤ T ≤ 10 test cases; Σ|s| ≤ 10⁵.
Time / memory: 4 s, 256 MB (2× default time).

Key idea

DP across the typed string. Each press contributes a contiguous chunk of s of length 1, 2, or 4 — but with any permutation of its digits. So dp[i] = number of ways to parse s[0..i). Transitions: dp[i] += dp[i−1] (every single digit is a valid 1-press); dp[i] += dp[i−2] · [{s[i−2], s[i−1]} is one of the 12 adjacent unordered pairs, AND the press's two permutations both match the multiset] — careful with duplicates; dp[i] += dp[i−4] · [the multiset {s[i−4..i−1]} equals one of the 4 squares {1,2,4,5}, {2,3,5,6}, {4,5,7,8}, {5,6,8,9}, AND every permutation realisable]. Counting "ways" means: for a chosen press, the number of orderings of its digit multiset that equal the typed substring — which is 1 if the typed slice is one specific permutation of the press's digits. Actually the count is: number of valid (press, ordering) pairs that match. For a press P (a set of k digits), the typed slice must be a permutation of P (k! / dupes orderings; here k ∈ {1,2,4} with distinct digits, so all permutations are distinct). So each match contributes 1 way (the press itself), regardless of which permutation appeared.

Complexity target

O(|s|) per test case with precomputed adjacency/square sets.

C++ reference solution

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

int main(){
    // 12 adjacent unordered pairs on the 3x3 grid:
    //   horizontal: 12,23,45,56,78,89    vertical: 14,25,36,47,58,69
    set<set<int>> pair2 = {
        {1,2},{2,3},{4,5},{5,6},{7,8},{8,9},
        {1,4},{2,5},{3,6},{4,7},{5,8},{6,9}
    };
    set<set<int>> sq4 = { {1,2,4,5}, {2,3,5,6}, {4,5,7,8}, {5,6,8,9} };

    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int n = s.size();
        vector<long long> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i-1];                                            // single press
            if (i >= 2) {
                set<int> m = { s[i-2]-'0', s[i-1]-'0' };
                if (m.size() == 2 && pair2.count(m)) dp[i] = (dp[i] + dp[i-2]) % MOD;
            }
            if (i >= 4) {
                set<int> m = { s[i-4]-'0', s[i-3]-'0', s[i-2]-'0', s[i-1]-'0' };
                if (m.size() == 4 && sq4.count(m)) dp[i] = (dp[i] + dp[i-4]) % MOD;
            }
        }
        cout << dp[n] << '\n';
    }
    return 0;
}

Pitfalls

"Count" semantics: each valid press contributes exactly one intended-sequence way (the multiset uniquely fixes the press), regardless of how many orderings of that multiset equal the typed slice. Re-read the statement carefully [verify] https://usaco.org/current/data/sol_prob3_platinum_feb22.html.
If the typed slice has duplicate digits, it can't be a 2-pair or 4-square (those use distinct digits) — the m.size() == k guard handles it.
Use modular arithmetic throughout; dp values fit in long long but the running total grows.