Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

Total results3,128 problems

		Topics				Judge
Choose Your Own ArithmeticGiven working digits and exactly W add-or-multiply steps applied left to right from a single digit, decide whether each target value is reachable.	Medium5	Brute forceDynamic programming+2	No attempts yet	2s	512 MB	Judgeable
NukitGiven counts of particles A, B, C, D, two players alternately remove one of five fixed multisets; find who wins under optimal play.	Medium5	Game theoryDynamic programming+2	No attempts yet	1s	128 MB	Judgeable
Super PlumberFind the maximum total coin value on a path from the bottom-left to the bottom-right of a grid where SP moves right, up, or down without revisiting cells.	Medium5	Dynamic programmingImplementation	No attempts yet	1s	128 MB	Judgeable
King Thrór's GoldCount the ways to choose exactly k distinct bar values summing to T, and list all solutions in lexicographic order when there are at most 20.	Medium5	Dynamic programmingBacktracking+2	No attempts yet	1s	128 MB	Judgeable
The Millionaire and the OrphansGiven three orphanages with fixed basket areas and children counts, compute the expected total gift value each orphanage catches as gifts are thrown in order.	Medium5	ProbabilityMath+1	No attempts yet	1s	1024 MB	Judgeable
Wooden SticksGiven n sticks with length and weight, order them to minimize the number of setup steps, where a setup is needed unless both length and weight are nondecreasing from the previous stick.	Medium5	SortingGreedy+1	No attempts yet	1s	128 MB	Judgeable
InvestmentStarting capital grows over at most 40 years by rebuying a portfolio of bonds each year; maximize the final amount.	Medium5	Dynamic programmingGreedy	No attempts yet	1s	128 MB	Judgeable
DivisibilityGiven a sequence and a modulus K, decide whether some choice of + or - before each later element makes the total divisible by K.	Medium5	Dynamic programmingMath+2	No attempts yet	1s	128 MB	Judgeable
RelocationSplit up to 10 furniture items between two cars with capacity limits so that every item gets moved in the fewest number of paired trips.	Medium5	Dynamic programmingBinary search+2	No attempts yet	1s	128 MB	Judgeable
Balanced ChangeGiven counts of five coin types in a drawer and an amount, choose coins to give out so that the imbalance of the remaining coins is minimized.	Medium5	Dynamic programmingBrute force+1	No attempts yet	1s	128 MB	Judgeable
Betting SetsPartition an N by M table of probabilities into groups of one cell per column to maximize the expected number of all-heads groups.	Medium5	Dynamic programmingBit manipulation+2	No attempts yet	1s	128 MB	Judgeable
Apocalyptic AlignmentGiven two A/B strings of equal length, find the minimum number of operations that repaint a contiguous segment with one fruit type to turn the first string into the second.	Medium5	Dynamic programmingGreedy+1	No attempts yet	1s	128 MB	Judgeable
Game DiceGiven up to 13 dice with various face counts and a target total, compute the probability of rolling exactly that sum, to five decimals.	Medium5	Dynamic programmingProbability+1	No attempts yet	1s	128 MB	Judgeable
FootballGiven pairwise win probabilities, find the team most likely to win a fixed single-elimination bracket of 2^n teams.	Medium5	Dynamic programmingProbability+1	No attempts yet	1s	128 MB	Judgeable
Three Bit ComputerGiven a string over {a,b,c}, decide whether an all-uninitialized memory can be initialized to exactly that string with the two given operations.	Medium5	Dynamic programmingGreedy	No attempts yet	1s	32 MB	Judgeable
Digit Sum Over a RangeGiven l and u up to 2e9, find the total of the digit sums of every integer in that inclusive range.	Medium5	MathDynamic programming+2	No attempts yet	1s	128 MB	Judgeable
No Pause TelegraphGiven a string of dots and dashes and seven fixed letter codes, split it into codewords that minimize the resulting message alphabetically, or report that no split exists.	Medium5	Dynamic programmingString+2	No attempts yet	1s	128 MB	Judgeable
PearlsGiven demand and price per pearl for classes in increasing quality order, find the cheapest way to buy all pearls when each class's order may be upgraded to a higher class, paying 10 extra pearls' worth per purchase.	Medium5	Dynamic programmingPrefix sum+1	No attempts yet	1s	128 MB	Judgeable
Afternoon TeaTrack the tea and milk levels in a cup over a sequence of half drinks and refills, and report which ingredient was consumed more.	Medium5	Dynamic programmingMath+1	No attempts yet	3s	32 MB	Judgeable
Chocolate WholesalerGiven n independent bars with individual surprise probabilities, find the probability that a carton has at least k surprises.	Medium5	ProbabilityDynamic programming	No attempts yet	1s	128 MB	Judgeable
Cash DispenserCount 4-digit PINs whose digits appear as a subsequence of every recorded finger-movement sequence.	Medium5	StringDynamic programming+1	No attempts yet	3s	128 MB	Judgeable
PassageSplit n people into groups whose total weight is at most W, minimizing the sum of each group's slowest crossing time.	Medium5	Dynamic programmingBit manipulation+1	No attempts yet	3s	128 MB	Judgeable
ProtocolsCount the length-m strings over k symbols with no run of l equal symbols, then output floor((n/m) * log2(count)).	Medium5	Dynamic programmingCombinatorics+2	No attempts yet	3s	128 MB	Judgeable
BalanceGiven weights, split some into two equal-sum disjoint groups; find the largest weight that can be the heaviest used one.	Medium5	Dynamic programmingSorting+2	No attempts yet	3s	128 MB	Judgeable
BitmapFor each black pixel in an n by m bitmap, output the Manhattan distance to the closest white pixel.	Medium5	BFSGraph+1	No attempts yet	1s	128 MB	Judgeable
The Number of N-k-special SetsCount subsets of {1,...,n} with no two consecutive numbers whose sum exceeds k, for n up to 100.	Medium5	Dynamic programmingCombinatorics	No attempts yet	1s	128 MB	Judgeable
Building BlocksRemove blocks from a tower so the most remaining blocks sit at an altitude equal to their printed number.	Medium5	Dynamic programmingGreedy+1	No attempts yet	1s	128 MB	Judgeable
ElectricityGiven k lines between n homes and m windmills on parallel lines, count subsets of non-crossing lines where every home and windmill has degree at most one, modulo r.	Medium5	Dynamic programmingSorting+1	No attempts yet	1s	128 MB	Judgeable
DiceFind the k-th non-decreasing sequence of length m with values from 1 to n, in lexicographic order.	Medium5	CombinatoricsDynamic programming+2	No attempts yet	1s	128 MB	Judgeable
MatchesFlip the fewest matches in a row so fire lit at the left end spreads through every neighboring pair.	Medium5	Dynamic programmingPrefix sum	No attempts yet	1s	512 MB	Judgeable
Raffle TicketsBuy tickets from baskets with known winning and losing counts to guarantee at least g wins with the fewest tickets.	Medium5	Dynamic programming	No attempts yet	1s	128 MB	Judgeable
WatchtowersFind the maximum sum over any nonempty block of consecutive towers arranged in a circle.	Medium5	Dynamic programmingArray	No attempts yet	1s	128 MB	Judgeable
KonkotenacjaCount the ways to split the word into nonempty pieces joined by the literal separator kot, modulo 1000000007.	Medium5	Dynamic programmingPrefix sum+1	No attempts yet	2s	128 MB	Judgeable
SalesmenGiven a graph and a reported vertex sequence, find the fewest entries to change so consecutive vertices stay put or follow an edge.	Medium5	Dynamic programmingGraph	No attempts yet	1s	128 MB	Judgeable
Graceful Prime DecompositionCount ordered sums of N from primes up to K where no two neighboring primes are equal.	Medium5	Dynamic programmingNumber theory	No attempts yet	1s	128 MB	Judgeable
TaekwondoSort both weight lists and pair players to minimize the total absolute weight difference across all matches.	Medium5	Dynamic programmingSorting	No attempts yet	1s	128 MB	Judgeable
Message BroadcastingCompute the fewest rounds to spread a message from the root when each informed node calls at most one child per round.	Medium5	GreedyTree+2	No attempts yet	1s	128 MB	Judgeable
Servicing ClientsChoose clients whose distance-times-demand costs fit the budget to maximize total priority.	Medium5	Dynamic programmingShortest path	No attempts yet	1s	128 MB	Judgeable
Tug of WarDecide whether N student weights (4 to 30) split into two teams whose total strengths differ by at most X.	Medium5	Dynamic programming	No attempts yet	1s	128 MB	Judgeable
Tiling Up BlocksFind the largest subset of blocks that stacks so both knob counts never decrease from bottom to top.	Medium5	Dynamic programmingSorting	No attempts yet	1s	128 MB	Judgeable
Project staffingAssign at most n hired workers to m projects so the total expected profit from rewards, fines, and conditional wages is maximal.	Medium5	Dynamic programmingProbability+1	No attempts yet	1s	128 MB	Judgeable
77377Split a digit string into dictionary words whose telephone-keypad encoding matches each segment.	Medium5	Dynamic programmingTrie+1	No attempts yet	1s	128 MB	Judgeable
Nested Shrubbery BoxesChoose the largest subset of boxes that nest when every box is rotated to fit strictly inside the next box.	Medium5	Dynamic programmingSorting	No attempts yet	1s	128 MB	Judgeable
Family TreesEach person lists two parents, so answer each query with the inherited share one person contributes to another as a reduced fraction, or report no relation.	Medium5	GraphDynamic programming+1	No attempts yet	1s	128 MB	Judgeable
Reconstructing the Longest Common SubsequenceFind the length of the longest common subsequence of two uppercase strings and output the lexicographically smallest one.	Medium5	Dynamic programmingGreedy	No attempts yet	0.1s	256 MB	Judgeable
PointsPick a subset of targets in a row to maximize the total where each picked target scores based on how many neighbors are also picked.	Medium5	Dynamic programming	No attempts yet	3s	128 MB	Judgeable
The Hopeless QueueCount fillings of the movable spots with equal coin totals so every prefix keeps at least as many 50 coins as 100 coins, modulo 1000000.	Medium5	Dynamic programmingCombinatorics	No attempts yet	2s	128 MB	Judgeable
Frozen SprinklersCut pipes with minimum total force so no water flows from the central node to any leaf sprinkler in the tree.	Medium5	Dynamic programmingTree+1	No attempts yet	3s	128 MB	Judgeable
Freeing Up CapacityChoose RAID-1 sets to convert so the gained capacity reaches e GB while the total size of converted sets is minimal.	Medium5	Dynamic programming	No attempts yet	2s	512 MB	Judgeable
Wrestling Team SelectionSplit up to 100 wrestlers into two teams of nearly equal size so the total weights differ as little as possible.	Medium5	Dynamic programming	No attempts yet	1s	128 MB	Judgeable
Prefix-Free SubsetsCount the subsets of the given word set in which no word is a prefix of another word.	Medium5	TrieDynamic programming+1	No attempts yet	1s	128 MB	Judgeable
Minimum Cost SortingFind the cheapest total of moved values needed to sort the array when moving one element to any position costs its value.	Medium5	Dynamic programmingSorting	No attempts yet	1s	128 MB	Judgeable
Cut the ListSplit the list into K consecutive pieces to minimize the sum of each piece's max minus min.	Medium5	Dynamic programmingIntervals	No attempts yet	2s	128 MB	Judgeable
Number of LocksCount length-n strings over heights 1 to 4 that use at least three distinct heights and have an adjacent pair differing by exactly 3.	Medium5	Dynamic programmingCombinatorics	No attempts yet	1s	128 MB	Judgeable
Tutor SimulationChoose a sequence of teaching, training, and book-buying actions within the time limit that maximizes final cash.	Medium5	Dynamic programmingBrute force	No attempts yet	2s	512 MB	Judgeable
InvestChoose one of five products to buy each month, respecting minimum holding periods, to maximize the total resale value at the end.	Medium5	Dynamic programming	No attempts yet	2s	512 MB	Judgeable
HoleFind the side length of the largest all-zero square in an n by n binary grid given by the positions of its ones.	Medium5	Dynamic programmingMatrix	No attempts yet	2s	512 MB	Judgeable
The Umbrella ProblemEach turn the lemming steps one row down while laser beams rotate, and the task asks whether any grass square in the last row is reachable alive.	Medium5	Dynamic programmingSimulation+1	No attempts yet	1s	128 MB	Judgeable
Club ScheduleCount attendance and key-passing schedules over N days where each day's leader attends and the key stays with attendees.	Medium5	Dynamic programmingCombinatorics	No attempts yet	1s	128 MB	Judgeable
Shark TourSteer a car through a grid tunnel with blocked cells to collect the most sharks and print the tie-breaking action sequence.	Medium5	Dynamic programmingMatrix	No attempts yet	1s	256 MB	Judgeable
Heracles and the Stables of AugeasPick rivers whose water totals at least W so the sum of straight-line digging distances from the stable is smallest.	Medium5	Dynamic programmingGeometry	No attempts yet	1s	256 MB	Judgeable
Distinct Subarray GCDsCount the distinct GCD values taken over all contiguous subarrays for each test case.	Medium5	Number theoryDynamic programming+1	No attempts yet	5s	256 MB	Judgeable
EquatorEach test case gives city profits around a circle and asks for the most profitable contiguous block, or zero when all are losses.	Medium5	Dynamic programmingArray	No attempts yet	1s	256 MB	Judgeable
ShopsPick cells with no shared side in an N by 5 profit grid to maximize the summed profit.	Medium5	Dynamic programmingBit manipulation	No attempts yet	2s	256 MB	Judgeable
Chomsky Normal Form GrammarDecide whether a given string of up to 1000 lowercase letters belongs to the language generated from start symbol S by a CNF grammar.	Medium5	Dynamic programmingIntervals	No attempts yet	5s	256 MB	Judgeable
Zeroing a Binary SequenceCount ordered flip sequences of exactly K moves that turn a given binary sequence into all zeroes.	Medium5	CombinatoricsDynamic programming	No attempts yet	1s	256 MB	Judgeable
Restaurant RatingsCount how many nonnegative score sheets rank no better than the given sheet under total sum first and critic order second.	Medium5	CombinatoricsDynamic programming	No attempts yet	1s	256 MB	Judgeable
Travel CardGiven daily bus and train ride counts, compute the cheapest mix of single fares and 1, 7, and 30 day bus and travel passes.	Medium5	Dynamic programmingPrefix sum	No attempts yet	1s	256 MB	Judgeable
Narrow Art GalleryClose exactly k rooms with no row fully closed and no diagonal closures to keep the maximum total value of open rooms.	Medium5	Dynamic programming	No attempts yet	2s	256 MB	Judgeable
A Walk TogetherTwo walkers follow turn-by-turn routes on a grid, and you compute the most blocks they can walk together by waiting and matching identical directed blocks.	Medium5	Dynamic programmingSimulation	No attempts yet	1s	256 MB	Judgeable
Cent SavingsSplit up to 2000 item prices in order into at most d+1 consecutive groups so the sum of each group rounded to the nearest 10 cents is smallest.	Medium5	Dynamic programmingPrefix sum	No attempts yet	5s	512 MB	Judgeable
Super Pipes and Ant FeedingFind the smallest amount of liquid to pour into the root of a tree so percentage splits with optional squaring pipes still meet every leaf demand.	Medium5	Dynamic programmingTree+1	No attempts yet	1s	32 MB	Judgeable
Marathon 2Run checkpoints 1 to N in order while skipping at most K middle checkpoints to minimize total Manhattan distance.	Medium5	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Meeting TimeFind the smallest total travel time that both cows can achieve on separate downhill paths from field 1 to field N.	Medium5	Dynamic programmingGraph	No attempts yet	1s	256 MB	Judgeable
Restore CalculationCount ways to fill each ? in equal-length strings A, B, and C with digits, leading digits nonzero, so A plus B equals C, modulo 1,000,000,007.	Medium5	Dynamic programmingMath	No attempts yet	8s	512 MB	Judgeable
Two-Area DatabaseRead a fixed sequence of data kinds using a one-slot cache that loads at cost c and serves hits for free, and minimize total read cost.	Medium5	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Pi Day Pie DistributionCount the nondecreasing distributions of n pie pieces among k people with each person getting at least one piece.	Medium5	Dynamic programmingCombinatorics	No attempts yet	1s	256 MB	Judgeable
EmpireFind the fastest route from A to B whose total hull damage stays strictly below K.	Medium5	Shortest pathDynamic programming	No attempts yet	1s	256 MB	Judgeable
Honey Butter ChipArrange the M extra bags within the N fixed bags and pick no two adjacent bags to maximize the chip total.	Medium5	Dynamic programmingArray	No attempts yet	5s	256 MB	Judgeable
Square Piece CutCut an n by m integer-sided rectangle with guillotine cuts into the fewest integer-sided squares.	Medium5	Dynamic programming	No attempts yet	2s	256 MB	Judgeable
Card GameTwo piles of N cards are compared from the top, and the program finds the largest score earned by discarding a smaller right card.	Medium5	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Sequence ArtisanFind the largest product of any contiguous block in an array with values from -2 to 2, then report it modulo 1000000007.	Medium5	GreedyDynamic programming+1	No attempts yet	1s	256 MB	Judgeable
Traveling Salesman Tour 2Find the cheapest tour that starts at one city, visits each of N cities exactly once, and returns to the start using the given directed costs.	Medium5	Dynamic programmingBit manipulation+1	No attempts yet	2s	256 MB	Judgeable
Lucky Cookie BakeryAssign each dough ball to one of two ovens with different baking times to minimize the time the slower oven finishes.	Medium5	Dynamic programming	No attempts yet	5s	128 MB	Judgeable
Explosive MaterialsSplit conflicting materials into two safe boxes and minimize the fuller box size.	Medium5	GraphBFS+1	No attempts yet	3s	256 MB	Judgeable
The Missing PermutationFill the zeros with the missing values to maximize the length of the longest increasing subsequence.	Medium5	GreedyDynamic programming+1	No attempts yet	15s	256 MB	Judgeable
Attendance AwardCount length-N strings over L, O and A with at most one L and no three consecutive As for each N up to 3000.	Medium5	Dynamic programmingCombinatorics	No attempts yet	1s	256 MB	Judgeable
Longest Bitonic SubsequenceGiven a sequence of up to 1000 numbers, find the length of its longest subsequence that strictly rises then strictly falls.	Medium5	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Criboard Max APress A, select all, copy, and paste within N keystrokes to show the most As possible.	Medium5	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
Football scorelinesCount the ordered scoring sequences by both teams that reach the given final score under the listed play values, modulo 1000000009.	Medium5	Dynamic programmingCombinatorics	No attempts yet	2s	256 MB	Judgeable
Vampire DiceCompute the success probability of scoring at least y points from x exploding ten-sided dice where 8 to 10 score and 10 grants an extra roll.	Medium5	ProbabilityDynamic programming	No attempts yet	1s	256 MB	Judgeable
TV WarPick non-overlapping weekly TV programs to maximize the total preference score.	Medium5	Dynamic programmingSorting+2	No attempts yet	1s	256 MB	Judgeable
RobberiesPick a subset of banks that maximizes the stolen money while the combined capture probability stays strictly below the given limit.	Medium5	Dynamic programmingProbability	No attempts yet	1s	256 MB	Judgeable
Combat OddsGiven N independent battles with win chance p, compute the chance that a losing run of at least L occurs.	Medium5	ProbabilityDynamic programming	No attempts yet	1s	256 MB	Judgeable
CarrotFor each N, count the steps to reach zero by subtracting one when the pile splits into equal piles of at least two and subtracting two otherwise.	Medium5	Number theoryDynamic programming	No attempts yet	1s	256 MB	Judgeable
Atomic ComputerCount the length-y signed-binary strings over -1, 0 and 1 whose digits weighted by powers of two sum to x.	Medium5	Dynamic programmingBit manipulation	No attempts yet	1s	256 MB	Judgeable
Gimli's GulletPack unlimited servings of M foods into capacity C for the most calories, breaking ties by the lexicographically smallest serving counts.	Medium5	Dynamic programming	No attempts yet	1s	256 MB	Judgeable
SurfPick waves with no wait-time overlap so the sum of fun points is as large as possible.	Medium5	Dynamic programmingSorting+1	No attempts yet	4s	256 MB	Judgeable
Feast CoinsCount ways to reach total S with owned coins so that every chosen coin value appears the same number of times.	Medium5	Dynamic programmingCombinatorics	No attempts yet	3s	256 MB	Judgeable
King's WalkMove a king n cells over a letter grid to match the motto in as many positions as possible, breaking ties by the smallest coordinate sequence.	Medium5	Dynamic programmingMatrix	No attempts yet	1s	256 MB	Judgeable