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 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
    • 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 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

Computational Geometry

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.
  • 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 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.
  • 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
    • 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.
  • 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.

Miscellaneous

Search

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].

Sort

Hash

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.