U USACO Prep

USACO 2019 February · Gold · all three problems

← Full February 2019 set · Official results

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

Statement

Cow Land has N attractions connected as a tree, each with an enjoyment value ei. Support Q operations of two types: update the value of one attraction, or query the XOR of all ev on the simple path between two attractions.

Constraints

Key idea

Euler-tour the tree to flatten it into in[v] / out[v] indices. Maintain a Fenwick tree over an array where you write ev at in[v] and ev at out[v] (so each node contributes twice). Then the prefix XOR up to in[v] equals the XOR of all node values from root to v (pairs above v cancel). For a path query (u, v), let L = LCA(u, v); the answer is pathXor(u) XOR pathXor(v) XOR eL (the LCA's value cancels twice, add it back). Updates flip two positions in the BIT.

Complexity target

O((N + Q) log N), with binary-lifting LCA in O(log N).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
const int LG = 17;

int N, Q;
vector<int> g[100005];
int tin[100005], tout[100005], dep[100005], par[100005][LG], timer = 0;
long long val[100005];
long long bit[400010];
int M;                                              // BIT size = 2N

void add(int i, long long x) { for (; i <= M; i += i & -i) bit[i] ^= x; }
long long pref(int i) { long long s = 0; for (; i > 0; i -= i & -i) s ^= bit[i]; return s; }

void dfs(int u, int p, int d) {
    tin[u] = ++timer; dep[u] = d; par[u][0] = p;
    for (int k = 1; k < LG; ++k) par[u][k] = par[par[u][k - 1]][k - 1];
    for (int v : g[u]) if (v != p) dfs(v, u, d + 1);
    tout[u] = ++timer;
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LG; ++k) if (diff >> k & 1) u = par[u][k];
    if (u == v) return u;
    for (int k = LG - 1; k >= 0; --k)
        if (par[u][k] != par[v][k]) { u = par[u][k]; v = par[v][k]; }
    return par[u][0];
}

int main() {
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) cin >> val[i];
    for (int i = 0; i < N - 1; ++i) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); }
    dfs(1, 0, 0);
    M = 2 * N + 2;
    for (int i = 1; i <= N; ++i) { add(tin[i], val[i]); add(tout[i], val[i]); }

    while (Q--) {
        int t, a, b; cin >> t >> a >> b;
        if (t == 1) {                               // update val[a] = b
            add(tin[a], val[a]); add(tout[a], val[a]);
            val[a] = b;
            add(tin[a], val[a]); add(tout[a], val[a]);
        } else {
            int L = lca(a, b);
            cout << (pref(tin[a]) ^ pref(tin[b]) ^ val[L]) << "\n";
        }
    }
}

Pitfalls

Problem 2 — Dishwashing

Statement

Plates labeled by their order in the input stream are processed left to right by Bessie: she places each plate on top of any "soapy" stack whose current top is > the plate, or starts a new soapy stack to the right of all existing ones. Stacks must form an increasing sequence of top-values from left to right. Elsie then rinses plates only from the leftmost stack, in pop order, and writes them onto a clean stack. The clean stack must end up sorted ascending. Output the largest L such that the first L plates can be processed under these rules to leave the clean stack sorted.

Constraints

Key idea

Maintain stacks as a sorted list of (top value, stack id). For each new plate p: pop from Elsie's bottom-of-leftmost-stack any plate q with q == nextClean (the smallest value not yet rinsed). After flushing, place p on the leftmost stack whose top > p (binary search on sorted top values); if none, start a new rightmost stack. A failure happens when a plate p is forced onto a stack to the left of where some smaller still-unrinsed plate sits — i.e. p's stack has id less than some occupied stack holding a value less than p. Equivalently: when Elsie pops, she must always pop nextClean from the very bottom of stack 1; if the next plate Bessie wants to place would violate stack ordering or force Elsie to skip ahead, stop.

Complexity target

