U USACO Prep

2024 US Open · Bronze

← Back to 2024 US Open · Official results page

Three Bronze problems, 5 hours combined. The flavor this round was unusually heavy on case analysis — Bronze 1 wants careful parsing of boolean expressions, Bronze 2 wants a clean geometry walk, and Bronze 3 is a classic reconstruct-the-permutation puzzle that punishes off-by-one errors.

Paraphrase warning. Statements here are summarized for my notes. Read the official problem on usaco.org before coding. Each problem links to the canonical statement.

B1 · Logical Moos

Official statement (cpid=1419)

Statement (paraphrase)

You're given a boolean expression of length N (odd) where tokens alternate between values (true/false) and operators (AND/OR), with AND binding tighter than OR. For each of Q queries (l, r, v), decide whether replacing the subarray [l..r] with the single boolean v makes the whole expression evaluate to true. Queries are independent.

Constraints

Key idea

Split the expression by OR into "AND-blocks." The whole expression is true iff at least one AND-block evaluates to true (every value in it is true). Precompute, for each AND-block, whether it is currently true. A query [l, r] affects at most a contiguous range of AND-blocks: the one containing l, the one containing r, and every block strictly between them is "consumed" into the replacement. So pre-compute "is any AND-block outside [L_block, R_block] already true?" with prefix/suffix OR arrays. Then check the residual left fragment, the residual right fragment, and the inserted value v.

Complexity

O(N + Q) after one linear preprocess. Each query is O(1) after locating the affected block range with the precomputed token → block index map.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<string> tok(N);
    for (auto &t : tok) cin >> t;

    // Split into AND-blocks by OR. block_id[i] = which block token i belongs to.
    vector<int> block_id(N), block_l, block_r;
    int b = 0;
    block_l.push_back(0);
    for (int i = 0; i < N; i++) {
        block_id[i] = b;
        if (tok[i] == "OR") {
            block_r.push_back(i - 1);
            b++;
            block_l.push_back(i + 1);
            block_id[i] = -1; // separator
        }
    }
    block_r.push_back(N - 1);
    int B = (int)block_l.size();

    // val[b] = AND of all values in block b (operators ignored).
    vector<int> val(B, 1);
    for (int j = 0; j < B; j++)
        for (int i = block_l[j]; i <= block_r[j]; i += 2)
            if (tok[i] == "false") val[j] = 0;

    // Prefix/suffix OR of val[].
    vector<int> pre(B + 2, 0), suf(B + 2, 0);
    for (int j = 0; j < B; j++) pre[j + 1] = pre[j] | val[j];
    for (int j = B - 1; j >= 0; j--) suf[j] = suf[j + 1] | val[j];

    // Per-block prefix AND of value tokens, by token index within block.
    // To answer "is left fragment [block_l[B_l], l-1] all-true?" we use a prefix
    // "has-false up to index i" array.
    vector<int> bad_pref(N + 1, 0);
    for (int i = 0; i < N; i++)
        bad_pref[i + 1] = bad_pref[i] + (i % 2 == 0 && tok[i] == "false");

    string out;
    out.reserve(Q);
    while (Q--) {
        int l, r;
        string vs;
        cin >> l >> r >> vs;
        --l; --r;
        int v = (vs == "true");

        // Find affected block range.
        // Slide l rightward to skip OR token if l lands on one.
        int Bl = (tok[l] == "OR") ? block_id[l - 1] + 1 : block_id[l];
        int Br = (tok[r] == "OR") ? block_id[r + 1] - 1 : block_id[r];
        // Outside blocks contribute their OR.
        int outside = pre[Bl] | suf[Br + 1];
        if (outside) { out += 'Y'; continue; }

        // Inner: left residual (block_l[Bl] .. l-1), value v, right residual (r+1 .. block_r[Br]).
        // The merged block evaluates true iff (left all-true) AND v AND (right all-true).
        int left_l = block_l[Bl], right_r = block_r[Br];
        bool left_ok = (bad_pref[l] - bad_pref[left_l] == 0);
        bool right_ok = (bad_pref[right_r + 1] - bad_pref[r + 1] == 0);
        out += (left_ok && v && right_ok) ? 'Y' : 'N';
    }
    cout << out << "\n";
}

Pitfalls

B2 · Walking Along a Fence

Official statement (cpid=1420)

Statement (paraphrase)

A simple rectilinear closed polygon has P posts (vertices). N cows each give a start and end point that lie on the fence (on some edge between consecutive posts). Each cow walks along the fence and takes the shorter of the two possible directions. Output the distance each cow walks.

Constraints

Key idea

Parameterize the fence by arc length: walk the polygon once and assign each post a cumulative perimeter offset. For any query point on edge (i, i+1), compute its offset as offset[i] + distance from post i. The two possible walks have length |a − b| and perimeter − |a − b|; answer is the min.

Complexity

