# Algorithm Contest Problem Summary

# Advanced Algorithms

# Advanced Data Structures

- Suffix Array
- USACO Music Theme: There is also a DP solution. See USACO analysis.
- USACO Hidden Passwords: Sort rotates of a string.

# Computational Geometry

- Lattice Point
- Convex Hull
- Graham Scan
- USACO Fencing the Cows

- Rectangle
- USACO Window Area: Rectangle overlapping algorithm (floating-up).

- Line Sweeping
- USACO Picture: Find perimeter of stacked rectangles.

# Dynamic Programming

- USACO Number Triangles: Find maximum sum from root to leaf in a tree.
- USACO Subset Sums: Find number of possible subsets adding to a number.
- USACO Longest Prefix: Find the longest prefix of a string constructable by words from a dictionary.
- USACO Cow Pedigrees: Find number of possible complete binary trees with N nodes.
- USACO Money Systems: Find number of ways to compose N given smaller numbers.
- USACO Score Inflation: 0/1 knapsack.
- USACO Stamps: Find minimum number that cannot be summed to by at most K numbers drawn from a set.
- USACO Stringsobits: Find the k-th largest number having no more than N 1-bits.
- USACO Shopping Offers: Find the minimum cost to satisify a target combination with given combinations.
- USACO Home on the Range: Find all squares in an area with obstacles.
- USACO Raucous Rockers: Store maximum number of songs in CDs with chronological order. (Brute force will also do though)
- USACO Beef McNuggets: Find minimum number that cannot be summed to by a set of numbers.
- USACO Buy Low, Buy Lower: Find number of unique longest decreasing subsequences.
- USACO Milk Measuring: DFSID + DP validation also works.
- USACO Big Barn: Find maximum square in an area with obstacles.
- USACO Canada Tour
- USACO Character Recognition
- USACO Two Five: High demension DP.

# Greedy

- USACO Mixing Milk: Fraction knapsack.
- USACO Barn Repair: Cover P points within L lines with minimum total length.
- USACO Job Processing: Minimize the time of 2-phase jobs flowing through M1 phase-1 machines and M2 phase-2 machines, with different job processing times.
- POJ 1328 Radar Installation: Interval coverage.
- POJ 2586 Y2K Accounting Bug

# Graph

- Shortest Path
- Bellman-Ford
- Dijkstra
- Floyd
- USACO Bessie Come Home
- USACO Cow Tours
- USACO Sweet Butter
- USACO Camelot: Modified BFS. Nice sub-problem definition in USACO analysis!
- USACO Fence Loops: Find smallest perimeter of a weighted graph.
- POJ 1860 Currency Exchange
- POJ 3259 Wormholes

- Eularian Path
- Fleury
- USACO Riding the Fences

- Minimum Spanning Tree
- Prim
- Kruskal
- USACO Agri-Net

- Network Flow
- Max-Flow
- Edmond-Karp
- USACO Drainage Ditches
- USACO Pollutant Control: Find minimum cut with minimum number of edges.
- USACO TeleCowmunication: Minimum point cut.

- Maximum Matching

- Max-Flow
- Flood Filling
- Strong Connected Region
- Tarjan algorithm
- USACO Network of Schools

# Math

- High Precision
- POJ 2109 Power of Cryptography: Need constant optimization.

- Mini-Max Search
- USACO A Game: Two players fetch numbers from two ends of a sequence for maximum sum.

- USACO Factorials: Find rightmost non-zero digit of n!.

# Miscellaneous

- Construction
- USACO Sorting a Three-Valued Sequence: Construct an optimized swapping solution to sort 1, 2, 3s.
- POJ 3295 Tautology

- Emulation
- USACO Your Ride is Here
- USACO Greedy Gift Givers
- USACO Friday the Thirteenth
- USACO Broken Necklace
- USACO Milking Cows
- USACO Transformations
- USACO Name That Number
- USACO Preface Numbering Roman number.
- USACO The Tamworth Two
- USACO Fractions to Decimals
- USACO Spinning Wheels
- USACO Magic Squares
- USACO Starry Night
- POJ 1068 Parencodings
- POJ 1573 Robot Motion
- POJ 2632 Crashing Robots
- POJ 2993 Emag eht htiw Em Pleh
- POJ 2996 Help Me with the Game

- Enumeration
- USACO Palindromic Squares
- USACO Dual Palindromes
- USACO Prime Cryptarithm
- USACO Combination Lock
- USACO Wormholes
- USACO The Tamworth Two
- USACO Ski Course Design: There is an O(Nlog(M)) solution, where M is the range of heights.
- USACO Arithmetic Progressions: Search space pruning.
- USACO Prime Palindromes: Find all palindrome primes between two numbers.
- USACO Superprime Rib: Find all numbers whose prefixes are all prime.
- USACO Runaround Numbers
- USACO Healthy Holsteins
- USACO Party Lamps
- USACO Zero Sum: 24-point game.
- USACO Humble Numbers: Given N primes, find the Kth largest product produced by them.
- USACO Contact: Find substrings with top-K appearance.
- USACO Feed Ratios
- POJ 1753 Flip Game
- POJ 2965 The Pilots Brothers’ Refrigerator: Need constant optimization.

- Divide & Conquer
- USACO Ordered Fractions: Print all fractions represented by 1…N. Simple enumeration worked well. (Faster solution: if n1/n2 <= d1/d2, then n1/n2 <= (n1+d1)/(d1+d2) <= d1/d2)
- USACO American Heritage: Given in-order and pre-order, print post-order

- Linked List
- Recursion

# Search

- USACO Mother’s Milk
- USACO The Castle
- USACO Hamming Code
- USACO Controlling Companies
- USACO Overfencing
- USACO Letter Game
- USACO Shuttle Puzzle: Formula solution exists. See USACO analysis.
- USACO Frame Up
- USACO Snail Trail