• 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 fixed-size box, find maximum value that can be bounded.
• Each point can be represented by a Y-axis 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).
• Binary Index Tree
• 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 p-th child deleted got number-of-p’s-divisors 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 left-down side of it.
• Process points in left-to-right, down-to-up order.
• POJ 1195 Mobile phones
• 2D point modification and range query
• 2D BIT, easy expansion from 1D case.
• Suffix Array

# 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 k-th largest number having no more than N 1-bits.
• DP on number of N-length no more than M-1-bit 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.
• 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.
• 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]: minimum cost of buying highest M classes of pearls when buying the M-th 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][j-1]+1, F[i+1][j-1] 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 sub-rectangle, 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 top-left gives O(N^2) solution, and from bottom-right gives O(N^3).
• POJ 1925 Spiderman
• The problem is not good, for its worst time complexity is too high.
• POJ 3034 Whac-a-Mole
• Find maximum score in a Whac-a-Mole 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 0-1 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 m-th 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.
• 0-1 encoding for vertical bricks and 1-1 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[m-1][n-1] (has 1) + F[m-n][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 2-phase jobs flowing through M1 phase-1 machines and M2 phase-2 machines, with different job processing times.
• See USACO solution.
• 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
• Bellman-Ford
• Dijkstra
• Floyd
• SPFA
• USACO Bessie Come Home
• Floyd.
• USACO Cow Tours
• Given un-connected regions, find minimum diameter of graph formed by connecting any two of them.
• Floyd and enumerate connected point pairs.
• USACO Sweet Butter
• Heap-optimized 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. Bellman-ford.
• 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
• 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 non-connected graph.
• Minimum Spanning Tree
• Network Flow
• Max-Flow
• Edmond-Karp
• USACO Drainage Ditches
• Bare Edmond-Karp.
• USACO Pollutant Control
• Find minimum edge cut with minimum edge number.
• To minimize the edge number, solve minimum cut among full-capacity edges. Full edges are refilled with weight 1, others with infinity. As a result, max-flow capacity == min-cut 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
• Bi-Partite 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 x-y bi-partite graph with super source and sink, find minimum cut (maximum match). Graph cut means no more points.
•  There is a Konig theorem: min-node-cov = max-match .
• POJ 3020 Antenna Placement
• Given (x, y) points, one can cover points using length-2 capsules. Find minimum capsules needed.
•  nodes = max-match + min-edge-cov . Positions as nodes, capsules as edges.
• POJ 2531 Network Saboteur
• Find maximum cut of a fully connected graph.
• O(2^(n-1)*n) time, state enumerate using gray code.
• Flood Filling
• Strong Connected Region

# Math

• High Precision
• 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!.
• POJ 3087 Shuffle’m Up
• Given two equal-length 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 i-th 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 Semi-prime H-numbers
• Given domain {4k+1}, find semi primes. A semi prime is a number produced by two-prime 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.

# String

• POJ 1035 Spell Checker
• Given a word and a dictionary, find all one-edit-distance 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].

# 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 |a-b|/min(a, b) < 1e-12.
• POJ 3122 Pie
• Given M pies with different radius, calculate maximum sub-piece 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.