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 results14,366 problems
TopicsJudge
Reverse a Road IIEach directed road carries at most one truck; find whether reversing one road increases the max number of edge-disjoint S-to-T paths, the new maximum, and how many roads achieve it.Hard9GraphBFS+2No attempts yet8s512 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
ArrayStart with array a_i = i, apply up to 300000 queries that reverse or rotate subarrays and ask for range min, max, sum, value at index, or index of a value, then print the final array.Hard9ArrayImplementation+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
PostersCompute the visible area of each of N rectangles pasted in order on the plane, where later rectangles cover earlier ones.Hard9GeometryDivide and conquer+2No attempts yet2s512 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
Laser SensorsGiven N blue points and 2N red points in general position, build the particular non-crossing perfect matching prescribed by the paper's recursive angular-sweep Solve/Attach procedure.Hard9Divide and conquerGeometry+2No attempts yet2s512 MBJudgeable
Distant StarsEach star moves at constant integer velocity; for each day 0 to T find the maximum pairwise squared distance, and report the earliest day attaining the minimum of that maximum.Hard9GeometryDivide and conquer+2No attempts yet2s512 MBJudgeable
One Pass ShortConstruct a directed graph with edge weights 1 or -1, no negative cycle, yet a Bellman-Ford variant that runs N-2 rounds then checks would falsely report a negative cycle; minimize the edge count and lexicographic order.Hard9GraphShortest path+2No 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
Three Kingdoms of BourdelotDecide whether some assignment of positive or negative polarity to each document is consistent with the hypothesis that person p is an ancestor of person q.Hard9GraphUnion-find+2No attempts yet4s512 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
Trees and Queries 10Given a tree with vertex weights, answer path maximum-subarray-sum queries and path range-assign-weight updates.Hard9Segment treeTree+2No attempts yet2s512 MBJudgeable
Fencing off the darknessGiven a grid of bulb strengths and a ceiling height, compute each square's light level, mark the dark ones, then find the cheapest set of interior squares that contains all dark squares and minimizes the perimeter cost.Hard9GraphMinimum spanning tree+2No attempts yet2s512 MBJudgeable
Bracket SubstringsCount how many distinct balanced bracket sequences appear as non-empty substrings of a given bracket string of length up to 500,000.Hard9StringHash map+2No attempts yet2s512 MBJudgeable
XOR QueriesMaintain an array under appends, rollbacks of the last k elements, and range queries for max XOR, count <= x, and k-th smallest.Hard9TrieSegment tree+2No attempts yet2s512 MBJudgeable
Lowest common ancestor in a dynamic forestMaintain a forest of rooted trees under link, cut, and lowest-common-ancestor queries, printing each LCA.Hard9TreeLinked list+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 6For each query range [i, j], report the highest number of occurrences of any single value inside that range.Hard9Segment treeDivide and conquer+2No attempts yet2s512 MBJudgeable
Counting points inside a circleFor each of M circle queries, count how many of N fixed points lie inside or on the circle, printing the count per query.Hard9GeometryDivide and conquer+2No attempts yet8s512 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
Where are the bubbles?Given the per-turn swap counts of bubblesort, reconstruct the lexicographically largest permutation that produces exactly those swap counts.Hard9ImplementationGreedy+2No attempts yet2s512 MBJudgeable
Allowed swapsMaintain an array under swaps and union operations, answering whether it can be sorted and counting pairs of clouds whose merge would fix both.Hard9Union-findImplementation+2No attempts yet6s512 MBJudgeable
Appropriate Coordinate MapGiven N points, choose a ring through all of them and endpoints A, B so the two legs are monotone in the projection onto AB, maximizing the smallest gap in that projection.Hard9GeometryGreedy+1No attempts yet5s512 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
Jumping ImpalaGiven a lake, a central island, and S unit rocks, find the minimum leap distance letting Vlad reach the island and return twice without landing on any rock twice.Hard9Binary searchGraph+2No attempts yet8s512 MBJudgeable
Mobile Network BandwidthGiven a graph whose edge capacities are polynomials in x, output the max-flow polynomial from node 1 to node N for large x.Hard9GraphGreedy+2No attempts yet8s512 MBJudgeable
Blue ForestGiven several planar floor maps that may be rigid-motion duplicates, unify matching maps, merge their warp gates, then find the shortest route from entrance to exit.Hard9GeometryGraph+2No attempts yet8s512 MBJudgeable
Magical Mystery Knight's TourFill the missing numbers so the 8x8 board becomes a semi-magical knight's tour with equal row and column sums, choosing the lexicographically smallest completion.Hard9BacktrackingBrute force+2No attempts yet2s512 MBJudgeable
Sequence and queries 12Maintain a dynamic sequence under point updates, deletions, and insertions, answering range queries for distinct count and the sum of triple products of distinct values.Hard9Segment treeHash map+2No attempts yet2s512 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
Driving in OptimistanGiven the pairwise distances among n port towns that lie on a tree, reconstruct the tree, place integer-kilometre signs along every edge, and output the average distance over all sign pairs as a reduced fraction.Hard9TreeGreedy+1No attempts yet2s512 MBJudgeable
Triple treeGenerate triples (a,b,c) satisfying a^2+b^2+c^2 = k(ab+bc+ca)+1 by two sweep operations from (1,k,k+k^2), then greedily print triples whose numbers are all new.Hard9MathNumber theory+2No attempts yet1s512 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
Hangar HurdlesGiven an n by n grid of blocked and empty cells, answer q queries asking for the largest centered square crate that can slide between two empty cells.Hard9Union-findBFS+2No attempts yet8s512 MBJudgeable
Risky LotteryFind the unique symmetric Nash equilibrium mixed strategy for a lottery where the winner is the player holding the smallest number written exactly once, and print each pick probability to five decimals.Hard9Game theoryProbability+2No attempts yet2s512 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
HackerSimulate substring comparisons, substring copy from a fixed string, and range letter-increment operations on a mutable string of length N.Hard9Segment treeHash map+2No attempts yet4s512 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
Large Ping Pong TournamentGiven the total points each of 2^N players scored in a knockout ping pong tournament, decide if Dudu, who always wins ties, could have been champion.Hard9GreedySorting+2No attempts yet2s512 MBJudgeable
EggscavationGiven up to 100000 shell species (each in at most 4 cells) and egg insertions, answer queries for the probability that a random K x K scoop covers at least V species and no egg.Hard9GeometryPrefix sum+2No attempts yet10s512 MBJudgeable
LegendsGiven a connected graph, decide whether it can be built from one of five small starting graphs using edge additions, isolated-vertex additions, and vertex splits (each split adds a new vertex adjacent to the old one).Hard9GraphDivide and conquer+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
MinerFor each lamp position above a polyline mine floor, find the reachable floor interval lit without crossing the floor.Hard9GeometryBinary search+2No attempts yet1.5s512 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
Robotic Cow HerdEach robot picks one model per location, and all K robots must differ somewhere; find the minimum total cost of K distinct robots.Hard9HeapGreedy+2No attempts yet2s512 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
Unlucky 89Average the circumferences of all integer right triangles whose hypotenuse is k*sqrt(89) with k up to n, printed as exact mixed numbers in an ASCII box.Hard9Number theoryMath+2No attempts yet2s512 MBJudgeable
Find the SequenceGiven B, decide whether there exist distinct integers A_i > 1 such that A_i^{B_i} is divisible by the product of all the other A_j.Hard9Number theoryMath+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
Map Reduce (Large)Each query asks whether walls can be removed so the shortest S-to-F path equals D, and if so reports the deterministic greedy removal order's final map.Hard9BFSGraph+2No attempts yet5s512 MBJudgeable
The Gardener of Seville (Large)Fill an R by C grid with slash or backslash hedges so that paired border courtiers connect through disjoint corridors, choosing the lexicographically smallest valid maze or reporting IMPOSSIBLE.Hard9ImplementationSimulation+2No attempts yet5s512 MBJudgeable
RonaldGiven a graph on N vertices, a move toggles all edges incident to one chosen vertex; decide whether the complete graph is reachable.Hard9GraphBit manipulation+2No attempts yet1s64 MBJudgeable
The Kingdom of JOIOIPartition an H by W grid into two connected regions whose row and column slices are contiguous, minimizing the larger altitude range within either region.Hard9Binary searchGreedy+2No attempts yet4s256 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
Rides 2Each day one child grows by 1 or 2, and we must report how many of Q fixed child-pair and ride triples become valid that day.Hard9Segment treeSorting+2No attempts yet2s256 MBJudgeable
Distinct Substring QueriesMaintain a string under push-back and pop-front operations, reporting the number of distinct substrings after each of up to a million queries.Hard9StringString matching+2No attempts yet2s512 MBJudgeable
Building a Tall BarnAssign K cows to N ordered floors, each with work a_i, so each floor gets at least one cow; minimize the sum of a_i/c_i over valid allocations, rounded to nearest integer.Hard9GreedyHeap+2No attempts yet2s512 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
Bracket PathsGiven a tree with '(' or ')' on each node, count ordered pairs (a,b) whose path string w_{a,b} is a properly matched bracket expression.Hard9TreeDivide and conquer+2No attempts yet3s1024 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
The Enormous SequenceDefine a_n by summing every nonempty subset sum of the first n-1 terms, then answer queries about gcd, 2-adic valuation of lcm, prefix sums, or a single term for various starting values.Hard9MathNumber theory+2No attempts yet2s128 MBJudgeable
Tarot Sham BoastGiven up to 10 equal-length strings over {R,P,S} and a length n random string, sort the strings by the probability each occurs as a contiguous block.Hard9String matchingProbability+2No attempts yet2s512 MBJudgeable
Shifty GridApply a fixed two-phase procedure of cyclic row and column shifts to sort a permutation grid into row-major order, following the exact TURN steps given.Hard9SimulationImplementation+2No attempts yet2s512 MBJudgeable
Rolling the BottleGiven a convex polygon as a bottle base and a water volume, find the minimum and maximum number of sides of the water region as the bottle rolls.Hard9GeometrySorting+2No attempts yet2.5s512 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
PseudoknotFind the largest t such that the string splits into u v z^R u^R y z with |u|>=t and |z|>=t, or report -1 if no such split exists.Hard9StringString matching+2No attempts yet2s512 MBJudgeable
Creating Fake NewsFind one story vector satisfying n linear equations, then the minimum number of starting people whose reach covers all n people.Hard9MathGraph+1No attempts yet2s512 MBJudgeable
Fashion ShowPlace models on an N by N grid (or upgrade existing ones) so every shared row or column has a plus and every shared diagonal has an x, maximizing style points.Hard9GreedyGraph+2No attempts yet5s512 MBJudgeable
Slate Modern (Large)Fill a huge R by C grid with positive integers so adjacent cells differ by at most D, matching N fixed cells, maximizing the total sum or reporting impossibility.Hard9GraphShortest path+2No attempts yet80s512 MBJudgeable
Omnicircumnavigation (Large)Given points on a unit sphere joined in order by shortest arcs, decide whether the closed path meets every great circle.Hard9GeometryMath+2No attempts yet120s512 MBJudgeable
Stack Management (Small)Decide whether a solitaire game on 2 to 4 short stacks of cards can be reduced to at most one card per stack using two allowed moves.Hard9Game theorySimulation+2No attempts yet5s512 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
Polynomial and QueriesEvaluate a degree-N polynomial with integer coefficients at K given points, all modulo the prime 786433, with N and K up to 250000.Hard9Number theoryDivide and conquer+2No attempts yet10s512 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
Smallest unreachable subsequence sumFor each subarray, find the smallest non-negative integer that no subsequence sums to.Hard9Segment treeGreedy+1No attempts yet2s512 MBJudgeable
Good triples of pathsCount triples of simple paths in a tree that are either node-disjoint or pairwise intersecting, modulo 1e9+7.Hard9CombinatoricsTree+2No attempts yet2s512 MBJudgeable
Strongly MatchableDecide whether an even-order graph admits a perfect bipartite matching for every balanced partition of its vertices.Hard9GraphMath+2No attempts yet3s512 MBJudgeable
Equivalent DeformationGiven two equal-area triangles, find the minimum number of vertex-sliding operations that map the first exactly onto the second.Hard9GeometryImplementation+2No attempts yet2s512 MBJudgeable
LeapfrogGiven up to 40 frogs, each starting at x_i with prime jump d_i, find the smallest position where the number of frogs that land there is largest.Hard9Number theoryMath+1No attempts yet2s512 MBJudgeable
Fractal TreeFor a recursively defined fractal tree F_k, answer queries giving the distance between two DFS-labeled vertices.Hard9TreeRecursion+2No attempts yet7s512 MBJudgeable
Arranging tilesGiven up to 14 convex tiles of equal height with cut corners, find the ordering and horizontal placement that minimizes the total frame width when packed side by side.Hard9Dynamic programmingGeometry+2No attempts yet1s1024 MBJudgeable
CratersFind the shortest single closed fence that surrounds all circles at distance 10 or more, given each crater's center and radius.Hard9GeometryDynamic programming+2No attempts yet2s512 MBJudgeable
Enlarging EnthusiasmCount the distinct final rankings achievable when positive point bonuses summing to x are announced in increasing order, with the lead changing hands each time.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Treasure MapOn a weighted undirected graph, gold decays each day at every mine; starting at mine 1 with forced moves, maximize total gold collected before stopping.Hard9GraphDynamic programming+2No attempts yet2s512 MBJudgeable
Jupiter Rock Paper ScissorsEach player crops a length-k substring, Alice morphs one block, then the play phase awards 2/1/1 points by who reaches m round wins first; report the optimal outcome.Hard9Game theoryImplementation+2No attempts yet2s512 MBJudgeable
IntuidiffFind the minimum number of blocks, each a substring of the first string or a single new character, whose concatenation equals the second string.Hard9String matchingGreedy+2No attempts yet7s512 MBJudgeable
Crazy RotationsGiven a row of coloured lights, find the smallest rotation amount that can appear at position p in a non-decreasing sequence of rotation craziness values.Hard9String matchingCombinatorics+2No attempts yet15s512 MBJudgeable