Chapter 4.2: Greedy in USACO

USACO problems that yield to greedy solutions are some of the most satisfying to solve — once you see the insight, the code practically writes itself. This chapter walks through several USACO-style problems where greedy is the key.

4.2.1 Pattern Recognition: Is It Greedy?

Before coding, ask yourself:

1. Can I sort the input in some clever way?
2. Is there a "natural" order to process elements that always leads to the best result?
3. Can I argue that taking the "obvious best" at each step never hurts?

If yes to any of these, try greedy. If your greedy fails a test case, reconsider — maybe it's actually a DP problem.

4.2.2 USACO Bronze: Cow Sorting

Problem: N cows in a line. Each cow has a "grumpiness" value g[i]. To sort them in increasing order, you can swap two adjacent cows, but you pay g[i] + g[j] for swapping cows i and j. Minimize total cost.

Key Insight: With adjacent swaps, each inversion (pair (i, j) where i < j but g[i] > g[j]) requires exactly one swap. The total cost is the sum of (g[i] + g[j]) over all inversions. There is no freedom to reduce this — every inversion pair must be swapped exactly once, and any ordering of swaps gives the same total cost.

⚠️ Common Misconception: The formula sumG + (n-2) × minG is NOT the correct answer for general Cow Sorting. That expression only coincidentally equals the answer in edge cases (e.g., n=2). The correct cost is always the sum over all inversions.

Counting inversions in O(N²):

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> g(n);
    for (long long &x : g) cin >> x;

    // Total cost = sum of (g[i] + g[j]) for every inversion pair i < j where g[i] > g[j]
    // Equivalently: for each element g[i], add g[i] * (# elements it must "cross"):
    //   (# elements to its left that are > g[i]) + (# elements to its right that are < g[i])
    // Both counts together = total inversions involving g[i].

    long long totalCost = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i] > g[j]) {
                totalCost += g[i] + g[j];  // this inversion costs g[i]+g[j]
            }
        }
    }

    cout << totalCost << "\n";
    return 0;
}
// Time: O(N²) — for N ≤ 10^5 use merge-sort inversion count (O(N log N))

Example:

Input: g = [3, 1, 2]
Inversions: (3,1) → cost 4; (3,2) → cost 5
Total: 9

Verification: Bubble sort on [3,1,2]:

• Swap(3,1) = cost 4 → [1,3,2]
• Swap(3,2) = cost 5 → [1,2,3]
• Total = 9 ✓

4.2.3 USACO Bronze: The Cow Signal (Greedy Simulation)

Many USACO Bronze problems are pure simulation with a greedy twist: process events in time order and maintain the optimal state.

Problem: N cows each leave the barn at time t[i] and must reach the pasture. The barn-pasture road has capacity C (at most C cows at once). Cows travel instantaneously but must wait if capacity is full. What is the time when the last cow arrives?

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, c;
    cin >> n >> c;

    vector<int> t(n);
    for (int &x : t) cin >> x;
    sort(t.begin(), t.end());  // process cows in order of departure time

    int ans = 0;
    // Process in groups of c
    for (int i = 0; i < n; i += c) {
        // Group starts at t[i] (the earliest cow in this batch)
        // But batch can't start before previous batch finished
        ans = max(ans, t[i]);  // this batch must start at least when earliest cow is ready
        ans++;  // takes 1 time unit
    }

    cout << ans << "\n";
    return 0;
}

4.2.4 USACO Silver: Paired Up

Problem: N cows in two groups (group A and B). Each cow in A must be paired with one in group B. Pairing cow with value a with cow with value b gives profit f(a, b). Maximize total profit.

For specific profit functions, greedy sorting works. The classic version: profit = min(a, b), maximize sum.

Greedy: Sort both groups. Pair the largest A with the largest B, etc.

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

int main() {
    int n;
    cin >> n;

    vector<int> A(n), B(n);
    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += min(A[i], B[i]);  // pair i-th smallest with i-th smallest
    }

    cout << total << "\n";
    return 0;
}

This works because if you pair (a_large, b_small) instead of (a_large, b_large) and (a_small, b_small), you get min(a_large, b_small) + min(a_small, b_small) ≤ min(a_large, b_large) + min(a_small, b_small). Always match sorted order.

4.2.5 USACO Silver: Convention

Problem (USACO 2018 February Silver): N cows arrive at times t[1..N] at a bus stop. There are M buses, each holding C cows. A bus departs when full or at a scheduled time. Assign cows to buses to minimize the maximum waiting time for any cow.

Approach: Binary search on the answer + greedy check.

This is a "binary search on the answer with greedy verification" problem:

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

int n, m, c;
vector<long long> cows;   // sorted arrival times

// Can we schedule all cows with max wait <= maxWait?
bool canDo(long long maxWait) {
    int busesUsed = 0;
    int i = 0;  // current cow index

    while (i < n) {
        busesUsed++;
        if (busesUsed > m) return false;  // ran out of buses

        // This bus serves cows starting from cow i
        // The bus must depart by cows[i] + maxWait
        long long depart = cows[i] + maxWait;

        // Fill bus with as many cows as possible (capacity c, all with arrival <= depart)
        int count = 0;
        while (i < n && count < c && cows[i] <= depart) {
            i++;
            count++;
        }
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> c;
    cows.resize(n);
    for (long long &x : cows) cin >> x;
    sort(cows.begin(), cows.end());

    // Binary search on the maximum wait time
    long long lo = 0, hi = 1e14;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }

    cout << lo << "\n";
    return 0;
}

4.2.6 USACO Bronze: Herding (Greedy Observation)

