cho.sh

Curated sets

Dynamic programming ladder

Every judgeable DP problem, easiest first.

All problems
Total results3,128 problems
TopicsJudge
Not Too Convex HullPartition the nails into B convex polygonal groups, all sharing the origin nail, minimizing the total covered area, with the origin strictly inside the global hull.Hard9Dynamic programmingGeometry+2No attempts yet1s128 MBJudgeable
Island TravelsGiven a grid with N islands and shallow water, find the minimum total swim distance to visit every island, starting anywhere.Hard9GraphBFS+2No attempts yet1s128 MBJudgeable
Taking TurnsTwo players alternately take bales from a line, skipping any number of earlier bales; each plays optimally and takes the leftmost optimal bale. Find each player's total.Hard9Dynamic programmingGreedy+2No attempts yet1s128 MBJudgeable
Cow HopscotchChoose an outbound path of jumps (each at most K squares) and a return path that only lands on squares one less than an outbound square, maximizing collected values.Hard9Dynamic programmingSegment tree+2No attempts yet1s128 MBJudgeable
Largest FenceGiven N grid points with no three collinear, find the size of the largest subset whose points form the vertices of a convex polygon.Hard9GeometryDynamic programming+2No attempts yet2s128 MBJudgeable
Winmine (Minesweeper)Count the ways to place the remaining mines on the unrevealed squares so that every revealed number matches its adjacent mine count, modulo 1000003.Hard9Dynamic programmingGraph+2No attempts yet2s512 MBJudgeable
Mine the GradientGiven a grayscale grid, find the largest square subgrid whose values follow a vertical, horizontal, or diagonal uniform gradient, and report its area.Hard9Dynamic programmingImplementation+2No attempts yet10s128 MBJudgeable
Alea iacta estGiven a linear congruential generator, compute the maximum Yahtzee score over eleven rounds by choosing which dice to keep and which combination to score each round.Hard9Dynamic programmingSimulation+2No attempts yet2s128 MBJudgeable
DownpaymentGiven future monthly interest rates for m mortgage plans, binding periods, and switch penalties, find the schedule of plan choices that minimizes the total money paid, with debt rounded down each month.Hard9Dynamic programmingGreedy+2No attempts yet1s256 MBJudgeable
A Romantic Movie OutingMaintain a dynamic set of occupied seats across a huge theatre, answer queries for the combined field-of-vision inconvenience of two seats, and at the end find the minimum over far unoccupied seat pairs.Hard9Segment treeDynamic programming+2No attempts yet2s512 MBJudgeable
TelecorpPlace one of M module types on any subset of N teleporters, each jump skipping ahead and multiplying speed, to minimize total travel time from 0 to L.Hard9Dynamic programmingGreedy+2No attempts yet1s1024 MBJudgeable
Longest Paths in a TreeA rooted tree has weighted edges. Handle point updates to edge weights and queries that ask for the maximum-weight downward path from a vertex inside its subtree.Hard9TreeSegment tree+2No attempts yet5s1024 MBJudgeable
Parallel ExpectationsGiven two programs run by randomly interleaving their instructions, find the expected final value of every shared variable.Hard9ProbabilityDynamic programming+1No attempts yet1s128 MBJudgeable
ExamGiven each student's distribution over exam scores, find the exact probability that the sequence of European marks from all students avoids every listed unpleasant string.Hard9Dynamic programmingString matching+2No attempts yet2s128 MBJudgeable
DuopolyGiven two sets of weighted bids on channels, where bids within one company are disjoint, pick a subset of non-conflicting bids to maximize total price.Hard9Dynamic programmingGreedy+1No attempts yet3s32 MBJudgeable
Structural IsomersCount the number of distinct alkane carbon skeletons (free trees in which every node has degree at most 4) with n carbon atoms.Hard9Dynamic programmingCombinatorics+2No attempts yet1s128 MBJudgeable
Juggle with CriteriaFor each of n five-symbol relation patterns (<, =, >) and a fixed length l, decide whether two permutations of length l exist whose inversion count, local inversions, LIS, longest increasing substring, and fixed points match that exact pattern.Hard9CombinatoricsDynamic programming+2No attempts yet1s128 MBJudgeable
Markov TrainsFind the station list maximizing the chance of arriving by a deadline when each train may be cancelled and the traveler waits for the next one after a cancellation.Hard9Dynamic programmingProbability+1No attempts yet1s128 MBJudgeable
Dextrogyrate CamelFind the longest closed camel route that starts at oasis 1 heading to oasis 2, always turns right by at most 180 degrees at each oasis, never crosses itself, and visits the most distinct oases.Hard9GeometryDynamic programming+2No attempts yet1s512 MBJudgeable
Bus TourChoose a sequence of attractions with strictly increasing construction times maximizing attractiveness collected plus Manhattan travel distance.Hard9Dynamic programmingSorting+2No attempts yet1s128 MBJudgeable
Driving ExamBuild at most k new horizontal one-way streets on a grid so that the number of streets whose southern end can reach every street's northern end is maximized.Hard9GraphDynamic programming+2No attempts yet1s128 MBJudgeable
HamstersFind the shortest lowercase string containing at least m occurrences of the given hamster names, counted with multiplicity.Hard9String matchingDynamic programming+2No attempts yet3s512 MBJudgeable
OnesGiven run lengths of n in binary, output run lengths of the binary form of sks(n), the total UFO count over 1 to n.Hard9MathCombinatorics+2No attempts yet3s512 MBJudgeable
Milk MultidrinkDecide whether a tree with n nodes has a Hamiltonian path from 1 to n where consecutive vertices stay within distance two.Hard9TreeDFS+2No attempts yet1s128 MBJudgeable
Ski RentalGiven daily snowfall amounts with point updates, answer queries asking for the maximum average snowfall over a consecutive run starting at a given day, reported as an irreducible fraction.Hard9Segment treeGeometry+1No attempts yet1s128 MBJudgeable
Hard ChoiceAfter streets are closed one by one offline, answer for each query whether two edge-disjoint paths still connect the given pair of junctions.Hard9GraphDFS+2No attempts yet5s128 MBJudgeable
FragmentsCount how many times each digit string appears as a contiguous substring across the decimal forms of all numbers in a union of disjoint integer intervals up to 10^18.Hard9String matchingDynamic programming+2No attempts yet1s128 MBJudgeable
Blindfold NimEach stack size is uniform on [0, a_i]; compute the probability that the first player wins a game of Nim with hidden positions where a player who overshoots a stack loses at once.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Dragon MilkdrinkerCompute the probability that the sum of n independent uniform [m, M] yields is strictly less than h, printed truncated to d decimals.Hard9ProbabilityMath+2No attempts yet1s128 MBJudgeable
MicrochipsCount directed walks whose edge-impedance product equals I, allowing repeated vertices and edges, and report infinity when infinitely many such walks exist.Hard9GraphNumber theory+2No attempts yet1s128 MBJudgeable
Fibonacci WordCount occurrences of a given binary pattern in the Fibonacci word F_m and count distinct subwords occurring at least that many times, mod 20062006, with m up to 1e9.Hard9StringDynamic programming+2No attempts yet1s128 MBJudgeable
HighwaysMaintain a layered graph where each province has a few cities and highway lane counts change over time, answering route-count queries modulo d after each update.Hard9MatrixSegment tree+1No attempts yet1s128 MBJudgeable
HighwaysGiven a tree plus extra highway edges, count for each query (x,y) the main tree path plus alternative single-highway paths that touch the main path only at x and y.Hard9TreeDFS+2No attempts yet3s128 MBJudgeable
SequenceFind the nth term of the nondecreasing sequence where each k appears exactly as many times as the kth term.Hard9MathBinary search+1No attempts yet1s512 MBJudgeable
PuzzleBuild the longest string over the first n capital letters that avoids all forbidden substrings, or print No when no maximum exists.Hard9String matchingTrie+2No attempts yet1s128 MBJudgeable
Dragon PatternCount how many times pattern S appears as a contiguous block in the length 2^n direction string of the order-n left dragon curve.Hard9String matchingRecursion+2No attempts yet5s128 MBJudgeable
Cactus AutomorphismsCount the automorphisms of a given cactus graph with up to 50000 vertices and print the count as a prime factorization.Hard9TreeDynamic programming+2No attempts yet5s256 MBJudgeable
GRADCities join the road network one by one with two roads each, and each query asks the shortest road distance between two cities.Hard9Shortest pathGraph+2No attempts yet2s256 MBJudgeable
FriendChoose a set of people with maximum total confidence so that no two chosen people are friends in the network grown by the three joining rules.Hard9GraphDynamic programming+1No attempts yet1s16 MBJudgeable
Maximum Transport ProfitPick two villages in the tree so the total profit of the given routes with both endpoints on the path between them is as large as possible.Hard9TreeDynamic programmingNo attempts yet3s256 MBJudgeable
TollgateFind the road with the largest expected toll income when every resident visits every restaurant by a random shortest round trip.Hard9Shortest pathGraph+2No attempts yet2s256 MBJudgeable
ExhibitionFind the cheapest linear-cost cuts to product 1's price, size and weight that put it in some k-set tying the best set without it.Hard9Dynamic programmingMath+1No attempts yet10s256 MBJudgeable
Combinator ExpressionCount the fewest BCKI rewrite steps that reduce the given expression to its normal form.Hard9Dynamic programmingTree+1No attempts yet1s256 MBJudgeable
Tokyo Olympics CenterAssign each lettered unit to one of K staff and order the visits to minimize the longest round trip from the start cell that checks every dead-end room.Hard9Dynamic programmingShortest path+1No attempts yet5s128 MBJudgeable
Revenge of Minimum Cost FlowSend f units of freight from city s to city t through directed carrier edges with two-piece linear costs and report the cheapest total.Hard9GraphShortest path+1No attempts yet3s256 MBJudgeable
Hashigo SamaCount black-white colorings of joined ladders where each monochrome block has size at most k, modulo 1,000,000,007.Hard9Dynamic programmingGraphNo attempts yet8s256 MBJudgeable
Overwriting GameYou repeat random prefix-rectangle repaints until the board matches the target, and report the expected total of painted cells as a reduced fraction.Hard9ProbabilityMatrix+1No attempts yet8s512 MBJudgeable
Slave to Achievements 2Repeatedly craft as many N-scrap daggers as possible and reclaim 0 to K scraps per dagger, then find the distribution of the final leftover under N scraps.Hard9ProbabilityDynamic programming+1No attempts yet3s256 MBJudgeable
Believer in I 2Over every ordering of A push, B add, and C multiply cards on an infinite stack of I, report the total of each of the top K stack values modulo 1,000,000,007.Hard9CombinatoricsDynamic programming+2No attempts yet3s256 MBJudgeable
Followers of I 3Sum, over every distinct order of the I, plus, and times cards run on an infinite I stack, the top K stack values modulo 1000000007.Hard9Dynamic programmingCombinatorics+1No attempts yet3s256 MBJudgeable
Tree Edit DistanceCompute the minimum leaf insertions, leaf deletions, and relabels that turn one ordered labeled tree into another.Hard9Dynamic programmingTreeNo attempts yet2s256 MBJudgeable
Highways and CountiesFind the smallest road length limit so cities joined by shorter roads form a group whose populations hold a subset summing to a multiple of K.Hard9Minimum spanning treeDynamic programming+2No attempts yet2s64 MBJudgeable
Dungeon CreationCount the spanning trees of the obstacle-free grid graph for each test case, modulo 1,000,000,007.Hard9Dynamic programmingGraph+1No attempts yet3s512 MBJudgeable
CasinoWith m dollars, a goal of n dollars and win chance p percent per play, pick each stake to maximize the chance of reaching the goal.Hard9ProbabilityDynamic programming+1No attempts yet2s256 MBJudgeable
Lights Out in the BarnStarting at an unknown vertex of a rectilinear barn, walk the walls to identify the position and reach the exit with the smallest worst-case extra distance.Hard9Dynamic programmingGame theory+1No attempts yet2s512 MBJudgeable
GaussStarting from A, pay divisor-based costs to shrink the number or stay on lucky numbers, and find the cheapest exact-move cost to end at B.Hard9Dynamic programmingShortest path+2No attempts yet2s256 MBJudgeable
WillowTwo players choose starting cities on a tree with coins and alternately collect cities, each road usable once, and Hanaa maximizes the final score difference.Hard9Game theoryTree+1No attempts yet5s512 MBJudgeable
Lost Password (Large)Given string S and integer k, compute the length of the shortest string containing every l33tspeak variant of each substring of S with length 1 to k.Hard9GraphShortest path+1No attempts yet100s512 MBJudgeable
Children Wearing Hats (Large)Given B black and W white hats for k children, count color sequences where the i-th child from the back first deduces their hat color, modulo 32749.Hard9Dynamic programmingGame theory+1No attempts yet5s512 MBJudgeable
Ninjutsu (Large)Pick a starting rope length so the counterclockwise swing catches as many targets as possible before settling into orbit.Hard9GeometryDynamic programming+1No attempts yet60s512 MBJudgeable
Half-plane land grab 2Maintain a dynamic set of lines under insertions and deletions and answer maximum-at-x queries online.Hard9Dynamic programmingDivide and conquer+2No attempts yet4s512 MBJudgeable
Counting StringsCount strings over the lowercase alphabet whose length lies between L*K and L*K+N and in which at most K non-overlapping copies of a given pattern S can be found.Hard9Dynamic programmingString matching+2No attempts yet2s512 MBJudgeable
Number of walksGiven a directed graph as an adjacency matrix, find the smallest K such that the number of walks of length L grows as O(L^K), or -1 if none exists.Hard9GraphDynamic programming+2No attempts yet2s512 MBJudgeable
Clique on a LineGiven n points on a line with weights, two points are adjacent when their weights sum to at most their distance; find the largest clique.Hard9Dynamic programmingSorting+2No attempts yet2s512 MBJudgeable
Growing a Binary TreeFor each tree, pick a root and count the fewest vertices to add so that the result becomes a complete binary tree (every internal vertex has exactly two children, all leaves equidistant from the root), minimizing that count and then the vertex index; output the count mod 1e9+7.Hard9TreeDFS+2No attempts yet4s512 MBJudgeable
YATPGiven a node-weighted, edge-weighted tree, for each node find the minimum of dist(u,v) + p_u*p_v over all v, and sum these minima over all nodes.Hard9TreeDivide and conquer+2No attempts yet5s512 MBJudgeable
Tree TransformationCount the minimum-size sets of edges whose removal splits the tree into components of power-of-two sizes, modulo 1e9+7.Hard9TreeDynamic programming+2No attempts yet1s512 MBJudgeable
Flowey's LoveA soul starting at the origin moves at speed at most 1 inside a rectangle; N moving points travel along fixed lines, and you must find the maximum number of points the soul can touch.Hard9GeometryDynamic programming+2No attempts yet1s512 MBJudgeable
Solve this one tooGiven an N x L matrix, find windows of 3N columns split into matrices A, B, C with A*B=C; pick disjoint windows to maximize total colored cells.Hard9MatrixDynamic programming+2No attempts yet5s512 MBJudgeable
Colored BracketsCount valid bracket strings of 2N brackets over K colors that equal their own reversal, modulo 1e9+7.Hard9CombinatoricsMath+2No attempts yet2s512 MBJudgeable
Drawing lotsCompute the expected number of draws until a blue lot has been drawn K times, where red lots are removed and green and blue lots are returned.Hard9ProbabilityMath+1No attempts yet2s512 MBJudgeable
Minimum cost increasing sequenceTransform A into a strictly increasing integer sequence B minimizing the sum of |B_i - A_i|, and output the lexicographically smallest such B.Hard9Dynamic programmingGreedy+1No attempts yet2s512 MBJudgeable
Almost Euler graphsCount the simple graphs on N labeled vertices that become Eulerian after adding or removing one edge, modulo 1e9+7.Hard9CombinatoricsGraph+2No attempts yet2s512 MBJudgeable
Binary cryptarithm decryptionGiven a short cipher string where letters replace some characters of an unknown binary equation, count how many valid equations from the given grammar match it.Hard9BacktrackingDynamic programming+2No attempts yet2s512 MBJudgeable
OracleGiven multipliers p_i and bet sizes j^2+aj+b for the j-th entered game, she picks a subsequence of exactly k games to maximize total profit, for every k.Hard9Dynamic programmingDivide and conquer+2No attempts yet3s256 MBJudgeable
Tree and queries 5On a tree where vertices flip black and white, answer for each query the distance from a given vertex to the nearest white vertex.Hard9TreeDivide and conquer+2No attempts yet2s512 MBJudgeable
Sequence and Queries 0For each query range [i,j] of a ±1 sequence, report the length of the longest contiguous subarray inside it whose sum is 0, or 0 if none exists.Hard9Segment treePrefix sum+2No attempts yet2.5s512 MBJudgeable
Sequence and Queries 9For each query range [i,j] and value k, count ordered pairs (p,q) from that range with A[p]*B[q] <= k.Hard9Divide and conquerSegment tree+2No attempts yet6s512 MBJudgeable
Polygon Shrinking KitEach polygon vertex is replaced by the midpoint toward A or toward B; among all choices keeping the vertices in convex order, find the minimum possible area.Hard9GeometryDynamic programming+2No attempts yet1s512 MBJudgeable
Game MovesGiven a reachable 2048 board and its score, find the minimum number of moves that could have produced that state, using the merge rules and random tile births.Hard9Dynamic programmingBacktracking+1No attempts yet1s512 MBJudgeable
British MenuGiven a directed graph where every cycle witnesses a repeat within at most four intervening dishes, find the longest simple path (no repeated vertex).Hard9GraphDynamic programming+2No attempts yet5s1024 MBJudgeable
Geohash GridFor a rectilinear polygon inside a 2^n by 2^n grid, answer up to 1e5 queries asking the smallest cell count of a union of at most t geohash intervals covering it.Hard9Divide and conquerTree+2No attempts yet5s512 MBJudgeable
ConferenceGiven M daily pairwise meetings among N people (first K are scientists), find the latest creation day for each invention so a journalist still learns it, then report which journalists learn anything and each invention's first journalist.Hard9GraphUnion-find+2No attempts yet2s512 MBJudgeable
AcrobatGiven a bipartite multigraph between two sets of N assistants, each rope may be swapped (i,j)->(j,i) at most once; find the minimum swaps so the edges form an Eulerian circuit, or report -1.Hard9GraphBit manipulation+2No attempts yet2s512 MBJudgeable
Mole TunnelsOn a binary-heap-shaped tree, each newly woken mole (in a fixed order) must be assigned to a hole with remaining food capacity, minimizing total walking distance; report the minimum for every prefix k.Hard9TreeGreedy+2No attempts yet2s512 MBJudgeable
PiratesFor every prefix of pirates, compute the oldest pirate's share under the stated voting and tie-breaking rules.Hard9GreedyDynamic programming+2No attempts yet10s512 MBJudgeable
Cactus giftIn a cactus graph with up to 4000 vertices, count directed simple paths of each length 1 to N, modulo 1e9+7.Hard9Dynamic programmingTree+2No attempts yet1.5s512 MBJudgeable
Function and QueriesGiven an array and a recurrence f(i,j)=min(f(i-1,j),f(i-1,j-1))+a_j, answer up to 1e5 offline queries for f(x,y).Hard9Dynamic programmingDivide and conquer+2No attempts yet2s512 MBJudgeable
Soldiers (Large)Two players alternately pick soldiers, each new pick must beat all previous picks in attack or in defense; decide if the first player can end up with strictly more picks.Hard9Game theoryDynamic programming+1No attempts yet5s512 MBJudgeable
Clash Royale (Large)Pick 8 of N cards and spend at most M coins on upgrades to maximize the total attack power of the chosen deck.Hard9Dynamic programmingGreedy+1No attempts yet20s512 MBJudgeable
RopeA rope of N unit cords with colors is repeatedly folded in half, paying the thickness of cords whose colors are changed, until length 2; for each color report the minimum total cost to end with a cord of that color.Hard9Dynamic programmingDivide and conquer+2No attempts yet2.5s256 MBJudgeable
Incremental Double Free StringsFind the nth string of length k(k+1)/2 that uses one letter j times for each j up to k and has no two equal adjacent letters, in alphabetical order.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Maximum Color CliqueGiven a complete graph whose every cycle has two adjacent same-color edges, sum over all nonempty node subsets the size of the largest same-color clique inside each subset, modulo 1e9+7.Hard9GraphCombinatorics+2No attempts yet2s512 MBJudgeable
Switch GrassA weighted connected graph has a color at each vertex; after each of Q point color updates, report the shortest distance between two vertices of different colors.Hard9GraphShortest path+2No attempts yet2s512 MBJudgeable
Largest window sumFor every window length K, find the largest possible sum of a length-K window over all non-negative arrays that satisfy each given length bound.Hard9GreedyPrefix sum+2No attempts yet1s512 MBJudgeable
Minimum Cycle MeanGiven a weighted simple digraph, find the minimum mean weight over all simple directed cycles, or 0 0 if no cycle exists, and output it as a reduced fraction.Hard9Dynamic programmingGraph+2No attempts yet2s512 MBJudgeable
Sequence and TransformationCount length-n sequences with entries in [1,m] whose image after applying a min-based affine transformation k times has the given max-minus-min value.Hard9CombinatoricsMath+2No attempts yet2s512 MBJudgeable
Expected value of the greatest common divisorEach of K values is chosen uniformly from its own interval; find the expected gcd of the K chosen numbers as a fraction mod 1e9+7.Hard9ProbabilityMath+2No attempts yet2s512 MBJudgeable
NPM998244353 (Hard)For every digit-sum cap from 0 to MM, count length-N digit strings divisible by P, modulo 998244353.Hard9CombinatoricsDynamic programming+2No attempts yet5s512 MBJudgeable
Counting multiples with a bounded digit sumCount length-N digit strings divisible by P with digit sum at most M, for every M up to the limit, modulo 998244353.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable