U USACO Prep

USACO 2015 US Open · Bronze · all four problems

← Full 2015 US Open set · Official results

Source. Statements and constraints paraphrased from usaco.org/index.php?page=open15results and the per-problem pages (cpids 545–548). Note: 2015 US Open Bronze had 4 problems, not 3.

Problem 1 — Moocryption

Statement

A puzzle grid was originally full of the word "MOO" appearing horizontally, vertically, or diagonally (all 8 directions). Then a substitution cipher was applied: every letter A–Z is remapped to some other letter, with two rules — the map is a permutation, and no letter maps to itself. You are given the encrypted N×M grid. Find the maximum number of "MOO" occurrences that any valid cipher can decrypt back to.

Constraints

Key idea

Decryption picks two distinct letters (m', o') in the encrypted alphabet that decode to M and O. For each ordered pair (m', o') with m' ≠ o', count how many length-3 lines in the 8 directions equal (m', o', o'). Take the maximum. Because the cipher forbids fixed points we also need m' ≠ M and o' ≠ O — though the "no fixed point" rule constrains the full permutation, so it's always extensible as long as 26 ≥ 2 (it is). Practically: precompute, for every ordered pair (x, y) with x ≠ y, the count of (x, y, y) triples appearing as straight lines; output the max.

Complexity target

O(N·M · 8) to count triples per ordered letter pair, then O(26²) to read off the max. Trivially fast.

Reference solution (C++)

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

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

    // cnt[x][y] = # length-3 straight lines (x, y, y) in any of 8 directions.
    int cnt[26][26] = {{0}};
    int dr[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1,-1, 1,-1, 0, 1};
    for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j)
        for (int d = 0; d < 8; ++d) {
            int i2 = i + dr[d], j2 = j + dc[d];
            int i3 = i + 2*dr[d], j3 = j + 2*dc[d];
            if (i3 < 0 || i3 >= N || j3 < 0 || j3 >= M) continue;
            if (i2 < 0 || i2 >= N || j2 < 0 || j2 >= M) continue;
            char a = g[i][j], b = g[i2][j2], c = g[i3][j3];
            if (b == c && a != b) cnt[a-'A'][b-'A']++;
        }
    int best = 0;
    for (int x = 0; x < 26; ++x) for (int y = 0; y < 26; ++y)
        if (x != y) best = max(best, cnt[x][y]);
    cout << best << "\n";
}

Pitfalls

Problem 2 — Bessie Gets Even

Statement

Given lists of possible values for variables B, E, S, I, G, O, M (each variable has up to 20 listed values, all integers in [−300, 300]), count the number of distinct assignments such that the product (B+E+S+S+I+E) · (G+O+E+S) · (M+O+O) is even.

Constraints

Key idea

Parity only — replace every value by its bit mod 2. With ≤ 20 values per variable and 7 variables, total assignment count is ≤ 207 ≈ 1.28·109, too many to enumerate directly. Instead: collapse each variable to two parity counts ev (even) and ov (odd). The factor (B+E+S+S+I+E) ≡ B+I (mod 2) since duplicates cancel; (G+O+E+S) and (M+O+O) ≡ M (mod 2) similarly. So the product's parity is determined by the parities of {B, I, G, O, E, S, M} via the three simplified factor expressions. Enumerate the 27 = 128 parity tuples, compute the factor parities, count the tuple as "even product" if at least one factor is even, and multiply the per-variable counts.

Concretely: factor F1 = B⊕I, F2 = G⊕O⊕E⊕S, F3 = M (since O+O is always even). Product is even iff F1 = 0 ∨ F2 = 0 ∨ F3 = 0. (Sum-of-bits arithmetic: a sum is odd iff an odd number of summands are odd. S appears twice in F1 so cancels; O appears twice in F3 so cancels.)

Complexity target

