U USACO Prep

USACO 2018 US Open · Bronze · all three problems

← Full US Open 2018 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=open18results. 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 — Team Tic Tac Toe

Statement

The barn's 3×3 tic-tac-toe board is fully filled — each cell holds a single uppercase letter A–Z, the initial of the cow that claimed it. Count two things:

  1. The number of single cows who win a row, column, or diagonal (all three cells share that cow's letter).
  2. The number of unordered pairs of distinct cows {X, Y} that together win some row, column, or diagonal — i.e. every cell of that line is either X or Y, and both letters appear in it.

Constraints

Key idea

There are exactly 8 winning lines (3 rows + 3 cols + 2 diagonals). For each line, collect the set of distinct letters appearing in it. If the set has size 1, that cow wins solo. If the set has size 2, that unordered pair wins as a team. Dedupe across lines using a std::set of letters and a std::set of pairs.

Complexity target

O(1). It's 8 lines × 3 cells.

Reference solution (C++)

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

int main() {
    vector<string> g(3);
    for (auto& r : g) cin >> r;

    // Eight winning lines as triples of (row, col).
    vector<array<pair<int,int>,3>> lines = {
        {{{0,0},{0,1},{0,2}}}, {{{1,0},{1,1},{1,2}}}, {{{2,0},{2,1},{2,2}}},
        {{{0,0},{1,0},{2,0}}}, {{{0,1},{1,1},{2,1}}}, {{{0,2},{1,2},{2,2}}},
        {{{0,0},{1,1},{2,2}}}, {{{0,2},{1,1},{2,0}}},
    };

    set<char> solo;
    set<pair<char,char>> team; // ordered pair (min,max) to dedupe

    for (auto& ln : lines) {
        set<char> s;
        for (auto [r, c] : ln) s.insert(g[r][c]);
        if (s.size() == 1) solo.insert(*s.begin());
        else if (s.size() == 2) {
            auto it = s.begin();
            char a = *it++; char b = *it;
            team.insert({min(a, b), max(a, b)});
        }
    }
    cout << solo.size() << "\n" << team.size() << "\n";
}

Pitfalls

Problem 2 — Milking Order

Statement

There are N cows numbered 1..N. Farmer John has observed a fixed hierarchy among M of them — a sequence h1, h2, ..., hM that must appear in that relative order in the final milking order (not necessarily contiguous). Additionally, K cows have hard-coded positions: cow cj must occupy slot pj. Output the smallest slot that cow 1 can occupy in any milking order satisfying both kinds of constraints. A valid order is guaranteed to exist.

Constraints

Key idea

N is tiny. Just try each slot s = 1..N in order: place cow 1 at slot s, honor all fixed-position assignments, then greedily fill the remaining slots left-to-right with the lowest hierarchy cow whose preceding hierarchy cows have already been placed. If the hierarchy can be threaded through the free slots in order while respecting cow 1's pinned position, s is feasible. Output the first such s.

Concretely: scan slots 1..N. At each free slot, if the next undelivered hierarchy cow is allowed here (not blocked by a pin), place it. Mark cow 1's slot as forbidden for the hierarchy unless cow 1 is the next hierarchy cow.

Complexity target

O(N²) trials in the worst case — fine for N ≤ 100.

Reference solution (C++)

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

int N, M, K;
vector<int> H;            // hierarchy sequence, 1-indexed cow ids
map<int,int> pin;          // slot -> cow (hard placements)
map<int,int> pinCow;       // cow -> slot

bool feasible(int slotForOne) {
    // Build slot assignments: pinned cows + cow 1 at slotForOne.
    vector<int> slot(N + 2, 0); // slot[i] = cow at slot i, 0 = empty
    for (auto [s, c] : pin) slot[s] = c;
    if (slot[slotForOne] != 0 && slot[slotForOne] != 1) return false;
    slot[slotForOne] = 1;

    // Sweep left-to-right; thread the hierarchy H through the empty slots.
    int hi = 0; // next hierarchy index to place
    for (int s = 1; s <= N; ++s) {
        if (slot[s] != 0) {
            // A pinned cow (or cow 1) sits here. If it's the next hierarchy cow, advance.
            if (hi < (int)H.size() && slot[s] == H[hi]) ++hi;
            continue;
        }
        // Empty slot: if the next hierarchy cow has no other pinned slot, drop it here.
        if (hi < (int)H.size()) {
            int c = H[hi];
            if (pinCow.count(c)) return false; // hierarchy cow is pinned elsewhere
            if (c == 1) return false;          // cow 1 must be at slotForOne, not here
            ++hi;
        }
    }
    return hi == (int)H.size();
}

int main() {
    cin >> N >> M >> K;
    H.assign(M, 0);
    for (auto& x : H) cin >> x;
    for (int i = 0; i < K; ++i) {
        int c, p; cin >> c >> p;
        pin[p] = c; pinCow[c] = p;
    }
    // If cow 1 is pinned, that's the only feasible slot.
    if (pinCow.count(1)) { cout << pinCow[1] << "\n"; return 0; }
    for (int s = 1; s <= N; ++s) if (feasible(s)) { cout << s << "\n"; return 0; }
}

Pitfalls

Problem 3 — Family Tree

Statement

There are N mother-child pairs forming a family tree (each cow has at most one mother in the input). Given two query cows X and Y, classify their relationship as one of:

Constraints

Key idea

Tiny N — just walk up the chain. For each cow store its mother (or none). For the query (X, Y), compute the list of ancestors of each (including self at depth 0). Find the lowest common ancestor by intersecting: walk from X collecting depths, then walk from Y looking for the first match. Let dX, dY be the depths from the LCA. Then:

Complexity target

O(N) per query — read N pairs, two walks up the tree.

Reference solution (C++)

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

map<string, string> mom; // child -> mother

// Return list of (ancestor, depth) starting from x (depth 0) walking up.
vector<pair<string,int>> chain(const string& x) {
    vector<pair<string,int>> r;
    string cur = x; int d = 0;
    while (true) { r.push_back({cur, d}); if (!mom.count(cur)) break; cur = mom[cur]; ++d; }
    return r;
}

int main() {
    int N; string X, Y; cin >> N >> X >> Y;
    for (int i = 0; i < N; ++i) { string m, c; cin >> m >> c; mom[c] = m; }

    auto cx = chain(X), cy = chain(Y);
    map<string,int> depthInX;
    for (auto& [a, d] : cx) depthInX[a] = d;

    // Find LCA: first ancestor of Y also present in X's chain.
    int dY = -1, dX = -1; string lca;
    for (auto& [a, d] : cy) if (depthInX.count(a)) { lca = a; dY = d; dX = depthInX[a]; break; }
    if (dY == -1) { cout << "NOT RELATED\n"; return 0; }

    if (dX == 0 && dY == 0) { cout << "SIBLINGS\n"; return 0; } // X == Y; problem usually rules this out
    if (dX == 0) {
        // X is ancestor of Y at depth dY.
        if (dY == 1) cout << X << " is the mother of " << Y << "\n";
        else { cout << X << " is the "; for (int i = 0; i < dY - 2; ++i) cout << "great-"; cout << "grand-mother of " << Y << "\n"; }
        return 0;
    }
    if (dY == 0) {
        if (dX == 1) cout << Y << " is the mother of " << X << "\n";
        else { cout << Y << " is the "; for (int i = 0; i < dX - 2; ++i) cout << "great-"; cout << "grand-mother of " << X << "\n"; }
        return 0;
    }
    if (dX == dY) { cout << (dX == 1 ? "SIBLINGS" : "COUSINS") << "\n"; return 0; }
    // Aunt case: smaller depth side is the aunt.
    const string& aunt  = (dX < dY) ? X : Y;
    const string& niece = (dX < dY) ? Y : X;
    int da = min(dX, dY);
    if (da == 1) cout << aunt << " is the aunt of " << niece << "\n";
    else { cout << aunt << " is the "; for (int i = 0; i < da - 1; ++i) cout << "great-"; cout << "aunt of " << niece << "\n"; }
}

Pitfalls

What Bronze US Open 2018 was actually testing