USACO 2016 January · Platinum · all three problems

← Full January 2016 set · Official results

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

Statement

Given an N×M grid of cells, each '.' (grass) or 'X' (swamp), find the largest axis-aligned rectangular area whose border (one-cell-wide frame) lies entirely on grass. The interior may include swamp cells — only the perimeter must be clear. Output the area (width · height) of the rectangle in square meters, counting the cells covered by the rectangle (including its interior).

Constraints

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

Key idea

For each pair of rows (r1, r2) with r1 ≤ r2, find the widest pair of columns (c1, c2) such that: (a) the row r1 between c1 and c2 has no 'X', (b) the row r2 between c1 and c2 has no 'X', (c) the column c1 between r1 and r2 has no 'X', and (d) the column c2 between r1 and r2 has no 'X'. With N, M ≤ 200, brute-force O(N²M²) ≈ 1.6·10⁹ is too slow; instead fix r1, r2 and sweep columns: for each candidate c2, the leftmost legal c1 is determined by the rightmost 'X' in row r1 or r2 between [c1, c2] and the lowest c1 such that column c1 has no 'X' in rows [r1, r2]. Precompute "next-X-right-in-row" and "row-range-of-column-X" arrays.

Complexity target

O(N · M²) ≈ 1.6·10⁷ for the sweep; precomputation O(NM).

Reference solution (C++)

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

int N, M;
vector<string> g;

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

    // colTopX[c][r] = nearest row <= r in column c that has 'X' (or -1)
    // For each pair (r1, r2), a column c is "vertically clear" iff colTopX[c][r2] < r1.
    vector<vector<int>> colTopX(M, vector<int>(N, -1));
    for (int c = 0; c < M; ++c) {
        int last = -1;
        for (int r = 0; r < N; ++r) {
            if (g[r][c] == 'X') last = r;
            colTopX[c][r] = last;
        }
    }
    // rowNextX[r][c] = nearest column >= c in row r that has 'X' (or M).
    vector<vector<int>> rowNextX(N, vector<int>(M + 1, M));
    for (int r = 0; r < N; ++r) {
        int nxt = M;
        for (int c = M - 1; c >= 0; --c) {
            if (g[r][c] == 'X') nxt = c;
            rowNextX[r][c] = nxt;
        }
    }

    int best = 0;
    for (int r1 = 0; r1 < N; ++r1) for (int r2 = r1; r2 < N; ++r2) {
        // For each c1, the largest c2 we can extend to is min(rowNextX[r1][c1], rowNextX[r2][c1]) - 1,
        // also limited by where any column in [c1+1, c2-1] has a vertical 'X' blocking the side wall.
        // Simpler: two-pointer style — for each c1 with column c1 clear, advance c2 as far as both rows
        // remain clear; check column c2 clear; record area.
        for (int c1 = 0; c1 < M; ++c1) {
            // column c1 must be vertically clear across [r1, r2]
            if (colTopX[c1][r2] >= r1) continue;
            int maxC2 = min(rowNextX[r1][c1], rowNextX[r2][c1]) - 1;
            // among c2 in [c1, maxC2], we want the largest c2 with column c2 also vertically clear
            // (best area is at maximum width). Scan downward — O(M) worst case.
            for (int c2 = maxC2; c2 >= c1; --c2) {
                if (colTopX[c2][r2] < r1) {
                    int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                    if (area > best) best = area;
                    break;
                }
            }
        }
    }
    cout << best << "\n";
}

Pitfalls

Interior cells may be swamp. Only the border must be 'X'-free; this is the entire trick.
Worst case is the inner loop. The scan-down for the largest legal c2 could be O(M), giving O(N²M²) ≈ 1.6·10⁹ in the worst case. For tight TLs, precompute "max c2 with column-clear >= c1" via a sparse table indexed by (r1, r2).
Area is (r2−r1+1) · (c2−c1+1) in cells; the problem statement counts the rectangle's full enclosed area, not just its perimeter.
1×k and k×1 frames are degenerate. A 1-row or 1-column rectangle is just a clear segment; it still counts.

Problem 2 — Mowing the Field

Statement

Farmer John mows a 2D field over N days. On day i he draws an axis-aligned segment from (x_i−1, y_i−1) to (x_i, y_i); consecutive segments alternate horizontal and vertical. Grass cut on day d regrows on day d + T. Count the number of times FJ's mowing path crosses a previously-cut segment where the previously-cut grass has already regrown. Crossings only count when one segment is horizontal and the other vertical (a proper interior crossing — endpoints excluded).

Constraints

2 ≤ N ≤ 10⁵, 1 ≤ T ≤ N, T even.
0 ≤ x_i, y_i ≤ 10⁹.
Each consecutive pair of segments shares an endpoint (the path is continuous).
Time limit: 2s.

Key idea

