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 results1,178 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
MarblecoinMarbles sit in stacks; only top marbles can be taken, one per day, and each marble's tax is value times 365 raised to days owned. Minimize the total tax modulo 1e9+7.Medium7GreedySorting+2No attempts yet1s1024 MBJudgeable
HopscotchCount lattice paths from (0,0) to (N,N) where each hop increases x by at least X and y by at least Y, modulo 1e9+7.Medium7Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Robot RaceFor each of up to a million queries on an n by m grid of obstacles, decide whether a monotone path moving only right or down connects the two given empty cells.Medium7Dynamic programmingPrefix sum+2No attempts yet2s1024 MBJudgeable
Palindromic PartitionsSplit a string into chunks so the chunk sequence is a palindrome, and report the maximum number of chunks possible.Medium7StringGreedy+2No attempts yet10s128 MBJudgeable
Skill TreeFor each triangular region of a weighted infinite triangle grid, compute the total cost of all cells in the region modulo 1e9+7.Medium7CombinatoricsMath+2No attempts yet2s512 MBJudgeable
A New SequenceGiven a circular sequence A, compute each b_i as the sum of a_{i+k mod N} weighted by (-1)^k times (k+1) over all k from 0 to N-1.Medium7MathPrefix sum+2No attempts yet2s512 MBJudgeable
TableGiven a rectangle with non-overlapping rectangular obstacles, count integer placements of each query rectangle that overlap none of them.Medium7Prefix sumMatrix+2No attempts yet5s512 MBJudgeable
Diagonal slices of a rectangle unionSum the total length of the union of axis-aligned rectangles cut by each diagonal line y = s - x for integer s in [L, R], and print the result divided by sqrt(2).Medium7GeometryIntervals+2No attempts yet2s512 MBJudgeable
MizuyokanGiven a bar divided by N-1 score lines into segments of given lengths, cut along some lines so the longest and shortest resulting pieces differ as little as possible.Medium7Dynamic programmingBinary search+2No attempts yet2s512 MBJudgeable
MateFor each query, count subsequences of S of length D whose last two characters are the given pair XY, modulo 1e9+7.Medium7CombinatoricsDynamic programming+2No attempts yet2s128 MBJudgeable
Snake EscapingGiven a toxicity value for each of 2^L bitmasks, answer Q queries: each query fixes some bits and leaves others free, and asks the sum of values over all matching masks.Medium7Bit manipulationPrefix sum+2No attempts yet2s64 MBJudgeable
Paul the barista picks coffee beansPick the longest subsequence of the given row so that consecutive picked values are congruent mod k or differ by at most d in absolute value.Medium7Dynamic programmingSegment tree+2No attempts yet1.5s64 MBJudgeable
A Particle on the TreeFor each query edge (U,V) and final color C, count pairs (start, end) whose shortest path uses that edge in that direction and whose arrival color matches C.Medium7TreeDFS+2No attempts yet1s128 MBJudgeable
Road ConstructionGiven a permutation, for each query [l,r] reverse that segment and report the number of maximal increasing runs in the resulting array.Medium7ArrayMath+2No attempts yet1s128 MBJudgeable
Heaven's Kitchen 2Given an array of integers, choose two non-overlapping nonempty contiguous subarrays and maximize the product of their sums.Medium7ArrayDynamic programming+2No attempts yet1s128 MBJudgeable
Open SesameGiven pebble and groove heights per column, choose subarray moves adding or subtracting 1 each second to align all pebbles with grooves in minimum time.Medium7ArrayPrefix sum+2No attempts yet1s256 MBJudgeable
GiftCount sequences of length N that split into blocks where each block is 0,1,...,L-1 with L at most K, modulo 1e9+7.Medium7Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
GameFor each starting size P, two players alternately take a number from a buffer that refills with later sequence elements, and we report Alice's score minus Bob's.Medium7GreedySorting+2No attempts yet2s512 MBJudgeable
File RecoveryDelete elements from a sequence so the remainder parses as length-prefixed blocks that end exactly at the last position, minimizing the largest likelihood among deleted elements.Medium7Dynamic programmingBinary search+2No attempts yet2s512 MBJudgeable
Thor's JourneyIn a perfect binary tree of up to 2^17-1 nodes with node weights, count for each query (start node A, target sum D) how many nodes B lie on a path from A with sum D.Medium7TreePrefix sum+2No attempts yet2s512 MBJudgeable
Avoiding the HeatCount the lattice paths from a start point to a home point using at most T unit steps in the four cardinal directions, avoiding N blocked points.Medium7Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
Andrew's Amazing ArchitectureGiven required block lengths for n columns, choose actual heights forming a unimodal sequence that respects each requirement and minimizes total volume.Medium7ArrayGreedy+2No attempts yet3s512 MBJudgeable
Points and RectanglesProcess point insertions and rectangle insertions online, after each query reporting how many (point, rectangle) pairs have the point inside or on the rectangle.Medium7Segment treePrefix sum+2No attempts yet2s512 MBJudgeable
Coprime IntegersCount ordered pairs (x, y) with x in [a, b] and y in [c, d] that share no common factor greater than 1.Medium7Number theoryMath+2No attempts yet2s512 MBJudgeable
Largest ValueChoose M disjoint contiguous groups in an array of up to 20 numbers so the total sum of their elements is as large as possible.Medium7Dynamic programmingPrefix sum+1No attempts yet2s512 MBJudgeable
New SalariesSalaries are drawn from nested closed intervals. Compute the expected total pairwise salary gaps and output it divided by N squared.Medium7Prefix sumMath+2No attempts yet2s512 MBJudgeable
Expected Value of a PermutationFind the expected total of sums of arrays that zero all indices divisible by each next permutation value, and output that expectation mod 1000000007.Medium7MathNumber theory+2No attempts yet1s512 MBJudgeable
NLOEach day a circular UFO zeroes the grass in cells it covers, remaining grass grows by 1 per day; sum all grass after K days.Medium7GeometryPrefix sum+2No attempts yet3s512 MBJudgeable
Buying Cards 3Sum, over all contiguous subarrays, of (maximum minus minimum) in the subarray.Medium7StackArray+2No attempts yet2s512 MBJudgeable
Sequence and Queries 23Given a sequence and range queries, count for each query the number of pairs inside the range where an earlier element exceeds a later one.Medium7Divide and conquerSorting+2No attempts yet5s512 MBJudgeable
Grid QueryProcess N rectangle-add updates and Q rectangle-sum queries on a sparse 200000 by 200000 grid, then XOR all query answers.Medium7Prefix sumMatrix+2No attempts yet4s1024 MBJudgeable
Goldbach TripleFor each odd N up to one million, count the unordered ways to write N as a sum of three primes.Medium7Number theoryMath+2No attempts yet2s512 MBJudgeable
King of Pie, Kim PieChoose one box length x in [L,R] to minimize x times the number of boxes needed to pack pies of given lengths into consecutive groups, where a length-0 pie must sit alone.Medium7Dynamic programmingBinary search+2No attempts yet1s512 MBJudgeable
Why the Rabbit Came to Information IslandA rabbit moves right, up-right, or down-right through a grid with walls, carrots, and side gates; maximize carrots collected before exiting a side gate.Medium7Dynamic programmingImplementation+2No attempts yet1s256 MBJudgeable
Energy HarvestingSum over all lattice points (x,y) with 1<=x<=n, 1<=y<=m of 2*gcd(x,y)-1, the energy lost reaching that point from the origin.Medium7Number theoryMath+2No attempts yet1s512 MBJudgeable
NyehuingGiven a sequence of N values, count for each ordered pair whether one value appears after another, then answer queries for the K-th smallest valid pair.Medium7CombinatoricsPrefix sum+2No attempts yet1s1024 MBJudgeable
Flag DanceMaintain an array under point updates and answer range queries for the absolute difference between sums of charismas at even and odd positions within the range.Medium7Segment treePrefix sum+2No attempts yet2s512 MBJudgeable
Hay WeightAfter each mowing that cuts every blade above height b, report the total hay cut, given growth rates and chronological mowing days.Medium7SortingBinary search+2No attempts yet2s512 MBJudgeable
Fortune TellingGiven M by N cards and K rectangle flip operations, count how many cards end face up after all operations.Medium7SortingPrefix sum+2No attempts yet2s512 MBJudgeable
Gluttonous GoopGiven an r by c grid of fungus cells and k steps, each step expands the fungus to all 8 neighbors, and the fungus grows past the grid; count occupied cells at the end.Medium7GeometryMath+2No attempts yet3s512 MBJudgeable
Beer MugsGiven a string of N characters over 20 brands, find the longest substring that is a palindrome after permuting it freely.Medium7Bit manipulationHash map+2No attempts yet2s512 MBJudgeable
Mixing DrinksCount the ways to split the sequence 1..N into consecutive nonempty blocks so that no block contains both endpoints of any listed bad pair, modulo 1e9+7.Medium7Dynamic programmingTwo pointers+2No attempts yet1s512 MBJudgeable
High Load DatabaseSplit a fixed array of transaction sizes into the fewest consecutive batches, each with total at most t, answering many t values; report Impossible when some transaction exceeds t.Medium7Binary searchPrefix sum+2No attempts yet2s512 MBJudgeable
WinteringMaintain acorn counts on a circular walkway split into contiguous regions, supporting range additions and range sum queries over possibly wrapping cell intervals.Medium7Segment treePrefix sum+2No attempts yet2s256 MBJudgeable
Radio PrizeIn a weighted tree, for every city u output the sum of (t[u] + t[v]) * dist(u, v) over all other cities v.Medium7TreeDFS+2No attempts yet3s512 MBJudgeable
Sum and ProductCount the subarrays of length at least 2 in which the sum of the elements equals their product, where each element is a positive integer up to 1e9.Medium7Two pointersMath+2No attempts yet2s512 MBJudgeable
Milk VisitsGiven a tree with a cow type at each node, answer for each of M queries whether a node on the path from A to B has type C.Medium7TreeDFS+2No attempts yet2s512 MBJudgeable
Moortal CowmbatRewrite a length-N string into streaks of at least K identical letters, where changing any single position from letter i to j costs a shortest-path distance over an M-letter graph; minimize total cost.Medium7Dynamic programmingShortest path+2No attempts yet1s512 MBJudgeable
Trous de LoupGiven n weighted positions, a sandbag budget p, and a plank covering d consecutive positions, find the longest contiguous segment that can be fully disarmed.Medium7Sliding windowTwo pointers+2No attempts yet2s512 MBJudgeable
Stacking horizontal blocksDrop N horizontal blocks one by one at fixed positions, each landing on the tallest surface below it, and report the final stack height.Medium7Segment treeBinary search+2No attempts yet1s512 MBJudgeable
Christmas TreeMaintain a dynamic set of colored nodes in a rooted tree under insertions and deletions, and after each update report the lowest common ancestor of all colored nodes.Medium7TreeDFS+2No attempts yet2s512 MBJudgeable
Flipping El-fetieraEach of K operations picks a uniformly random rectangular submatrix and flips every cell in it; compute the expected number of cells holding 1 at the end.Medium7ProbabilityDynamic programming+2No attempts yet10s512 MBJudgeable
Equal DigitsCount the ways to delete disjoint substrings of length over 1 whose first and last digits match, so the remaining non-empty string has all distinct digits.Medium7Dynamic programmingCombinatorics+2No attempts yet3s256 MBJudgeable
Cube SummationFor each N, sum k^3 over all partitions of N with k parts, modulo 998244353, with up to 1e5 queries.Medium7Dynamic programmingCombinatorics+2No attempts yet4s512 MBJudgeable
Matrix SumCount the submatrices of an N by M matrix whose element sum is at most x.Medium7Prefix sumTwo pointers+2No attempts yet2s256 MBJudgeable
Random GeneratorSimulate repeatedly picking the p-th remaining copy from a multiset where value i appears w_i times, and output the order in which values are exhausted.Medium7Segment treeBinary search+2No attempts yet1s1024 MBJudgeable
PilotFor each of Q altitude limits, count subarrays of heights whose maximum is at most that limit.Medium7StackSorting+2No attempts yet1s512 MBJudgeable
LasersEach row holds sliding walls of fixed widths; count laser positions blocked in every possible configuration across all rows.Medium7IntervalsGreedy+2No attempts yet1s512 MBJudgeable
Downloading EpisodesChoose one fixed sequence of byte requests so that all n episodes download with minimum total packet size, where each packet adds a fixed header k.Medium7Dynamic programmingGreedy+2No attempts yet1s512 MBJudgeable
School OlympiadAssign n students at given coordinates to three locations with capacity limits so the total walking distance is minimized.Medium7GreedySorting+2No attempts yet1s512 MBJudgeable
Nemmo Nemmo 2020The board holds rows of nemmo forming a nonincreasing staircase; for each query (x, y), count the nemmo removed by a laser firing up column x and right along row y.Medium7Binary searchPrefix sum+2No attempts yet3s1024 MBJudgeable
Fighting RoutineFor every window length d from 1 to n, sum the number of distinct task types over all length-d windows of the given array.Medium7ArrayPrefix sum+2No attempts yet2s512 MBJudgeable
School DemocracyPartition the classes into consecutive groups of size between l and r, and maximize the total difference between elected boys and girls, where each group elects the side with more votes or both on a tie.Medium7Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
Interval TrainingCount sequences of positive integers starting at k, summing to n, whose adjacent comparisons strictly alternate up and down, modulo 1e9+7.Medium7Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
UnicornCount the number of paths on an N by M letter grid where a chess unicorn piece spells out a given word, modulo 1e9+7.Hard8Dynamic programmingPrefix sum+2No attempts yet2s128 MBJudgeable
Floor DecorationGiven a rectangular window into an infinite 1x5 plank tiling pattern, find the minimum number of 1x5 boards needed to supply all the pieces inside it.Hard8MathImplementation+2No attempts yet2s128 MBJudgeable
Misheard BinaryCount distinct binary strings obtainable by shifting each bit of an N-bit number at most D positions, then output the K-th smallest such string.Hard8Dynamic programmingCombinatorics+2No attempts yet2s128 MBJudgeable
Returning to FarmingCount unordered pairs of non-empty axis-aligned rectangles on an N x N grid that touch at exactly one corner and have equal total cell profit.Hard8Prefix sumHash map+2No attempts yet1s256 MBJudgeable
Weather ForecastingChoose r horizontal and s vertical cut lines on an N x M grid to minimize the maximum sum of cell values inside any resulting rectangular section.Hard8Binary searchDynamic programming+2No attempts yet2s128 MBJudgeable
Jinuk's FarmGiven up to 50 axis-aligned square paint operations over an N up to 1000 grid, find the largest square subregion containing no fruit type 0 and at most two distinct fruit types.Hard8Binary searchPrefix sum+1No attempts yet2s128 MBJudgeable
SquaresGiven up to 50 axis-aligned rectangles whose overlapping edges may form extra squares, count every square whose sides lie entirely on drawn line segments.Hard8GeometryPrefix sum+2No attempts yet2s128 MBJudgeable
Rook AttacksPlace two rooks on an N x N grid so the total value of all cells attacked by either rook (excluding the rook cells) is maximized.Hard8MathPrefix sum+2No attempts yet2s128 MBJudgeable
Freight TrainGiven two trains as unions of intervals of occupied cars, find the smallest forward shift of one train that maximizes the count of aligned occupied cars.Hard8IntervalsMath+2No attempts yet2s128 MBJudgeable
PyramidFind placement of an a×b pyramid and interior c×d room on a height grid maximizing the average height of pyramid cells excluding the room, requiring 2D prefix sums and sliding min-window optimization.Hard8Prefix sumSliding window+2No attempts yet2s128 MBJudgeable
Two SequencesPartition two sequences from the back into matched groups to minimize the total sum of products of adjusted group sums, requiring an optimized DP over prefix sums.Hard8Dynamic programmingPrefix sum+1No attempts yet2s128 MBJudgeable
Student GroupsPartition an ordered list of students into contiguous groups minimizing mismatches between grouping and a given friendship graph, using DP over prefix structure with an efficient cost computation.Hard8Dynamic programmingGraph+1No attempts yet1s256 MBJudgeable
Tug of WarSplit two weighted sequences each into three ordered nonempty contiguous parts so paired-part weight differences stay under 50 and the maximum difference is minimized.Hard8Binary searchPrefix sum+1No attempts yet1s128 MBJudgeable
Easy Group MatchingGiven a text sequence and two patterns, count group-matching positions for each pattern, then find the smallest integer n that maximizes group matches for the concatenated pattern P1·n·P2 and report that count.Hard8Dynamic programmingPrefix sum+1No attempts yet30s1536 MBJudgeable
Monoliteral PolygonsCount integer translations of a given rectilinear polygon so it stays inside a lettered grid and covers cells of only one letter.Hard8Prefix sumGeometry+1No attempts yet2s128 MBJudgeable
Black RectanglesCount unordered pairs of disjoint all-black axis-aligned rectangles (each containing at least two cells) in an up to 1000x1000 grid, modulo 10007.Hard8Prefix sumCombinatorics+1No attempts yet1s128 MBJudgeable
FishermenGiven fish production along towns on a line with transport losses proportional to distance, find the maximum equal number of children every town can feed via binary search on feasibility.Hard8Binary searchGreedy+1No attempts yet1s128 MBJudgeable
DistanceGiven a walk on a grid, find a contiguous segment of moves to delete so the remaining path stays within a bounding rectangle and ends as close as possible to the target point.Hard8Prefix sumTwo pointers+2No attempts yet1s128 MBJudgeable
DominanceGiven up to 3000 colored squares each with a Manhattan-distance attack range on a huge grid, count how many grid cells are dominated by white versus black using a diamond-shaped coverage counting technique.Hard8GeometryPrefix sum+1No attempts yet2s128 MBJudgeable
AntsGiven a forest of towns formed by persistent range-add copies of parent towns, answer range-sum queries on each newly created version using online, XOR-derived parameters that depend on previous answers.Hard8Segment treePrefix sum+2No attempts yet3s128 MBJudgeable
Gadgets FactoryGiven m sorted factories each producing one of n part types, find all coordinates t minimizing the sum over parts of squared distance to the nearest factory of that part, expressed as exact fractions.Hard8MathBinary search+2No attempts yet3s256 MBJudgeable
CommandoPartition soldiers into consecutive blocks, each block's score is a concave quadratic of its sum, and maximize the total score.Hard8Dynamic programmingDivide and conquer+2No attempts yet1s64 MBJudgeable
Digging for OilPlace three non-overlapping K by K squares on an M by N grid of oil estimates to maximize the total sum covered, with the grid up to 1500 by 1500.Hard8Prefix sumDynamic programming+2No attempts yet2s128 MBJudgeable
Square CountCount all axis-aligned squares whose unit tiles lie in the union of rectangular rooms, where adjacent rooms connect through centered doors.Hard8GeometryImplementation+2No attempts yet1s128 MBJudgeable
Coffee ShopsFor each query radius m, find the grid intersection reached by the most coffee shops within Manhattan distance m, breaking ties by smallest y then smallest x.Hard8Prefix sumGeometry+2No attempts yet5s128 MBJudgeable
Magic SticksSplit a chain of segments into disjoint runs of consecutive segments, close each run into a cyclic polygon, and maximize the total area, where each polygon's best area is the cyclic one.Hard8Dynamic programmingGeometry+2No attempts yet8s128 MBJudgeable
Brownie Points IIGiven points in the plane, Stan picks a vertical line and Ollie a horizontal line through it; find Stan's guaranteed score and the distinct best Ollie scores.Hard8SortingPrefix sum+2No attempts yet1s128 MBJudgeable
Spare the Ewoks!Given an m by n grid with blocked cells, choose up to three non-overlapping axis-aligned rectangles to maximize the total covered area.Hard8Dynamic programmingPrefix sum+1No attempts yet3s128 MBJudgeable
StatisticiansGiven a grid of counts, take the median of the mean densities over all axis-aligned subrectangles whose area lies in [a,b].Hard8Prefix sumBinary search+1No attempts yet1s128 MBJudgeable
HeritageDivide a region under a polygonal line into parcels whose areas match given ratios, choosing vertical cuts that minimize the total fence length.Hard8Dynamic programmingGeometry+2No attempts yet0.3s64 MBJudgeable
Pyramid BaseGiven up to 1000 weighted rectangles on a grid up to 10^6 by 10^6, find the largest axis-aligned square whose total cost of intersected rectangles is at most B.Hard8Binary searchGeometry+2No attempts yet5s128 MBJudgeable
GardenPlace two non-overlapping rectangles, each holding exactly k roses, and minimize the sum of their perimeters over an l by w grid with n roses.Hard8ArrayPrefix sum+2No attempts yet1s128 MBJudgeable
MountainsMaintain a piecewise-constant sequence of elevation changes under range assignments, and after each update find the first prefix-sum position whose elevation exceeds a query height h.Hard8Segment treeBinary search+2No attempts yet3s256 MBJudgeable
ArtemisGiven N points with distinct x and y, find the axis-parallel rectangle with two opposite corners on points that contains at least T points and the fewest total points.Hard8Prefix sumBinary search+2No attempts yet2s128 MBJudgeable
Bubble SortSwap exactly one pair of elements in the array, then find the minimum number of swaps the given bubble sort performs on the result.Hard8SortingPrefix sum+1No attempts yet1s128 MBJudgeable
Habitat Range of FishGiven up to 50 axis-aligned boxes in 3D, compute the total volume covered by at least K of them.Hard8SortingDivide and conquer+1No attempts yet1s128 MBJudgeable