Part 8: USACO Gold Topics
π Prerequisites: Before starting Part 8, you should be comfortable with everything in Parts 2β7, especially:
- Graph algorithms: BFS/DFS, Dijkstra, Bellman-Ford, Union-Find (Chapters 5.1β5.4)
- Dynamic programming: Memoization, tabulation, bitmask DP, interval DP (Chapters 6.1β6.3)
- Data structures: Segment trees, Fenwick trees, monotonic structures (Chapters 3.x)
USACO Gold is the level where problems stop having clear "apply algorithm X" patterns. You'll need to recognize which technique fits, combine multiple ideas, and implement them efficiently under contest pressure.
This part covers the five core categories that appear most frequently in USACO Gold problems.
π Chapter Overview
| Chapter | Topic | Key Techniques | Difficulty |
|---|---|---|---|
| Ch.8.1: Minimum Spanning Tree | Connect all nodes with minimum total edge weight | Kruskal (DSU), Prim (priority queue), MST properties, Kruskal-style greedy | π‘ Medium |
| Ch.8.2: Topological Sort & DAG DP | Ordering in directed acyclic graphs; DP on DAGs; SCC | Kahn's algorithm, DFS-based toposort, longest path, Tarjan/Kosaraju SCC, condensation DAG, 2-SAT, difference constraints | π΄ Hard |
| Ch.8.3: Tree DP & Rerooting | DP on trees; handling all roots efficiently; tree knapsack | Subtree DP, rerooting technique (sum+max), diameter, tree knapsack O(NW) | π΄ Hard |
| Ch.8.4: Euler Tour & Flattening | Flatten a tree into an array for range queries | Euler tour, DFS in/out times, LCA via binary lifting, path queries | π΄ Hard |
| Ch.8.5: Combinatorics & Number Theory | Counting, modular arithmetic, number properties | nCr mod p, fast power, inclusion-exclusion, sieve, Euler's Ο function, Chinese Remainder Theorem | π΄ Hard |
πΊοΈ Dependency Graph
Part 5 (Graphs) βββββββββββββββββββΊ Ch.8.1 MST
β
ββββΊ Ch.8.2 Topo Sort & DAG DP
β
Part 5.3 (Trees) ββββββββββββββββββΊ Ch.8.3 Tree DP & Rerooting
β
ββββΊ Ch.8.4 Euler Tour & LCA
β
Part 2 (Math) + Ch.3.x (DS) βββββββΊ Ch.8.5 Combinatorics & Number Theory
π― What Makes Gold Different from Silver?
At Silver, most problems map to one technique: "this is a BFS problem," "this is a prefix sum problem."
At Gold, the challenge is:
- Recognition β figuring out which technique applies, often obscured by the problem statement
- Composition β combining two or more techniques (e.g., DSU + sorting for MST, or Euler tour + BIT for tree queries)
- Efficiency β the same idea that works in O(NΒ²) for Silver needs to be O(N log N) for Gold
- Proof β Gold problems often require verifying that your greedy choice is correct before coding
π‘ Gold Strategy: For each Gold problem, ask yourself:
- Is there a graph structure? β Think MST, shortest path, topo sort
- Is there a tree? β Think tree DP, rerooting, Euler tour + data structure
- Is the answer a count? β Think combinatorics, DP with counting states
- Can I sort and greedily pick? β Think Kruskal-style greedy
π USACO Gold Problem Distribution
Based on recent USACO contests, here's roughly how often each topic appears:
| Topic | Frequency | Notes |
|---|---|---|
| Graph algorithms (MST, shortest path, DSU) | ~30% | Almost every contest has one |
| DP (tree DP, bitmask, interval) | ~35% | Most common single topic |
| Data structures (segment tree, BIT, ordered set) | ~20% | Often combined with other topics |
| Combinatorics / math | ~10% | Usually appears in January contest |
| Ad hoc / constructive | ~5% | Hard to prepare for directly |
π How This Part Connects to Platinum
After Gold, USACO Platinum introduces:
- Segment tree beats and Li Chao trees (advanced data structures)
- Centroid decomposition (tree algorithms)
- Suffix arrays (string algorithms)
- Max flow / min cut (network flow)
Everything in Part 8 is a prerequisite for Platinum. Euler tour (Ch.8.4) is particularly important β it appears in nearly every Platinum tree problem.