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
Flyswatter placementsCount the integer translations of a fixed polygon that keep it inside an axis-aligned rectangle and avoid all given points, including points on the boundary.Hard8GeometryPrefix sum+2No attempts yet1s256 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
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
Jenga BoomSimulate removals from a Jenga-like tower and report whether it falls, and at which removal, when a level's center of mass leaves the convex hull of the blocks still supporting it.Hard8GeometrySimulation+2No attempts yet2s512 MBJudgeable
Solar FlightFor a line segment query, find the maximum total intercept-weight above a given ray over all x in a length-K window.Hard8GeometrySorting+2No attempts yet15s512 MBJudgeable
Broadcast Tower OffersFor each offered tower height, find the best position along a row of buildings and report how many buildings to its west can receive its westward signal.Hard8StackSorting+2No attempts yet2s512 MBJudgeable
FenceSum x! times y! over all unit cells inside an axis-aligned polygon, modulo 1e9+7, with coordinates up to 1e9.Hard8MathPrefix sum+2No attempts yet3s512 MBJudgeable
Beautiful PathsOn a tree with capitals 1 and 2, sum over all pairs of cities of the minimum distance-to-nearest-capital along their path.Hard8TreeDFS+2No attempts yet1s128 MBJudgeable
IvoizationSum the Ivoization values of every K by K submatrix, where Ivoization is the pairwise absolute-difference sum of all K^2 entries, modulo 10007.Hard8SortingPrefix sum+2No attempts yet1.5s128 MBJudgeable
TrufflesGiven a grid of per-meter values, compute for each of M slanted lines the weighted length integral of the line through the grid, rounded to five decimals.Hard8GeometryPrefix sum+1No attempts yet3s128 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
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
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
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
Company Culture 4On a rooted tree, praise spreads downward from an employee to all descendants or upward to all ancestors, the direction flips over time, and queries ask for an employee's accumulated praise.Hard8TreePrefix sum+2No attempts yet2s512 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
PoklonFor each query interval, count distinct values that occur exactly twice within it. N and Q go up to 500,000.Hard8Prefix sumHash map+1No attempts yet5s512 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
SemiexpressChoose exactly K stops for a new train so that the number of stations reachable from station 1 within T minutes is maximized.Hard8GreedyBinary search+1No attempts yet1s256 MBJudgeable
Rides 1Each day one child grows by 1 cm; after each growth, count how many of Q given pairs (i,j) can ride their specified ride, where the pair's combined height meets the ride's limit.Hard8SortingBinary search+2No attempts yet2s256 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
Modern Art (Platinum)Given the final N x N canvas painted by N^2 nested rectangles, count how many colors could have been painted first.Hard8ImplementationPrefix sum+1No attempts yet2s512 MBJudgeable
Segment Friends (Large)Given N segments on a line, build the intersection graph and answer Q shortest-path queries between segment pairs, or report -1.Hard8GraphBFS+2No attempts yet2s256 MBJudgeable
RMT Subway Load TestEach subway line is a cycle of stations; line operations rotate passenger counts around the cycle, and range-sum surveys must be answered online.Hard8Segment treePrefix sum+2No attempts yet5s512 MBJudgeable
Product of GCDsCompute the product of gcd(i, j) over all pairs 1<=i<=N, 1<=j<=M, modulo 1e9+7, with N and M up to 15 million.Hard8Number theoryMath+2No attempts yet5s512 MBJudgeable
Sum of least common multiplesSum lcm(x, y) over all pairs 1<=x<=n, 1<=y<=m that share no squared prime factor.Hard8Number theoryMath+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
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
Even substringsFor each query listing up to 5 letters, count substrings of S in which every listed letter occurs an even number of times.Hard8Bit manipulationHash map+1No attempts yet2s512 MBJudgeable
Airport CoffeeGiven spaced coffee carts along a corridor, choose where to buy cups so the total walking time with alternating slow and fast phases is minimized, output as a fraction.Hard8Dynamic programmingGreedy+2No attempts yet6s512 MBJudgeable
BrincadeiraGiven an LFSR over N up to 30 bits, find a contiguous run of at least Y generated values whose sum is divisible by X, minimizing the end index then the start index.Hard8Prefix sumHash map+1No attempts yet1s1024 MBJudgeable
LinearvilleFor each query, find the length of a shortest path between two grid crossings when the path must alternate directions at every crossing.Hard8Shortest pathGraph+2No attempts yet1s1024 MBJudgeable
Joker's Card TrickAfter each point update to a row of nonzero integers, find the smallest prefix index maximizing the running sum of values scaled by the total positive and total negative sums.Hard8Segment treePrefix sum+2No attempts yet3s512 MBJudgeable
Corporate life after a hostile takeoverGiven two rooted trees on the same n employees, count for each employee how many others are descendants in both trees.Hard8TreeDFS+2No attempts yet0.5s1024 MBJudgeable
Posters on the wallGiven up to 50000 non-overlapping axis-aligned rectangles, answer online queries that ask for the total rectangle area inside a query rectangle, with coordinates decoded from the previous answer.Hard8Segment treeSorting+2No attempts yet2s1024 MBJudgeable
Buffalo BarricadesFor each settler arriving in order, count the buffalos inside the region bounded by rivers and fences whose upper right corner is the settler's post.Hard8SortingPrefix sum+2No attempts yet5s512 MBJudgeable
Donut DroneSimulate a drone on a toroidal grid where each step moves to the highest of three rightward neighbors, handling up to 1e9 steps per move query and elevation updates.Hard8SimulationBinary search+2No attempts yet8s512 MBJudgeable
The Great WallEach design picks two length-r intervals whose overlap height adds extra cost; find the k-th smallest total wall height over all interval pairs.Hard8Binary searchPrefix sum+2No attempts yet3s512 MBJudgeable
Medical CheckupGiven n students in a fixed queue and their per-item service times, report the item each student is on or waiting for at time t+0.5.Hard8SimulationMath+2No attempts yet2s512 MBJudgeable
Starting a Scenic Railroad ServiceFor n travel segments, compute the minimum seats needed under arbitrary online seat choices and under optimal offline assignment.Hard8GreedySorting+2No attempts yet2s512 MBJudgeable
Winning SegmentsGiven a permutation of 0..2^M-1, count the nonempty subarrays whose XOR can be made equal to 2^M-1 by one mandatory swap of two elements.Hard8Bit manipulationPrefix sum+2No attempts yet4s256 MBJudgeable
K-summaryGiven segment lengths K_i, count how many array positions are pinned down by all the K_i-summaries.Hard8MathNumber theory+2No attempts yet0.5s64 MBJudgeable
Guardians of the LunaticsSplit a row of L cells into at most G contiguous nonempty blocks, where a block of length k multiplies each member's craziness by k, to minimize the total cost.Hard8Dynamic programmingDivide and conquer+2No attempts yet7s512 MBJudgeable
Computer ScienceFind the smallest L such that for each a_i we can pick an interval [x_i, x_i+L] covering a_i and containing at least K of the given integers.Hard8Binary searchSorting+2No attempts yet2s512 MBJudgeable
HH CountryFor each query set of tree vertices, output twice the sum of pairwise tree distances.Hard8TreeDFS+1No attempts yet10s512 MBJudgeable
K-Uniform StringCount binary strings of length N where, for each of M given intervals, every length-K substring inside it contains the same number of ones, modulo 1e9+7.Hard8Dynamic programmingCombinatorics+2No attempts yet1s256 MBJudgeable
Äventyr 2On a tree, timelines get marked over time, and after each mark you must report the distance from a queried vertex to the nearest marked vertex.Hard8TreeBFS+2No attempts yet1s256 MBJudgeable
SlingshotFor each of M queries (a, b), find the minimum time to move manure from a to b using the tractor (cost equals distance) plus at most one slingshot that flies from x to y in time t.Hard8Divide and conquerSorting+2No attempts yet2s512 MBJudgeable
MagicCount substrings of an N-character string in which all K distinct letters of the whole string appear an equal number of times, modulo 1e9+7.Hard8Hash mapPrefix sum+2No attempts yet2s512 MBJudgeable
ANTSGiven a tree and a set of up to 50 marked nodes per query, find the node minimizing the sum of distances to all marked nodes, for up to 5000 queries.Hard8TreeDFS+2No attempts yet2s512 MBJudgeable
Nordic CampingGiven a grid with rocky cells blocked, answer queries each asking for the area of the largest all-usable square subgrid that contains a specified water source cell.Hard8Dynamic programmingBinary search+2No attempts yet2s512 MBJudgeable
Split and MergeGiven two tilings of a 1xL board by 1x1 and 1x2 pieces, find the minimum number of split/merge operations to transform one into the other and count the ways.Hard8Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
Harmonious MatrixGiven a 2xN or 3xN matrix of distinct integers, find the largest subset of columns whose orderings within each row are identical, and report its column count.Hard8SortingHash map+2No attempts yet5s768 MBJudgeable
ShootingsGiven non-overlapping axis-aligned rectangles and shots that are vertical or 45-degree half-lines, compute for each shot the squared total length of its intersection with all rectangles.Hard8GeometrySorting+2No attempts yet1s512 MBJudgeable
Fair ShareGiven n weighted points around the origin, choose a line through the origin that splits them into two half-planes, minimizing the absolute difference of the two half-plane weight sums.Hard8GeometrySorting+2No attempts yet5s512 MBJudgeable
Injecting DNAFor every suffix of a string, compute its toxicity from the number of out-of-order suffix pairs, then output the length of the suffix with the largest effectiveness.Hard8StringSorting+2No attempts yet2s512 MBJudgeable
CherrypickFor each cell, find the axis-aligned square containing it that maximizes the minimum cherry sweetness minus the square of its side length.Hard8MatrixBinary search+2No attempts yet2s512 MBJudgeable
Number Theory and Applications: RecitationGiven n up to 1e9 and v up to 100, compute the sum over i=1..n and u=1..v of Jordan's totient function modulo 1e9+7.Hard8Number theoryMath+2No attempts yet4s512 MBJudgeable
ClustersPartition companies 1..N into contiguous clusters, each led by its first or last company whose limit L_i caps the size, minimizing the sum of C_i*S + T_i over leaders.Hard8Dynamic programmingPrefix sum+2No attempts yet3s1024 MBJudgeable
Array StudyFor each of q subarray queries on an array of 1 and -1, find the longest zero-sum subarray inside it, and print the sum of these lengths.Hard8Prefix sumDivide and conquer+2No attempts yet2s512 MBJudgeable
RectanglesGiven up to 100,000 axis-aligned rectangles drawn by XOR-flipping pixels on a white field, find the total count of black pixels.Hard8Segment treePrefix sum+2No attempts yet2s512 MBJudgeable
Metro LinesA tree is given, and for each query with two pairs of terminals, count the stations shared by the two paths between those pairs.Hard8TreeLinked list+2No attempts yet2s512 MBJudgeable
Pixel TrianglesGiven up to four million right isosceles triangles on a 2000x2000 grid, count the total number of grid cells covered by at least one triangle.Hard8Prefix sumMatrix+2No attempts yet2s512 MBJudgeable
Dropping BlocksGiven pile heights, decide whether prefix-wise operations (add 1 to a prefix or a suffix starting at k) can produce exactly that array, and say valid or invalid.Hard8GreedyMath+2No attempts yet2s512 MBJudgeable
King Kog's ReceptionKnights join or cancel reservations with a start time and duration; after each change, a query asks how long a visitor arriving at time t must wait, since she yields to a knight arriving at the same instant.Hard8Segment treeBinary search+2No attempts yet2s512 MBJudgeable
Three Primary ColorsGiven up to 25,000 colored rectangles painted one at a time without repainting already covered pixels, report the total area of each of the seven resulting color regions.Hard8Divide and conquerSegment tree+2No attempts yet3s256 MBJudgeable
Sequential YahtzeeGiven up to 195 sequential dice rolls, assign consecutive segments to the 13 Yahtzee categories in order to maximize the total score.Hard8Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
XOR SubmatrixBuild the N by M matrix with A[i][j] = V[i] xor U[j] and find the submatrix whose elementwise xor is maximal.Hard8Bit manipulationTrie+2No attempts yet2s512 MBJudgeable
Sequence and Queries 22Given a sequence and a stream of updates and range-sum queries, answer each query for the sequence state after its k-th update only, where k can be any earlier prefix of updates.Hard8Segment treeDivide and conquer+2No attempts yet1s512 MBJudgeable
Piece of CakeGiven a convex polygon with n vertices in clockwise order, compute the expected area of the convex polygon formed by picking k of the vertices uniformly at random.Hard8CombinatoricsGeometry+2No attempts yet2s512 MBJudgeable
RedistrictingGiven a string of H and G representing a line of cows, split it into contiguous districts of length at most K minimizing the number of districts where G outnumbers or ties H.Hard8Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
Cow DatingGiven probabilities p_i, choose a contiguous interval maximizing the chance that exactly one bull accepts, and print 10^6 times that probability rounded down.Hard8MathTwo pointers+2No attempts yet2s512 MBJudgeable
Painting the Barn (Gold)Given N painted axis-aligned rectangles on a 200x200 grid, add up to two disjoint rectangles to maximize the total area covered by exactly K coats.Hard8Prefix sumMatrix+2No attempts yet2s512 MBJudgeable
Artifact RestorationGiven a grid with some unknown cells, fill unknowns with 0 or 1 so that the total number of people summed over all subrectangles is divisible by K.Hard8MathNumber theory+2No attempts yet1s512 MBJudgeable
Broken DataDelete some integers from a sequence so the rest reads as N M U1 V1 ... UM VM with 1 <= Ui,Vi <= N; among all valid restorations, maximize N, then M.Hard8ImplementationGreedy+2No attempts yet1s512 MBJudgeable
Ants on a CircleAnts move on a circle of N points, reversing on collision; for each query (P, X) find the earliest time point P has been visited at least X times.Hard8MathSimulation+2No attempts yet1s512 MBJudgeable
Circular DNAGiven a circular sequence of start and end markers for many gene types, choose a cut position that maximizes how many gene types have their markers properly nested in the resulting linear subsequence.Hard8ArrayStack+2No attempts yet3s512 MBJudgeable
ZooGiven a string, count for each prefix the non-overlapping prefix-suffix matches and output the product of (count+1) modulo 1e9+7.Hard8StringString matching+2No attempts yet1s512 MBJudgeable
Highway CyclingChoose a constant speed for each of N road segments so the total energy spent stays within EU and the total travel time is minimized.Hard8Binary searchMath+2No attempts yet1s512 MBJudgeable
Super PianoPick k distinct subarrays whose lengths lie between L and R, maximizing the total sum of their elements.Hard8HeapPrefix sum+2No attempts yet2s512 MBJudgeable
Union of BallsAll ball centers lie on the x-axis, so the union is a solid of revolution; compute its volume as p/q times pi and output p times q inverse mod 1e9+7.Hard8GeometrySorting+2No attempts yet2s1024 MBJudgeable
Making a FlyswatterGiven a simple polygon, find the expected squared distance between two points chosen independently and uniformly inside it.Hard8GeometryMath+2No attempts yet1s1024 MBJudgeable
Paris by NightGiven N graded points in general position, pick two boundary monuments and split the rest by the line through them to minimize the absolute difference of the two side sums.Hard8GeometrySorting+2No attempts yet15s512 MBJudgeable
Stop Counting!Given a deck of integers, choose one contiguous block to skip so the average of the remaining cards is maximized.Hard8MathPrefix sum+2No attempts yet7s1024 MBJudgeable
XORangesMaintain an array under point updates and answer queries for the XOR of every contiguous subarray inside [l, u].Hard8Bit manipulationSegment tree+2No attempts yet1s512 MBJudgeable
ExamFor each of Q threshold triples, count students with S>=X, T>=Y, and S+T>=Z, where N and Q reach 100000.Hard8SortingPrefix sum+2No attempts yet3s1024 MBJudgeable
IOIOI CardsGiven a row of I/O cards and interval flip operations with per-length costs, decide whether all cards can be turned face up and find the minimum total flip time.Hard8Shortest pathGraph+2No attempts yet1s512 MBJudgeable
Fibonacci MusicBuild a digit string from Fibonacci numbers reduced mod M and answer queries for the N-th digit, with N up to 10^15.Hard8MathNumber theory+2No attempts yet1s512 MBJudgeable
Ranch CCTVFor each query, sheep in a grid shift one cell per day in a fixed direction for K days; report the XOR of the daily maximum over the CCTV rectangle.Hard8Prefix sumMatrix+2No attempts yet2s256 MBJudgeable
3D Points and QueriesCount points inside axis-aligned 3D boxes, where each query's box coordinates are decoded by XOR with the running sum of previous answers.Hard8Segment treeSorting+2No attempts yet7s1024 MBJudgeable
Strike ZoneGiven weighted point sets P1 (+c1 each) and P2 (-c2 each) with distinct x and y coordinates, find an axis-parallel rectangle maximizing c1*s minus c2*b.Hard8Dynamic programmingSorting+2No attempts yet1s512 MBJudgeable
True/False WorksheetCount binary strings of length n that satisfy range hints, where each hint says a range is all equal or not all equal, modulo 1e9+7.Hard8Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
Water Tanks of Seongdae CountryA tree of water tanks rooted at a capital. Adding water at city A adds 1,2,3,... along the root-to-A path. Answer queries about how much water a given city currently holds.Hard8TreeDFS+2No attempts yet1s256 MBJudgeable
Shortest Paths and QueriesGiven a grid with up to 5 rows and 100,000 columns, answer queries for the minimum-weight monotone-free path between two cells.Hard8Dynamic programmingMatrix+2No attempts yet5s512 MBJudgeable
GrudanjeGiven a word and Q substrings, find the first snowball throw index (in a given order of positions) after which no substring contains two uncovered equal letters.Hard8ArrayBinary search+2No attempts yet2s512 MBJudgeable
Close NumbersGiven a permutation p and q range queries [l, r], find the minimum absolute difference between any two values in the subarray p[l..r].Hard8ArraySorting+2No attempts yet2s512 MBJudgeable
Black DebtContestants get point increases over time; after each update, report the total count of (yellow, black) pairs where the black contestant has strictly more points.Hard8Segment treeBinary search+2No attempts yet1s512 MBJudgeable
Hero's HistogramGiven a histogram of n columns, for every prefix of the first j columns report the largest axis-aligned rectangle that fits inside that prefix.Hard8StackPrefix sum+2No attempts yet1s512 MBJudgeable