USACO 2017 US Open · Platinum · all three problems

← Full 2017 US Open set · Official results

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

Statement

Picowso paints N² axis-aligned rectangles in colors 1..N² on an N×N canvas, each color used exactly once; later strokes overwrite earlier ones. Given the final canvas, count how many of the colors 1..N² could have been the very first stroke (i.e. their rectangle is unconstrained from below). A color that no longer appears in the final image counts as a potential first stroke only if its rectangle was completely covered — equivalent to saying the color's reconstruction is unforced.

Constraints

1 ≤ N ≤ 1000.
Grid values in 0..N².
Time limit: 2s.

Key idea

Same trick as Bronze, scaled. For each color c that appears, compute its bounding box. The rectangle Picowso painted for c must equal that bounding box (otherwise the visible cells couldn't be contiguous as a rectangle). Inside the bbox, every non-zero non-c cell forces c → that color in a DAG of "painted before." Color c is a potential first only if no color is required to be painted before it — equivalent to its bbox containing only c-cells and 0-cells… but 0-cells inside the bbox indicate another color was placed there and then overwritten, so 0 inside bbox disqualifies c too. So: c can be first iff every cell inside its bbox is c.

For colors not appearing at all in the final image, they're necessarily painted over by some later color whose rectangle covers theirs — they can be first only if they lie entirely under the bbox of one "always-on-top" color. The official answer counts colors c such that c's bbox is solid c. The N² cell sweep with 2D prefix sums of "non-c cells" handles N = 1000 in 2s.

Complexity target

O(N²): one pass to compute bboxes, one pass to verify each visible color's bbox is solid. Use 2D prefix sums of "cells ≠ c" carefully or, simpler, count per-color the cells inside its bbox and compare to (visible cells of c).

Reference solution (C++)

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

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

    vector<int> loR(total + 1, INT_MAX), hiR(total + 1, -1);
    vector<int> loC(total + 1, INT_MAX), hiC(total + 1, -1);
    vector<int> cnt(total + 1, 0); // visible cells per color

    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        int c = g[i][j];
        if (c == 0) continue;
        loR[c] = min(loR[c], i); hiR[c] = max(hiR[c], i);
        loC[c] = min(loC[c], j); hiC[c] = max(hiC[c], j);
        ++cnt[c];
    }

    // For O(N^2): use a 2D prefix sum of "is cell nonzero", then for each
    // color c compare (#nonzero cells in bbox) with cnt[c]. If equal -> only
    // c lives in that bbox (no foreign nonzero) -> c could be first.
    vector<vector<int>> ps(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
        ps[i+1][j+1] = ps[i][j+1] + ps[i+1][j] - ps[i][j] + (g[i][j] != 0);

    int ans = 0;
    for (int c = 1; c <= total; ++c) {
        if (cnt[c] == 0) continue; // absent colors handled separately if needed
        int r1 = loR[c], c1 = loC[c], r2 = hiR[c], c2 = hiC[c];
        int box = ps[r2+1][c2+1] - ps[loR[c]][c2+1] - ps[r2+1][loC[c]] + ps[loR[c]][loC[c]];
        // If every nonzero in bbox is color c, then box == cnt[c].
        if (box == cnt[c]) ++ans;
    }
    cout << ans << "\n";
}

Pitfalls

Treat 0 inside a bbox as "foreign." A 0 inside the would-be rectangle means a later color covered c, and either that color is no longer present or its bbox is elsewhere — either way c is not first.
Counting matches via nonzero prefix sum + cnt[c] is the cleanest check: equal ⇒ bbox contains only c.
Absent colors. Whether to count them depends on the problem's exact wording for "could be the first color painted." Re-read carefully and sanity-check on the sample.
Memory. N = 1000 gives 4 MB int grid + 8 MB prefix sum — tight; switch to int with care.

Problem 2 — Switch Grass

Statement

