U USACO Prep

USACO 2015 US Open · Gold · all three problems

← Full 2015 US Open set · Official results

Source. Statements paraphrased from usaco.org/index.php?page=open15results and per-problem pages (cpids 552–554).

Problem 1 — Googol

Statement

Interactive problem. A company is a balanced binary tree: each node either has both children, only a left child, or no children, with the left subtree's size equal to or one more than the right subtree's size. The CEO has ID 1. By querying any employee ID, you receive the IDs of its left and right children (or 0). Determine the total number of employees N in at most 70 000 queries.

Constraints

Key idea

The tree shape is fully determined by N (left subtree of any node has ceil((s−1)/2) nodes where s is that subtree's size). So we just need N. Crucial structural fact: the leftmost path from the root has length exactly ⌈log2(N+1)⌉ = h, and the deepest level is either fully left-only or some prefix of nodes have both children. Walk down the left spine to learn h. Then binary search on the index k ∈ [1, 2h−1] of the leftmost missing leaf at depth h: probe the k-th leaf at that depth via path bits (left at bit 0, right at bit 1). N = 2h−1 − 1 + k_last where k_last is the largest leaf that exists. Each query touches O(h) ancestors at worst, but for the binary search we only need h + log2(N) ≈ 2h ≈ 700 queries — comfortably under 70 000.

Because N can be 10100, all arithmetic is on big integers; in C++ use a simple bignum or __int128-plus-decimal-string approach. Below I sketch the path-probing loop using a big-int via boost-style operations replaced with strings + helper functions.

Complexity target

≈ 2·log2(N) ≈ 700 queries for N up to 10100. Wall time dominated by I/O.

Reference solution (C++)

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

// Sketch only: this problem needs a big-integer library and an interactive
// protocol. The full big-int code is >100 lines; the structure is what matters.
// "BigInt" below is any class supporting +, -, *, /, %, comparison, and
// "from_string"/"to_string". Use Java BigInteger or Python int in a real
// submission for less pain.

struct BigInt { /* ... a minimal decimal-string bignum ... */ };

string query(const string& id) {
    cout << id << endl;          // ask judge for children of `id`
    string L, R; cin >> L >> R;
    return L + " " + R;             // pack for caller; in real code return a pair
}

// 1) Walk leftmost path: query 1, then its left child, etc., until left child is 0.
//    The depth reached is h.
// 2) Now we know N is in [2^(h-1), 2^h - 1].
// 3) Binary search on k = N - (2^(h-1) - 1) in [1, 2^(h-1)].
//    To test "does leaf #k exist at depth h?" trace the path from root by k's bits
//    (interpreted with MSB = first move): 0 -> left, 1 -> right. The leaf exists
//    iff every step's requested child is nonzero.
// 4) Output "Answer N" where N = 2^(h-1) - 1 + (largest existing k).

int main() {
    // Pseudocode: real submission instantiates BigInt and runs the two stages above.
    // Stage 1: find h.
    // Stage 2: binary search k. Each probe is O(h) queries.
    // Total < 2h^2 queries; for h=333 that's ~220k -> tighten by reusing path prefixes
    // (visit ancestor only once per descent). Practically 2h queries suffice.
    return 0;
}

Full implementation requires bignum arithmetic and careful I/O flushing — see the official editorial at usaco.org/current/data/sol_googol.html .

Pitfalls

Problem 2 — Palindromic Paths (Gold)

Statement

Same setup as Bronze P4: N×N grid of A–Z, walk top-left to bottom-right with down/right moves only, count the paths that spell palindromes. Mod 109+7.

Constraints

Key idea

Two walkers advance in lock-step on opposite anti-diagonals: walker A from (0,0) moving D/R, walker B from (N−1,N−1) moving U/L. After step k each has walked k cells. A path-pair contributes iff the letters match at every step. State: dp[k][r1][r2] = number of valid lock-step pairs where after k steps walker A is at row r1 (so column k−r1) and walker B at row r2 (column N−1−(k−r2)). Transition: 4 combinations (A moves D/R) × (B moves U/L), each subject to letter equality at the new cell. Final answer: sum over middle anti-diagonal (k = N−1) states with r1 == r2 (they must meet to spell a palindrome). For palindromes counted as paths (not distinct strings) each path-pair (forward, reverse) corresponds to one path-tracing-palindrome contribution; the answer is dp[N−1][r][r] summed (or with one half-step adjustment for parity).

Memory: O(N²) per layer suffices (rolling two layers). 500² · 500 ≈ 1.25·108 transitions — fits in 2s with tight inner loops.

Complexity target

O(N³) time, O(N²) memory.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1'000'000'007;

int N;
vector<string> g;

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

    // Walker A at row r1, col k - r1; walker B at row r2, col (N-1) - (k - r2).
    // Use rolling 2D arrays cur/nxt over (r1, r2).
    vector<vector<int>> cur(N, vector<int>(N, 0)), nxt(N, vector<int>(N, 0));
    if (g[0][0] == g[N-1][N-1]) cur[0][N-1] = 1;        // k = 0

    for (int k = 1; k <= N - 1; ++k) {
        for (auto& row : nxt) fill(row.begin(), row.end(), 0);
        for (int r1 = 0; r1 <= k; ++r1) {
            int c1 = k - r1;
            if (r1 >= N || c1 >= N || c1 < 0) continue;
            for (int r2 = N - 1; r2 >= N - 1 - k; --r2) {
                int c2 = (N - 1) - (k - (N - 1 - r2));
                if (r2 < 0 || c2 < 0 || c2 >= N) continue;
                if (g[r1][c1] != g[r2][c2]) continue;
                // Predecessors: A came from (r1-1, c1) or (r1, c1-1).
                //               B came from (r2+1, c2) or (r2, c2+1).
                ll s = 0;
                for (int da = 0; da < 2; ++da) for (int db = 0; db < 2; ++db) {
                    int pr1 = r1 - (da == 0 ? 1 : 0);
                    int pc1 = c1 - (da == 1 ? 1 : 0);
                    int pr2 = r2 + (db == 0 ? 1 : 0);
                    int pc2 = c2 + (db == 1 ? 1 : 0);
                    if (pr1 < 0 || pc1 < 0 || pr2 >= N || pc2 >= N) continue;
                    s += cur[pr1][pr2];
                }
                nxt[r1][r2] = (int)(s % MOD);
            }
        }
        swap(cur, nxt);
    }

    // After N-1 steps, both walkers sit on the central anti-diagonal r1+c1 = N-1
    // = r2+c2. For a palindrome, the two walkers must be on the SAME cell:
    // r1 == r2.
    ll ans = 0;
    for (int r = 0; r < N; ++r) ans = (ans + cur[r][r]) % MOD;
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Trapped in the Haybales (Gold)

Statement

Same physics as Bronze/Silver. Bessie may stand anywhere on the road (not on a bale). Output the total length of starting positions from which she cannot escape past either end bale.

Constraints

Key idea

Sort bales. The "trapped" predicate is monotone in two senses, so for each inter-bale gap (pi, pi+1) the trapped sub-interval is a contiguous segment — binary search its boundaries. The challenge is making the per-position simulation fast. The classic trick is to process the bales in increasing size order while maintaining a doubly linked list of still-unbroken bales. When you process bale b of size s, every position in the open gap to its left or right where the runway is > s lets Bessie smash b — link it out. After all bales are processed (or once b is large enough that no runway suffices), the surviving "wall" structure tells you, for each gap, the trapped length.

An equivalent, slightly cleaner formulation: stack-based scan twice (left-to-right and right-to-left) computing, for each gap, the farthest a particle starting at every x can travel — using monotonic stacks of (position, size) bales. Per-side O(N log N) with binary search inside the stack; total O(N log N).

Complexity target

O(N log N).

Reference solution (C++)

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

int N;
vector<ll> pos, sz;

// Given Bessie starts at real x in gap i (between bale i and i+1),
// can she escape RIGHT past bale N-1?  Simulate with a pointer + stack.
// We do this twice with the same routine, mirrored.
bool escapeRight(int gap, ll x) {
    int i = gap + 1; ll p = x;
    while (i < N) {
        ll D = pos[i] - p;
        if (D > sz[i]) { p = pos[i]; i++; } else return false;
    }
    return true;
}
bool escapeLeft(int gap, ll x) {
    int i = gap; ll p = x;
    while (i >= 0) {
        ll D = p - pos[i];
        if (D > sz[i]) { p = pos[i]; i--; } else return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    vector<pair<ll,ll>> b(N);              // (pos, size)
    for (int i = 0; i < N; ++i) cin >> b[i].second >> b[i].first;
    sort(b.begin(), b.end());
    pos.resize(N); sz.resize(N);
    for (int i = 0; i < N; ++i) { pos[i] = b[i].first; sz[i] = b[i].second; }

    ll total = 0;
    for (int i = 0; i + 1 < N; ++i) {
        ll lo = pos[i] + 1, hi = pos[i+1] - 1;
        if (lo > hi) continue;
        // escapeRight is easier when x is small -> predicate "true at lo, false at hi"
        // is monotone decreasing in x? Larger x => smaller right-runway => harder to escape right.
        // So escapeRight is monotone: true for x in [lo, hiR], false above.
        // Binary search hiR.
        ll hiR = lo - 1;
        {
            ll l = lo, r = hi;
            while (l <= r) {
                ll m = l + (r - l) / 2;
                if (escapeRight(i, m)) { hiR = m; l = m + 1; } else r = m - 1;
            }
        }
        // escapeLeft monotone increasing in x: false below loL, true above.
        ll loL = hi + 1;
        {
            ll l = lo, r = hi;
            while (l <= r) {
                ll m = l + (r - l) / 2;
                if (escapeLeft(i, m)) { loL = m; r = m - 1; } else l = m + 1;
            }
        }
        // Trapped: x where neither side works => x in (hiR, loL).
        ll tlo = hiR + 1, thi = loL - 1;
        if (tlo <= thi) total += thi - tlo + 1;
    }
    cout << total << "\n";
}

The above is O(N² log N) worst case (each binary search does O(N) work). It passes when most gaps binary-search quickly. For a full O(N log N) bound, replace escapeRight/Left with a precomputed sparse table answering "starting at p in gap i, how far right can I get?" via repeated doubling on a "next blocking bale" function (the standard editorial approach).

Pitfalls

What Gold 2015 US Open was actually testing