cho.sh

Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

All problems
Total results3,128 problems
TopicsJudge
Largest Increasing SubmatrixGiven a matrix, find the largest rectangular submatrix whose row-by-row linearization is strictly increasing.Hard8Dynamic programmingMatrix+1No attempts yet2s512 MBJudgeable
Number of DivisorsGiven a, b, c up to 2000, compute the sum over all i<=a, j<=b, k<=c of the divisor count of i*j*k, modulo 2^30.Hard8Number theoryMath+2No attempts yet2s512 MBJudgeable
It looks like the Fibonacci sequence, but...Sum F_i times i^k for i from 1 to n, where F is Fibonacci with F_1=1, F_2=2, and n can reach 10^17.Hard8MathDynamic programming+2No attempts yet2s512 MBJudgeable
Five-Dimensional ChocolateCount the ways to tile a 2x2x2x2xn five-dimensional box with 1x1x1x1x2 domino pieces, modulo 1000000007.Hard8Dynamic programmingMath+1No attempts yet2s512 MBJudgeable
Determinants and GCDFor a tridiagonal matrix with a fixed pattern, let D(k) be its k-by-k determinant and compute the sum of gcd(D(i), D(N)) for i from 1 to N, modulo 1e9+7.Hard8MathNumber theory+2No attempts yet2s512 MBJudgeable
Maximum Tent VolumeAssign n poles of given heights to a central hole and n-1 fixed holes around it to maximize the total volume of the resulting triangles.Hard8GeometryDynamic programming+2No attempts yet2s512 MBJudgeable
Calculating TaxesOn a tree where each house picks a divisor of its income, maximize the total sum of chosen values so that every pair of adjacent houses picks coprime values.Hard8Dynamic programmingTree+2No attempts yet8s512 MBJudgeable
HikingGiven directed step costs on a grid with no negative cycles, find the average shortest path over all ordered pairs of distinct cells, rounded up.Hard8GraphShortest path+2No attempts yet10s512 MBJudgeable
RtetrisGiven a fixed 6 by 7 pit and a hand of up to 200 Tetris pieces, decide if all pieces can be placed without creating a gap, and maximize cleared rows.Hard8Dynamic programmingSimulation+1No attempts yet2s512 MBJudgeable
Subsets whose lexicographic order matchesCount non-empty subsets of the integers from A to B whose numeric order equals their lexicographic decimal order, modulo P.Hard8CombinatoricsDynamic programming+2No attempts yet8s512 MBJudgeable
Camera ControlMembers move along timed polygonal routes around a fixed camera, and you may switch followers only when two members lie on the same ray; maximize total time filming a singing member.Hard8GeometryDynamic programming+1No attempts yet8s512 MBJudgeable
Controlled TournamentCount knockout brackets of minimum height in which player M wins the tournament, given a fixed win relation over N up to 16 players.Hard8Divide and conquerDynamic programming+2No attempts yet8s512 MBJudgeable
Palindrome cipher decryptionFor each string, find its longest palindromic subsequence and output the lexicographically smallest one among those of maximal length.Hard8Dynamic programmingString+2No attempts yet8s512 MBJudgeable
The Extreme SlalomGiven up to 12 disjoint line-segment gates in order, find the shortest path that touches each gate in sequence.Hard8GeometryDynamic programming+1No attempts yet8s512 MBJudgeable
Eight PrincesCount the ways to seat eight distinct princes on N round-table seats so that no two occupy adjacent seats or opposite seats (opposite only when N is even).Hard8CombinatoricsMath+2No attempts yet8s512 MBJudgeable
ExamGiven each student's fixed semester points and a distribution of exam points, find the probability that the grade string avoids all forbidden substrings.Hard8Dynamic programmingString matching+2No attempts yet1.5s512 MBJudgeable
Internet TroublePlace 1 to N stations on a line of towns to minimize station cost plus weighted cable cost, where each house connects to the nearest station.Hard8Dynamic programmingDivide and conquer+2No attempts yet2s512 MBJudgeable
Washroom Satisfaction IndexAfter each point update to guest washroom times, compute the minimum sum over assignments of wait-plus-service times to W washrooms, where each washroom serves a subset in some order.Hard8GreedySorting+2No attempts yet10s512 MBJudgeable
Binary StringsCount binary strings whose length lies in [L, R], is a multiple of K, and contains no two adjacent 1s, modulo 1e9+7.Hard8MathCombinatorics+2No attempts yet1s512 MBJudgeable
Printing PressGiven a DAG of book-ordering constraints, choose how many days to shorten each book so all finish within X, minimizing printing plus shortening cost.Hard8Dynamic programmingGraph+2No attempts yet10s512 MBJudgeable
Arranging HatEach of n m-digit strings may have individual digits rewritten; find the minimum number of digit changes so the sequence becomes nondecreasing.Hard8Dynamic programmingGreedy+2No attempts yet5s512 MBJudgeable
ZoltanCero builds a deque by placing each array element on the left or right in order; over all 2^(N-1) builds, find the longest strictly increasing subsequence length and the total number of subsequences attaining it, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet1s32 MBJudgeable
Bipartite BlanketCount vertex subsets of a weighted bipartite graph whose total weight is at least t and that some matching covers completely.Hard8Dynamic programmingBit manipulation+2No attempts yet3s512 MBJudgeable
PasswordsCount length A to B alphanumeric passwords with mixed case and a digit that avoid blacklist substrings, where digits can stand in for similar letters.Hard8Dynamic programmingString matching+2No attempts yet2s512 MBJudgeable
LefkaritikaGiven a grid with blocked points, count the maximum number of axis-aligned square items of any side length that can be placed without covering blocked points, respecting placement order and same-size non-overlap rules.Hard8ArrayDynamic programming+2No attempts yet2s512 MBJudgeable
CruiseChoose a closed polygonal cruise from Piraeus through the islands so that collected point value divided by route length is maximized.Hard8GeometryDynamic programming+2No attempts yet2s512 MBJudgeable
Delight for a CatChoose sleep or eat each hour to maximize total delight, with at least ms sleep and me eat hours in every window of k consecutive hours.Hard8Dynamic programmingSliding window+2No attempts yet2s512 MBJudgeable
Timpani RetuningChoose tunings for up to 4 ordered drums before each of N notes so the shortest retuning interval time is maximized; output that time rounded to two decimals.Hard8Binary searchDynamic programming+2No attempts yet2s512 MBJudgeable
Field TripGiven a graph where each vertex has degree at most 2, delete edges so that the remaining components are cliques of size exactly K, maximizing total covered vertices then minimizing deletions.Hard8GraphUnion-find+2No attempts yet2s512 MBJudgeable
K-th good stringGiven a bracket string S, list the distinct good strings that appear as subsequences in lexicographic order and print the K-th one.Hard8Dynamic programmingString+1No attempts yet2s512 MBJudgeable
K representatives on a lineFor each K from 1 to N, place K real points on a line to minimize the total distance to all given points.Hard8Dynamic programmingDivide and conquer+2No attempts yet2s512 MBJudgeable
BitstockGiven share prices, income rates, and a support forest where each owned share can subsidize its children at half price, find the minimum time until income reaches P per second.Hard8GreedyTree+2No attempts yet1s128 MBJudgeable
Substring appearing twiceGiven a string and at most K letter replacements, maximize the length of the longest substring that occurs at two different starting positions, allowing overlap.Hard8StringBinary search+2No attempts yet6s128 MBJudgeable
SortFor an array of at most 8 elements, compute the expected number of random-swap steps until sorted for two different swap schemes.Hard8ProbabilityDynamic programming+1No attempts yet2s128 MBJudgeable
ZvonimirFind the minimum number of operations (type one letter, or copy a contiguous block of already typed text and append it) to produce string X.Hard8Dynamic programmingString+2No attempts yet2s128 MBJudgeable
Permutations that contain a wordCount distinct permutations of A that contain B as a contiguous substring, modulo 10007.Hard8Dynamic programmingCombinatorics+2No attempts yet2s128 MBJudgeable
Restaurant RecommendationsRestaurants recommend each other through a favorite digraph; find the cheapest cost to visit exactly k restaurants for every k, where each step's price depends on whether the recommender is a favorite of the current restaurant.Hard8GraphDynamic programming+2No attempts yet3s128 MBJudgeable
TripsCount assignments of N people to two trips, each internally a clique, at least A and B people, covering everyone, modulo 10007.Hard8GraphCombinatorics+1No attempts yet0.5s128 MBJudgeable
SamtrisGiven N marked cells in a 7-column grid, find the fewest 3x1 bars (vertical or horizontal) that can be dropped so all marked cells end up covered.Hard8Dynamic programmingGreedy+2No attempts yet5s128 MBJudgeable
Scout GatheringsOn a tree, support adding a member at a city and querying the sum of weighted distances from all members to the current gathering city, which moves along edges.Hard8TreeDFS+2No attempts yet1s128 MBJudgeable
ParticlesCount functions from N chambers to themselves such that applying the function K times returns every element to its start, modulo M.Hard8CombinatoricsDynamic programming+1No attempts yet5s64 MBJudgeable
Titteop LandPartition the line into K consecutive groups so the sum of pairwise awkwardness inside every group is minimized.Hard8Dynamic programmingDivide and conquer+1No attempts yet2s512 MBJudgeable
Sticks and CarrotsChoose a subset of at least three vertices of a convex polygon so every carrot lies strictly inside the new polygon, minimizing its area.Hard8GeometryDynamic programming+2No attempts yet2s512 MBJudgeable
Son of DurinGiven a grid with walls, teleport pads, and up to 15 coin caves, find the most gold collectible within L moves and P teleports.Hard8BFSDynamic programming+2No attempts yet2s512 MBJudgeable
FunctionCount functions on {1..n} whose eventual image (the set of values reached after iterating long enough) has size exactly k, modulo 1e9+7.Hard8CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
The Lazy PostmanGiven a directed weighted graph on n cities, find the minimum total distance of a walk with exactly n cities visited in sequence (n-1 moves), where the same city may repeat.Hard8GraphShortest path+2No attempts yet2s512 MBJudgeable
Splitting Game LevelsPartition n levels into k consecutive groups to minimize the expected total time of a random coin-draw process, and print it to six decimals.Hard8Dynamic programmingDivide and conquer+2No attempts yet2s512 MBJudgeable
Beautiful GraphOver all complete graphs on N vertices whose edges cost 1 or 2, sum the number of minimum spanning trees that are paths (every degree at most 2).Hard8GraphMinimum spanning tree+2No attempts yet2s512 MBJudgeable
Wolves 2Count binary strings of length N in which every given interval contains at most two ones, modulo 1e9+7.Hard8Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
Coprime NeighborsGiven a set of up to 50 distinct integers, insert the fewest new distinct positive integers so that consecutive values in sorted order are coprime.Hard8MathNumber theory+2No attempts yet2s512 MBJudgeable
f(X) = A + X + B + X + CCount occurrences of pattern F in the K-fold string expansion f(X)=A+X+B+X+C applied to S, modulo 1e9+7.Hard8String matchingDynamic programming+2No attempts yet2s512 MBJudgeable
Road ConstructionCount the ways to place exactly M undirected edges among N houses, each edge joining houses at distance at most K, so that every house has even degree, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Block stackingCount structures built on one 1x1xw base block using unlimited 1x1x1, 1x1x2, and 1x1x3 blocks with height at most h, where long blocks need both ends supported.Hard8Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Stretch Rope (Large)Given N rubber bands with stretch ranges [A_i, B_i] and prices, pick a subset whose summed range contains L at minimum total cost within budget M.Hard8Dynamic programmingGreedy+2No attempts yet30s512 MBJudgeable
Monster Path (Large)Walk exactly S steps on a grid, catching each cell's monster with probability P or Q on first visit, to maximize the expected number caught.Hard8Dynamic programmingBit manipulation+2No attempts yet5s512 MBJudgeable
Safe Squares (Large)Count all grid-aligned square regions of any size that contain no monster, given a sparse set of at most K monster cells on an R by C board.Hard8ArrayDynamic programming+2No attempts yet5s512 MBJudgeable
Sherlock and Permutation Sorting (Large)For each N and modulus M, sum f(p)^2 over all permutations of 1..N, where f(p) is the maximum number of blocks that can be sorted independently; output the sum mod M.Hard8Dynamic programmingCombinatorics+2No attempts yet10s512 MBJudgeable
Integeregex (Large)Count integers in [A, B] whose decimal form (no leading zeros) matches a small regular expression over digits.Hard8Dynamic programmingString+2No attempts yet5s512 MBJudgeable
String TableBuild a table whose cells are huge concatenated strings defined by comparing neighbors, then print 50 characters from a given position of the final cell.Hard8Dynamic programmingString+2No attempts yet2s512 MBJudgeable
PianoGiven N equally likely piano tones, find the expected number of presses until a fixed M-tone sequence appears, for every prefix of it.Hard8String matchingDynamic programming+2No attempts yet1s64 MBJudgeable
WellsOn a tree where placing wells at a vertex counts for it and its direct neighbors, find the minimum number of wells so every village's demand is met.Hard8TreeDynamic programming+2No attempts yet2s256 MBJudgeable
Counting CyclesCount all closed walks (cycles) of length less than K in a directed graph, where rotations count separately, modulo M.Hard8GraphMatrix+2No attempts yet2s512 MBJudgeable
Subsequence ReversalReverse one subsequence of a length-N array, then find the longest non-decreasing subsequence length achievable.Hard8Dynamic programmingArray+2No attempts yet2s512 MBJudgeable
Why Did the Cow Cross the Road 11Given a permutation of breeds on each side of a road, connect pairs whose breed numbers differ by at most 4 using non-crossing edges, maximizing the count.Hard8Dynamic programmingDivide and conquer+2No attempts yet2s512 MBJudgeable
Tidying the Plush ToysGiven a row of N toys of M types, find the fewest toys to remove so that after reinserting them all toys of each type form one contiguous block.Hard8Dynamic programmingBit manipulation+1No attempts yet2s512 MBJudgeable
Pieces of ParenthesesGiven n pieces of parentheses, choose and order some pieces to build the longest balanced parenthesis string.Hard8Dynamic programmingGreedy+1No attempts yet2s512 MBJudgeable
Stretching StreamersCount ways to draw non-crossing chords among n points on a circle so the graph is a tree, edges only between numbers sharing a factor.Hard8Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Ski ResortFor each query, count the size-k sets of areas such that every favorite area has exactly one stocked area lying on every path from the top, and all chosen areas lie on paths to favorite areas.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
RaspadSum the number of connected components of 1-cells over every contiguous band of rows in an n by m grid, with m at most 50 and n up to 100000.Hard8Dynamic programmingDivide and conquer+2No attempts yet6s1024 MBJudgeable
The Rabbit's Escape RouteCount self-avoiding walks on a 3 by N grid from the top left cell to the bottom right cell, modulo 1e9+9.Hard8Dynamic programmingCombinatorics+2No attempts yet1s256 MBJudgeable
Balance ScaleCount the orders and pan choices for placing weights 2^1 through 2^N so the left pan never outweighs the right, modulo 1e9+9.Hard8CombinatoricsDynamic programming+2No attempts yet1s256 MBJudgeable
CommunismAssign each of N jobs to one of three people so that Ad's total and Larry's total differ by at most D, and count the assignments.Hard8MathBacktracking+2No attempts yet1s512 MBJudgeable
Toppling Dominoes (Small)Sort the dominoes by position and find the minimum number of manual pushes so that chains topple every domino.Hard8Dynamic programmingSorting+1No attempts yet1s512 MBJudgeable
Dominoes (Large)Find the fewest pushes (each a domino plus a direction) needed to topple every domino through chain reactions.Hard8GreedySorting+2No attempts yet1s512 MBJudgeable
Yunho the Potion ThiefEach bought potion yields at most one divisor, and divisors chosen across potions must share no prime factor; maximize how many such divisors can be extracted.Hard8Number theoryDynamic programming+2No attempts yet1s512 MBJudgeable
Yeongseon takes the baitOn a tree, count alternating left/right paths from a fixed start where each vertex is used once; report the maximum over all starting vertices.Hard8TreeDFS+2No attempts yet1s512 MBJudgeable
Nemmo Nemmo (Hard)Count subsets of occupied cells in an N by M grid (N times M at most 300) that contain no full 2 by 2 square, modulo 1e9+7.Hard8Dynamic programmingBit manipulation+2No attempts yet2s512 MBJudgeable
Map LabelingPlace disjoint unit-height labels on a line above given points and count the minimum number of connectors that cannot run straight down to their own label.Hard8Dynamic programmingSorting+2No attempts yet1s512 MBJudgeable
Pony Express (Large)For each of Q deliveries, find the minimum travel time using horses of limited endurance, allowing instant horse swaps at cities.Hard8Shortest pathGraph+2No attempts yet5s512 MBJudgeable
Core Training (Small2)Distribute U training units among N cores, each unit adding 1 to a core's success probability (capped at 1), to maximize the chance that at least K cores succeed.Hard8Dynamic programmingGreedy+2No attempts yet5s512 MBJudgeable
Shoot the Turrets (Small)With each soldier walking at most M steps on a grid with walls, find the maximum number of turrets that can be destroyed, given line-of-sight firing rules and turret-firing-on-exit timing.Hard8BFSGraph+2No attempts yet5s512 MBJudgeable
Mountain Tour (Large)Given a directed graph where each camp has exactly two departing and two arriving tours with daily departure hours and durations, find the fastest route that uses every tour once and returns to camp 1.Hard8GraphDynamic programming+2No attempts yet5s512 MBJudgeable
Smallest Graph with K Spanning TreesFind the smallest node count of a graph built by the move/attach process whose spanning tree count equals K, for K up to 10000.Hard8GraphDynamic programming+2No attempts yet5s512 MBJudgeable
Coin Combinations and QueriesFor each query, count the multisets of at most d_i coins of denomination c_i (i=1..4) that sum to exactly v; answers fit in 64-bit.Hard8Dynamic programmingCombinatorics+2No attempts yet3s512 MBJudgeable
dojuCount increasing sequences of distinct integers within bounds for which both wrong formulas a_n/g and a_n-n give the wrong parity, modulo q.Hard8MathNumber theory+2No attempts yet2s512 MBJudgeable
Gathering clamsGiven an N by N grid of clam limits, compute after each of N single-cell +1/-1 updates the sum over all cells of the maximum-weight monotone staircase path to the top-left.Hard8Dynamic programmingPrefix sum+1No attempts yet2s512 MBJudgeable
MonstersGiven a binary N x M grid, choose one intact cell to destroy so that the number of all-1 submatrices remaining is minimized, and report that minimum count.Hard8ArrayDynamic programming+2No attempts yet1s32 MBJudgeable
Permutation SwapsFor each k from 1 to n-1, count permutations reachable from A in exactly k swaps, modulo 1e9+7.Hard8CombinatoricsDynamic programming+1No attempts yet2s512 MBJudgeable
Goodness of a sequenceFor every contiguous block, subtract the maximum increasing-subsequence sum from the block sum, then report the best value and how many shortest blocks achieve it.Hard8Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
ACGCount assignments of N ordered problems to three solvers so A's count is a multiple of k, C never solves two in a row, and G solves at least one, modulo 10000007.Hard8Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Rectangle ColoringCount the black-or-white colorings of an N by M grid where every X by Y subrectangle contains both colors.Hard8Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Number of good permutationsCount permutations of 1..N that respect given fixed positions and contain at least one pair i<j with P[i]>j and P[j]>i, modulo 2000000011.Hard8CombinatoricsMath+2No attempts yet2s512 MBJudgeable
Tree path decompositionCount the ways to partition all nodes of an unrooted tree into vertex-disjoint paths, where each path's node sum is nonnegative, modulo 1e9+7.Hard8TreeDynamic programming+1No attempts yet2s512 MBJudgeable
Who made the Christmas soundRoot the tree at socket 1 and count colorings with R, G, B bulbs, respecting the green and blue adjacency rules, whose total cost is divisible by K.Hard8Dynamic programmingTree+2No attempts yet1s512 MBJudgeable
Alien microbesCount the breeding patterns over H days starting from one microbe, where each day the microbes alive produce children with a total of at most W.Hard8Dynamic programmingCombinatorics+2No attempts yet2s256 MBJudgeable
Broadcast StationsGiven a tree, assign non-negative integer powers to vertices so every zero-power vertex lies within reach of some positive-power vertex, minimizing the total power. Report that minimum sum.Hard8Dynamic programmingTree+2No attempts yet0.5s512 MBJudgeable
Vacation PlansFind the minimum total cost for up to three people to each travel from city 1 to their airports across separate countries in the same number of days.Hard8Shortest pathDynamic programming+2No attempts yet1s512 MBJudgeable
Shooting GalleryA row of ducks, each with a species; a good round hits two ducks of the same species and keeps only the ducks strictly between them, and rounds continue while same-species pairs remain. Find the longest possible run of good rounds.Hard8Dynamic programmingArray+2No attempts yet2s512 MBJudgeable
Booming BusinessCount ordered rooted trees with exactly w nodes and height exactly h, modulo 1e9+7, where children of each node are an ordered sequence.Hard8Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
GhostbustersGiven independent button press probabilities, find the most likely set of pressed buttons that produces the observed row-to-column connectivity signals.Hard8GraphDynamic programming+2No attempts yet2s512 MBJudgeable