O(P + N · log P). For each query we binary-search which edge the point lies on (or do O(P) per query for full credit, since N·P ≤ 2·10¹⁰ — actually too slow, so use binary search by sorted edge ranges in x or y).

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, P;
    cin >> N >> P;
    vector<int> px(P), py(P);
    for (int i = 0; i < P; i++) cin >> px[i] >> py[i];

    // Cumulative arc length at each post (closed polygon, edge i -> i+1 mod P).
    vector<long long> arc(P + 1, 0);
    auto edgeLen = [&](int i) {
        int j = (i + 1) % P;
        return (long long)(abs(px[i] - px[j]) + abs(py[i] - py[j]));
    };
    for (int i = 0; i < P; i++) arc[i + 1] = arc[i] + edgeLen(i);
    long long peri = arc[P];

    // Given a point (x,y) on the fence, find its arc offset.
    auto offsetOf = [&](int x, int y) -> long long {
        for (int i = 0; i < P; i++) {
            int j = (i + 1) % P;
            int x1 = px[i], y1 = py[i], x2 = px[j], y2 = py[j];
            // axis-aligned: either x1==x2 or y1==y2.
            if (x1 == x2 && x == x1 &&
                min(y1, y2) <= y && y <= max(y1, y2))
                return arc[i] + abs(y - y1);
            if (y1 == y2 && y == y1 &&
                min(x1, x2) <= x && x <= max(x1, x2))
                return arc[i] + abs(x - x1);
        }
        return -1; // unreachable per problem
    };

    while (N--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        long long a = offsetOf(x1, y1), b = offsetOf(x2, y2);
        long long d = llabs(a - b);
        cout << min(d, peri - d) << "\n";
    }
}

Pitfalls

B3 · Farmer John's Favorite Permutation

Official statement (cpid=1421)

Statement (paraphrase)

Start with an unknown permutation of 1..N in a deque. Repeatedly: compare the front and back; if front < back, pop the front and write down what is now the new front; otherwise pop the back and write down the new back. You're given the N−1 written values; reconstruct the lexicographically smallest permutation that could produce them, or print −1.

Constraints

Key idea

Process the hints from last to first, reconstructing the deque in reverse. The final deque has 1 element; at each reverse step we know which end (front or back) gained an element and what value is now adjacent. Maintain "what was the front" and "what was the back" as we grow the deque outward. Use the lex-smallest choice when the missing value is ambiguous.

Complexity

O(N) per test case using a deque and a "used value" boolean array.

Reference C++

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

void solve() {
    int N;
    cin >> N;
    vector<int> h(N - 1);
    for (auto &x : h) cin >> x;

    // Reverse-simulate. After the last operation the deque is [h[N-2]] (the last written value).
    // Walk hints right to left: each hint h[i] was the "new neighbor" after a pop.
    // We don't know the popped value, but we know it must be the larger end (if it was
    // a front pop, popped < old_back; etc.). Track candidates and pick lex-smallest assignment.

    deque<int> dq;
    vector<char> used(N + 2, 0);

    dq.push_back(h[N - 2]);
    used[h[N - 2]] = 1;

    // Greedy: at reverse step i (going N-3 .. 0), we must prepend or append a value.
    // The current front and back of dq are known. The new value must satisfy:
    //   - if front comparison made the previous pop happen from front: new_front > current_front
    //   - if from back: new_back > current_back
    // and after the pop, the hint we wrote becomes the new neighbor.
    // The deterministic rule: the LARGER of the new front and new back is what was popped.
    // Pick the smallest unused value satisfying constraints.

    for (int i = N - 3; i >= 0; i--) {
        int v = h[i]; // value that became visible at the relevant end after pop
        // v must already be present and adjacent to the popped end; if not, try inserting.
        bool placed = false;
        for (int cand = 1; cand <= N && !placed; cand++) {
            if (used[cand]) continue;
            // Try as new front: front becomes cand, then pop front -> new front is dq.front() which must equal v
            if (dq.front() == v && cand > dq.front()) {
                // popped element would be cand only if cand > dq.back() too? Actually the rule
                // (pop the larger end) means the popped end equals max(front,back). So cand
                // must equal max(cand, dq.back()) i.e. cand >= dq.back().
                if (cand >= dq.back()) { dq.push_front(cand); used[cand] = 1; placed = true; break; }
            }
            if (dq.back() == v && cand > dq.back()) {
                if (cand >= dq.front()) { dq.push_back(cand); used[cand] = 1; placed = true; break; }
            }
        }
        if (!placed) { cout << -1 << "\n"; return; }
    }
    // Fill remaining unused values; lex-smallest means place them at the back in ascending order.
    for (int v = 1; v <= N; v++) if (!used[v]) dq.push_back(v);

    for (size_t i = 0; i < dq.size(); i++) cout << dq[i] << " \n"[i + 1 == dq.size()];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}

Pitfalls