Treat the N−1 segments as events. For each vertical segment v (column x = X_v, spanning y ∈ [yL, yH], drawn on day d_v), count the number of horizontal segments h (row y = Y_h, spanning x ∈ [xL, xH], drawn on day d_h) such that xL < X_v < xH, yL < Y_h < yH, and |d_v − d_h| ≥ T. Standard offline-counting: coordinate-compress, sweep along one axis, use a BIT indexed by the other, and gate by day-difference (process each segment twice — once "active after T days have passed", once as a query).

Complexity target

O(N log N) sweep with a Fenwick tree on compressed coordinates.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Sketch — full implementation is ~80 lines. Structure:
//  1. Build N-1 segments, classify horizontal vs vertical with day index.
//  2. Coordinate-compress x and y separately.
//  3. Sweep "day" axis: at day d, add all segments drawn on day d-T (they're now regrown)
//     to a 2D index; for each segment drawn on day d, query how many regrown ones it crosses.
//  4. For horizontal queries use a BIT indexed by x; for vertical queries use a BIT indexed by y.

struct Seg { int day; int axis; ll fixedCoord; ll lo, hi; };  // axis: 0=H, 1=V

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, T; cin >> N >> T;
    vector<ll> xs(N), ys(N);
    for (int i = 0; i < N; ++i) cin >> xs[i] >> ys[i];
    vector<Seg> seg;
    for (int i = 1; i < N; ++i) {
        if (xs[i] == xs[i-1]) {
            // vertical
            seg.push_back({i, 1, xs[i], min(ys[i], ys[i-1]), max(ys[i], ys[i-1])});
        } else {
            seg.push_back({i, 0, ys[i], min(xs[i], xs[i-1]), max(xs[i], xs[i-1])});
        }
    }
    // Compress coordinates separately along each axis.
    auto compress = [&](vector<ll> v) {
        sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
        return v;
    };
    vector<ll> XS, YS;
    for (auto& s : seg) {
        if (s.axis == 1) { XS.push_back(s.fixedCoord); YS.push_back(s.lo); YS.push_back(s.hi); }
        else             { YS.push_back(s.fixedCoord); XS.push_back(s.lo); XS.push_back(s.hi); }
    }
    XS = compress(XS); YS = compress(YS);
    auto cx = [&](ll v) { return (int)(lower_bound(XS.begin(), XS.end(), v) - XS.begin()); };
    auto cy = [&](ll v) { return (int)(lower_bound(YS.begin(), YS.end(), v) - YS.begin()); };

    // Two BITs, one for activated horizontal segments (indexed by their y), one for verticals (by x).
    // For each query on day d we want segments activated by day d - T inclusive.
    // Use a delayed activation queue.
    int Hsz = (int)YS.size() + 2, Wsz = (int)XS.size() + 2;
    vector<ll> bitH(Hsz, 0), bitV(Wsz, 0); // point counters
    auto bitUpd = [&](vector<ll>& b, int i, ll v) { for (++i; i < (int)b.size(); i += i & -i) b[i] += v; };
    auto bitQry = [&](vector<ll>& b, int i) { ll s = 0; for (++i; i > 0; i -= i & -i) s += b[i]; return s; };
    auto bitRange = [&](vector<ll>& b, int l, int r) { return bitQry(b, r) - (l ? bitQry(b, l - 1) : 0); };

    // Map: at day d activate segment with index d-T. We iterate days in order.
    ll answer = 0;
    // For each segment, store its "midpoint coordinate" to add to the BIT on activation.
    // We need ranged queries: H seg at row Y over x in (xL, xH) crosses any active V seg with
    // X in (xL, xH) AND Y_seg.lo < Y < Y_seg.hi. A point BIT keyed by X alone isn't enough —
    // we also need the V's y-range to contain the H's y. The trick: process events by Y too.
    //
    // Full solution merges both axes via a 2D sweep (sweep-line on day, secondary BIT on
    // the geometric axis). Implementation omitted here for brevity; complexity O(N log N).
    (void)bitUpd; (void)bitRange; (void)cx; (void)cy;
    cout << answer << "\n";   // [verify against editorial] cpid=601
}

Pitfalls

Only perpendicular crossings count. Two parallel overlapping segments don't count as a crossing.
Endpoints excluded. The crossing point must lie strictly inside both segments — every segment shares an endpoint with its neighbour, so the path itself is full of "endpoint coincidences" you must ignore.
Day difference ≥ T, strict. Grass regrows at day d+T, so the new cut on day d+T is the first eligible re-cut. Check the inclusive/exclusive boundary carefully.
Sketch only. The full 2D offline counting is ~80 lines; the snippet above lays out the data structure shape but does not implement the cross-axis range query.

Problem 3 — Lights Out

Statement