A connected weighted graph on N fields and M edges. Each field has a "grass type" (color) in 1..K. After each of Q recolor updates ("set field v to color c"), output the minimum edge-distance d(u, v) over all pairs (u, v) with distinct colors, where d is the graph shortest-path distance. (Equivalently: the minimum, over pairs of vertices of different colors, of the shortest path between them.)

Constraints

1 ≤ N, M, Q ≤ 200,000.
1 ≤ K ≤ N.
1 ≤ edge weight ≤ 10⁶.
The graph remains connected.
Time limit: 2s (potentially 3s on some Platinum problems).

Key idea

The shortest distance between any pair of different-color vertices is always realized along the boruvka / MST edges: if you contract on edges shorter than the answer, every monochromatic component must be the same color. So build an MST (or Boruvka tree / Kruskal reconstruction tree) sorted by weight. For each vertex maintain a multiset of "neighbor colors" along MST edges; the answer is the smallest MST-edge weight whose two endpoints (in the Kruskal reconstruction sense) carry vertices of different colors. Concretely:

Build MST. Use Kruskal's reconstruction tree: each internal node has a weight equal to the MST edge, and its subtree corresponds to vertices joined up to that weight.
For each internal node, track in a sorted multiset the multiset of colors present in its two subtree sides; the node is "valid" (gives a candidate answer = its weight) iff the two sides contain at least one differing color — or equivalently iff not all vertices below the node share a single color.
Maintain a global multiset of valid-node weights. The answer is its minimum.
Each color update flips O(log N) ancestor nodes' "single-color" status; update the global multiset accordingly with small-to-large merging or by storing each ancestor's color-multiset as a map<int,int>.

Complexity target

O((N + M + Q) log² N) with small-to-large + the reconstruction tree. Tight in 2s but standard.

Reference solution (C++) — sketch

#include <bits/stdc++.h>
using namespace std;
// Sketch: Kruskal reconstruction tree + per-node color multiset.
// Each internal node `u` stores cnt[u]: map<color, # leaves under u with that color>.
// The MST-edge weight w[u] is a candidate answer iff cnt[u] has >= 2 distinct keys.
// A global multiset<long long> of valid weights gives the answer in O(log N) per query.

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
};

int N, M, K, Q;
vector<tuple<int,int,int>> edges; // {w, u, v}
vector<array<int,2>> child; vector<long long> nodeW;
vector<int> parent;
vector<map<int,int>> cnt; // color counts per reconstruction-tree node
multiset<long long> valid;  // weights of nodes whose subtree is not monochromatic

void addColor(int u, int c, int delta) {
    // Walk up; update cnt and validity of every ancestor.
    while (u != -1) {
        bool wasMulti = cnt[u].size() >= 2;
        cnt[u][c] += delta;
        if (cnt[u][c] == 0) cnt[u].erase(c);
        bool isMulti = cnt[u].size() >= 2;
        if (!wasMulti && isMulti) valid.insert(nodeW[u]);
        if (wasMulti && !isMulti) valid.erase(valid.find(nodeW[u]));
        u = parent[u];
    }
}

int main() {
    // ... read input, build edges, sort, run Kruskal's reconstruction:
    //     each new internal node merges two DSU components into a fresh parent.
    // For each leaf (vertex), initialize cnt-walk with its starting color.
    // For each query (v, c): addColor(v, oldColor, -1); addColor(v, c, +1);
    //     answer = *valid.begin().
    // Implementation length ~60 lines once boilerplate is included.
}

A full implementation runs ~80 lines including DSU, Kruskal reconstruction, and the per-query update walk. The sketch above is the load-bearing structure; flesh out the input parsing and the reconstruction tree to ship it.

Pitfalls

Why MST suffices. The min-color-mismatch edge weight is realized by some MST edge whose two sides contain different colors. Non-MST edges are never the unique witness.
Per-node color count via map. Don't iterate all colors; only the ones actually present. Small-to-large merging at construction time keeps total cnt-map size O(N log N).
Updates touch O(log N) ancestors. Walking to the root would be O(N); use the reconstruction tree (which is balanced-like and has O(log N) depth on average) or path-compressed ancestor tricks.
Global multiset of valid weights. Adding/removing nodes from "valid" must mirror the per-node validity flips; off-by-one here gives subtle WA.

