cho.sh

Curated sets

Math and counting

Number theory, combinatorics, and geometry.

All problems
Total results6,670 problems
TopicsJudge
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
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
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
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
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
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
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
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
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
GCD SumFor each k from 1 to n, split a multiset of n numbers into k nonempty groups to maximize the sum of the groups' gcds. n is up to 500000 and each value up to 10^12.Hard9Number theoryGreedy+2No attempts yet2s1024 MBJudgeable
SkiingFind the shortest polygonal path from S down to F that crosses n horizontal gates in top-to-bottom order, and output its breakpoints.Hard9GeometryGreedy+2No attempts yet1s1024 MBJudgeable
Restaurant BribesGiven a friendship graph and a list of k people to bribe, choose a real bribe for each so the total restaurant revenue minus bribe money is maximized, and print the answer as an exact reduced fraction.Hard9GraphMath+2No attempts yet2s512 MBJudgeable
Lunar LandscapeCompute the total area covered by axis-aligned squares and 45-degree rotated squares, counting overlaps once.Hard9GeometrySorting+1No attempts yet2s512 MBJudgeable
ToysCount the number of distinct toys formed by strings joining n evenly spaced clamps on one disc to m on another, where rotating each disc independently gives the same toy, modulo 1,000,000,007.Hard9CombinatoricsNumber theory+2No attempts yet2s512 MBJudgeable
Workbook AlgorithmsCount the number of undirected graphs X on N vertices whose number of permutations P satisfying G(P)=X lies between l and r, modulo 1e9+7.Hard9CombinatoricsGraph+2No attempts yet1s512 MBJudgeable
Secret AgentGiven a planar straight-line graph (castle walls) where crossing a wall costs its height, find the minimum cost to travel between successive query points, starting from infinity.Hard9GraphGeometry+2No attempts yet2s512 MBJudgeable
GarageMaintain a sequence under point updates, and for each range query count subarrays whose elements share a common divisor greater than 1.Hard9Segment treeNumber theory+2No attempts yet4s256 MBJudgeable
Counting CyclesA connected undirected graph with n vertices and at most n+15 edges is given; count all simple cycles, where a simple cycle is a connected subgraph with every degree exactly two.Hard9GraphDFS+2No attempts yet4s512 MBJudgeable
LeadersAnimals in a circle alternately raise a running number by 1 to K; whoever is forced to say M loses, and we find the winner of every start position.Hard9Game theoryDynamic programming+2No attempts yet3s512 MBJudgeable
Disco Dance DebacleGiven a grid where some cells are unlit (unions of rectangles), find the fewest cell states to flip so that a set of alternating row-column dances can cover all lit cells, each dance starting and ending on the same cell with different first and last feet.Hard9GraphGreedy+2No attempts yet5s512 MBJudgeable
KabobsCount length-K strings over the given alphabet that satisfy all substring-implication rules of the form b>e, modulo 10^7.Hard9Dynamic programmingString+2No attempts yet5s512 MBJudgeable
Vera and Love TrianglesFor each pair of friends, a crush direction is set by the parity of the bit-count of a modular power expression; count cyclic triples.Hard9CombinatoricsNumber theory+2No attempts yet2s256 MBJudgeable
DramaCount the number of valid pyramid colourings of an H by N grid with exactly N black cells, modulo 10^9+7.Hard9CombinatoricsDynamic programming+1No attempts yet2s512 MBJudgeable
L-th K-th numberGiven N cards, take the K-th smallest value of every contiguous block of length at least K, then report the L-th smallest of all those values.Hard9Binary searchArray+2No attempts yet2s512 MBJudgeable
Revenge of the Endless BFSDecide whether a buggy BFS that forgets visited vertices ever terminates on a given directed graph, and if so output the loop count modulo 1e9+7.Hard9GraphBFS+2No attempts yet2s512 MBJudgeable
Conveyor BeltAfter each of Q delivery requests (a, b, p) is added, report the minimum time to finish all tasks, given plates arrive one per second and each plate carries one product.Hard9MathGreedy+2No attempts yet2s512 MBJudgeable
Blocks 2Count the ways to tile an N x M rectangle with rotated k x N blocks (k=1..N), modulo 1999, where M can be as large as 10^10.Hard9CombinatoricsDynamic programming+2No attempts yet1s256 MBJudgeable
Stamp PaintingCount the distinct colorings of an N-unit canvas obtainable by stamping K-wide colored stamps so every unit ends up painted, modulo 1e9+7.Hard9Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Euclidean NimFor each pair of move sizes p and q and starting pile n, decide which player wins the take-or-add game, or that it draws.Hard9Game theoryMath+1No attempts yet2s512 MBJudgeable
Maximal polygon brightnessGiven a convex polygon and a sequence of vertex deletions, compute after each deletion the largest total length of edges that a single external light point can illuminate.Hard9GeometryDynamic programming+2No attempts yet3s1024 MBJudgeable
In honor of Taekhee's graduationDeer bounce on a line segment [0,T], each with strength; a statue at x falls when the net force of deer that have reached it exceeds W. Maximize the fall time over x.Hard9MathSimulation+2No attempts yet3s128 MBJudgeable
Want to solve a problem?For given K and C, choose A > 0 to maximize the characters saved by writing K+A repeated K+A times instead of K repeated K times, minus C times A.Hard9String matchingMath+2No attempts yet1s128 MBJudgeable
The Number of SequencesFor a given N and C, find the lexicographically smallest triple (X, Y, Z) such that exactly C ordered N-tuples of 31-bit integers have OR X, AND Y, XOR Z, or report none exists.Hard9Bit manipulationCombinatorics+2No attempts yet1s128 MBJudgeable
Uncrossed Knight's TourGiven an m by n board (m at most 8, n up to 1e15), find the maximum number of squares a closed knight tour can visit without crossing itself.Hard9GreedyDynamic programming+2No attempts yet2s1024 MBJudgeable
TteokpireCount the number of ways to write N as an ordered sequence of one or more positive integers; equivalently, count compositions of N, modulo 1e9+7, for N up to 1e12.Hard9CombinatoricsMath+2No attempts yet1s128 MBJudgeable
Circle SelectionProcess circles in decreasing radius order; each chosen circle removes all remaining circles that intersect it, and for every circle you must report which chosen circle eliminated it.Hard9GeometrySorting+2No attempts yet3s1024 MBJudgeable
United States of EurasiaSplit N points sorted by x into at most K contiguous groups, minimizing the largest squared diameter within any group.Hard9Binary searchDynamic programming+2No attempts yet20s1024 MBJudgeable
Voronoi DiagramGiven a connected weighted graph and a set of source vertices, assign every point on every edge to its nearest source (smallest index on ties) and report the total length each source owns.Hard9GraphShortest path+2No attempts yet2s1024 MBJudgeable
Cryptarithm?!Given three letter strings A+B=C, decide whether some assignment of distinct digits to letters makes the addition valid, columns up to 18 long.Hard9BacktrackingMath+2No attempts yet1s128 MBJudgeable
Tree EscapeOn a rooted tree where each leaf starts with one piece, players alternately move a piece to its parent and remove it at the root; decide if the first player wins.Hard9Game theoryTree+2No attempts yet2s512 MBJudgeable
SquareFreeGiven n up to 10^18, find the n-th squarefree positive integer using Mobius inversion and binary search.Hard9MathNumber theory+2No attempts yet5s512 MBJudgeable
Fibonacci Digit CountCount occurrences of the substring "11" within the first N characters of the infinite string formed by writing 1, 2, 3, ... in Fibonacci (Zeckendorf) representation.Hard9MathDynamic programming+2No attempts yet2s1024 MBJudgeable
f and gCompute g(T,k)=sum_{x=0}^{T} sum_i (x+a_i)^k mod 1e9+7 for every k from 0 to K, given N up to 1e5, K up to 5e4, T up to 1e18.Hard10MathCombinatorics+2No attempts yet3s512 MBJudgeable
Find Marble Positions and VelocitiesReconstruct each marble's starting x-coordinate and constant velocity from N+1 unordered snapshots of N linearly moving marbles.Hard10MathCombinatorics+2No attempts yet2s128 MBJudgeable
Coalescing ContinentsGiven K rectangles with total area 25 on a 20x20 grid, decide if they can be translated to tile a square, and find the minimum total moves.Hard10Brute forceMath+2No attempts yet1s128 MBJudgeable
CubesCount the orbits of general-purpose chip placements on cube faces under face rotations and cube rearrangement, given a fixed pattern of encoding chips.Hard10CombinatoricsMath+2No attempts yet1s128 MBJudgeable