Problem: 3 cows at positions a, b, c on a number line. In one move, you can move any cow to any empty position. Find the minimum moves to get all 3 cows into consecutive positions.

Insight: 2 moves are always sufficient (you can move the outer two to surround the middle). Can 1 move work? Can 0 work? Check these cases.

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    // Make sure a <= b <= c
    long long pos[3] = {a, b, c};
    sort(pos, pos + 3);
    a = pos[0]; b = pos[1]; c = pos[2];

    // 0 moves: already consecutive
    if (c - a == 2) { cout << 0; return 0; }

    // 1 move: check if moving one cow can make them consecutive
    // Options:
    // - Move a to b+1 or b-1 (if that makes 3 consecutive with c)
    // - Move c to b-1 or b+1 (if that makes 3 consecutive with a)
    // - Move b to somewhere

    // Case: after moving a, we have {b, b+1, b+2} or similar
    bool one_move = false;
    // Move a: can {b, c} be made consecutive with a new position?
    // Need b and c to differ by 1: c - b == 1 (then a → b-1 or c+1)
    if (c - b == 1) one_move = true;
    // Or c - b == 2: then a → b+1 fills the gap
    if (c - b == 2) one_move = true;

    // Move c symmetrically
    if (b - a == 1) one_move = true;
    if (b - a == 2) one_move = true;

    // Move b:
    // After moving b, we have {a, c} and new position x
    // Need {a, x, c} consecutive: x = a+1, c = a+2
    if (c - a == 2) one_move = true;  // already handled above
    // Or put b adjacent to a or c
    if (a + 1 == c - 1 && a + 1 != b) one_move = true; // if a+1 == c-1 means c-a=2 already...

    // Simpler approach: just try all possible "target" consecutive triples
    // The cows need to end up at some {x, x+1, x+2}
    // In 1 move: one cow is already at its target, two others might need to move... wait, exactly 1 cow moves
    // So two cows stay put and one moves. Check all combos.
    // Pairs that stay: (a,b), (a,c), (b,c)

    // Pair (b, c) stays: a moves. Consecutive triple containing b and c:
    // {b-2, b-1, b} with c = b (c!=b), {b-1, b, b+1} with c = b+1, {b, b+1, b+2} with c = b+2
    if (c - b == 1 || c - b == 2) one_move = true;
    // Pair (a, b) stays: c moves.
    if (b - a == 1 || b - a == 2) one_move = true;
    // Pair (a, c) stays: b moves. We need {a, x, c} consecutive.
    // c - a == 2 → already checked. c - a == 3: put b at a+1 or c-1.
    if (c - a == 3) one_move = true;

    if (one_move) { cout << 1; return 0; }

    cout << 2;
    return 0;
}

4.2.7 Common Greedy Patterns in USACO

Chapter Summary

📌 Key Takeaways

Greedy algorithms in USACO often involve:

1. Sorting the input in a clever order
2. Scanning once (or twice) with a simple update rule
3. Occasionally combining with binary search on the answer

❓ FAQ

Q1: What is the template for "binary search on answer + greedy check"?

A: Outer layer: binary search on answer X (lo=min possible, hi=max possible). Inner layer: write a check(X) function that uses a greedy strategy to verify whether X is feasible. Adjust lo/hi based on the result. The key requirement is that check must be monotone (if X is feasible, so is X+1, or vice versa).

Q2: How are USACO greedy problems different from LeetCode greedy problems?

A: USACO greedy problems typically require proving correctness (exchange argument) and are often combined with binary search and sorting. LeetCode tends to focus on simpler "always pick max/min" greedy. USACO Silver greedy problems are noticeably harder than LeetCode Medium.

Q3: When should I use priority_queue to assist greedy?

A: When you repeatedly need to extract the "current best" element (e.g., Huffman coding, minimum meeting rooms, repeatedly picking max/min values). priority_queue reduces "find the best" from O(N) to O(log N).

🔗 Connections to Other Chapters

• Chapter 4.1 covered the theory of greedy and exchange arguments; this chapter applies them to real USACO problems
• Chapter 3.3 (Binary Search) introduced the "binary search on answer" pattern used directly in the Convention problem here
• Chapter 7.1 (Understanding USACO) and Chapter 7.2 (Problem-Solving Strategies) will further discuss how to recognize greedy vs DP in contests
• Chapter 3.1 (STL) introduced priority_queue, which appears frequently in greedy simulations in this chapter

Practice Problems

Problem 4.2.1 — USACO 2016 December Bronze: Counting Haybales N haybales at positions on a number line. Q queries: how many haybales are in [L, R]? (Prefix sums, but practice the sorting mindset)

Problem 4.2.2 — USACO 2019 February Bronze: Sleepy Cow Sorting N cows labeled 1 to N (not in order). Move cows to sort them. Each move takes one cow from the end and inserts it somewhere. Minimum moves? (Greedy: find the longest already-sorted suffix)

Problem 4.2.3 — Task Scheduler N tasks labeled A–Z. Must wait k steps between two instances of the same task. Minimum time to complete all tasks? (Greedy: always schedule the most frequent remaining task)

Problem 4.2.4 — USACO 2018 February Silver: Convention II Cows arrive at a watering hole with arrival times and drink durations. The most senior waiting cow goes next. Simulate and find the maximum wait time. (Greedy simulation with priority queue)

Problem 4.2.5 — Weighted Job Scheduling N jobs with start, end, and profit. Select non-overlapping jobs to maximize total profit. (This one requires DP, NOT greedy — a good lesson in when greedy fails!)