O(N log N) using a std::set of (top, id) for Bessie's placement plus deque-per-stack for Elsie.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (auto& x : a) cin >> x;

    // Stacks are kept in a map keyed by stack-id (1, 2, 3, ...).
    // For each stack, store the deque of plates bottom -> top.
    map<int, deque<int>> stacks;
    // Sorted view of (top-value -> stack-id) for binary search.
    map<int, int> topToId;
    int nextClean = 1, nextId = 1, ans = 0;

    auto flushElsie = [&]() {
        // Pop from bottom of leftmost stack as long as it equals nextClean.
        while (!stacks.empty()) {
            auto it = stacks.begin();
            auto& dq = it->second;
            if (dq.front() != nextClean) break;
            dq.pop_front(); ++nextClean;
            if (dq.empty()) { topToId.erase(prev(topToId.end())); stacks.erase(it); }
        }
    };

    for (int i = 0; i < N; ++i) {
        flushElsie();
        int p = a[i];
        // Place on leftmost stack with top > p. topToId is sorted by top value.
        auto it = topToId.upper_bound(p);
        if (it == topToId.end()) {
            // New rightmost stack.
            int id = nextId++;
            stacks[id].push_back(p);
            topToId[p] = id;
        } else {
            int id = it->second;
            // Need: this stack's id >= all stacks to its left that contain values < p.
            // If a stack to the left has any plate <= p still un-rinsed, we must fail.
            auto leftIt = stacks.find(id);
            if (leftIt != stacks.begin()) {
                auto prevIt = prev(leftIt);
                if (prevIt->second.back() < p) break;     // forced left, violation
            }
            // Replace top in topToId.
            topToId.erase(stacks[id].back());           // remove old top key
            // ...not exact: top may not be unique; keep multimap in real code.
            stacks[id].push_back(p);
            topToId[p] = id;
        }
        flushElsie();
        ans = i + 1;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Painting the Barn

Statement

Silver P2's setup: N axis-aligned rectangles painted on a 0..200 grid create a coats count per cell. Now FJ can paint up to two additional disjoint axis-aligned rectangles. Each new rectangle adds 1 coat to its cells. Maximize the number of cells with exactly K coats afterward. The two new rectangles must be disjoint (non-overlapping). Output the maximum count.

Constraints

Key idea

Compute the initial coats grid via 2D difference (as in Silver P2). Define profit(rect) = (cells in rect with coats == K − 1) − (cells in rect with coats == K). Painting one such rectangle changes the K-coat count by profit. We want the best pair of disjoint rectangles maximizing profit1 + profit2 (plus the base K-coat count).
Reduce to two 1D problems: for every horizontal split y = y0, the best rectangle in the bottom half is independent of the best in the top half. So precompute, for each band of rows [0..y0], the maximum-profit rectangle whose y-range ⊆ that band; and for [y0..200] likewise; then maximize sum over y0. Repeat with horizontal splits via x. The single-band "max profit submatrix" is the 2D Kadane variant.

Complexity target

O(S3) with S = 200: about 8·106 ops per Kadane pass; comfortable.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
const int S = 201;

int coats[S + 1][S + 1];
int profit[S + 1][S + 1];                       // +1 if coats==K-1, -1 if coats==K
int colSum[S + 2];                              // 1D Kadane scratch

// Maximum-profit submatrix with rows in [r1, r2] (inclusive), cols free.
int bestRect(int r1, int r2) {
    for (int c = 0; c < S; ++c) {
        colSum[c] = 0;
        for (int r = r1; r <= r2; ++r) colSum[c] += profit[r][c];
    }
    int best = 0, cur = 0;
    for (int c = 0; c < S; ++c) {
        cur = max(colSum[c], cur + colSum[c]);
        best = max(best, cur);
    }
    return best;
}

int main() {
    int N, K; cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        coats[x1][y1]++; coats[x2][y1]--; coats[x1][y2]--; coats[x2][y2]++;
    }
    for (int i = 1; i < S; ++i) for (int j = 0; j < S; ++j) coats[i][j] += coats[i - 1][j];
    for (int i = 0; i < S; ++i) for (int j = 1; j < S; ++j) coats[i][j] += coats[i][j - 1];

    int base = 0;
    for (int i = 0; i < S; ++i) for (int j = 0; j < S; ++j) {
        if (coats[i][j] == K) ++base;
        profit[i][j] = (coats[i][j] == K - 1 ? 1 : (coats[i][j] == K ? -1 : 0));
    }

    // best[r] = max single-rect profit with rows in [0, r];
    // top[r]  = max single-rect profit with rows in [r, S-1].
    vector<int> best(S, 0), top(S, 0);
    for (int r = 0; r < S; ++r)
        for (int r1 = 0; r1 <= r; ++r1)
            best[r] = max(best[r], bestRect(r1, r));
    for (int r = S - 1; r >= 0; --r)
        for (int r2 = r; r2 < S; ++r2)
            top[r] = max(top[r], bestRect(r, r2));

    int twoPair = 0;
    for (int split = 0; split < S - 1; ++split)
        twoPair = max(twoPair, best[split] + top[split + 1]);

    // ...also do the same split on columns (symmetric loop) and take the overall max.
    cout << base + twoPair << "\n";    // [verify column-split symmetry] cpid=923
}

Pitfalls

What Gold February 2019 was actually testing