cho.sh

Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

All problems
Total results3,128 problems
TopicsJudge
Strongly MatchableDecide whether an even-order graph admits a perfect bipartite matching for every balanced partition of its vertices.Hard9GraphMath+2No attempts yet3s512 MBJudgeable
Arranging tilesGiven up to 14 convex tiles of equal height with cut corners, find the ordering and horizontal placement that minimizes the total frame width when packed side by side.Hard9Dynamic programmingGeometry+2No attempts yet1s1024 MBJudgeable
CratersFind the shortest single closed fence that surrounds all circles at distance 10 or more, given each crater's center and radius.Hard9GeometryDynamic programming+2No attempts yet2s512 MBJudgeable
Enlarging EnthusiasmCount the distinct final rankings achievable when positive point bonuses summing to x are announced in increasing order, with the lead changing hands each time.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Treasure MapOn a weighted undirected graph, gold decays each day at every mine; starting at mine 1 with forced moves, maximize total gold collected before stopping.Hard9GraphDynamic programming+2No attempts yet2s512 MBJudgeable
IntuidiffFind the minimum number of blocks, each a substring of the first string or a single new character, whose concatenation equals the second string.Hard9String matchingGreedy+2No attempts yet7s512 MBJudgeable
Workbook AlgorithmsCount the number of undirected graphs X on N vertices whose number of permutations P satisfying G(P)=X lies between l and r, modulo 1e9+7.Hard9CombinatoricsGraph+2No attempts yet1s512 MBJudgeable
GarageMaintain a sequence under point updates, and for each range query count subarrays whose elements share a common divisor greater than 1.Hard9Segment treeNumber theory+2No attempts yet4s256 MBJudgeable
LeadersAnimals in a circle alternately raise a running number by 1 to K; whoever is forced to say M loses, and we find the winner of every start position.Hard9Game theoryDynamic programming+2No attempts yet3s512 MBJudgeable
Imelda's Shopping SpreeMaintain a sequence of prices under range-add and range-reverse, and after each update output the number of contiguous segments whose values are strictly increasing.Hard9Segment treeArray+2No attempts yet5s512 MBJudgeable
KabobsCount length-K strings over the given alphabet that satisfy all substring-implication rules of the form b>e, modulo 10^7.Hard9Dynamic programmingString+2No attempts yet5s512 MBJudgeable
DramaCount the number of valid pyramid colourings of an H by N grid with exactly N black cells, modulo 10^9+7.Hard9CombinatoricsDynamic programming+1No attempts yet2s512 MBJudgeable
Revenge of the Endless BFSDecide whether a buggy BFS that forgets visited vertices ever terminates on a given directed graph, and if so output the loop count modulo 1e9+7.Hard9GraphBFS+2No attempts yet2s512 MBJudgeable
Conveyor BeltAfter each of Q delivery requests (a, b, p) is added, report the minimum time to finish all tasks, given plates arrive one per second and each plate carries one product.Hard9MathGreedy+2No attempts yet2s512 MBJudgeable
Pipe Fitter and the Fierce DogsIn a grid where every odd row and column holds a house, cover all houses with downhill chains, minimizing the cost of pipes through dog blocks, using at most K chains.Hard9Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
Blocks 2Count the ways to tile an N x M rectangle with rotated k x N blocks (k=1..N), modulo 1999, where M can be as large as 10^10.Hard9CombinatoricsDynamic programming+2No attempts yet1s256 MBJudgeable
Stamp PaintingCount the distinct colorings of an N-unit canvas obtainable by stamping K-wide colored stamps so every unit ends up painted, modulo 1e9+7.Hard9Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Maximal polygon brightnessGiven a convex polygon and a sequence of vertex deletions, compute after each deletion the largest total length of edges that a single external light point can illuminate.Hard9GeometryDynamic programming+2No attempts yet3s1024 MBJudgeable
Street TreesMaintain a minimum-cost coloring of N vertices with two colors under incremental equality/inequality constraints and point cost updates, reporting the optimum after each operation.Hard9Union-findGraph+2No attempts yet2s256 MBJudgeable
The Number of SequencesFor a given N and C, find the lexicographically smallest triple (X, Y, Z) such that exactly C ordered N-tuples of 31-bit integers have OR X, AND Y, XOR Z, or report none exists.Hard9Bit manipulationCombinatorics+2No attempts yet1s128 MBJudgeable
Uncrossed Knight's TourGiven an m by n board (m at most 8, n up to 1e15), find the maximum number of squares a closed knight tour can visit without crossing itself.Hard9GreedyDynamic programming+2No attempts yet2s1024 MBJudgeable
Maximum Weight Matching in a General GraphGiven a weighted undirected graph, find a matching with maximum total edge weight.Hard9GraphGreedy+1No attempts yet2s512 MBJudgeable
United States of EurasiaSplit N points sorted by x into at most K contiguous groups, minimizing the largest squared diameter within any group.Hard9Binary searchDynamic programming+2No attempts yet20s1024 MBJudgeable
Xtreme NP-hard Problem?!Find the minimum-weight simple path from vertex 1 to vertex n that uses exactly k edges, or report -1; with n, m, k up to 10^6 this is explicitly NP-hard.Hard9GraphShortest path+2No attempts yet5s1024 MBJudgeable
Travelling MerchantGiven a directed weighted graph and per-market buy/sell prices for K items, find the maximum profit-to-duration ratio of a closed walk trading at most one item at a time, floor it.Hard9GraphShortest path+2No attempts yet2s512 MBJudgeable
Tree EscapeOn a rooted tree where each leaf starts with one piece, players alternately move a piece to its parent and remove it at the root; decide if the first player wins.Hard9Game theoryTree+2No attempts yet2s512 MBJudgeable
Fibonacci Digit CountCount occurrences of the substring "11" within the first N characters of the infinite string formed by writing 1, 2, 3, ... in Fibonacci (Zeckendorf) representation.Hard9MathDynamic programming+2No attempts yet2s1024 MBJudgeable
LogoGiven up to five polyomino patch shapes (each a subset of a 3x3 grid, flippable and rotatable) and up to three grid designs up to 55x5, decide if each design can be tiled exactly by non-overlapping patches and find the minimum patch count, or report NIE.Hard10Dynamic programmingBit manipulation+2No attempts yet1s128 MBJudgeable