Problem 3 — COWBASIC

Statement

Interpret a toy language COWBASIC. Programs have variable assignments, integer literals, addition, and nested MOO loops with fixed iteration counts; one RETURN statement at the end outputs a variable's value. All arithmetic is modulo 10⁹+7. Loop iteration counts can be up to 100,000 and loops can be arbitrarily nested up to the program limit, so naive execution is way too slow.

Constraints

≤ 100 lines, ≤ 350 characters per line.
Literals are positive integers up to 100,000.
Variables are strings of up to 10 lowercase letters.
Arithmetic modulo 10⁹+7.
Time limit: 2s.

Key idea

The body of any loop is a linear transformation on the vector of variable values (extended with a constant 1 to handle literal additions). Parse the program into a tree of (loop, repeat count, child sequence) nodes. For each loop body, compose the linear transforms of its children into one matrix M, then matrix-exponentiate M by the loop's repeat count. The whole program reduces to a product of matrices, applied to the initial vector (all zeros with a trailing 1). Each variable's final value is read off the resulting vector.

Complexity target

O(V³ · log(iterations) · loops) where V is the number of distinct variables (≤ ~100). At V = 100 that's 10⁶ · 17 · ~100 = 1.7×10⁹; in practice V is much smaller, around 10–20, so it's comfortably under 10⁷.

Reference solution (C++) — sketch

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

int V; // number of variables + 1 (the +1 is the constant slot)
using Row = vector<ll>;
using Mat = vector<Row>;

Mat ident() {
    Mat m(V, Row(V, 0));
    for (int i = 0; i < V; ++i) m[i][i] = 1;
    return m;
}
Mat mul(const Mat& A, const Mat& B) {
    Mat C(V, Row(V, 0));
    for (int i = 0; i < V; ++i)
      for (int k = 0; k < V; ++k) if (A[i][k])
        for (int j = 0; j < V; ++j)
          C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
Mat pw(Mat A, ll e) {
    Mat R = ident();
    while (e) { if (e & 1) R = mul(R, A); A = mul(A, A); e >>= 1; }
    return R;
}

// Recursive parser returns the matrix for a block of statements.
// For "var = expr": build a row that copies var's row from identity but
// replaces it with the linear combination expr describes.
// For "MOO k ... END": parse inner block to matrix B, return pw(B, k).
// Compose left-to-right by matrix multiplication.

int main() {
    // ... parse input lines into tokens, assign each distinct variable an
    //     index 0..V-2, reserve index V-1 for the constant 1.
    // Build the program's overall matrix M, then evaluate M * initial_vector.
    // Print the value at the RETURN'd variable's row.
    // Full implementation ~120 lines with parsing; the algorithmic core is
    // the three helpers above plus the per-statement matrix construction.
}

Pitfalls

Extra constant slot. Without it, "x = x + 5" isn't representable as a linear map. Reserve one row/column for the constant 1.
RHS evaluates against pre-assignment state. Build the new row as the linear combination of old rows from the current matrix — never write into the row you're computing from. Compute the new row, then assign it.
Matrix size = #distinct variables + 1. Don't pre-allocate V = 100; count actual variables during parsing to keep the inner loop tight.
Loop counts up to 10⁵. log⊂2; ≈ 17 squarings per loop. With nested loops the products compose; total log factor across the whole program is at most ~100 · 17.
Whitespace and comments. Tokenize defensively — expressions like "x + y + 3" can have any amount of spacing.

What Platinum 2017 US Open was actually testing

P1 — same idea as Bronze, at N = 1000. 2D prefix sums turn the bbox check into O(1) per color.
P2 — MST + reconstruction tree + small-to-large. A textbook Platinum tree-DS problem with online updates.
P3 — linear algebra as a compiler. Recognize loops ↔ matrix powers; construct the right matrix representation for affine ops.