cho.sh

Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

All problems
Total results3,128 problems
TopicsJudge
Travel Plan (Large)Visit every planet on a line exactly once and return to Earth, maximizing total travel distance without exceeding the fuel limit.Hard8Dynamic programmingSorting+1No attempts yet5s512 MBJudgeable
Fence BoardsPick the fewest boards from N unlimited lengths to total exactly L for a fence up to 1e18 long, or report IMPOSSIBLE.Hard8Shortest pathDynamic programming+1No attempts yet20s512 MBJudgeable
Sums with Distinct Column DigitsCount unordered additions that sum to N in base B where digits in each column are pairwise distinct, modulo 1000000007.Hard8Dynamic programmingCombinatorics+1No attempts yet5s512 MBJudgeable
Counting Cryptarithm EquationsCount unordered base-B summand sets with distinct digits in each column that sum to N.Hard8Dynamic programmingCombinatorics+1No attempts yet60s512 MBJudgeable
BacteriaRectangular colonies on a grid evolve each second by a north-and-west neighbor rule, and the task asks when every cell becomes empty.Hard8Dynamic programmingMatrixNo attempts yet5s512 MBJudgeable
MarblesGiven 2n marbles of n colors in a row, find the minimum height of non-crossing paths pairing each color, or -1 if impossible.Hard8Dynamic programmingImplementation+1No attempts yet5s512 MBJudgeable
Interesting RangesCount subranges of [L, R] containing an even number of decimal palindromes, for L and R up to 10^100, modulo 1e9+7.Hard8MathCombinatorics+1No attempts yet45s512 MBJudgeable
Stock ChartsPartition n stock price sequences into the fewest groups so that within each group no two polylines cross or touch at any time point.Hard8Dynamic programmingGreedy+1No attempts yet5s512 MBJudgeable
The Year of Code Jam (Small)Assign each '?' day blue or white to maximize total blue-day value, where a blue day starts at 4 and loses 1 for each blue neighbor above, below, left, or right in a grid of N months by M days.Hard8Dynamic programmingGraph+2No attempts yet5s512 MBJudgeable
The Year of Code Jam (Large)On a grid of N months by M days, choose white or blue for each '?' cell to maximize total happiness, where each blue day scores 4 minus its blue neighbors.Hard8Dynamic programmingGraph+2No attempts yet5s512 MBJudgeable
Painting a Fence (Large)Pick the fewest offers from N interval-and-color proposals so every one of 10000 fence sections is covered using at most 3 distinct colors.Hard8IntervalsGreedy+2No attempts yet10s512 MBJudgeable
Bus Stops (Small)Count the ways K buses starting at the first K stops can cover all N stops and end at the last K, with gaps of at most P.Hard8Dynamic programmingBit manipulation+1No attempts yet5s512 MBJudgeable
Bus Stops (Large)Count schedules assigning every stop to one of K left-to-right buses whose consecutive stops are at most P apart, modulo 30031.Hard8Dynamic programmingBit manipulation+1No attempts yet5s512 MBJudgeable
Test Passing Probability (Large Input)With M submissions allowed and independent per-question probabilities, choose answers to maximize the chance that one submission is fully correct.Hard8ProbabilityDynamic programming+1No attempts yet5s512 MBJudgeable
Becoming a MillionaireBet any fraction of your money each round to maximize the chance of ending with at least one million dollars.Hard8Dynamic programmingProbability+1No attempts yet5s512 MBJudgeable
Millionaire (Large)Bet any fraction of your money over M rounds with win probability P; maximize the chance of holding $1,000,000 at the end.Hard8Dynamic programmingProbabilityNo attempts yet20s512 MBJudgeable
PermRLE (Large)Find the permutation of positions 1 to k applied to every block of the string that minimizes the number of runs after run-length encoding.Hard8Dynamic programmingBit manipulation+1No attempts yet5s512 MBJudgeable
Increasing Speed Limits (Large)Generate a sequence from a recurrence, then count modulo 1e9+7 how many non-empty strictly increasing subsequences it has.Hard8Dynamic programmingSegment treeNo attempts yet5s512 MBJudgeable
BoatCount subsets of schools with an assigned boat count in [a_i, b_i], strictly increasing in school order, excluding the empty setup, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
FireworksGiven a rooted tree whose leaves are explosives and whose edges have lengths, find the minimum total change of edge lengths so all leaves ignite at the same time.Hard8TreeDynamic programming+1No attempts yet2s512 MBJudgeable
BossesBuild a rooted tree on n employees where each node's parent is one of its accepted bosses, then assign minimum positive salaries with every boss exceeding the sum of children.Hard8TreeDynamic programming+2No attempts yet1.5s256 MBJudgeable
The Great Mixing Song FestivalPartition the given songs into groups of exactly c songs each within a year span of m, maximizing the total length of the longest common substring in each group.Hard8Dynamic programmingBit manipulation+2No attempts yet5s128 MBJudgeable
Half-plane land grabLines are added one at a time, and after each addition you must report the maximum y value over all added lines at a given x.Hard8GeometryDynamic programming+1No attempts yet2s128 MBJudgeable
Bridge testingGiven a weighted tree and two timed walkers on their respective paths, decide for each query whether both occupy some bridge simultaneously over a positive-length interval.Hard8TreeDynamic programming+2No attempts yet4s256 MBJudgeable
Similar SubwaysGiven two trees with up to 50 nodes each, find the largest k such that some connected k-node subtree of the first is isomorphic to some connected k-node subtree of the second.Hard8TreeDynamic programming+2No attempts yet3s512 MBJudgeable
InvestigationGiven a tree and a thief hidden at one node, find the minimum worst-case number of queries to locate him in an optimal search strategy.Hard8TreeDynamic programming+1No attempts yet2s1024 MBJudgeable
Wall RepairA robot on a line must visit every point; each point's repair cost grows linearly with the time it waits, so find the visiting order of minimum total cost.Hard8Dynamic programmingIntervals+2No attempts yet1s1024 MBJudgeable
NewspapersGiven a weighted tree, find the maximum average edge weight over all simple paths that contain at least k edges, printed to eight decimals.Hard8Binary searchDynamic programming+2No attempts yet4s1024 MBJudgeable
Organizing Cards 2Given N boxes and M colors with per-box color counts, move individual cards so each color occupies exactly one box, minimizing total moves.Hard8Dynamic programmingBit manipulation+2No attempts yet1s512 MBJudgeable
Walk on the Main Campus 2Count closed walks of exactly D minutes from building 1 back to building 1 in a given 8-vertex graph, modulo 1e9+7.Hard8GraphMatrix+2No attempts yet1s512 MBJudgeable
Hongjun Loves PaintingBricks start with color equal to their index and colorfulness 0; range paint operations add the absolute color change to each brick, and queries ask for the total colorfulness over a range.Hard8Segment treeImplementation+2No attempts yet2s512 MBJudgeable
Remainder GameCount ways to pick one block per basket, forming a b-digit number whose remainder mod x is k, where baskets share the same multiset of digits.Hard8Dynamic programmingMatrix+2No attempts yet2s512 MBJudgeable
JourneyTwo weighted graphs share vertices; alternate one edge per graph, each strictly decreasing that graph's distance to t, and find the longest total route or -1 if infinite.Hard8Shortest pathDynamic programming+2No attempts yet2s512 MBJudgeable
A Lot of GamesGiven a trie of strings, play the prefix-building game k times with the loser starting next; report who wins the last game.Hard8TrieGame theory+2No attempts yet2s512 MBJudgeable
Favorite Arrays 2Count length-N arrays with entries in 1..K where no adjacent pair has A > B with A divisible by B, modulo 1e9+7.Hard8Dynamic programmingNumber theory+2No attempts yet2s512 MBJudgeable
Substring CountCount length-L lowercase strings that contain exactly C of N given words (N at most 6, L at most 50) as substrings, modulo 1,000,000,009.Hard8Dynamic programmingString matching+2No attempts yet2s512 MBJudgeable
Flipping a Bit StringGiven a binary string and a divisor M of its length, find the minimum number of operations (single flip, prefix flip of a multiple of M, or suffix flip of a multiple of M) to make all characters 1.Hard8Dynamic programmingGreedy+1No attempts yet2s512 MBJudgeable
Direction BoardGiven a toroidal N x M grid of arrows (N,M <= 15), change the fewest arrows so that every cell lies on a cycle of length 1.Hard8GraphBit manipulation+2No attempts yet2s512 MBJudgeable
ChessboardPlace as many L-trominoes as possible on a board at most 4 rows tall, where each tile's corner cell must sit on a black square and pieces block cells.Hard8Dynamic programmingBit manipulationNo attempts yet2s512 MBJudgeable
Chessboard 2Place as many non-overlapping L-trominoes as possible on a grid with blocked cells, with each tile's corner on a black square.Hard8GraphBit manipulation+1No attempts yet2s512 MBJudgeable
Sum of ScoresFind a non-empty vertex subset connected in both given trees whose score sum is maximized, with vertex counts up to 50.Hard8Dynamic programmingTree+1No attempts yet2s512 MBJudgeable
Red segments and blue segmentsColor N points red or blue, then draw non-crossing same-color segments so that no red and blue segment touch; maximize total segment scores.Hard8Dynamic programmingGeometry+2No attempts yet2s512 MBJudgeable
Array GCDDelete one contiguous block and change at most one element by 1 each, so the remaining array has gcd greater than 1, at minimum cost.Hard8Number theoryGreedy+2No attempts yet2s512 MBJudgeable
Favorite SequenceCount fillings of at most 5 erased positions in a permutation so the number of pairs i<j with A_i<A_j equals S.Hard8Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Counting strings with LCS n-1Count length-n strings over the first m letters whose longest common subsequence with a given string S has length exactly n-1.Hard8Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Decorating with FlowersCount the ways to choose exactly s blossoms from n kinds with limits f_i, modulo 1e9+7, where n is at most 18 and s can reach 1e14.Hard8CombinatoricsMath+1No attempts yet2s512 MBJudgeable
Hongjun and the Possible SetsCount the nonempty connected vertex subsets of a weighted tree whose maximum minus minimum weight is at most d.Hard8TreeDFS+2No attempts yet3s512 MBJudgeable
Kiwi JuicePour juice between N bottles of capacity C, each pour filling or emptying one, to maximize the sum of prices over all final amounts.Hard8Dynamic programmingGreedy+1No attempts yet2s512 MBJudgeable
Special AbilityFind the minimum cost walk from vertex 1 to N in a directed weighted graph, where the ability can negate the weight of at most C edge crossings.Hard8GraphShortest path+1No attempts yet2s512 MBJudgeable
Special Ability 2Given a weighted directed graph, find the minimum cost path from vertex 1 to N where each edge traversal may be negated, using at most C negations.Hard8GraphShortest path+1No attempts yet2s512 MBJudgeable
Picking Out NumbersChoose between 1 and k distinct integers from [l, r] minimizing the XOR of the chosen set, and output that minimum XOR.Hard8Bit manipulationMath+2No attempts yet2s512 MBJudgeable
Hongjun and the TreeProcess subtree updates that add a distance-dependent value to each vertex, answering point-weight queries modulo 1e9+7.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Easily Happy TreeDelete the fewest leaves from a rooted tree so that no remaining vertex has a descendant farther away than that descendant's own limit a_u.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Polygon GameTwo players alternately draw chords inside a convex N-gon that avoid all earlier chords, including shared endpoints; decide the winner under optimal play.Hard8Game theoryCombinatorics+2No attempts yet2s512 MBJudgeable
TreeMaintain a rooted tree under vertex deletions (children reparent to grandparent) and answer distance queries between two live vertices.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Alternative Bracket NotationConvert a balanced bracket string into the shortest alternative notation, where each pair's header gives absolute start and end indices of its contents.Hard8Dynamic programmingTree+2No attempts yet10s512 MBJudgeable
Programming TeamChoose exactly k candidates from a tree where each pick needs its recommender picked, maximizing total productivity divided by total salary; print the ratio to three decimals.Hard8Dynamic programmingTree+2No attempts yet3s512 MBJudgeable
Jewel ThiefFor each knapsack capacity 1 through k, compute the maximum total value of a subset of n jewels whose sizes sum to at most the capacity.Hard8Dynamic programmingGreedy+1No attempts yet10s512 MBJudgeable
Optimal TournamentPlace N contestants with given strengths at the leaves of a knockout bracket of height at most K so that the total strength difference over all matches is minimized.Hard8Dynamic programmingSorting+2No attempts yet5s512 MBJudgeable
Website TourWalk a directed graph of N websites, watching ads (points p, time t, at most k times each) to maximize points within T seconds.Hard8GraphDynamic programming+2No attempts yet8s512 MBJudgeable
Binary Search GameDetermine whether a player can always guess x within a_x comparison questions given a monotone budget array, and list all valid first questions q.Hard8Binary searchGreedy+1No attempts yet2s64 MBJudgeable
Baseball WatchingEach of N students sits in one of three sections for nine innings; find the min and max number of students a moving teacher can avoid catching.Hard8Dynamic programmingBit manipulation+1No attempts yet1s256 MBJudgeable
Fallen CrystalsGiven N crystals with distinct strengths and a hidden target at rank K, minimize the worst-case number of swings to break it using forces up to P without risking an explosion (force gap W).Hard8Binary searchGame theory+1No attempts yet1s512 MBJudgeable
CoinsCount how many of the 2^N head/tail coin layouts are wins for the second player under optimal play in this flipping game.Hard8Game theoryDynamic programming+1No attempts yet1s512 MBJudgeable
WoodworkingGiven plank recovery probabilities for a box needing N planks, compute the expected number of boxes built starting with M planks.Hard8Dynamic programmingProbability+1No attempts yet7s512 MBJudgeable
HandshakesCompute the expected number of random handshakes until all N people belong to one acquaintance component, and output it modulo 1e9+7.Hard8ProbabilityDynamic programming+2No attempts yet4s512 MBJudgeable
Black and WhiteEach cell is black or white with probability 1/2; find the expected product of the number of all-black subrectangles and all-white subrectangles.Hard8CombinatoricsProbability+2No attempts yet2s512 MBJudgeable
PopealaPartition T weighted test cases into exactly K consecutive subtasks to minimize total scored points, for each K up to S.Hard8Dynamic programmingPrefix sum+1No attempts yet2s512 MBJudgeable
CasinoWith N players, M areas, and K rounds of random elimination, find the best survival probability for the group.Hard8Dynamic programmingProbability+1No attempts yet2s512 MBJudgeable
Beauty of the sequenceGiven N trees with independent uniform height ranges, find the expected maximum beauty of a zigzag subsequence.Hard8Dynamic programmingProbabilityNo attempts yet2s512 MBJudgeable
JailbreakPartition L cells into at most G consecutive blocks, minimizing the sum over each cell of its escape power times its block length.Hard8Dynamic programmingDivide and conquer+1No attempts yet2s512 MBJudgeable
Cookie TrayCount tilings of an N by 5 grid with 2x1 dominoes, given K fixed 1x1 cells, modulo 1e9+7, with N up to 1e18.Hard8Dynamic programmingMatrix+1No attempts yet2s256 MBJudgeable
Fibonacci Numbers of Subset SumsSum F[sum(s)] over all K-element subsets s of a set of N distinct numbers, modulo 99991.Hard8CombinatoricsDynamic programming+2No attempts yet5s512 MBJudgeable
Dots and BoxesGiven a Dots and Boxes position with no completed square, find the longest sequence of moves that still avoids closing any square, then print that length plus one.Hard8GraphDynamic programming+2No attempts yet2s512 MBJudgeable
Pseudo PalindromeGiven a string w and a rational theta, split w into the fewest substrings that are each a theta-palindrome (form uvu^R with enough border), or report 0.Hard8Dynamic programmingString matching+1No attempts yet2s512 MBJudgeable
Cartesian TreeCount permutations of 1..N whose Cartesian tree has total child-position gap score at most S, modulo a prime.Hard8Dynamic programmingTree+1No attempts yet5s512 MBJudgeable
Two TreesPick a vertex subset connected in both of two trees to maximize the total score, with the empty set allowed.Hard8TreeDFS+1No attempts yet2s512 MBJudgeable
LandlordFind the minimum travel time to visit a fixed sequence of districts, starting at 0, when cars parked in some districts can be used once each for faster driving.Hard8Shortest pathDynamic programming+1No attempts yet2s512 MBJudgeable
The Longest Welded SwordSelect and order all plates so that widths strictly decrease, orienting each plate to maximize the total contributed length sum.Hard8GreedySorting+2No attempts yet7s512 MBJudgeable
Special TablesCount the number of N by M tables with entries from 1 to C in which all rows are distinct and all columns are distinct, modulo 1e9+7.Hard8CombinatoricsDynamic programmingNo attempts yet2s512 MBJudgeable
Palindrome MatrixFlip the fewest bits in an even-by-even 0/1 matrix so that at least R rows and at least C columns read as palindromes.Hard8Bit manipulationBrute force+1No attempts yet2s512 MBJudgeable
Cartesian Tree 2Sum the scores of the Cartesian trees of all N! permutations of 1..N, where a node's score is the index gap between its two children, modulo a prime.Hard8CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Black and White BoxesGiven up to 40 piles of black and white boxes, pick a subset so the first-player draw decides the winner and maximize total boxes.Hard8Game theoryDynamic programming+1No attempts yet2s512 MBJudgeable
Inversions of a simple path sequenceGiven a connected unimodal (unicyclic) graph, find a minimum inversion count over simple paths visiting at least K vertices, or -1 if none exist.Hard8GraphDynamic programming+2No attempts yet2s512 MBJudgeable
Blue vertex distance sums on a treeProcess paint and distance-sum queries on a weighted tree, reporting for each query 2 the total distance from x to all blue vertices.Hard8TreePrefix sum+2No attempts yet5s512 MBJudgeable
Segments in a Regular PolygonCount the orders in which the remaining polygon vertices can be visited so each new segment crosses an existing one and the path closes back to P0.Hard8BacktrackingDynamic programming+2No attempts yet2s512 MBJudgeable
New Store NameSplit each of two short strings into two non-overlapping contiguous pieces so that A+C equals B+D, and output the lexicographically smallest longest result.Hard8StringBrute force+1No attempts yet2s512 MBJudgeable
Multiplying DigitsGiven base B and target N, find the smallest positive integer whose base-B digits multiply to N, or report that none exists.Hard8Number theoryDynamic programming+2No attempts yet3s512 MBJudgeable
Minimum Chain CoverGiven a DAG, find the minimum number of vertex-disjoint directed paths that together cover every vertex.Hard8GraphDynamic programming+1No attempts yet2s512 MBJudgeable
Jack and the BeanbagFind the minimum number of cows Jack needs so that, against adversarial farms, he secures the required count of each bean kind.Hard8Game theoryDynamic programming+1No attempts yet3s512 MBJudgeable
CompensationGiven scheduled trains with known delays, find the smallest start time of a booking whose promised arrival is at least 1800 seconds before any possible real arrival at station N.Hard8Binary searchDynamic programming+2No attempts yet2s512 MBJudgeable
Buying StampsCount the ways to spend exactly K won using N kinds of 1-won stamps and M kinds of 2-won stamps, allowing repeats, modulo prime P.Hard8CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Bridge ParkGiven a connected planar straight-line graph on convex-position vertices, add the fewest non-crossing edges so the graph becomes 2-edge-connected.Hard8GraphGreedy+1No attempts yet1s512 MBJudgeable
VirusGiven a binary tree, find the minimum number of nodes that end up infected when one node may be protected each round.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Knight Moves 2Count knight paths of length at most k on a 2n by 2n board that start at the top-left corner and end on any corner, modulo 1000007.Hard8MatrixDynamic programming+1No attempts yet2s512 MBJudgeable
Sequence TransformationCount length-n integer sequences with entries in [1, 2^k) whose prefix bitwise-OR values are strictly increasing, for n up to 1e18 and k up to 30000.Hard8CombinatoricsBit manipulation+2No attempts yet10s512 MBJudgeable
Rectangular PlazaCount axis-aligned rectangles whose corners include two given lamps and whose interior contains no other lamp, given all X and Y coordinates are distinct.Hard8GeometrySorting+1No attempts yet1s512 MBJudgeable
Dona MinhocaOn a cactus graph, for each query (entry chamber, worm length) decide whether a closed non-backtracking walk of length at most M exists and give the shortest such distance.Hard8GraphDFS+2No attempts yet2s512 MBJudgeable
Ecology PreserveGiven an N by N grid of tree counts, pick a connected set of exactly M cells (M at most 10) maximizing the total tree count.Hard8Dynamic programmingDFS+2No attempts yet2s512 MBJudgeable
Tire PatchesOn a circular tire, cover all hole positions with the minimum total length of uncut patches of two given lengths and return that total length.Hard8Dynamic programmingArray+2No attempts yet2s512 MBJudgeable