cho.sh

Problems

Pick a problem and write your solution in the built-in editor. The judge runs it against real test cases while you watch, and the wider archive is open to read whenever you like.

Total results3,683 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
LCS 6Given two uppercase strings of up to 50000 characters, print the length of their longest common subsequence.Hard8StringDynamic programming+1No attempts yet1s8 MBJudgeable
LCS 7Given two strings of length up to 50000, find the length of their longest common subsequence and print one such subsequence.Hard8StringDynamic programming+2No attempts yet2s8 MBJudgeable
Post Office 1Place P post offices among V villages on a circular road of circumference L to minimize the total distance from every village to its nearest office, and output both the cost and chosen positions.Hard8Dynamic programmingBinary search+2No attempts yet1s1024 MBJudgeable
Ignore SubmasksFor each k-bit mask x, find the first array element that does not contain x as a submask, and sum these indices modulo 998244353.Hard8Bit manipulationDynamic programming+2No attempts yet1s512 MBJudgeable
Expected ValueRepeatedly pick a random adjacent pair, replace the left value by its difference with the right, drop the right. Find the expected final value modulo 1e9+7.Hard8Dynamic programmingProbability+2No attempts yet3s16 MBJudgeable
Nonsense TimeElements of a random permutation are unfrozen one at a time; after each unfreeze report the longest increasing subsequence length among the currently available elements.Hard8Dynamic programmingBinary search+2No attempts yet12s512 MBJudgeable
Snowy SmileGiven up to 2000 weighted points, find an axis-aligned rectangle maximizing the sum of weights of points inside or on its border, allowing an empty rectangle for zero.Hard8Dynamic programmingSorting+2No attempts yet3s512 MBJudgeable
Game PredictionFor each subarray query, compute both players' final scores when they alternately take the leftmost or rightmost element, playing optimally.Hard8Dynamic programmingGame theory+2No attempts yet1s512 MBJudgeable
AlakazamGiven an array and range shuffle operations that permute a segment uniformly at random, answer point queries for the expected value at a position.Hard8MathProbability+2No attempts yet2s512 MBJudgeable
Road NetworkGiven a tree, add one edge so that the number of bridges in the resulting graph is minimized, and report that minimum count.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
KhoshafCount arrays of length N with entries in [L, R] that have exactly K contiguous subarrays whose sum is divisible by 3, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet12s512 MBJudgeable
ExpEach of n independent monsters grants i experience (0 to k) with probability p_i, totals are capped at x, and the expected capped total must be computed modulo 998244353.Hard8ProbabilityDynamic programming+2No attempts yet5s512 MBJudgeable
Bridge ConstructionCount unlabeled connected graphs on N vertices with maximum degree at most 4, modulo a prime X.Hard8CombinatoricsDynamic programming+2No attempts yet2s256 MBJudgeable
The Moo ParticleGiven N points with distinct coordinates, one of two points may vanish when one dominates the other; find the minimum number of points that can remain.Hard8SortingGreedy+2No attempts yet1s512 MBJudgeable
Longest Increasing Subsequence ksGiven a permutation-like sequence, find the K-th longest increasing subsequence when all LISs are sorted lexicographically by index, or -1 if fewer than K exist.Hard8Dynamic programmingGreedy+2No attempts yet0.25s512 MBJudgeable
Encryption FunctionGiven the output of a digit-subset-sum encryption, find any positive integer that encrypts to it or report that none exists.Hard8MathDynamic programming+2No attempts yet1s64 MBJudgeable
Printer's HeadGiven a permutation of heights 1..n to print in order, find the minimum number of left-to-right or right-to-left sweeps, where each sweep prints positions in order with heights dropping by 1.Hard8GreedyDynamic programming+1No attempts yet1.5s64 MBJudgeable
Alice and BobCount placements of at most one token per vertex on a colored DAG where Alice (white moves) beats Bob (black moves) under optimal play.Hard8Game theoryDynamic programming+2No attempts yet1s512 MBJudgeable
Banned WordsCount length-L strings over 26 letters avoiding a given set of banned substrings, modulo 998244353, with L up to 1e9.Hard8String matchingTrie+2No attempts yet2s512 MBJudgeable
Non-Decreasing Subarray GameFor each query range, Yuto picks an integer to minimize and Platina then picks one to maximize the count of non-decreasing subarrays inside the interval they bound; output the resulting score.Hard8Game theoryDynamic programming+2No attempts yet2s256 MBJudgeable
KnapsackCount subsets of weights where each of n types has 2 copies and masses grow at least by a factor of 2, so the total equals W.Hard8Dynamic programmingGreedy+2No attempts yet3s512 MBJudgeable
Partition into TeamsFor n people each choosing red, blue, or spectator uniformly, compute 3^n times the probability that red wins, modulo a prime p.Hard8CombinatoricsMath+2No attempts yet1s256 MBJudgeable
Counting DivisorsFor each query with l, r, k, compute the sum of d(i^k) for i from l to r, modulo 998244353, where d counts divisors.Hard8Number theoryMath+2No attempts yet7s512 MBJudgeable
Lazy RunningStarting and ending at checkpoint p2 on a 4-cycle, find the shortest closed walk whose swipe-recorded total distance is at least K, given the four edge lengths.Hard8Shortest pathDynamic programming+2No attempts yet1s256 MBJudgeable
Rikka with LinkerGiven a directed dependency graph on n libraries, find the shortest sequence of library names in which every edge (a,b) has some occurrence of a before some occurrence of b.Hard8Bit manipulationDynamic programming+2No attempts yet2s512 MBJudgeable
Remove the TreeGiven a tree, repeatedly delete the vertices of any chosen path (and incident edges); find the minimum number of path-deletions needed to remove every edge.Hard8TreeGreedy+2No attempts yet2s256 MBJudgeable
Hokusai ArtworksOn a directed graph, each city has a museum open only on even days; find the maximum total weight of distinct museums visitable starting at city 0 on an even day.Hard8GraphDynamic programming+2No attempts yet1s512 MBJudgeable
Wavel SequenceCount pairs of increasing index sequences from two arrays whose selected values are equal and form a strictly alternating up-down wave, modulo 998244353.Hard8Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
Nutella's LifeChoose a subsequence of contests with nondecreasing values, where skipping x contests in a row costs x+1 each, to maximize total fun.Hard8Dynamic programmingSegment tree+1No attempts yet2s512 MBJudgeable
Anna and Lucky TicketsCount n-digit palindromes that are lucky under neither the alternating-position sum test nor the first-half-versus-second-half sum test, modulo 1e9+7.Hard8CombinatoricsDynamic programming+2No attempts yet2s256 MBJudgeable
Subsequence SumsGiven the multiset of all subsequence sums of a hidden positive-integer sequence, reconstruct the sequence, choosing the lexicographically smallest one.Hard8Dynamic programmingGreedy+2No attempts yet1s512 MBJudgeable
Leave Out All The RestGiven two arrays with distinct values, interleave them into one sequence so that its longest increasing subsequence is as long as possible, and output that maximum length.Hard8Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
OnesFor each k up to 1e9, output a 1-expression using only ones, +, *, and parentheses that evaluates to k with at most 100 ones, or NO.Hard8Dynamic programmingMath+2No attempts yet1s512 MBJudgeable
MonkeysChoose K vertices of a tree and delete edges so every chosen monkey can reach another, minimizing the number of surviving edges.Hard8TreeDynamic programming+2No attempts yet4s512 MBJudgeable
Master Zhu and Math ProblemCount quadruples (a,b,c,d) within given bounds that satisfy two linear inequalities, modulo 1e9+7, with bounds up to 1e18.Hard8MathCombinatorics+2No attempts yet3s512 MBJudgeable
Bipartite Graph ColoringSum, over all 2^n black/white colorings of a bipartite graph, the product of per-edge weights that depend on the colors of each edge's endpoints, modulo 1e9+7.Hard8MathDynamic programming+2No attempts yet12s512 MBJudgeable
Independent SetCount vectors of n nonnegative integers summing to m where positions flagged by a and parent-child pairs in the implicit binary heap cannot both be positive, modulo 1e9+7.Hard8Dynamic programmingTree+2No attempts yet2s512 MBJudgeable
Saddle PointCount the n by m matrices with entries in 1..k that contain at least one position that is a strict maximum of both its row and its column, modulo 1e9+7.Hard8CombinatoricsDynamic programming+2No attempts yet1s512 MBJudgeable
KolmogorovIn a connected undirected graph where each minute one random edge lights up, find the minimum expected time for an optimal walker to travel from node 1 to node N.Hard8GraphDynamic programming+2No attempts yet1s512 MBJudgeable
Cleaning RobotsCount the ways to partition all vertices of a tree into vertex-disjoint paths such that no two paths can be merged into a longer path.Hard8TreeDynamic programming+2No attempts yet1s512 MBJudgeable
Fibonacci's NightmareFor a random sequence built by summing two earlier terms, find the variance of the n-th term modulo 10^9+7.Hard8ProbabilityDynamic programming+2No attempts yet2s256 MBJudgeable
Infinite Binary EmbeddingCount the ways to embed a finite binary tree into the infinite binary tree so that each leaf lands at a prescribed height, modulo 1e9+7.Hard8TreeDynamic programming+2No attempts yet2s256 MBJudgeable
Key StorageFor each key, count how many other positive integers produce the same multiset of remainders when repeatedly divided by 2, 3, 4, and so on.Hard8CombinatoricsMath+2No attempts yet3s512 MBJudgeable
TrenerCount ways to pick one surname from each length bucket so every shorter surname is a substring of every longer one, modulo 1e9+7.Hard8StringDynamic programming+2No attempts yet2s512 MBJudgeable
min-xorMaintain a dynamic set under insertions and deletions, and after each min-xor query report the smallest XOR of any two elements currently in the set.Hard8TrieBit manipulation+2No attempts yet0.4s8 MBJudgeable
Related LanguagesGiven strings A and B and an integer k, find the longest pair of equal-length substrings, one from each string, that differ in at most k positions.Hard8Binary searchDynamic programming+2No attempts yet10s512 MBJudgeable
Dynamic Input ToolFind the minimum number of append-character and append-subsequence-of-current-string operations needed to build a given string from empty.Hard8Dynamic programmingString+2No attempts yet2s512 MBJudgeable
BelieverFor each n up to 1e18, find the maximum over all positive-integer sequences summing to n of the total popcount of the multiplicities of the distinct values.Hard8Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
Kids Aren't AlrightGiven m up to 1e18, count the non-empty sets of positive integers whose gcd is 1 and lcm is m, modulo 998244353.Hard8Number theoryCombinatorics+2No attempts yet2s512 MBJudgeable
Median on Binary TreeGiven a heap-shaped binary tree with distinct weights, for every a find the largest a-median, defined as the element at position floor((k-a+1)/2) of a subtree sorted by weight.Hard8TreeDynamic programming+2No attempts yet2s512 MBJudgeable
Expected LCPCompute the expected length of the longest common prefix among n independent uniform random infinite binary strings, output as a fraction mod 1e9+7.Hard8ProbabilityCombinatorics+2No attempts yet1.5s256 MBJudgeable
WeltallFind the d-th lexicographic permutation of 1..n that has exactly k fixed points.Hard8CombinatoricsDynamic programming+2No attempts yet4s256 MBJudgeable
Best DivisionGiven a pseudorandom array, find the largest K such that A can be split into K nonempty intervals of length at most L, each with XOR sum at most X.Hard8Dynamic programmingPrefix sum+2No attempts yet1s256 MBJudgeable
Intersection is Not Allowed!Count the ways to route K non-crossing monotone paths from fixed top squares to fixed bottom squares on an N by N board, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet1s256 MBJudgeable
Eel and GridAn eel on a toroidal H by W grid walks right or down, painting cells, until it returns to a painted cell; count Hamiltonian-style walks that cover every cell and end at (0,0).Hard8CombinatoricsMath+1No attempts yet1s256 MBJudgeable
Cups and BeansBeans sit in cups 1 through N-1, each with a move limit C_i; players alternate sliding one bean to a lower cup and whoever cannot move loses. Decide the winner.Hard8Game theoryDynamic programming+2No attempts yet1s256 MBJudgeable
Delivering FlyersOn a unit-weight tree, find the shortest closed walk from S that covers every node, given the rider can cover all nodes within distance D from any single stop.Hard8TreeGreedy+2No attempts yet1s1024 MBJudgeable
TriangulationCount, over all triangulations of a regular N-gon with a proper red/blue coloring, the total number of red triangles, modulo 998244353.Hard8CombinatoricsDynamic programming+2No attempts yet2.5s256 MBJudgeable
Drought (Large)Maximize the sum of a_i minus the sum of b_j over nonnegative reals a and b subject to a_i - b_j <= c_ij, then round the answer to the nearest integer.Hard8Dynamic programmingGreedy+2No attempts yet1s1024 MBJudgeable
Taking ItemsEach item may require others first, cycles mean all-or-nothing; pick a feasible set of items maximizing total mood change.Hard8GraphDynamic programming+2No attempts yet1s1024 MBJudgeable
Second Diameter of a TreeGiven a weighted tree with up to 100,000 vertices, find the distance of the second farthest pair of vertices, allowing a tie with the diameter.Hard8TreeDFS+2No attempts yet1s1024 MBJudgeable
How Many Burgers?Split N burgers with given utilities among three people so that the youngest gets the most he can while not exceeding either senior's total.Hard8Dynamic programmingGreedy+2No attempts yet1s1024 MBJudgeable
FeastChoose at most K disjoint non-empty subarrays of A so that the total sum of their elements is as large as possible.Hard8Dynamic programmingGreedy+2No attempts yet1s512 MBJudgeable
QuadtreeGiven a 2^n by 2^n binary matrix and a budget k, flip at most k entries so the resulting matrix has a quadtree with the fewest possible cells.Hard8TreeDynamic programming+2No attempts yet2s512 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
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