U USACO Prep

USACO 2017 December · Platinum · all three problems

← Full December 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec17results. 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 — Standing Out from the Herd

Statement

There are N strings. For each string si, count the number of distinct substrings of si that do NOT appear as a substring of any other sj (j ≠ i). Output one number per string.

Constraints

Key idea

Build a generalized suffix automaton (GSA) over all N strings. Each state of the SAM represents an equivalence class of substrings with identical right-extension behavior; the number of substrings in a state is len(state) − len(link(state)). Tag each state by the set (or single owner if unique) of string indices whose suffixes pass through it. A state contributes to string i iff its owner set is exactly {i}. Sum len − len(link) over those states for each i.

Complexity target

O(Σ|s| · α) for SAM construction, O(states) to tally owners. α is alphabet (26).

Reference solution (C++)

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

// Schematic generalized suffix automaton. Real implementations are ~80 lines;
// this sketches just the unique-substring tally on top of a built SAM.
struct SAM {
    struct St { int len, link; array<int,26> nxt; int owner; };
    // owner: -1 = none, -2 = multiple (disqualified), else string index.
    vector<St> st;
    int last;
    void init() {
        st.clear(); st.push_back({0,-1,{},-1}); st[0].nxt.fill(-1); last = 0;
    }
    void extend(int c, int idx) {
        // Standard SAM extend; on each visited (newly-created or cloned) state,
        // mark owner = idx if -1, else mark -2 if owner != idx.
        // (Implementation omitted; see cp-algorithms SAM.)
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<string> s(N);
    SAM sam; sam.init();
    for (int i = 0; i < N; ++i) {
        cin >> s[i];
        sam.last = 0; // reset for generalized: continue from root each new string
        for (char ch : s[i]) sam.extend(ch - 'a', i);
    }
    vector<long long> ans(N, 0);
    for (int v = 1; v < (int)sam.st.size(); ++v) {
        if (sam.st[v].owner >= 0)
            ans[sam.st[v].owner] += sam.st[v].len - sam.st[sam.st[v].link].len;
    }
    for (auto x : ans) cout << x << "\n";
}

Pitfalls

Problem 2 — Push a Box

Statement

A grid with obstacles holds a single box at start cell B and Farmer John at cell F. To push the box, FJ must be on the side opposite the desired push direction, and that cell must be empty (or reachable around the box). For each query target cell T, decide whether the box can be pushed from B to T.

Constraints

Key idea

State = (box cell, side FJ is on relative to box) ∈ R·C·4. From a state, to push the box in direction d, FJ must occupy side d̄ (opposite of d) — i.e. be the current state — and the cell beyond the box in direction d must be open. The transition: box moves to that new cell, FJ is now on side d̄ relative to the new box position (he stepped into the old box square). Sub-step: FJ can also walk around the box without pushing — those are free transitions between (box, side1) and (box, side2) iff side1 and side2 are connected in the grid with the box treated as an obstacle. Precompute connectivity once per box position lazily, or BFS the 4·R·C state graph directly. Then the box can reach T iff some (T, side) is reachable from (B, initial-side).

Complexity target

O(R · C · 4) states · O(1) average per transition ≈ O(R · C) BFS.

Reference solution (C++)

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

int R, C;
vector<string> g;
const int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};

// id(r,c,side) = (r*C + c)*4 + side
int id(int r, int c, int s) { return (r * C + c) * 4 + s; }
bool ok(int r, int c) { return 0 <= r && r < R && 0 <= c && c < C && g[r][c] != '#'; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q; cin >> R >> C >> Q;
    g.resize(R);
    for (auto& row : g) cin >> row;
    int br = 0, bc = 0, fr = 0, fc = 0;
    for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) {
        if (g[r][c] == 'B') { br = r; bc = c; g[r][c] = '.'; }
        if (g[r][c] == 'A') { fr = r; fc = c; g[r][c] = '.'; }
    }
    // BFS on (box, side). Initial: every side s such that FJ can reach
    // (br+dr[s], bc+dc[s]) treating box at (br,bc) as obstacle.
    vector<char> reach(R * C * 4, 0);
    queue<tuple<int,int,int>> q;
    // (Initialization: BFS from FJ with box as obstacle to mark which sides
    // of (br,bc) FJ can occupy.) Omitted for brevity.

    while (!q.empty()) {
        auto [r, c, s] = q.front(); q.pop();
        for (int d = 0; d < 4; ++d) {
            // To push in direction d, FJ must be on side opposite d:
            // i.e. current state side s must equal "opposite of d", meaning
            // FJ at (r - dr[d], c - dc[d]); new box at (r+dr[d], c+dc[d]).
            int nr = r + dr[d], nc = c + dc[d];
            // and we need s to be the "opposite of d" side index.
            if (s != (d ^ 1)) continue;
            if (!ok(nr, nc)) continue;
            int nid = id(nr, nc, d ^ 1);
            if (!reach[nid]) { reach[nid] = 1; q.push({nr, nc, d ^ 1}); }
        }
        // Plus: free side-walks at the same box cell, computed via a small
        // BFS in the grid-minus-box. Omitted.
    }
    while (Q--) {
        int r, c; cin >> r >> c; --r; --c;
        bool yes = (r == br && c == bc);
        for (int s = 0; s < 4; ++s) if (reach[id(r, c, s)]) yes = true;
        cout << (yes ? "YES" : "NO") << "\n";
    }
}

Pitfalls

Problem 3 — Greedy Gift Takers

Statement

N cows stand in a line for gifts. Each cow i has a "greed" value ci. The cow at the front takes a gift and re-inserts herself ci positions back. This continues forever (gifts are infinite). Count how many cows in the original line will NEVER reach the front and so never get a gift.

Constraints

Key idea

Binary-search the boundary k such that the first k cows are "stuck" forever and the last N − k get gifts. Test predicate: sort c1..ck (the front k that we conjecture take gifts). For each i, the i-th cow (1-indexed within that prefix) inserts herself c(i) places back; for this prefix to be self-sustaining (everyone in it gets a gift before any of the last N − k advances to the front), we need that after the i-th re-insertion, fewer than k − i cows from the back have moved in. Concretely: sort the prefix's greeds ascending; for i = 1..k we need c(i) > i (so the insertion lands past position k). The largest k satisfying "for all i in sorted prefix, c(i) > i" is the count of takers. Answer = N − k.

Complexity target

O(N log² N) with binary search + per-step sort, or O(N log N) with a Fenwick tree.

Reference solution (C++)

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

int N;
vector<int> c;

// predicate: do the first k cows (positions 1..k of original) all get a gift?
bool feasible(int k) {
    vector<int> v(c.begin(), c.begin() + k);
    sort(v.begin(), v.end());
    // i-th in sorted order (1-indexed) must satisfy v[i-1] > i, so its
    // re-insertion lands beyond the prefix of remaining takers.
    for (int i = 0; i < k; ++i) if (v[i] <= i + 1 - 1) return false;
    // Equivalently v[i] > i (0-indexed). Wait: condition is v[i] >= k - i,
    // i.e. lands at-or-past the boundary of prefix. Off-by-one is the
    // classic gotcha here; see editorial.
    for (int i = 0; i < k; ++i) if (v[i] < k - i) return false;
    return true;
}

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

    // Largest k in [0..N] with feasible(k). Use binary search since
    // feasibility is monotone in k.
    int lo = 0, hi = N;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (feasible(mid)) lo = mid; else hi = mid - 1;
    }
    cout << (N - lo) << "\n";
}

Pitfalls

What Platinum December 2017 was actually testing