Hard Algorithms (USACO Gold Level)
Video Solutions for Gold Algorithms
Easy DP
| Algorithm | Example | Level |
|---|---|---|
| DP | Climbing Stairs | Easy |
| DP | Unique Paths II | Easy |
| DP | House Robber | Medium |
| DP | Marathon | Medium |
Backtrack
| Algorithm | Example | Level |
|---|---|---|
| Backtrack | Subsets | Medium |
| Backtrack | Permutation | Easy |
| Backtrack | Combination | Easy |
| Backtrack | Knights Tour | Easy |
| Backtrack | Hamiltonean Cycles | Easy |
| Backtrack | Palindrome Partitioning | Easy |
Subsequences (LIS, LCS)
| Algorithm | Example | Level |
|---|---|---|
| DP | Passing Notes | Medium |
| DP | LIS (Longest Increasing Sequence, N^2 Algorithm) | Medium |
| Binary Search | LIS (Longest Increasing Sequence, NLogN Algorithm) | Hard |
| LIS,DFS | Missile Defense System | Hard |
| DP | LCS (Longest Common Sequence) | Medium |
| LIS | Sister Cities | Medium |
| LIS | Chorus | Medium |
| LIS | Best Time to Buy and Sell Stock | Easy |
| Backtrack, LIS | Missile Defense System | Medium |
| LIS/LCS | LCIS(Longest Common Increasing Sequence) | Hard |
Monotonous Stack
| Algorithm | Example | Level |
|---|---|---|
| Monotonous Stack | Stock Spanner | Easy |
Knapsack DP
| Algorithm | Example | Level |
|---|---|---|
| 0/1 | 0/1 Knapsack Problem | Easy |
| Unbounded | Currency System | Easy |
| Unbounded | Number Combination | Easy |
| Multiple | Multiple Knapsack Problem | Easy |
| Mixed | Mixed Knapsack Problem | Medium |
| Multiple Constraits | Knapsack with Multiple Constraits | Hard |
| Group | Group Knapsack | Easy |
Interval DP
| Algorithm | Example | Level |
|---|---|---|
| Interval DP | Stone Merger | Easy |
| Interval DP | Bonus Binary Tree | Easy |
DP on Finite Automata
| Algorithm | Example | Level |
|---|---|---|
| DP on FA | Corn Yard | Medium |
| DP on FA | Little King | Medium |
| DP on FA | Password Counting | Medium |
| DP on AC FA | DNA Repairing | Medium |
State Compression DP
| Algorithm | Example | Level |
|---|---|---|
| State Compression DP | Treasure Hunt | Medium |
| State Compression DP w/ Rolling Array | Artillary Position | Medium |
| State Compression DP | Traveling by Stagecoach | Medium |
DP on Digits
| Algorithm | Example | Level |
|---|---|---|
| DP on Digits | Sum of Digits | Medium |
DP & Combinatorics
| Algorithm | Example | Level |
|---|---|---|
| Combinatorics | KK’s Chemicals | Medium |
DP on a Tree
| Algorithm | Example | Level |
|---|---|---|
| DP on a Tree | A Party Without a Boss | Medium |
| DP on a Tree | Course Selection | Medium |
Graph
| Algorithm | Example | Level |
|---|---|---|
| Dijkstra | Dijkstra’s Shortest Path | Medium |
| Shortest Path Faster Algorithm (SPFA) | Layout | Medium |
TopologySort
| Algorithm | Example | Level |
|---|---|---|
| TopologySort | Milking Order | Medium |
Point Update Range Query
| Algorithm | Example | Level |
|---|---|---|
| BIT | Cow Haircut | Medium |
Euler Tour, LCA
| Algorithm | Example | Level |
|---|---|---|
| Euler Tour, LCA,BIT | Cow Land | Medium |
| Euler Tour, LCA, Custom Hash | Milk Visits | Medium |