cho.sh

Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

All problems
Total results3,128 problems
TopicsJudge
Airport CoffeeGiven spaced coffee carts along a corridor, choose where to buy cups so the total walking time with alternating slow and fast phases is minimized, output as a fraction.Hard8Dynamic programmingGreedy+2No attempts yet6s512 MBJudgeable
Royal TaxGiven a tree of cities, each with tax gold and a carriage of capacity C, find the minimum total distance to collect all gold into the capital vault.Hard8TreeDynamic programming+2No attempts yet1s1024 MBJudgeable
LinearvilleFor each query, find the length of a shortest path between two grid crossings when the path must alternate directions at every crossing.Hard8Shortest pathGraph+2No attempts yet1s1024 MBJudgeable
The Uncertainty of PoliticsEach hearing has a start time and a uniform integer length in [a,b]; pick hearings to attend fully so the expected count is maximized.Hard8Dynamic programmingProbability+2No attempts yet2s512 MBJudgeable
Avoiding AirportsFind a flight itinerary from country 1 to country n minimizing the sum of squared waiting times at airports.Hard8GraphShortest path+2No attempts yet3s512 MBJudgeable
Spinning Up PalindromesGiven a digit string of up to 40 wheels, find the minimum number of single-digit advances (with cascading carries) to reach a palindrome.Hard8Dynamic programmingGreedy+2No attempts yet1s512 MBJudgeable
Flipping OutCount the strings that, added to the given patterns, make the flip rule reproduce the given flip sequence, or -1 if infinitely many work.Hard8StringDynamic programming+2No attempts yet2s512 MBJudgeable
Hidden SupervisorsGiven a partial parent array, fill in the missing supervisors to complete a rooted tree and maximize the number of disjoint parent-child pairs.Hard8TreeDynamic programming+2No attempts yet3s512 MBJudgeable
Haggling With a WitcherGiven an unknown target fee uniform on [L,R], maximize expected gold by naming fees over time, where each attempt or save-reload costs 100 ms and time is capped by T.Hard8Dynamic programmingMath+2No attempts yet2s512 MBJudgeable
Competition DayFind the shortest simple path from F to C, then the shortest simple path different from it, and report their time difference.Hard8GraphShortest path+2No attempts yet2s512 MBJudgeable
Bracket PathGiven a directed graph whose edges carry bracket symbols, find the length of a shortest path from s to t whose edge labels form a correct bracket expression, or -1 if none exists.Hard8GraphBFS+2No attempts yet0.2s512 MBJudgeable
CounterspellsAfter each of n leaf insertions into a rooted tree, find the minimum number of vertex recolorings needed to restore the unique well coloring.Hard8TreeDFS+2No attempts yet1s1024 MBJudgeable
IronmanFind the fastest path across n horizontal layers with different speeds, entering and exiting each layer boundary at an optimal x position, and print the minimum travel time.Hard8Dynamic programmingMath+2No attempts yet2s512 MBJudgeable
EvenOddSum f(X) for every X in [L, R], where f counts the steps of a process that halves even numbers and adds 1 to odd numbers until reaching 1. The bounds reach 10^18.Hard8MathBit manipulation+2No attempts yet2s512 MBJudgeable
Lights OutFind the shortest walk from room 1 to room 0 whose switches span exactly the set of reachable lamp states, counting repeated visits.Hard8GraphBit manipulation+2No attempts yet2s512 MBJudgeable
Boom!Count the ways to fold a strip of N segments so that no two chemically coated faces touch.Hard8Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Building BridgesPick a subset containing the first and last pillars, pay (h_i-h_j)^2 for each bridge section and w_i for each skipped pillar, and minimize the total.Hard8Dynamic programmingGreedy+1No attempts yet3s128 MBJudgeable
ChaseJerry walks a simple path in a tree, dropping up to v breadcrumbs that zero out neighbor pigeon counts; maximize the pigeons Tom later meets minus the pigeons Jerry met.Hard8TreeDynamic programming+1No attempts yet4s512 MBJudgeable
Embedding EnumerationCount the ways to place a labeled tree's nodes into a 2 by n grid so node 1 sits at the top-left, edges touch, and no cell repeats, modulo 1e9+7.Hard8TreeDFS+2No attempts yet4s512 MBJudgeable
Kitchen KnobsGiven n seven-digit knobs, find the fewest range rotations (each turning a contiguous block by the same amount) so every knob reads its maximum-power digit.Hard8GreedyImplementation+2No attempts yet3s512 MBJudgeable
The Great WallEach design picks two length-r intervals whose overlap height adds extra cost; find the k-th smallest total wall height over all interval pairs.Hard8Binary searchPrefix sum+2No attempts yet3s512 MBJudgeable
Fence InvasionCount how many distinct convex polygons can be formed as the convex hull of some subset of at least 3 of the given points, modulo 1e9+7.Hard8GeometryCombinatorics+2No attempts yet5s512 MBJudgeable
Mindol TourCount Hamiltonian cycles starting and ending at trampoline 0 in a graph where node 0 connects to all and node i reaches nodes within distance A_i, with A_i at least i.Hard8Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
The Infosci Pirate CrewGiven N islands with coordinates, treasure values, and safe hardness, choose a monotone northeast path and a hardness interval to maximize collected value minus interval length.Hard8Dynamic programmingSorting+2No attempts yet1s512 MBJudgeable
Directing the TreeCount the orientations of a tree's edges such that every given vertex pair has a directed path one way or the other, modulo 1e9+7.Hard8TreeDFS+2No attempts yet2s256 MBJudgeable
Parallel LinesGiven up to 16 distinct points, pair them up to maximize the number of parallel pairs among the drawn segments.Hard8Bit manipulationDynamic programming+2No attempts yet10s512 MBJudgeable
Pizza DeliveryGiven a directed weighted graph with source 1 and target 2, each day flips the direction of one distinct edge; report whether the shortest path distance shrinks, stays equal, or grows (or becomes unreachable).Hard8GraphShortest path+1No attempts yet2s512 MBJudgeable
HomeworkGiven n assignments split into two courses with release days and deadlines, simulate fixed tie-break rules over adaptive coin choices and find the maximum and minimum number he can finish.Hard8Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
MarsFor each query substring, find the minimum number of bit flips that make it match no substring of the DNA, or report Impossible.Hard8String matchingDynamic programming+1No attempts yet2s512 MBJudgeable
RetroGiven a grid where the player moves horizontally while objects fall one row per turn, collect brackets to form the longest valid expression and output the lexicographically smallest one of that length.Hard8Dynamic programmingGreedy+2No attempts yet0.5s512 MBJudgeable
CesteFor each city, find the route from city 1 that minimizes the product of total travel time and total cost, or report -1 if unreachable.Hard8GraphShortest path+2No attempts yet2.5s128 MBJudgeable
Guardians of the LunaticsSplit a row of L cells into at most G contiguous nonempty blocks, where a block of length k multiplies each member's craziness by k, to minimize the total cost.Hard8Dynamic programmingDivide and conquer+2No attempts yet7s512 MBJudgeable
Off the RailsGiven n cities sorted by x, cover them with straight non-vertical segments so that the sum of squared vertical distances plus C per segment is minimized.Hard8Dynamic programmingGeometry+2No attempts yet5s512 MBJudgeable
Concert Attendance SchedulesCount the ways to pick increasing day positions matching a target band sequence, where each pick must wait h_b+1 days after that band's previous pick.Hard8Dynamic programmingStringNo attempts yet0.3s128 MBJudgeable
Binary TransformationsGiven starting bits, target bits, and per-bit costs, flipping a bit i costs the sum of costs of all bits equal to 1 after the flip; find the minimum total price to reach the target.Hard8Dynamic programmingGreedy+2No attempts yet1s256 MBJudgeable
TetrisOn a 3-wide, 10-tall Tetris board, pieces from a repeating shape sequence arrive forever; maximize how many land before the top fills, or output -1 if play can continue indefinitely.Hard8Dynamic programmingSimulation+2No attempts yet2.5s512 MBJudgeable
Canonical Coin SystemsGiven a sorted coin system, decide whether the greedy algorithm always makes change with the fewest coins, or whether some amount is a counterexample.Hard8Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
Cat and MiceFind the smallest initial speed v so the cat can visit all points in some order, each arrival at or before its deadline, with speed multiplied by m after every meal.Hard8Binary searchDynamic programming+2No attempts yet2s512 MBJudgeable
Vera and Canada DayAfter each laser is added, choose one of four L-shaped firing orientations per laser so that the total awe from lasers hit by beams is maximized.Hard8Dynamic programmingGraph+2No attempts yet2s512 MBJudgeable
Vera and the Engineering BuildingsGiven a tree of N nodes with distinct hidden values and inspection costs, find the minimum total cost of an adaptive strategy that is guaranteed to locate a local maximum.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
A Simple FunctionDefine f via a Pascal-like recurrence that resets to 0 whenever the sum is divisible by prime M, and answer up to 10^4 queries f(a, b, M) modulo 10^9+7.Hard8Number theoryCombinatorics+2No attempts yet1s512 MBJudgeable
DeforestationCut trees in a grid so the top-left and bottom-right cells become connected, minimizing the total walking time to cut each tree and haul it back to the mill.Hard8GraphShortest path+2No attempts yet2s512 MBJudgeable
Picking Numbers on a CirclePick exactly K numbers from a circle of N values so that no two chosen are adjacent, maximizing the sum.Hard8Dynamic programmingGreedy+2No attempts yet1s512 MBJudgeable
K-Uniform StringCount binary strings of length N where, for each of M given intervals, every length-K substring inside it contains the same number of ones, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet1s256 MBJudgeable
Programming Duel TournamentChoose a duel schedule for N contestants, where the higher skill always wins and each contestant duels at most L_i times, to maximize total duel XOR interest minus fatigue.Hard8GreedyTree+2No attempts yet2s256 MBJudgeable
Making a Beautiful PuzzleFill each square of an N by M board with one of four colors so that orthogonal neighbors differ, maximizing total beauty and counting optimal placements modulo 1e9+7.Hard8Dynamic programmingBacktracking+2No attempts yet3s128 MBJudgeable
Tree SeparatorGiven a tree, delete all vertices on some simple path between two chosen vertices; maximize the number of remaining components of size at least K.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Coin SliderChoose the largest subset of at most 16 coins and an order of moves so no moving coin ever collides with a stationary or already-moved coin.Hard8GeometryBit manipulation+2No attempts yet2s512 MBJudgeable
MultisectGiven a hidden failing revision among n candidates and up to K simultaneous tests per round, find the strategy that minimizes expected total cost when a round with i failures costs T_i.Hard8Dynamic programmingBinary search+2No attempts yet2s512 MBJudgeable
Non-redundant DriveIn a tree where each node gives g fuel and each edge costs d, find the longest simple path from any start such that the running fuel never drops below zero, refueling once per node.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Dango MakerChoose disjoint horizontal or vertical runs of three cells reading R, G, W in order on an N by M grid, maximizing how many such sticks fit.Hard8Dynamic programmingMatrix+2No attempts yet2s256 MBJudgeable
Commuter PassPick a shortest S-T path to make free, then find the minimum U-V travel cost, where edges on that path cost 0 and others cost their fare.Hard8GraphShortest path+1No attempts yet2s256 MBJudgeable
Maximum Interval Sum 2For a sequence with point updates, answer range queries for the maximum of U times a subarray sum plus V times its length minus one.Hard8Segment treeDivide and conquer+2No attempts yet1s256 MBJudgeable
Blocks 4Count the tilings of an N by M rectangle using blocks of size k by N (rotatable) for k from 1 to N, modulo 1999, where M can be as large as 1e10.Hard8Dynamic programmingMath+2No attempts yet1s256 MBJudgeable
Lifeguards (Platinum)Fire exactly K of N lifeguard shifts to maximize the total time covered by at least one remaining shift.Hard8Dynamic programmingSorting+2No attempts yet2s512 MBJudgeable
Cow at Large (Platinum)In a tree, for each barn find the minimum number of farmers placed at exits needed to catch Bessie, who starts there and runs for the nearest exit at equal speed.Hard8TreeDFS+2No attempts yet4s512 MBJudgeable
Ascending PhotoGiven a sequence of n heights, find the minimum number of cuts so the pieces can be reordered into a nondecreasing sequence.Hard8GreedySorting+2No attempts yet3s512 MBJudgeable
Hit of the SeasonFind the shortest print matrix over R, G, B that can reproduce a wallpaper string, where specified stripes must never be overprinted and at most 19 stripes are unspecified.Hard8StringBrute force+2No attempts yet2s512 MBJudgeable
The StagingGiven n gangsters each aiming at a distinct target, count survivors after each of q updates to the shooting time of one gangster.Hard8GraphDynamic programming+2No attempts yet2s512 MBJudgeable
The CaptainFind the minimum total north-south distance the Captain must steer on a route from island 1 to island n, where he handles one axis per leg.Hard8GraphShortest path+1No attempts yet2s512 MBJudgeable
Two tetrominoesPlace two non-overlapping tetrominoes anywhere on an N by M grid so the total of the covered cells is maximized.Hard8Brute forceDynamic programming+1No attempts yet2s512 MBJudgeable
Catch the PlaneChoose an adaptive strategy of buses to maximize the probability of reaching station 1 by time k, where each bus runs independently with a known probability.Hard8Dynamic programmingProbability+2No attempts yet10s1024 MBJudgeable
Gem IslandAt each of d steps a uniformly random gem splits in two; find the expected total held by the r largest holders after d splits.Hard8ProbabilityDynamic programming+2No attempts yet3s1024 MBJudgeable
xor gameCount sequences of n xor masks (each below 2^31) that carry a to b, modulo 1e9+7.Hard8MathCombinatorics+2No attempts yet0.5s128 MBJudgeable
New BarnsProcess online queries that add a leaf to a growing forest or ask for the eccentricity (distance to the farthest node) of a given node.Hard8TreeGraph+2No attempts yet2s512 MBJudgeable
DuathlonCount ordered triples (s, c, f) of distinct vertices such that some simple path visits s, then c, then f, in an undirected graph with n up to 1e5.Hard8GraphBFS+2No attempts yet1s1024 MBJudgeable
RecipeBuy ingredients on some days, hold each in the fridge until a later day, cook it there if freshness stays at least L_i, and maximize the total of F_i minus elapsed days times C_j; print Impossible if day N can't be a cooking day.Hard8Dynamic programmingGreedy+2No attempts yet1s1024 MBJudgeable
SixN has at most six distinct prime divisors; count the sequences of divisors greater than 1 where each new divisor shares a factor with at most one earlier entry, modulo 1e9+7.Hard8CombinatoricsMath+2No attempts yet2s512 MBJudgeable
ExperienceGiven a rooted tree with values on nodes, partition nodes into vertex-disjoint downward paths to maximize the sum over paths of (max value minus min value).Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Namje AdventureN people hang at depths 1 to N and must reach the bottom depths D-N+1 to D; only the highest person can move down 1 to L steps, find the least total energy.Hard8Dynamic programmingGreedy+1No attempts yet3s512 MBJudgeable
Random Number GeneratorGiven how many values from 1 to N have been seen zero or one time, find the expected number of draws until every value appears at least twice.Hard8ProbabilityDynamic programming+2No attempts yet2s512 MBJudgeable
Sacred ScarecrowsCount subsets of empty cells in an R x C grid, modulo 1e9+7, such that every row has a scarecrow and every pair of consecutive columns has one.Hard8Dynamic programmingBit manipulation+2No attempts yet2s512 MBJudgeable
PathsCount simple paths in a vertex-colored graph where every vertex on the path has a distinct color, counting both directions separately.Hard8GraphDFS+2No attempts yet3s1024 MBJudgeable
Nordic CampingGiven a grid with rocky cells blocked, answer queries each asking for the area of the largest all-usable square subgrid that contains a specified water source cell.Hard8Dynamic programmingBinary search+2No attempts yet2s512 MBJudgeable
Split and MergeGiven two tilings of a 1xL board by 1x1 and 1x2 pieces, find the minimum number of split/merge operations to transform one into the other and count the ways.Hard8Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
Team SelectionSplit N players into two equal teams so the difference between the captains' total scores is minimized, choosing the lexicographically smallest assignment.Hard9Divide and conquerDynamic programming+2No attempts yet2s128 MBJudgeable
DominoesCount how many ways a given set of dominoes can be partitioned into one or more edge-disjoint cycles using every piece exactly once.Hard9GraphCombinatorics+2No attempts yet2s128 MBJudgeable
Diameter of a CactusGiven a cactus graph (each edge in at most one cycle), compute the maximum shortest-path distance between any two vertices.Hard9GraphDFS+2No attempts yet1s128 MBJudgeable
Coloring RectanglesGiven N rectangles, choose exactly K of them to maximize the total visible union area under a max-index-wins overlap rule, picking the lexicographically smallest tie-break.Hard9GeometryDynamic programming+2No attempts yet2s128 MBJudgeable
Maximum Matching in an Almost Bipartite GraphCompute the maximum matching size in a graph formed by two paths (A and B) joined by up to 50 extra cross edges.Hard9GraphDynamic programming+2No attempts yet2s128 MBJudgeable
Small SquaresDetermine the winner of an optimal-play coloring game on a grid where players color 1x1 or restricted 2x2 squares, using Sprague-Grundy analysis.Hard9Game theoryDynamic programming+2No attempts yet2s512 MBJudgeable
Pro Gamer YoungsikGiven time and resource budgets, compute the maximum number of top-tier units obtainable from a chain of unit upgrades where each unit can repeatedly spawn the next type.Hard9Dynamic programmingGreedy+2No attempts yet2s128 MBJudgeable
CowboysGiven N cowboys shooting in turns with hit probabilities and optimal target choice under strategic play, compute each cowboy's probability of being the sole survivor.Hard9Game theoryDynamic programming+2No attempts yet2s128 MBJudgeable
Hangul-Missing NumbersGiven which Hangul letters are forbidden, find the N-th positive integer up to 10^52-1 whose Korean numeral representation avoids all forbidden jamo, using digit DP over decomposed syllables.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Roller CoasterFind a self-avoiding path from top-left to bottom-right on a grid up to 1000x1000 that maximizes the sum of visited cells' joy values.Hard9Dynamic programmingGraph+1No attempts yet1s256 MBJudgeable
Beautiful ArchipelagoFor each queried sea level, count unordered pairs of islands (connected land regions after flooding) that are translation-equivalent in shape, over up to 1000x1000 grid and 100000 queries.Hard9Union-findHash map+1No attempts yet2s128 MBJudgeable
Chip RoutingAssign each marked point on a square chip a direction toward a side so that drawn segments never cross or pass through other points, minimizing the total segment length.Hard9Dynamic programmingGreedy+2No attempts yet1s128 MBJudgeable
Once You Shoot, You Cannot StopGiven board dimensions and bead counts per color, arrange beads and clear groups to maximize the sum of squared group sizes.Hard9CombinatoricsDynamic programming+1No attempts yet1s128 MBJudgeable
Protein IdentificationGiven peaks from an imperfect MS2 experiment, find the minimum number of noise peaks over all P/Q proteins whose total mass equals the largest peak.Hard9Dynamic programmingGreedy+2No attempts yet1s512 MBJudgeable
DNA SequencesGiven a DNA pattern with wildcards and a rank R, find the R-th lexicographic matching string that decomposes into at most K non-decreasing runs.Hard9Dynamic programmingCombinatorics+2No attempts yet1s128 MBJudgeable
ZooChoose cages to empty on a circle so that the most children watching 5-cage arcs become happy, where each child needs one feared animal removed or one liked animal kept.Hard9Dynamic programmingBit manipulation+2No attempts yet2s128 MBJudgeable
Nice PrefixesCount length-L strings over a K-letter alphabet where every prefix keeps all symbol counts within 2 of each other, modulo 1e9+7, with L up to 1e18.Hard9Dynamic programmingCombinatorics+2No attempts yet1s128 MBJudgeable
Planning Rolling BlackoutsPartition an h by w grid by recursive guillotine cuts so that the heaviest set of groups left powered stays within capacity, maximizing the group count and then the reserve.Hard9Dynamic programmingPrefix sum+2No attempts yet3s512 MBJudgeable
A Broken DoorGiven a grid maze with card-locked doors on some walls, find the fewest cards that always suffice to reach the exit whichever single door is broken, or -1 if some broken door cuts off the exit.Hard9GraphShortest path+2No attempts yet3s128 MBJudgeable
Old MemoriesGiven pieces of an original text and an altered copy with at most d edits, list all original strings whose edit distance to the copy is at most d and where every position lies inside some piece occurrence.Hard9String matchingDynamic programming+2No attempts yet10s128 MBJudgeable
Around the TrackFind the Eulerian circuit of a planar-ish graph whose total turning cost is minimized, where each degree-4 node requires choosing how to pair its incident edges.Hard9GraphDynamic programming+2No attempts yet1s128 MBJudgeable
The Floor BricksCover a column-height profile of a bare floor with rotated 3x3 polyomino bricks of given prices, minimizing total cost.Hard9Dynamic programmingImplementation+1No attempts yet1s128 MBJudgeable
Navi NavigationGiven a weighted undirected graph with fruit types on nodes and multiple queries, find for each pair a shortest path that visits exactly one node of every fruit type.Hard9GraphShortest path+2No attempts yet1s128 MBJudgeable
TablesCount the tilings of a polyiamond on a triangular grid by isosceles trapezoids made of three unit triangles, given the shape's boundary as a sequence of grid nodes.Hard9Dynamic programmingGeometry+2No attempts yet1s128 MBJudgeable
Synnerg LifeformGiven rewriting rules that merge adjacent synnergs with multiplicative lifetimes, find all maximum-lifetime synnergs obtainable by fully unifying some contiguous block of each input sequence.Hard9Dynamic programmingIntervals+2No attempts yet1s128 MBJudgeable