U USACO Prep

USACO 2021 US Open · Bronze · all three problems

← Full US Open 2021 set · Official results

Source. Statements and constraints are paraphrased from usaco.org/index.php?page=open21results. 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 — Acowdemia I

Subtasks

Statement

Bessie has N papers with citation counts ci. She is writing one survey article that can cite up to L of her own existing papers, adding +1 citation to each chosen paper (at most one +1 per paper). The h-index is the largest h such that at least h papers have at least h citations each. Maximize the final h-index.

Constraints

Key idea

Sort citations descending. For a candidate h-index value h, we need at least h papers with ≥ h citations. Papers already at ≥ h cost nothing; papers with exactly h−1 can be bumped to h with one survey citation (cost 1 each); papers with ≤ h−2 cannot be saved (a single +1 can't reach h). Binary-search or sweep h from high to low: feasible iff (papers with c ≥ h) + min(L, papers with c = h−1) ≥ h.

Complexity target

O(N log N) — sort once, then a single linear scan with two pointers tracking "≥ h" and "= h−1" counts.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, L; cin >> N >> L;
    vector<int> c(N);
    for (auto& x : c) cin >> x;
    sort(c.rbegin(), c.rend());        // descending

    // For each candidate h from N down to 0, check feasibility.
    // Papers 0..h-1 (the top h sorted) must each reach >= h.
    // Each of those can be raised by at most 1 (one survey citation).
    // So feasibility = (# of top-h papers with c >= h - 1) == h AND
    //                  (# of top-h papers with c < h, i.e. = h-1) <= L.
    for (int h = N; h >= 0; --h) {
        if (h == 0) { cout << 0 << "\n"; return 0; }
        // top h papers are c[0..h-1] (descending)
        // The h-th paper (0-indexed c[h-1]) is the smallest of the top h.
        if (c[h - 1] >= h) { cout << h << "\n"; return 0; }
        // Otherwise count how many of c[0..h-1] equal h-1 — those need a bump.
        int need = 0;
        bool ok = true;
        for (int i = 0; i < h; ++i) {
            if (c[i] >= h) continue;
            if (c[i] == h - 1) ++need;
            else { ok = false; break; }    // gap > 1: unsalvageable
        }
        if (ok && need <= L) { cout << h << "\n"; return 0; }
    }
}

Pitfalls

Problem 2 — Acowdemia II

Subtasks

Statement

There are N lab members and K publications. In each paper, authors are listed in order of decreasing effort, with alphabetical tie-breaks. Senior members have less time and so cannot contribute strictly more effort than juniors — meaning if A appears before B in a paper and A < B alphabetically, that paper tells us nothing about A vs B's seniority; otherwise A contributed at least as much effort, hence A is junior-or-equal to B. For every pair of members, output whether one is definitively more senior, definitively more junior, or undetermined.

Constraints

Key idea

Build a directed graph: edge A → B means "A is definitely junior-or-equal to B" (A contributed at least as much effort somewhere). Scan each publication; for each adjacent pair (a, b) in the author list, if a appears before b and a is not alphabetically earlier than b (i.e. order is not the tie-break), then a is junior-or-equal to b. Take transitive closure (Floyd–Warshall on a boolean matrix), then for each pair (i, j) check the four cases.

Complexity target

O(N3) for Floyd–Warshall on N ≤ 100. K ≤ 100 papers contribute O(K · author_count) edges.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<string> name(N);
    map<string, int> id;
    for (int i = 0; i < N; ++i) { cin >> name[i]; id[name[i]] = i; }

    // junior[a][b] = true if a is definitely junior-or-equal to b (a contributed
    // at least as much effort, hence less senior). Transitive.
    vector<vector<bool>> jr(N, vector<bool>(N, false));

    for (int p = 0; p < K; ++p) {
        int m; cin >> m;
        vector<string> au(m);
        for (auto& s : au) cin >> s;
        for (int i = 0; i + 1 < m; ++i) {
            // a listed before b. Tie-break (equal effort) is alphabetical.
            // If au[i] < au[i+1] alphabetically, this could be the tie-break — no info.
            // Otherwise au[i] contributed strictly more, so au[i] is junior-or-equal to au[i+1].
            if (au[i] >= au[i + 1]) jr[id[au[i]]][id[au[i + 1]]] = true;
        }
    }

    // Floyd–Warshall transitive closure.
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i) if (jr[i][k])
            for (int j = 0; j < N; ++j) if (jr[k][j]) jr[i][j] = true;

    for (int i = 0; i < N; ++i) {
        string row;
        for (int j = 0; j < N; ++j) {
            if (i == j) row += 'B';
            else if (jr[i][j] && !jr[j][i]) row += '0';   // i junior, j senior
            else if (jr[j][i] && !jr[i][j]) row += '1';   // i senior
            else row += '?';
        }
        cout << row << "\n";
    }
}

Pitfalls

Problem 3 — Acowdemia III

Subtasks

Statement

An N × M pasture has cells of three types: 'C' (a cow), 'G' (grass), '.' (empty). Two cows can become friends if there is a grass cell orthogonally adjacent to both of them; meeting consumes that grass cell. Each grass cell can be used by at most one pair. Each cow can participate in many pairings (with different friends). Maximize the number of friend pairs.

Constraints

Key idea

For each grass cell, look at the up-to-4 orthogonal neighbors that are cows. That grass can pair any two of those cows — so it contributes at most 1 pair. Bronze-level: a grass cell with k cow-neighbors offers C(k, 2) candidate pairs but only one slot. The trick is two cows can share a friendship only through one grass cell, so it's: for each grass with ≥ 2 cow-neighbors, pick any one pair; greedy works because each grass is independent (different grass cells produce different pairs unless the same two cows happen to be co-adjacent to multiple grass cells — then we still only pair them once globally). Use a set of unordered (cow-id, cow-id) keys to count distinct pairings.

Complexity target

O(N · M) cells, each contributing O(1) work; total O(NM) ≈ 106.

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;

    // Assign each cow a unique id by (row, col) position.
    auto cid = [&](int r, int c) { return r * M + c; };
    int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

    // For each grass cell with >= 2 cow-neighbors, record the candidate pairs.
    // A pair (a,b) becomes "friends" if at least one grass cell is adjacent to both.
    // Each grass cell can serve at most one pair; but the same cow-pair could be
    // adjacent to multiple grass cells — we only count it once, and we use up only
    // ONE of those grass cells. So: for each pair, if any adjacent grass exists, +1.
    set<pair<int,int>> pairs;
    for (int r = 0; r < N; ++r)
      for (int c = 0; c < M; ++c) if (g[r][c] == 'G') {
        vector<int> nbrs;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            if (g[nr][nc] == 'C') nbrs.push_back(cid(nr, nc));
        }
        // Every pair of these cow-neighbors becomes a candidate friendship.
        for (size_t i = 0; i < nbrs.size(); ++i)
          for (size_t j = i + 1; j < nbrs.size(); ++j) {
              int a = nbrs[i], b = nbrs[j];
              if (a > b) swap(a, b);
              pairs.insert({a, b});
          }
      }
    cout << pairs.size() << "\n";
}

Pitfalls

What Bronze US Open 2021 was actually testing