Advanced Algorithms

Advanced Data Structures

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.

Greedy

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

Miscellaneous

Search

String

Sort

Hash