U USACO Prep

USACO 2015 February · Silver · all three problems

← Full February 2015 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=feb15results. 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 — Censoring (Silver)

Statement

Same statement as Bronze P1: given S and a single pattern T, repeatedly delete the earliest occurrence of T from S and continue until none remain. Output the final S, which is guaranteed non-empty. The only difference vs. Bronze is the size: |S| up to 106, so the naive O(|S|·|T|) stack-with-tail-compare can be too slow.

Constraints

Key idea

Build KMP failure function for T. Process S character by character maintaining a stack of (character, kmp_state) pairs. For each incoming character c, advance from the current top state using KMP fail-jumps until either we match T[state] = c (advance), or fall off (state = 0). Push (c, new_state) onto the stack. If new_state equals |T|, pop |T| entries — and crucially the new top of stack has the previous state, ready to continue. This handles chain-deletions in O(|S|).

Complexity target

O(|S| + |T|) time, O(|S|) memory.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string S, T; cin >> S >> T;
    int m = (int)T.size();
    // KMP failure function
    vector<int> fail(m, 0);
    for (int i = 1, k = 0; i < m; ++i) {
        while (k > 0 && T[k] != T[i]) k = fail[k - 1];
        if (T[k] == T[i]) ++k;
        fail[i] = k;
    }
    // Stack of (char, state_after_consuming_this_char)
    vector<char> outC;     outC.reserve(S.size());
    vector<int>  outS;     outS.reserve(S.size());
    int state = 0;
    for (char c : S) {
        while (state > 0 && T[state] != c) state = fail[state - 1];
        if (T[state] == c) ++state;
        outC.push_back(c);
        outS.push_back(state);
        if (state == m) {
            // delete last m chars
            for (int k = 0; k < m; ++k) { outC.pop_back(); outS.pop_back(); }
            state = outS.empty() ? 0 : outS.back();
        }
    }
    cout.write(outC.data(), (int)outC.size());
    cout << "\n";
    return 0;
}

Pitfalls

Problem 2 — Cow Hopscotch (Silver)

Statement

R × C grid; each cell holds an integer label in 1..K. Same jump rule as Bronze (strictly down, strictly right, different label). Count distinct jump-sequences from (1, 1) to (R, C) modulo 109+7.

Constraints

Key idea

Same DP as Bronze: f[r][c] = number of jump-sequences ending at (r, c), with f[0][0] = 1, and 

f[r][c] = sum_{r' < r, c' < c, label[r'][c'] != label[r][c]} f[r'][c'].

At Silver, R, C ≤ 100 ⇒ at most 10⁴ cells, each summing over up to 10⁴ predecessors ⇒ 10⁸ elementary ops with a constant-time mod, which is borderline but fits within 2s in C++. No fancy optimisation needed.

Complexity target

O(R² · C²) ≈ 10⁸ ops at the limits — fine with tight inner loops.

Reference solution (C++)

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

int R, C, K;
int g[105][105];
long long f[105][105];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> R >> C >> K;
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c) cin >> g[r][c];
    f[0][0] = 1;
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (r == 0 && c == 0) continue;
            long long sum = 0;
            int lab = g[r][c];
            for (int rp = 0; rp < r; ++rp) {
                for (int cp = 0; cp < c; ++cp) {
                    if (g[rp][cp] != lab) sum += f[rp][cp];
                }
            }
            f[r][c] = sum % MOD;
        }
    }
    cout << f[R-1][C-1] << "\n";
    return 0;
}

Pitfalls

Problem 3 — Superbull

Statement

Single-elimination tournament with N teams. In each match, the score is the XOR of the two teams' IDs, and FJ chooses which team is eliminated. The tournament runs N − 1 matches (one team remains). Maximise the sum of all match scores.

Constraints

Key idea

Treat the N teams as vertices of a complete graph; the edge weight between i and j is idi XOR idj. The N − 1 matches form a spanning tree of this graph (any single-elimination bracket on N nodes is a tree with N − 1 edges, and conversely any spanning tree can be realised as a bracket because we choose which team is eliminated). Maximising the sum of edge weights = maximum spanning tree. With N ≤ 2000 the dense Prim's algorithm in O(N²) is the cleanest fit.

Complexity target

O(N²) ≈ 4·10⁶ operations.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> id(N);
    for (auto& x : id) cin >> x;
    // Dense Prim for maximum spanning tree.
    vector<ll> best(N, -1);
    vector<char> inTree(N, 0);
    best[0] = 0;
    ll total = 0;
    for (int it = 0; it < N; ++it) {
        int u = -1;
        for (int v = 0; v < N; ++v) {
            if (!inTree[v] && (u == -1 || best[v] > best[u])) u = v;
        }
        inTree[u] = 1;
        total += best[u];
        for (int v = 0; v < N; ++v) {
            if (!inTree[v]) {
                ll w = id[u] ^ id[v];
                if (w > best[v]) best[v] = w;
            }
        }
    }
    cout << total << "\n";
    return 0;
}

Pitfalls

What Silver February 2015 was actually testing