Algorithm Contest Problem Summary
Advanced Algorithms
Advanced Data Structures
 Suffix Array
 USACO Music Theme
 DP solution by maintaining len[i][j], longest common prefix starting from i and j.
 USACO Hidden Passwords
 Sort rotates of a string.
 USACO Music Theme
Computational Geometry
 Lattice Point
 USACO Electric Fence
 Find lattice points in a triangle.
 USACO Electric Fence
 Convex Hull
 Graham Scan
 USACO Fencing the Cows
 Rectangle
 USACO Window Area
 Rectangle overlapping algorithm (floatingup); Cutting up, down, left and right.
 USACO Window Area
 Line Sweeping
 USACO Picture
 Find perimeter of stacked rectangles.
 USACO Picture
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.
 Typical knapsack.
 USACO Longest Prefix
 Find the longest prefix of a string constructable by words from a dictionary.
 Use Trie with DP.
 USACO Cow Pedigrees
 Find number of possible complete binary trees with N nodes.
 Catalan number.
 USACO Money Systems
 Find number of ways to compose N given smaller numbers M1, M2, …, Mi.
 Typical complete knapsack.
 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.
 DP on minimum number of solution summed to M with first N numbers.
 USACO Stringsobits
 Find the kth largest number having no more than N 1bits.
 DP on number of Nlength no more than M1bit numbers.
 USACO Shopping Offers
 Find the minimum cost to satisify a target combination with given combinations.
 Multiple dimension knapsack.
 USACO Home on the Range
 Find all squares in an area with obstacles.
 DP on maximum square edge size.
 USACO Raucous Rockers
 Store maximum number of songs in CDs with chronological order. (Brute force will also do though)
 DP on F[M][N][T], maximum of songs can put with first M songs, first N CD’s and last CD remaining time T.
 USACO Beef McNuggets
 Find minimum number that cannot be summed to by a set of numbers. Number usage is not limited.
 Extended euclid: ax + by = gcd(a, b). If gcd > 1, then no limit. If smallest number == 1, then all ok. Else, use method in Stamps. Exit once the following 256 bits are all 1.
 USACO Buy Low, Buy Lower
 Find number of unique longest decreasing subsequences.
 Find maximum length, then count unique ones. For i < j, if maxLen[i] + 1 == maxLen[j], then uniqNums[j] = uniqNums[i] if nums[i] == nums[j], uniqNums[j] = uniqNums[i] + uniqNums[j] if nums[i] < nums[j].
 USACO Milk Measuring
 Given a set of numbers and a target, find minimum subset, numbers drawn from which summed to the target.
 DFSID + DP validation also works.
 USACO Big Barn
 Find maximum square in an area with obstacles.
 USACO Canada Tour
 Hamilton circle on a straight line.
 F[m][n]: max city number from m > start > n. m is always <= n.
 USACO Character Recognition
 F[m] = min(F[m  19] + cost(missing), F[m  20] + cost(normal), F[m  21] + cost(duplicate))
 USACO Two Five
 Very good question! See answer and solution on USACO for more details.
 POJ 1837 Balance
 Given a balance and weights and loadable positions, find number of balanced configurations.
 State: F[M][N], number of ways by which load N can be reached by first M weights.
 POJ 1276 Cash Machine
 0/1 Knapsack with object number limit.
 Need binary optimization (2^0, 2^1, …, 2^k, N(1+…+2^k)), where k is the maximum i.e. N(…)>=0.
 POJ 2151 Check the difficulty of problems
 Probability DP. Given probability list, F[m][n]: probability of selecting n from m.
Greedy
 USACO Mixing Milk
 Fraction knapsack.
 USACO Barn Repair
 Given points 1 to n, one can cover a given point set using no more than L lines. Find the minimum number of points need to be covered.
 Greedily choose minimum seperations.
 USACO Job Processing
 Minimize the time of 2phase jobs flowing through M1 phase1 machines and M2 phase2 machines, with different job processing times.
 See USACO solution.
 POJ 1328 Radar Installation
 Given intervals, find minimum points to color all intervals.
 POJ 2586 Y2K Accounting Bug
Graph
 Shortest Path
 BellmanFord
 Dijkstra
 Floyd
 SPFA
 USACO Bessie Come Home
 Floyd.
 USACO Cow Tours
 Given unconnected regions, find minimum diameter of graph formed by connecting any two of them.
 Floyd and enumerate connected point pairs.
 USACO Sweet Butter
 Heapoptimized Dijkstra.
 USACO Camelot
 SPFA (BFS without visited), for each knight calculate minimum cost to all grids with or w/o king. Note that “no king” can go to “with king”, but not vice versa.
 USACO Fence Loops
 Find shortest cycle in a weighted graph.
 For each edge break it and do dijkstra.
 POJ 1860 Currency Exchange
 Find exchange rate > 1 in the exchange grph, from given currency. Bellmanford.
 POJ 3259 Wormholes
 Find negative circle in the whole graph. Floyd.
 POJ 1062 昂贵的聘礼
 Define “having nothing” state HN. For each gift G valued p, we have (HN, G) edge with cost p. For each replacement G’ with better price q, we have (G’, G) with cost q. Do shortest path with Dijkstra.
 POJ 2253 Frogger
 For each point, find minimum of max edge length of path to it. Dijkstra, change objective to minimize edge length. Greedy policy can be prooved.
 POJ 1125 Stockbroker Grapevine
 Bare floyd.
 POJ 2240 Arbitrage
 Similar to 1860, but consider all start currency. Floyd.
 Topological Sort
 POJ 1094 Sorting It All Out
 Bare topological sort.
 POJ 1094 Sorting It All Out
 Eularian Path
 Hierholzer’s algorithm
 USACO Riding the Fences
 Minimum Spanning Tree
 Prim
 Kruskal
 USACO AgriNet
 Bare MST.
 POJ 1789 Truck History
 Find MST in string distance graph.
 POJ 2485 Highways
 Find the spanning tree with minimum maximum edge. MST satisfies the condition.
 POJ 1258 AgriNet
 Same with USACO AgriNet.
 POJ 3026 Borg Maze
 Bare MST. STL queue will timeout, use vanilla array.
 Network Flow
 MaxFlow
 EdmondKarp
 USACO Drainage Ditches
 Bare EdmondKarp.
 USACO Pollutant Control
 Find minimum edge cut with minimum edge number.
 To minimize the edge number, solve minimum cut among fullcapacity edges. Full edges are refilled with weight 1, others with infinity. As a result, maxflow capacity == mincut capacity == min edge number.
 USACO TeleCowmunication
 Minimum node cut.
 POJ 1459 Power Network
 Given power plants, consumers and dispatchers, find maximum power consumed.
 Bare max flow. Connect plants to source and consumers to sink.
 Maximum Matching
 BiPartite Graph
 Hungarian
 POJ 3041 Asteroids
 Given (x, y) points, one can eliminate a row or a col. Find minimum steps to eliminate all points.
 Build xy bipartite graph with super source and sink, find minimum cut (maximum match). Graph cut means no more points.

There is a Konig theorem: minnodecov = maxmatch .
 POJ 3020 Antenna Placement
 Given (x, y) points, one can cover points using length2 capsules. Find minimum capsules needed.

nodes = maxmatch + minedgecov . Positions as nodes, capsules as edges.
 MaxFlow
 Flood Filling
 Strong Connected Region
 Tarjan algorithm
 USACO Network of Schools
Math
 High Precision
 POJ 2109 Power of Cryptography
 Need constant optimization.
 POJ 2109 Power of Cryptography
 MiniMax Search
 USACO A Game
 Two players fetch numbers from two ends of a sequence for maximum sum.
 USACO A Game
 USACO Factorials
 Find rightmost nonzero digit of n!.
Miscellaneous
 Construction
 USACO Sorting a ThreeValued Sequence
 Construct an optimized swapping solution to sort 1, 2, 3s.
 Count 1in2, 1in3, 2in1, 2in3, 3in1, 3in2. Then do pairwise elimination (1in2 and 2in1). Then rest is 231 or 132.
 POJ 3295 Tautology
 Build an recursive parser.
 USACO Sorting a ThreeValued Sequence
 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
 There are digitletter mapping (2ABC,3DEF,…) and a dictionary with 4length words. Given a 4length number, find all corresponding words.
 Binary search.
 USACO Preface Numbering
 USACO The Tamworth Two
 Whether farmer J will meet the cow. Break after step mn, where mn is the area of the maze.
 USACO Fractions to Decimals
 USACO Spinning Wheels
 Stop iteration after 360 times, because every spin will return to initial state.
 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 Ski Course Design
 Given hills, one can change their heights with cost pow(deltaH, 2). Find minimum cost to change them into a 17 interval.
 O(Nlog(M)) time by binary search.
 USACO Arithmetic Progressions
 Find a + nb in p^2 + q^2.
 Search in p^2 and q^2 only.
 USACO Prime Palindromes
 Find all palindrome primes between two numbers (can be 0 to 10^9).
 USACO Superprime Rib
 Find all numbers whose prefixes are all prime.
 USACO Runaround Numbers
 USACO Healthy Holsteins
 USACO Party Lamps
 USACO Zero Sum
 24point game, with only + and .
 USACO Humble Numbers
 Given N primes, find the Kth largest product produced by them. O(NK) time.
 USACO Contact
 Find substrings within 12length with topK appearance in 01 string. Bit manipulation.
 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 inorder and preorder, print postorder
 USACO Ordered Fractions
Search
 USACO Mother’s Milk
 USACO The Castle
 USACO Hamming Code
 USACO Controlling Companies
 Given controlling relations among Co.LTD’s, find all controlling relations.
 DFS for every company, do further search when new company is under control.
 USACO Overfencing
 Given a maze with multiple exits, find the point with minimum worst exit path.
 USACO Letter Game
 USACO Shuttle Puzzle
 Formula solution exists. See USACO analysis.
 USACO Frame Up
 USACO Snail Trail
String
 POJ 1035 Spell Checker
 Given a word and a dictionary, find all oneeditdistance matches.
 POJ 3080 Blue Jeans
 Given a set of strings, find their longest common substring.
 Binary search LCS length.
 POJ 1936 All in All
 Implement isSubString.
Sort
 POJ 2388 Who’s in the Middle
 Find median.
 POJ 2299 UltraQuicksort
 Find all reverse pairs.
 BIT/Segment tree/instrumented merge sort.
Hash
 POJ 3349 Snowflake Snow Snowflakes
 Given lengths of snowflake akes, find twin snowflakes.
 Find lexicographically mininimum representation.
 POJ 3274 Gold Balanced Lineup
 Find longest subarray that all bits appear same times.
 Prefix sum, generate relative hash, and for each hash find maximum gap.