O(N) to read, O(27) to enumerate parity tuples — instant.

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;
    // index variables: B=0 E=1 S=2 I=3 G=4 O=5 M=6
    map<char,int> id = {{'B',0},{'E',1},{'S',2},{'I',3},{'G',4},{'O',5},{'M',6}};
    ll cnt[7][2] = {{0}};       // [var][parity]
    for (int i = 0; i < N; ++i) {
        char v; int x; cin >> v >> x;
        cnt[id[v]][((x % 2) + 2) % 2]++;
    }

    ll ans = 0;
    // Enumerate all 128 parity assignments.
    for (int mask = 0; mask < 128; ++mask) {
        int p[7];
        for (int i = 0; i < 7; ++i) p[i] = (mask >> i) & 1;
        int F1 = p[0] ^ p[3];               // B ^ I
        int F2 = p[4] ^ p[5] ^ p[1] ^ p[2]; // G ^ O ^ E ^ S
        int F3 = p[6];                      // M
        bool even = (F1 == 0) || (F2 == 0) || (F3 == 0);
        if (!even) continue;
        ll ways = 1;
        for (int i = 0; i < 7; ++i) ways *= cnt[i][p[i]];
        ans += ways;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Trapped in the Haybales (Bronze)

Statement

A road has N hay bales, each at a position pi and with size si. Bessie stands somewhere on the road (not on a bale). She cannot cross a bale unless, after running distance D in one direction, she has D > s for the next bale. Bessie is "trapped" if she cannot escape past either the leftmost or the rightmost bale. Compute the total length of road positions from which Bessie is trapped.

Constraints

Key idea

Sort bales by position. Between consecutive bales i and i+1 lies an open interval (pi, pi+1). For Bessie inside that interval, simulate: she can run left up to bale i, gaining speed equal to (current position − pi); if that exceeds si, she breaks through and now has a wider runway to the previous bale. Repeat. Symmetric for the right side. Bessie is trapped from interval (pi, pi+1) iff she gets stuck on both sides. Because the trapping condition splits the gap into "left-escape", "right-escape", and "trapped" sub-intervals at the crossover points, a careful simulation per gap suffices. With N ≤ 100 a quadratic simulation per gap is plenty.

Complexity target

O(N³) worst case (per gap, expand both sides through up to N bales): well under a second.

Reference solution (C++)

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

// Given Bessie at position x in gap between bale L (left) and R (right) of a sorted bale array,
// returns true iff she cannot escape past either end.
bool trapped(const vector<pair<ll,ll>>& b, int L, int R, ll x) {
    // Try right: starting at x, repeatedly attempt to break through b[R], b[R+1], ...
    auto canRight = [&](ll start) {
        int i = R; ll pos = start;
        while (i < (int)b.size()) {
            ll D = b[i].first - pos;     // run distance to reach bale i
            if (D > b[i].second) { pos = b[i].first; i++; }
            else return false;
        }
        return true;                     // ran off the right end
    };
    auto canLeft = [&](ll start) {
        int i = L; ll pos = start;
        while (i >= 0) {
            ll D = pos - b[i].first;
            if (D > b[i].second) { pos = b[i].first; i--; }
            else return false;
        }
        return true;
    };
    return !canLeft(x) && !canRight(x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<pair<ll,ll>> b(N);             // (position, size)
    for (auto& p : b) cin >> p.second >> p.first; // input is "size pos"
    sort(b.begin(), b.end(), [](auto& a, auto& c){ return a.first < c.first; });

    ll total = 0;
    for (int i = 0; i + 1 < N; ++i) {
        ll lo = b[i].first + 1, hi = b[i+1].first - 1;
        // Binary search the leftmost x in [lo,hi] from which Bessie can escape left;
        // similarly the rightmost x from which she can escape right. The trapped
        // sub-interval lies between them. (Both predicates are monotonic in x.)
        // Left-escape is monotonically true as x grows? No — running RIGHT to escape
        // gets easier as x DECREASES (more runway). Mirror it.
        auto canL = [&](ll x){ return !trapped(b, i, i+1, x); }; // not trapped => escapes one side
        // simple linear scan suffices for N <= 100, hi-lo can be up to 1e9 so binary search.
        // We instead compute the two thresholds with binary search per gap.
        ll loE = lo - 1, hiE = hi + 1; // sentinels meaning "no x escapes"
        // Right-escape: easier when x is small. Find largest x that escapes right.
        {
            ll l = lo, r = hi, ans = lo - 1;
            while (l <= r) {
                ll m = l + (r - l) / 2;
                int idx = i + 1; ll pos = m; bool ok = true;
                while (idx < N) {
                    ll D = b[idx].first - pos;
                    if (D > b[idx].second) { pos = b[idx].first; idx++; }
                    else { ok = false; break; }
                }
                if (ok) { ans = m; l = m + 1; } else { r = m - 1; }
            }
            hiE = ans; // x in [lo, hiE] escapes right
        }
        // Left-escape: easier when x is large. Find smallest x that escapes left.
        {
            ll l = lo, r = hi, ans = hi + 1;
            while (l <= r) {
                ll m = l + (r - l) / 2;
                int idx = i; ll pos = m; bool ok = true;
                while (idx >= 0) {
                    ll D = pos - b[idx].first;
                    if (D > b[idx].second) { pos = b[idx].first; idx--; }
                    else { ok = false; break; }
                }
                if (ok) { ans = m; r = m - 1; } else { l = m + 1; }
            }
            loE = ans; // x in [loE, hi] escapes left
        }
        ll trappedLo = hiE + 1, trappedHi = loE - 1;
        if (trappedLo <= trappedHi) total += trappedHi - trappedLo + 1;
    }
    cout << total << "\n";
}

Pitfalls

Problem 4 — Palindromic Paths (Bronze)

Statement

Bessie walks an N×N grid of uppercase letters from the top-left to bottom-right, moving only down or right. Each path spells a string of length 2N−1. Count the number of distinct palindromic strings that can be produced (different paths spelling the same palindrome count once).

Constraints

Key idea

A length-(2N−1) palindrome is determined by its first N characters (positions 0..N−1). Walk N−1 steps from (0,0) and simultaneously N−1 steps backward from (N−1,N−1), requiring the letters at matching palindrome positions to be equal at every step. Track the "front" and "back" cursors on the anti-diagonal of step k (cells where row+col = k from start and row+col = 2N−2−k from end). Insert the resulting prefix strings into a set and report the size. With N ≤ 18 the prefix is 18 letters and BFS frontiers stay small relative to 269.

Complexity target

Worst case state space O(N · (number of distinct prefix strings on anti-diagonal k) · 2). For N=18 a hash-set of pairs (front_cell, back_cell, prefix) keeps this tractable; output is at most ~105–106 distinct palindromes in practice.

Reference solution (C++)

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

int N;
vector<string> g;
set<string> found;

// Two cursors walk in lock-step. The "front" starts at (0,0) and moves D/R;
// the "back" starts at (N-1,N-1) and moves U/L. After N-1 steps they sit
// on the middle anti-diagonal (row+col = N-1). The string is a palindrome
// iff every paired letter matched along the way.
void dfs(int r1, int c1, int r2, int c2, string& pref) {
    if (g[r1][c1] != g[r2][c2]) return;
    pref.push_back(g[r1][c1]);
    if (r1 + c1 == N - 1) {
        // r1 == r2, c1 == c2 (middle diagonal converged) => full palindrome built.
        if (r1 == r2 && c1 == c2) {
            string s = pref;
            for (int i = (int)pref.size() - 2; i >= 0; --i) s.push_back(pref[i]);
            found.insert(s);
        }
    } else {
        // front moves D or R; back moves U or L.
        int dr1[2] = {1, 0}, dc1[2] = {0, 1};
        int dr2[2] = {-1, 0}, dc2[2] = {0, -1};
        for (int a = 0; a < 2; ++a) for (int b = 0; b < 2; ++b) {
            int nr1 = r1 + dr1[a], nc1 = c1 + dc1[a];
            int nr2 = r2 + dr2[b], nc2 = c2 + dc2[b];
            if (nr1 < N && nc1 < N && nr2 >= 0 && nc2 >= 0)
                dfs(nr1, nc1, nr2, nc2, pref);
        }
    }
    pref.pop_back();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    g.resize(N);
    for (auto& r : g) cin >> r;
    string pref;
    dfs(0, 0, N - 1, N - 1, pref);
    cout << found.size() << "\n";
}

Pitfalls

What Bronze 2015 US Open was actually testing