Algorithm Contest Problem Summary
Advanced Algorithms
Advanced Data Structures
 Segment Tree
 POJ 2528 Mayor’s posters
 Given posters and their placement order, find number of posters visible.
 Segment tree with lazy update.
 POJ 2777 Count Color
 Range update, range query for number of different elements.
 Use bitmap to mark elements.
 If using plain array for segment tree, we need O(4L) space because it might not be a complete binary tree.
 POJ 2750 Potted Flower
 Given a number circle and modification instructions, find maximum arc after each instruction but not the full circle.
 Represent the circle by a chain. max_arc = max(max_chain, sum  min_chain) if max_chain != sum else sum  min_chain.
 POJ 2482 Stars in Your Window
 Given points with values and a fixedsize box, find maximum value that can be bounded.
 Each point can be represented by a Yaxis segment, and scan along X axis.
 POJ 3264 Balanced Lineup
 Range min/max query.
 POJ 3368 Frequent values
 Range query most frequent number.
 Actually a DP problem, for each segment maintains (maxCnt, minVal, minCnt, maxVal, maxCnt).
 POJ 2528 Mayor’s posters
 Binary Index Tree
 POJ 2828 Buy Tickets
 Finish insertion sort given the insertion sequence.
 Reverse the insertion sequence. Maintain slots remaining in [0, m], and binary search for the position with valid slots for each insertion.
 POJ 2886 Who Gets the Most Candies?
 Given a circle made by children. Each child has an offset. Each time we delete a child from the circle and find the next child according to the offset. The pth child deleted got numberofp’sdivisors score. Find the child with maximum score.
 Maintain slots remaining in [0, m], similar to 2828.
 Number of divisors are calculated by sieve method.
 POJ 2352 Stars
 Given points, define level of a point as number of points in the leftdown side of it.
 Process points in lefttoright, downtoup order.
 POJ 1195 Mobile phones
 2D point modification and range query
 2D BIT, easy expansion from 1D case.
 POJ 2828 Buy Tickets
 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.
 POJ 3267 The Cow Lexicon
 Given a dictionary and a string, find minimum characters to remove from string to make the string compositable by words from the dictionary.
 For each position try drop or match each word in dictionary.
 POJ 1836 Alignment
 Given a line of soldiers, find minimum number of soldiers needed to move inorder to make each soldier in the line can see either left or right extremity.
 Strict LIS on both sides.
 POJ 1260 Pearls
 There are M classes of pearls and their value V. One has to pay 10 more units when buying any class of pearls. Better pearls can replace worse ones. Given a shopping list, find minimum cost.
 F[M][2]: minimum cost of buying highest M classes of pearls when buying the Mth class or not.
 POJ 2533 Longest Ordered Subsequence
 POJ 3176 Cow Bowling
 Typical triangle sum DP.
 POJ 1080 Human Gene Functions
 Typical weighted LCS.
 POJ 1159 Palindrome
 Given a string, find minimum inserts to make it palindrome.
 Let F[i][j] is minimum inserts between i and j. F[i][j] = min(F[i+1][j]+1, F[i][j1]+1, F[i+1][j1] only if s[i]==s[j]).
 POJ 1191 棋盘分割
 Given a weighted 8x8 chess board. You can cut one rectangle off for n times. Find minimum of variance of pieces.
 For each subrectangle, maintain minimum variance for cutting into x pieces.
 POJ 3280 Cheapest Palindrome
 Given a string, find minimum insert/deletes to make it palindrome.
 Similar to POJ 1159.
 POJ 2029 Get Many Persimmon Trees
 Given points and a rectangle, find maximum points boundable by the rectangle.
 Can do with prefix sum. 2D BIT solution similar to POJ 1195.
 POJ 2948 Martian Mining
 Given a grid, there are mineral type A and B on grid points. One can build conveyor belts to collect A to left and B to top. Find maximum mineral that can be collected.
 Maintain F[i][j] as maximum mineral in [0,i]x[0,j] area. Scan from topleft gives O(N^2) solution, and from bottomright gives O(N^3).
 POJ 1925 Spiderman
 The problem is not good, for its worst time complexity is too high.
 POJ 3034 WhacaMole
 Find maximum score in a WhacaMole game. Hammers can move from/to integer points in straight lines only.
 F[m][n][t]: maximum score with hammer’s end position at (m, n) at time t.
 POJ 3254 Corn Fields
 Given a 01 matrix. One can select 1’s from it but without adjacent 1’s. Find number of valid selections.
 F[m][n]: number of selections with first m rows when mth row is of state n.
 POJ 1185 炮兵阵地
 Similar to 3254, but need consider two rows/columns for whether adjacent. Need to calculate valid states first to shrink state space.
 POJ 2411 Mondriaan’s Dream
 Given mxn field, find number of filling methods with 1x2 bricks.
 01 encoding for vertical bricks and 11 for horizontal bricks. Then similar to 3254.
 OpenJudge 4119 复杂的整数划分问题
 Given a number M, find number of plans to 1) divide it into K numbers 2) divide it into different numbers 3) divide it into odd numbers
 1) is F[m][n] = F[m1][n1] (has 1) + F[mn][n] (no 1). 2) and 3) are knapsack.
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
 POJ 3253 Fence Repair
 Given a single wood plank, cut it into given pieces. Each cut cost is the length of the plank being cut, find minimum cost.
 Huffman tree.
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
 POJ 2513 Colored Sticks
 Given sticks with colored two ends, find whether they can be aligned i.e. ends with same colors are connected.
 Note that there might be nonconnected graph.
 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.
 POJ 2031 Building a Space Station
 Bare MST, need to merge connected points.
 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.
 POJ 2531 Network Saboteur
 Find maximum cut of a fully connected graph.
 O(2^(n1)*n) time, state enumerate using gray code.
 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!.
 POJ 3087 Shuffle’m Up
 Given two equallength sequences, one can shuffle them. E.g., ABAB and BABA > BAABBAAB. Find whether it’s possible to get a sequence by shuffling multiple times.
 This is a out perfect shuffle problem. See solution file for further explanation.
 POJ 3252 Round Numbers
 Define “round number” is a number whose binary representation has more 1 than 0. Find how many round numbers are there in a given range [x, y].
 POJ 1850 Code
 Given encoding rule a=1, b=2, …, z=26, ab=27, …, az=51, bc=52, …, vwxyz=83681, find encoding for any word.
 POJ 1019 Number Sequence
 Given number sequence like 112123123412345…, find ith digit.
 POJ 1942 Paths on a Grid
 Calculate C(m+n, m). Be careful with timeout when m == 1 or m == 2.
 POJ 2635 The Embarrassed Cryptographer
 Given big M (~100 digits), calculate its minimum prime factor. Need prime sieve.
 POJ 3292 Semiprime Hnumbers
 Given domain {4k+1}, find semi primes. A semi prime is a number produced by twoprime multiplication.
 POJ 1845 Sumdiv
 Given A and B, find sum of all natural divisors of A^B mod 9901.
 Factorize A^B as a1^n1*a2^n2 …, sum can be represented by generative function: (1+a1+…+a1^n1)(1+a2+…+a2^n2)…
 POJ 2115 C Looooops
 Find minimum solution for module linear equation.
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
 POJ 2488 A Knight’s Journey
 Given a chess board and a knight, find whether there is a hamilton path.
 POJ 3083 Children of the Candy Corn
 Walk through a maze by walking alongside left/right wall and shortest path.
 Turn left/right when there is path to left/right. Else if no path turn right/left.
 POJ 3009 Curling 2.0
 Throw stones to the target in a grid. The stone can brick one wall at a time.
 Use DFS since the maze can change.
 POJ 1321 棋盘问题
 Generalized Nqueen problem.
 POJ 2251 Dungeon Master
 Given a 3D maze, find shortest path from start to end. Simple BFS.
 POJ 3278 Catch That Cow
 Given N and K, one can do N+1, N1 and N*2 to get K, find minimum steps.
 Simple BFS since 0 <= N (state number) <= 100000.
 POJ 1426 Find The Multiple
 Given n, find m i.e. m % n == 0 and m’s decimal representation contains only 0 and 1.
 Do bfs on remainder space of n.
 POJ 3126 Prime Path
 Given two 4digit primes A and B, find least number of 1digit replacements to convert A to B. Simple BFS.
 POJ 3414 Pots
 Given two pots with volume A and B, and three actions FILL, DROP and POUR, find least steps to make C unit water. Simple BFS.
 POJ 1416 Shredding Company
 Given two numbers A and B, find the way to cut B that sum of the segments is maximum and no more than A.
 POJ 2676 Sudoku
 Solve a 9x9 sudoku.
 POJ 1129 Channel Allocation
 Vertex coloring problem.
 POJ 3411 Paid Roads
 Given a road graph, roads have costs. Some roads can be prepaid at some node. Find minimum cost from node 1 to node N.
 DFS, state is prepaid roads and current city. Haven’t get accepted yet.
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.
 POJ 1961 Period
 Given a string s, for each its prefix judge whether is periodical.
 Use KMP next array WITHOUT optimization. Cycle length is n  next(n) for 1 <= n <= len(s).
 POJ 2406 Power Strings
 Given a string s, find whether it’s periodical.
 Similar with POJ 1961. Or find s in (s+s)[1:1].
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.
 POJ 1840 Eqs
 Given ai (1 <= i <= 5), find number of solutions of SUM(ai * xi) = 0.
 Similar to LeetCode two sum.
 POJ 2002 Squares
 Given 2d points, find number of squares.
 O(n^2) enumeration.
 POJ 2503 Babelfish
 Translate words given a dictionary.
Binary search
 POJ 3273 Monthly Expense
 Given N numbers, find M segments with minimum maximum segment sum.
 Binary search for the maximum sum.
 POJ 3258 River Hopscotch
 Given 0, L and N points between 0 and L, find maximum of minimum distance by removing M points.
 Binary search the distance. To validate the answer, use greedy policy to remove stones.
 POJ 1905 Expanding Rods
 Find solution of sin(A/x) = B/x (A > B).
 Binary search, termination condition is defined by ab/min(a, b) < 1e12.
 POJ 3122 Pie
 Given M pies with different radius, calculate maximum subpiece for N people.
Union find
 POJ 1703 Find them, Catch them
 There are two gangs in a city. Given enemy relationships and queries for relationship, answer yes/no/unkonwn.
 For each person maintain its enemy. Do merges in enemy relationships.
 POJ 2492 A Bug’s Life
 Similar to 1703, but need to find contradiction.
 Judge before each merge.