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,786 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
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
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
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
FlippingCount initial black/white colorings of an N by M grid that can reach the given coloring when a press inverts the whole monochromatic connected component containing that cell, modulo 1e9+7.Hard9GraphUnion-find+2No attempts yet5s256 MBJudgeable
Cloud computingChoose a set of orders and a set of computers to buy so every accepted order gets enough cores at its minimum clock rate, maximizing payments minus computer costs.Hard9Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
BuildingsCount the distinct houses formed by placing m walls of n by n colored squares around an m-gon, up to rotation, modulo 1e9+7.Hard9CombinatoricsMath+2No attempts yet2s512 MBJudgeable
Black ChainGiven a chain of n rings (up to 10^18), find the fewest rings to open so the resulting pieces can be combined into every weight from 1 to n.Hard9GreedyCombinatorics+2No attempts yet0.1s512 MBJudgeable
Prime Tree - 6Assign labels 1 to n to tree vertices so that edges joining two numbers with a shared factor are as few as possible.Hard9GraphGreedy+2No attempts yet10s512 MBJudgeable
Prime Tree - 10Relabel the vertices of a given tree with 1..n so that as few edges as possible join two labels sharing a common divisor; this is an output-only optimization task.Hard9Number theoryGreedy+2No attempts yet10s512 MBJudgeable
CryptoCount permutations of 1..N whose window-product multiset, taken as the K smallest primes, has exactly P distinct values, modulo 1e9+7.Hard9CombinatoricsNumber theory+2No attempts yet2s512 MBJudgeable
Odd ColouringCount black/white ball colorings under cycle-index and Hadamard identities with large R, C, N, returning the count modulo 998244353.Hard9MathCombinatorics+2No attempts yet1s256 MBJudgeable
Decorator CubeloverArrange n decorations on an n^3-cycle so each window of three labels is unique and the positional-value sum is minimal; report the nth digit of p-1.Hard9CombinatoricsMath+2No attempts yet1s512 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
Forgotten LandSum over all partitions of a tree's vertices into arbitrary sets of the total language difficulty, where a set's difficulty depends on the union of languages on its vertices and on paths between them.Hard9Dynamic programmingTree+2No attempts yet3s512 MBJudgeable
Youngkwail Club RoomCover all '.' cells of a grid with 1x1 and 1x2 tiles, avoiding 'X' pillars, using the fewest tiles possible.Hard9GraphDFS+2No attempts yet1s256 MBJudgeable
Nim Game Without RepeatsNim with piles of size up to 60, but each specific removal size can be used at most once per pile; decide the winner under optimal play.Hard9Game theoryDynamic programming+2No attempts yet2s512 MBJudgeable
Quarry GameEach of N piles is a run of M consecutive pile sizes starting at X; a move takes at least one stone from one pile. Decide the winner under optimal play.Hard9Game theoryMath+2No attempts yet2s512 MBJudgeable
XOR SequencesCount, modulo 1e9+7, the ordered sequences of n distinct m-bit integers consistent with a given nearest-XOR-label map over all 2^m query values.Hard9Bit manipulationDivide and conquer+2No attempts yet2s512 MBJudgeable
Moorio KartCount and sum the lengths of simple cycles (at least Y) formed by joining every tree in a forest with one X-length edge between consecutive trees and a chosen path inside each tree.Hard9TreeDynamic programming+2No attempts yet3s512 MBJudgeable
MessageCount length-n lowercase strings that contain a given pattern p as a substring, modulo m, where n can reach 10^12 and p has length at most 50.Hard9Dynamic programmingString matching+2No attempts yet5s512 MBJudgeable
Sweet and SourChoose which Candy Country players drink a potion that randomizes their sweetness and sourness, maximizing Candy's expected match points under all random player orders and event coin flips.Hard9ProbabilityCombinatorics+2No attempts yet1s512 MBJudgeable
Africa 2Submit code that matches the judge on exactly half its hidden test cases while passing the sample, a problem about exploiting judge behavior rather than a computable answer.Hard9ImplementationBrute force+2No attempts yet1.357s1357 MBJudgeable
Overflowing UncertaintyFor each interval [i,j] compute the probability that the gcd of j-i+1 independent uniform values in [1,Y] is coprime with Y, sum over all intervals, and report the numerator modulo 1e9+9 with denominator Y^N.Hard9Number theoryDynamic programming+2No attempts yet1s256 MBJudgeable
Gosu 2Given a tournament on N players, find a transitive subtournament (chain) of size exactly 1 + floor(log2 N).Hard9Divide and conquerCombinatorics+2No attempts yet2s1024 MBJudgeable
Hanging RackGiven a binary hanging rack with 2^n hooks, find the hook number (mod 1e9+7) used on the k-th step when coats are hung to keep every rod balanced within 0 or 1.Hard9MathRecursion+2No attempts yet1s512 MBJudgeable
RulerFind the shortest ruler with N marks (0 to L) where all pairwise distances between marks are distinct, and print the mark positions.Hard9BacktrackingBrute force+2No attempts yet2s512 MBJudgeable
AsceticismCount permutations of 1..N such that an optimal daily reading schedule (reading consecutive sentences within each day's time slots) finishes the sutra in exactly K days.Hard9Dynamic programmingCombinatorics+2No attempts yet0.6s256 MBJudgeable
MessengerDesign strategies for two players who alternately move a piece on a 4x4 grid, knowing neither the call order nor its timing, so B can deduce the secret value X within 10000 moves.Hard9ImplementationSimulation+2No attempts yet2s512 MBJudgeable
ConstellationCount the ways to assign each unlabeled point to constellation A or B so that the two vertex sets can be drawn connected with mutually non-crossing segments.Hard9GeometryCombinatorics+2No attempts yet1s512 MBJudgeable
Graph and CyclesGiven a weighted complete graph on an odd number of vertices, partition all edges into edge-disjoint cycles and minimize the sum over each cycle of the max weight on consecutive edge pairs.Hard9GraphGreedy+2No attempts yet2s256 MBJudgeable
Nearest PointsCount the integer lattice points in an axis-aligned rectangle whose Euclidean distance to p1 is the minimum among K marked points.Hard9GeometryDivide and conquer+2No attempts yet2s512 MBJudgeable
DivModuloCompute C(M,N) after removing every factor of D, and report the remainder modulo D, for M up to 4e18 and D up to 1.6e7.Hard9MathNumber theory+2No attempts yet3s1024 MBJudgeable
Dance CircleCount, modulo 1e9+7, the binary assignments to n children around a circle matching n parity constraints, each covering a contiguous arc centered at some child.Hard9MathPrefix sum+2No attempts yet2s512 MBJudgeable
Tree DepthFor each node i, sum its depth over all permutations of 1..N with exactly K inversions, using the Cartesian-tree BST built by recursively taking the minimum. Output each sum mod a large prime.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Chessboard MovementCount paths from row 1 to row N on an N x M chessboard where odd rows restrict moves to same-colored adjacent cells and even rows allow any adjacent move, modulo 1e9+7.Hard9Dynamic programmingMatrix+2No attempts yet2s512 MBJudgeable
Graph CountingCount, modulo 998244353, the non-isomorphic undirected graphs on 2n vertices that have no perfect matching but lose that property when any missing edge is added.Hard9CombinatoricsGraph+2No attempts yet5s512 MBJudgeable
KnowledgeCount strings of length x reachable from s by inserting or deleting the blocks aa, bbb, and ababab, modulo 998244353.Hard9StringCombinatorics+2No attempts yet1s512 MBJudgeable
Bitwise XorCount non-empty subsequences in which the pairwise xor of every two chosen elements is at least x, modulo 998244353.Hard9Bit manipulationTrie+2No attempts yet2s512 MBJudgeable
Another Coin Weighing PuzzleGiven m weighings and k coins per bag, find the maximum number of bags whose unique heavy bag can be identified, modulo 998244353.Hard9CombinatoricsMath+2No attempts yet1s512 MBJudgeable
Counting Edit DistancesCount the number of distinct strings over 'A' to 'Z' whose Levenshtein distance from a given string s is exactly d, modulo 998244353.Hard9Dynamic programmingString+2No attempts yet10s512 MBJudgeable
Rooted SubtreesFor each query with two roots r and p, count the distinct non-empty sets that are the intersection of a subtree of the tree rooted at r and a subtree of the tree rooted at p.Hard9TreeDFS+2No attempts yet11s512 MBJudgeable
Basis ChangeGiven one linear recurrence with coefficients a_i, find the unique recurrence with prescribed lags b_i that every sequence satisfying the first also satisfies.Hard9MathImplementation+2No attempts yet2s512 MBJudgeable
Modulo-magic squaresCount n x n matrices over Z_m whose row, column, and two diagonal sums are all congruent to one constant, for n and m up to 1e9.Hard9MathCombinatorics+2No attempts yet1s512 MBJudgeable
KaleidoscopeCount colorings of the 60 faces of a rhombic hexecontahedron with n colors, each color i used at least c_i times, where colorings are identified under the rotational symmetry group, modulo p.Hard9CombinatoricsMath+2No attempts yet2s512 MBJudgeable
Expected CostPick a labeled tree on n vertices uniformly at random and find the expected value of the minimum sum of distances from any vertex to all others, modulo a prime.Hard9CombinatoricsTree+2No attempts yet3s512 MBJudgeable
FarawayCount lattice points (xe, ye) in [0, m]^2 such that for each of up to 10 constraints, (|xi - xe| + |yi - ye|) mod ki equals ti, with ki at most 5 and m up to 1e9.Hard9MathNumber theory+2No attempts yet1s512 MBJudgeable
Decimal ExpansionFor each query n up to 10^18, find the n-th digit after the decimal point of the infinite product (9/10)(99/100)(999/1000)...Hard9MathNumber theory+2No attempts yet1s512 MBJudgeable
Count the GraphsCount labeled connected undirected graphs on N nodes with exactly K bridges, modulo a possibly composite M, for up to 100 test cases.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
IneqGiven a finite set S of integer lattice points, decide whether S can be cut out as exactly the integer points lying strictly below every line of some finite family of half-planes.Hard9GeometryMath+2No attempts yet2s512 MBJudgeable
Help Yourself (Platinum)Sum the K-th power of the number of connected components of the union over all 2^N subsets of N intervals, modulo 1e9+7.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Sprinklers 2: Return of the AlfalfaCount the ways to place sweet corn and alfalfa sprinklers on an N by N grid, with some blocked squares, so that every square is covered by exactly one sprinkler type.Hard9Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
ExerciseGiven N and prime M, compute modulo M the product over all N! permutations of the order (number of iterations until identity) of each permutation.Hard9CombinatoricsNumber theory+2No attempts yet2s512 MBJudgeable
Cow ExerciseGiven N and prime M, sum every positive integer K for which some permutation of length N has order K, then output the sum modulo M.Hard9MathNumber theory+2No attempts yet1s512 MBJudgeable
Laser IntensificationFind probability p so that one photon entering the lower-left of a w by h grid, with nodes independently faulty with probability 1-p except n known faulty cells, yields k photons in expectation at the upper-right; print -1 if impossible.Hard9MathCombinatorics+2No attempts yet2s64 MBJudgeable
Yet Another Problem on EmpodiaCount, for each length i up to N, the number of equivalence classes of permutations of length i under the relation that agrees on which intervals are framed (max minus min equals length minus one), modulo a prime.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Curious Ball GameFor each query (N, M), find the M-th smallest bag size A such that drawing two balls gives probability exactly 1/N^2 that at least one is not red, outputting A and B mod 1e9+7.Hard9Number theoryMath+2No attempts yet0.5s256 MBJudgeable
Tree Average WeightGiven a degree sequence with some free entries, pick a labeled tree uniformly at random and find the integer part of its expected weight, where weight sums u*sz(u)+v*sz(v) over edges.Hard9CombinatoricsTree+2No attempts yet1s256 MBJudgeable
Continue the SequenceGiven n values, extend the sequence by m terms so that it agrees with a polynomial of the smallest possible degree modulo 998244353.Hard9MathNumber theory+2No attempts yet4s256 MBJudgeable
Counting Different SummandsSum f(a) over all ordered partitions of n into m positive parts, where f counts distinct part values, modulo 998244353, with n up to 1e18 and m up to 500.Hard9CombinatoricsMath+2No attempts yet2s256 MBJudgeable
Chiaki Sequence RevisitedSum the first n terms of the self-referential Chiaki sequence, where each term depends on earlier terms via a_{n-a_{n-1}} + a_{n-1-a_{n-2}}, modulo 1e9+7.Hard9MathCombinatorics+2No attempts yet1s256 MBJudgeable
RMQ Similar SequenceGiven sequence A, count the expected sum of a random real sequence B in [0,1] that has identical RMQ answers to A for every subarray, modulo 1e9+7.Hard9TreeCombinatorics+2No attempts yet2s256 MBJudgeable
Rikka with Proper FractionsCount reduced proper fractions e/f with f at most n lying between two given fractions a/b and c/d, answering modulo 998244353.Hard9Number theoryMath+2No attempts yet10s512 MBJudgeable
Good GameCount monotone lattice paths in n dimensions from the origin to a target, avoiding m forbidden points, modulo 1e9+7.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
TaxiSum over all ways to place M taxis and M customers on a weighted tree of the maximum-weight perfect matching cost, modulo 1e9+7.Hard9TreeDynamic programming+2No attempts yet1.5s256 MBJudgeable
CandiesFor each query k, count modulo 2 the pairs (child, candy kind) where buying only her favorite candy at that price leaves exactly k dollars.Hard9Number theoryMath+2No attempts yet1s512 MBJudgeable
Nice NumbersCount numbers in [L, R] that are pandigital (a permutation of all digits) in some base d, modulo 998244353, with L and R up to 5000-digit integers.Hard9CombinatoricsNumber theory+2No attempts yet1s512 MBJudgeable
Array ChallengeGiven a linear recurrence h and closed-form arrays b and a, compute floor(sqrt(a_n)) modulo 1e9+7 for n up to 1e15.Hard9MathNumber theory+2No attempts yet1s512 MBJudgeable
Master Zhu and CandiesGiven n candy heaps, players may remove any positive number from one heap or split one heap into three non-empty heaps; decide the winner under optimal play.Hard9Game theoryMath+2No attempts yet3s512 MBJudgeable
Master Zhu and the LeaperCount monotone leaper paths from (1,1) to (n,m) on a huge board with at most 100 blocked cells, modulo 110119.Hard9Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
Random PointsGiven n points in general position, output 2^n times the expected number of vertices of the convex hull of a uniformly random subset, modulo 1e9+7.Hard9GeometryCombinatorics+2No attempts yet5s512 MBJudgeable
GCD vs LCMFor each of q queries with n, m, a up to 1e5, sum lcm(i,j) over all i<=n, j<=m with gcd(i,j)<=a, modulo 1e9+7.Hard9Number theoryMath+2No attempts yet2.5s512 MBJudgeable
Power of XORGiven n integers, compute the sum over all 2^n subsets of the k-th power of the popcount of the XOR of the subset, modulo 1e9+7.Hard9Bit manipulationMath+2No attempts yet6s512 MBJudgeable
Airport Check-inEach counter has a random per-passenger time and a random remaining time for the current passenger; find the probability that the counter finishing first is also the one with the smallest per-passenger time.Hard9ProbabilityMath+1No attempts yet1s256 MBJudgeable
Window XORApply the operation that replaces each element with the XOR of K consecutive elements (cyclically) exactly T times, where T can be as large as 10^18.Hard9MathBit manipulation+2No attempts yet2s1024 MBJudgeable
K-th StringCount permutations t of n distinct letters whose k-th smallest non-empty substring equals s, modulo 1e9+7.Hard9StringCombinatorics+2No attempts yet1s256 MBJudgeable
Ascent Sequences Avoiding Pattern 201Count ascent sequences of length n that avoid the pattern 201, modulo a prime p, with n up to 500.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Connected Spanning SubgraphGiven a connected undirected graph, count the non-empty edge subsets whose chosen edges form a connected spanning subgraph, and print the count modulo 2.Hard9GraphCombinatorics+2No attempts yet1s512 MBJudgeable
Less Time, More ProfitChoose a subset of plants to build; a shop pays off only when every plant it needs is built. Minimize the maximum build time, then maximize profit within that time.Hard9Dynamic programmingGraph+2No attempts yet1s256 MBJudgeable
Pet TreeCount assignments of edge lengths (each within its own interval) to a tree's edges so the resulting tree diameter falls between S and E, modulo 1e9+7.Hard9Dynamic programmingTree+2No attempts yet8s1024 MBJudgeable
IslandGiven the edge list of a tree whose N leaves are towns and whose internal nodes all have degree at least 3, count the distinct circular orderings of the leaves realizable as the outer face, and print the count as a product of prime powers.Hard9TreeDFS+2No attempts yet1s512 MBJudgeable
Fermat's Last TheoremOrder all positive quadruples (a,b,c,n) with n>=3 by max element then lexicographically, and print the sign of a^n+b^n compared to c^n for positions l through r.Hard9MathCombinatorics+2No attempts yet2s512 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
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
HyperrectangleCompute d!V for the volume of a box with side lengths li where sum xi <= s via characteristic polynomials and Lenstra inclusion of capped orthants.Hard10MathDivide and conquer+2No attempts yet2s512 MBJudgeable