USACO Silver Practice – 5 Coding Problems with Python Solutions

The USA Computing Olympiad (USACO) Silver division is the second level after Bronze, where students encounter more advanced algorithmic problems.
Silver requires knowledge of sorting, greedy scheduling, binary search, disjoint set union, prefix sums, and dynamic programming.
This post provides 5 practice problems with Python reference solutions to help students prepare effectively.

🐄 Problem 1 — Hay Bale Stacking (Prefix Sums)

Task: You’re given N barns in a row. Each of K operations adds 1 bale to every barn in a range [a, b]. After all operations, print the final bale count per barn.


Input:
N K
a1 b1
a2 b2
...
aK bK

Output:
N integers, bale counts per barn

Sample Input

Sample Output

1 2 2 1 1

Python Reference Solution


def hay_bale_stacking(N, operations):
    diff = [0]*(N+2)  # difference array
    for a, b in operations:
        diff[a] += 1
        diff[b+1] -= 1
    result = []
    curr = 0
    for i in range(1, N+1):
        curr += diff[i]
        result.append(curr)
    return result

# Example
print(hay_bale_stacking(5, [(1,2),(2,4),(3,5)]))  # [1, 2, 2, 1, 1]

🎬 Problem 2 — Movie Festival (Greedy Scheduling)

Task: Given start and end times of N movies, find the maximum number you can watch in full without overlap.


Input:
N
s1 e1
s2 e2
...
sN eN

Output:
Max number of movies

Sample Input

Sample Output

Python Reference Solution


def movie_festival(movies):
    movies.sort(key=lambda x: x[1])  # sort by end time
    count, last_end = 0, 0
    for start, end in movies:
        if start >= last_end:
            count += 1
            last_end = end
    return count

# Example
print(movie_festival([(3,5),(4,9),(5,8)]))  # 2

🏗️ Problem 3 — Road Construction (Graph Connectivity)

Task: You have N towns and M roads added one by one. After each addition, output the number of connected components.


Input:
N M
u1 v1
u2 v2
...
uM vM

Output:
M integers, number of components after each road

Sample Input

Sample Output

3
2
1

Python Reference Solution


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            if self.size[ra] < self.size[rb]:
                ra, rb = rb, ra
            self.parent[rb] = ra
            self.size[ra] += self.size[rb]
            self.components -= 1

def road_construction(N, roads):
    dsu = DSU(N)
    result = []
    for u,v in roads:
        dsu.union(u-1,v-1)  # 0-index
        result.append(dsu.components)
    return result

# Example
print(road_construction(4, [(1,2),(3,4),(2,3)]))  # [3,2,1]

🐄 Problem 4 — Aggressive Cows (Binary Search Placement)

Task: Place N cows in M stalls such that the minimum distance between any two cows is maximized.


Input:
N M
p1 p2 ... pM

Output:
Largest minimum distance

Sample Input

3 5
1 2 8 4 9

Sample Output

Python Reference Solution


def can_place(stalls, N, dist):
    count, last = 1, stalls[0]
    for pos in stalls[1:]:
        if pos - last >= dist:
            count += 1
            last = pos
    return count >= N

def aggressive_cows(N, stalls):
    stalls.sort()
    lo, hi = 1, stalls[-1] - stalls[0]
    ans = 0
    while lo <= hi:
        mid = (lo+hi)//2
        if can_place(stalls, N, mid):
            ans = mid
            lo = mid+1
        else:
            hi = mid-1
    return ans

# Example
print(aggressive_cows(3, [1,2,8,4,9]))  # 3

📈 Problem 5 — Longest Increasing Subsequence (DP)

Task: Find the length of the Longest Increasing Subsequence (LIS) in a given array.


Input:
N
a1 a2 ... aN

Output:
Length of LIS

Sample Input

6
10 9 2 5 3 7

Sample Output

Python Reference Solution


import bisect

def LIS(arr):
    sub = []
    for x in arr:
        i = bisect.bisect_left(sub, x)
        if i == len(sub):
            sub.append(x)
        else:
            sub[i] = x
    return len(sub)

# Example
print(LIS([10,9,2,5,3,7]))  # 3

✅ Answer Key (Summary)

Problem 1: Use difference array + prefix sum. → 1 2 2 1 1
Problem 2: Sort by end time, greedy selection. → 2
Problem 3: Use DSU (Union-Find). → 3 2 1
Problem 4: Binary search on distance with greedy placement. → 3
Problem 5: LIS with binary search (O(N log N)). → 3

These USACO Silver-level problems cover essential algorithmic ideas:
prefix sums, greedy scheduling, graph connectivity with DSU, binary search, and dynamic programming (LIS).
By practicing these, students can strengthen their coding skills and get ready to transition from Bronze → Silver.

Keep following TheCareergram.com for more practice papers in AMC (Math), Science Olympiad, and USACO contests with full solutions.

Share on Social Media