Platinum version of Gold P3. Same rectilinear-polygon localisation problem: Bessie must reach vertex 1 in the dark, using turn-direction sensing and edge-length memory; output the worst-case (over starting vertices i > 1) of (dark distance − lit shortest distance). At Platinum the constraint stays N ≤ 200 but the required solution is exact and must handle every adversarial polygon — pathological cases include polygons with many congruent feature subsequences, where Bessie's signature ambiguity persists for many edges.

Constraints

4 ≤ N ≤ 200.
Coordinates integer in [−10⁵, 10⁵].
Output integer (rectilinear ⇒ all edge lengths integer).
Time limit: 2s.

Key idea

For every pair of starting candidates (i, j) with i ≠ j, find the smallest k such that the signatures (length, turn) of length k differ. This gives "separation index" sep[i][j]. From start i, the set of candidates consistent after k clockwise edges is {j : sep[i][j] > k}; Bessie can stop walking the moment this set has size 1. The first such k = max_{j ≠ i} sep[i][j] + (correction). Then dark distance from i = (clockwise walk for that many edges) + (lit distance from the resulting vertex back to 1). The answer is max_i (dark − lit). Build sep[][] in O(N²) via the Z-function on the doubled (length, turn) sequence.

Complexity target

O(N²) overall using string matching on the doubled signature.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Sketch — Platinum version of Gold P3. The full proof of why "walk until set is
// singleton" is optimal is in the official editorial; the implementation below
// computes sep[i][j] by direct O(N²) comparison (N=200 makes O(N³)=8e6, fine).

int N;
vector<ll> xs, ys;
vector<ll> edge;        // edge length i -> i+1
vector<int> turnSign;   // +1 or -1 at vertex i (turn from edge (i-1,i) to edge (i,i+1))

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    xs.resize(N); ys.resize(N);
    for (int i = 0; i < N; ++i) cin >> xs[i] >> ys[i];
    edge.assign(N, 0);
    for (int i = 0; i < N; ++i) {
        int j = (i + 1) % N;
        edge[i] = llabs(xs[j] - xs[i]) + llabs(ys[j] - ys[i]);
    }
    // turn sign via cross product of consecutive edges.
    turnSign.assign(N, 0);
    for (int i = 0; i < N; ++i) {
        int p = (i + N - 1) % N, q = (i + 1) % N;
        ll ax = xs[i] - xs[p], ay = ys[i] - ys[p];
        ll bx = xs[q] - xs[i], by = ys[q] - ys[i];
        ll cr = ax * by - ay * bx;
        turnSign[i] = (cr > 0) ? 1 : -1;
    }

    vector<ll> pref(N + 1, 0);
    for (int i = 0; i < N; ++i) pref[i + 1] = pref[i] + edge[i];
    ll perim = pref[N];
    auto cwDist = [&](int from, int to) {
        ll d = pref[to] - pref[from]; if (d < 0) d += perim; return d;
    };
    auto litDist = [&](int from) {
        ll a = cwDist(from, 0);
        return min(a, perim - a);
    };

    // sep[i][j] = smallest k where signatures of starts i, j differ in the first k edges.
    // O(N^3) brute force, fine for N = 200.
    vector<vector<int>> sep(N, vector<int>(N, N));
    for (int i = 1; i < N; ++i) for (int j = 1; j < N; ++j) if (i != j) {
        for (int k = 0; k < N; ++k) {
            int ei = (i + k) % N, ej = (j + k) % N;
            if (edge[ei] != edge[ej] || turnSign[(ei + 1) % N] != turnSign[(ej + 1) % N]) {
                sep[i][j] = k; break;
            }
        }
    }
    ll best = 0;
    for (int i = 1; i < N; ++i) {
        int k = 0;
        for (int j = 1; j < N; ++j) if (j != i) k = max(k, sep[i][j]);
        // walk k edges clockwise from i
        ll walked = 0; int cur = i;
        for (int t = 0; t < k; ++t) { walked += edge[cur]; cur = (cur + 1) % N; }
        ll dark = walked + litDist(cur);
        best = max(best, dark - litDist(i));
    }
    cout << best << "\n";
}

Pitfalls

Turn sign at vertex i is the turn after entering i, i.e. between edges (i−1, i) and (i, i+1). Index alignment matters.
Bessie may overshoot vertex 1. Once she identifies herself she walks the lit-distance to vertex 1, which may be shorter via the direction she just came from — be careful adding "dark walked" to "lit from current vertex".
O(N³) is OK at N = 200 (8·10⁶ ops). At higher N you'd need Z-function on the doubled (edge, turn) string.
Sketch caveat. The full solution must prove that walking exactly the separation index is optimal — the editorial gives a rigorous argument.

What Platinum January 2016 was actually testing

P1 — 2D rectangle search with frame-only constraint. Decompose into (rows, columns) pair sweeps with precomputed obstacle lookups.
P2 — offline 2D counting with a temporal gate. BIT sweep where activation is delayed by T days.
P3 — adversarial signature matching. Reduce a geometry-with-sensing puzzle to a longest-common-prefix question on a (length, turn) string.