U USACO Prep

USACO 2015 February · Bronze · 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 (Bronze)

Statement

Given a string S and a censored substring T, repeatedly find the earliest occurrence of T inside S and delete it. After a deletion, two previously-separated parts of S abut, possibly creating a new occurrence of T — keep going until no occurrence of T remains. Output the final S. S is guaranteed never to become empty.

Constraints

Key idea

Bronze accepts the "stack of characters" simulation. Push each character of S onto a stack; after each push, peek at the top |T| characters of the stack and, if they equal T, pop them. Because we re-check only after each push, any chain reaction from a deletion is handled the next time a character lands. With |T| short (Bronze tests are small), naive comparison is fine.

Complexity target

O(|S|·|T|) worst case for Bronze. (Silver tightens this to O(|S|+|T|) via KMP.)

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();
    string stk;
    stk.reserve(S.size());
    for (char c : S) {
        stk.push_back(c);
        if ((int)stk.size() >= m) {
            bool match = true;
            for (int i = 0; i < m; ++i) {
                if (stk[stk.size() - m + i] != T[i]) { match = false; break; }
            }
            if (match) stk.resize(stk.size() - m);
        }
    }
    cout << stk << "\n";
    return 0;
}

Pitfalls

Problem 2 — COW

Statement

You are given a string of length N over the alphabet {C, O, W}. Count the number of ways to choose three indices i < j < k such that S[i] = 'C', S[j] = 'O', S[k] = 'W'. In other words, count the occurrences of "COW" as a subsequence (not necessarily contiguous, and different choices may share characters).

Constraints

Key idea

Single pass, three running counters. Let c = number of C's seen so far, co = number of "CO" subsequences seen so far, cow = number of full COW subsequences. On reading character x:

Output cow. This is the standard "count subsequence of length k via k running counts" trick.

Complexity target

O(N) time, O(1) memory.

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;
    string s; cin >> s;
    ll c = 0, co = 0, cow = 0;
    for (char ch : s) {
        if (ch == 'C')      c   += 1;
        else if (ch == 'O') co  += c;
        else if (ch == 'W') cow += co;
    }
    cout << cow << "\n";
    return 0;
}

Pitfalls

Problem 3 — Cow Hopscotch (Bronze)

Statement

An R × C grid; each cell is 'R' (red) or 'B' (blue). Starting at (1, 1), Bessie wants to reach (R, C). A single jump from (r, c) to (r', c') is legal iff r' > r AND c' > c AND the destination cell has a different colour from the current cell. Count the number of distinct sequences of legal jumps from (1, 1) to (R, C).

Constraints

Key idea

Direct DP. Let f[r][c] = number of legal jump-sequences ending at cell (r, c). Then f[1][1] = 1 and for every other cell: 

f[r][c] = sum of f[r'][c'] over all (r', c') with r' < r, c' < c, colour(r',c') != colour(r,c).

Direct evaluation is O(R²C²) ≈ 50k operations — trivial.

Complexity target

O(R² · C²) — about 5·10⁴ operations at R = C = 15.

Reference solution (C++)

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

int R, C;
vector<string> g;
ll f[20][20];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> R >> C;
    g.resize(R);
    for (auto& row : g) cin >> row;
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (r == 0 && c == 0) continue;
            ll sum = 0;
            for (int rp = 0; rp < r; ++rp) {
                for (int cp = 0; cp < c; ++cp) {
                    if (g[rp][cp] != g[r][c]) sum += f[rp][cp];
                }
            }
            f[r][c] = sum;
        }
    }
    cout << f[R-1][C-1] << "\n";
    return 0;
}

Pitfalls

What Bronze February 2015 was actually testing