USACO Platinum course is for students who have advanced programming background and compete in USACO Platinum division. The goal is when the student finishes the course, the student will be comfortable in solving USACO Platinum division contest problems and improve their chance to qualify the USACO training camp.
PREREQUISITES:
At least one of the following requirements has to be satisfied:
- USACO Platinum level contestant
- The students should already have mastered at least 60% of the following gold level topics
- Graph: topological sort
- Graph: cycle detection
- Graph: Euler path
- Graph: Shortest Paths (Dijkstra, Bellman-Ford, Floyd Warshall)
- Graph: union find
- Graph: minimum Spanning Tree (Kruskal, Prim)
- DP basics
- DP on tree/DAG
- Digit DP
- Bitmask DP
- Binary/Ternary Search
- Merging Sets
- Geometry: Line Segment Intersection
- Geometry: Point in Polygon
- Geometry: Sweep Line
- Geometry: Convex Hull
- String: Hashing
- String: Miller-Rabin
- String: KMP
- String: Z algorithm
- Prefix Sums
- Fenwick Tree
- Segment Tree: basic
- Segment Tree: Lazy Propagation
- 2-D Segment Tree
- Binary lifting and Sparse Table
- Square Root Decomposition and Mo’s Algorithm
- Lowest Common Ancestor
| Lesson 1 | Review of Gold Topics |
| Lesson 2 | Advanced Data Structures Multi-dimensional segment trees Mo’s algorithm Treaps |
| Lesson 3 | Trees Heavy Light Decomposition Centroid Decomposition |
| Lesson 4 | Strings Suffix and LCP array |
| Lesson 5 | Advanced Dynamic Programming Common problems and techniques |
| Lesson 6 | Dynamic Programming Optimizations 1 |
| Lesson 7 | Dynamic Programming Optimizations 2 |
| Lesson 8 | Strongly Connected Components |
| Lesson 9 | Max Flow |
| Lesson 10 | Miscellaneous Number Theory Interactive problems Randomized algorithms |