Math and counting

Number theory, combinatorics, and geometry

Under construction

Still being built. Things may change

Total results13,164 problems

Automorphism
Hard8
Tree, Combinatorics+1
No attempts yet
Time limit
8s
Memory limit
512 MB
Judgeable
Knight
Hard8
Game theory, Graph
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Exact Arithmetic
Hard8
Implementation, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Form the Maximal Set
Hard8
Combinatorics, Greedy+1
No attempts yet
Time limit
5s
Memory limit
512 MB
Judgeable
Wavel Sequence
Hard8
Dynamic programming, Combinatorics+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Tris
Hard8
Implementation, Matrix+1
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Xormites
Hard8
Game theory, Bit manipulation+1
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Oleg and Data Science
Hard8
Number theory, Math+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Christmas Garland
Hard8
Array, Implementation+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Anna and Lucky Tickets
Hard8
Combinatorics, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Build the Graph
Hard8
Graph, Greedy+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Match
Hard8
Tree, Dynamic programming+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Subsequence Sums
Hard8
Dynamic programming, Greedy+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Lying From You
Hard8
Math, Geometry+2
No attempts yet
Time limit
10s
Memory limit
512 MB
Judgeable
From The Inside
Hard8
Game theory, Math+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
One Step Closer
Hard8
Math, Bit manipulation+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Invisible
Hard8
Segment tree, Bit manipulation+1
No attempts yet
Time limit
12s
Memory limit
512 MB
Judgeable
Faint
Hard8
Combinatorics, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Biggest Number
Hard8
Segment tree, Sorting+2
No attempts yet
Time limit
0.5s
Memory limit
256 MB
Judgeable
Hotter-colder
Hard8
Binary search, Implementation+2
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Ones
Hard8
Dynamic programming, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Seats
Hard8
Probability, Math+2
No attempts yet
Time limit
1.5s
Memory limit
256 MB
Judgeable
Primes
Hard8
Number theory, Prefix sum+2
No attempts yet
Time limit
8s
Memory limit
256 MB
Judgeable
Vertex covers
Hard8
Combinatorics, Math+1
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Boring Game
Hard8
Game theory, Combinatorics+2
No attempts yet
Time limit
4s
Memory limit
512 MB
Judgeable
Brother and Sister
Hard8
Graph, Math+2
No attempts yet
Time limit
1.5s
Memory limit
512 MB
Judgeable
Rotating Line
Hard8
Geometry, Sorting+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Master Zhu and Math Problem
Hard8
Math, Combinatorics+2
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Binomial Coefficient
Hard8
Math, Number theory+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Bipartite Graph Coloring
Hard8
Math, Dynamic programming+2
No attempts yet
Time limit
12s
Memory limit
512 MB
Judgeable
Control Point
Hard8
Dynamic programming, Tree+1
No attempts yet
Time limit
5s
Memory limit
512 MB
Judgeable
Three Points
Hard8
Geometry, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Independent Set
Hard8
Dynamic programming, Tree+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Subset Sum
Hard8
Heap, Sorting+2
No attempts yet
Time limit
5s
Memory limit
512 MB
Judgeable
2x+2
Hard8
Math, Greedy+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Escape Sequences
Hard8
String, Divide and conquer+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Balls and Holes
Hard8
Combinatorics, Bit manipulation+2
No attempts yet
Time limit
0.5s
Memory limit
512 MB
Judgeable
Simple Polygon
Hard8
Geometry, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Saddle Point
Hard8
Combinatorics, Dynamic programming+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Banach
Hard8
Geometry, Math
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Conway
Hard8
Game theory, Bit manipulation+2
No attempts yet
Time limit
5s
Memory limit
512 MB
Judgeable
Galois
Hard8
Combinatorics, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Harary
Hard8
Combinatorics, Graph+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Ito
Hard8
Geometry, Binary search+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Kolmogorov
Hard8
Graph, Dynamic programming+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Cleaning Robots
Hard8
Tree, Dynamic programming+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Mission Possible
Hard8
Geometry, Graph+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Yet Another Problem About Permutations
Hard8
Combinatorics, Greedy+2
No attempts yet
Time limit
3s
Memory limit
256 MB
Judgeable
Ambitious Plan
Hard8
Geometry, Sorting+1
No attempts yet
Time limit
4s
Memory limit
512 MB
Judgeable
Fibonacci's Nightmare
Hard8
Probability, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Infinite Binary Embedding
Hard8
Tree, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Key Storage
Hard8
Combinatorics, Math+2
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Trener
Hard8
String, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Enumeration of Tournaments
Hard8
Combinatorics, Recursion+1
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Game of Chairs
Hard8
Math, Prefix sum+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Lazy Student
Hard8
Probability, Math+1
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Construct Point
Hard8
Number theory, Geometry+1
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Antennas On Tree
Hard8
Tree, DFS+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
ADD, DIV, MAX
Hard8
Segment tree, Linked list+2
No attempts yet
Time limit
5s
Memory limit
256 MB
Judgeable
Simple APSP Problem
Hard8
Combinatorics, Math+2
No attempts yet
Time limit
3s
Memory limit
256 MB
Judgeable
Ability Draft
Hard8
Bit manipulation, Dynamic programming+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Oneness
Hard8
Number theory, Math+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Piecewise Linearity
Hard8
Math, Geometry+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Donut-shaped Enclosure
Hard8
Geometry, Prefix sum+2
No attempts yet
Time limit
3s
Memory limit
1024 MB
Judgeable
Sum of Circular Sequence Scores
Hard8
Combinatorics, Dynamic programming+1
No attempts yet
Time limit
1s
Memory limit
1024 MB
Judgeable
Number of Cycles
Hard8
Geometry, Graph+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Game of Sorting
Hard8
Game theory, Prefix sum+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Aftermath
Hard8
Number theory, Math+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Believer
Hard8
Dynamic programming, Greedy+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Gate 21
Hard8
Math, Geometry
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Kids Aren't Alright
Hard8
Number theory, Combinatorics+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Swap
Hard8
Graph, DFS+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Hanoi
Hard8
Dynamic programming, Recursion+1
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Pattern Matching
Hard8
Dynamic programming, Bit manipulation+1
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Very New York
Hard8
Geometry, Divide and conquer+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Sheep
Hard8
Geometry, Binary search+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
The Catcher in the Rye
Hard8
Geometry, Binary search+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Dominoes
Hard8
Implementation, Matrix+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Evacuation
Hard8
Geometry, Segment tree+1
No attempts yet
Time limit
4s
Memory limit
512 MB
Judgeable
Grasshoppers
Hard8
Matrix, Math+1
No attempts yet
Time limit
15s
Memory limit
512 MB
Judgeable
Even Three is Odd
Hard8
Dynamic programming, Combinatorics+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Welcome to ICPCCamp 2017
Hard8
Combinatorics, Greedy+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Edge-Disjoint Spanning Trees
Hard8
Graph, Greedy+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Randomized Binary Search Tree
Hard8
Dynamic programming, Probability+1
No attempts yet
Time limit
2.5s
Memory limit
512 MB
Judgeable
Random Numbers
Hard8
Number theory, Math+1
No attempts yet
Time limit
5s
Memory limit
512 MB
Judgeable
Eulerian Orientation
Hard8
Graph, Math+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Buggy Combination Lock
Hard8
Math, Sorting+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Cyclic Shifts
Hard8
String, String matching+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Jogging in the Park
Hard8
Graph, Shortest path+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Crazy Dreamoon
Hard8
Geometry, Math+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Forest Game
Hard8
Tree, Divide and conquer+1
No attempts yet
Time limit
4s
Memory limit
512 MB
Judgeable
Lonely Dreamoon 2
Hard8
Sorting, Greedy+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Order-Preserving Partition
Hard8
Array, Prefix sum+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Prime Tree
Hard8
Tree, Number theory+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Helter Skelter
Hard8
Two pointers, Prefix sum+1
No attempts yet
Time limit
2s
Memory limit
128 MB
Judgeable
Join The Future
Hard8
Union-find, Greedy+1
No attempts yet
Time limit
5s
Memory limit
64 MB
Judgeable
Alone in the Cactus
Hard8
DFS, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Izhevsk Training Camp
Hard8
Bit manipulation, Brute force+2
No attempts yet
Time limit
3s
Memory limit
256 MB
Judgeable
Expected LCP
Hard8
Probability, Combinatorics+2
No attempts yet
Time limit
1.5s
Memory limit
256 MB
Judgeable
Finite Walking
Hard8
Graph, DFS+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable

Title	Level	Topics	Solved	Time limit	Memory limit	Judge
AutomorphismVertices are attached one at a time under a given parent, and each query asks for the number of automorphisms of the subtree rooted at a vertex, modulo 998244353.	Hard8	TreeCombinatorics+1	No attempts yet	8s	512 MB	Judgeable
KnightGiven a board with broken squares and two knights that share one (r, c) move rule, decide whether Alice or Bob wins when no earlier knight configuration may repeat.	Hard8	Game theoryGraph	No attempts yet	2s	512 MB	Judgeable
Exact ArithmeticSimulate a stack calculator whose values are sums of rationals and rational multiples of square roots, and print each result in a canonical exact form.	Hard8	ImplementationMath+2	No attempts yet	1s	512 MB	Judgeable
Form the Maximal SetGiven n points on a circle joined by n/2 chords, replace up to k chords with arbitrary ones to get the largest set of pairwise intersecting chords.	Hard8	CombinatoricsGreedy+1	No attempts yet	5s	512 MB	Judgeable
Wavel SequenceCount pairs of increasing index sequences from two arrays whose selected values are equal and form a strictly alternating up-down wave, modulo 998244353.	Hard8	Dynamic programmingCombinatorics+2	No attempts yet	1s	512 MB	Judgeable
TrisGiven how many pieces of each of four tromino-like types there are, build a grid of at most 800 by 800 where all pieces form one simple cycle enclosing a single connected interior.	Hard8	ImplementationMatrix+1	No attempts yet	1s	256 MB	Judgeable
XormitesTwo players take turns removing values from either end of a sequence and XOR them into their own sums. Decide whether the first player wins, the second player wins, or the game is a draw.	Hard8	Game theoryBit manipulation+1	No attempts yet	1s	256 MB	Judgeable
Oleg and Data ScienceCount positive integers X such that ((S mod Q) mod X) equals (S mod X) for every S in [L, R], or report infinity.	Hard8	Number theoryMath+2	No attempts yet	2s	256 MB	Judgeable
Christmas GarlandGiven a garland of n bulbs with colors, each query flips the state of every bulb of one color, and after each flip you report the number of maximal lit segments.	Hard8	ArrayImplementation+2	No attempts yet	2s	256 MB	Judgeable
Anna and Lucky TicketsCount n-digit palindromes that are lucky under neither the alternating-position sum test nor the first-half-versus-second-half sum test, modulo 1e9+7.	Hard8	CombinatoricsDynamic programming+2	No attempts yet	2s	256 MB	Judgeable
Build the GraphGiven n nodes and at most m edges, build an undirected graph minimizing the sum of all-pairs shortest distances, where unreachable pairs count as n.	Hard8	GraphGreedy+2	No attempts yet	1s	512 MB	Judgeable
MatchGiven a tree with n nodes, count the edge subsets whose remaining forest has a maximum matching size divisible by m, modulo 998244353.	Hard8	TreeDynamic programming+2	No attempts yet	1s	512 MB	Judgeable
Subsequence SumsGiven the multiset of all subsequence sums of a hidden positive-integer sequence, reconstruct the sequence, choosing the lexicographically smallest one.	Hard8	Dynamic programmingGreedy+2	No attempts yet	1s	512 MB	Judgeable
Lying From YouGiven n lines y = a_i x + b_i, change coefficients at L1 cost so all lines pass through one point; find the infimum total cost.	Hard8	MathGeometry+2	No attempts yet	10s	512 MB	Judgeable
From The InsideGiven board sizes n and m and square size k with k <= n, m <= 3k, count the first moves that let Alice win under optimal play.	Hard8	Game theoryMath+1	No attempts yet	1s	512 MB	Judgeable
One Step CloserGiven a grid built from q rectangle XOR flips, decide whether repeatedly flipping the row and column of every plus cell ends with all minus, and count the operations.	Hard8	MathBit manipulation+1	No attempts yet	2s	512 MB	Judgeable
InvisibleProcess point updates and range queries on an array, printing any value that appears an odd number of times in the range, or -1 if none exists.	Hard8	Segment treeBit manipulation+1	No attempts yet	12s	512 MB	Judgeable
FaintSum the absolute differences between consecutive rows of a fixed column in the lexicographically ordered list of k-subsets of {1,...,n}, modulo 1e9+7.	Hard8	CombinatoricsMath+2	No attempts yet	1s	512 MB	Judgeable
Biggest NumberAfter each of Q point updates to the digits on N cards, report the largest base-D number obtainable by rearranging the cards, modulo 1e9+7.	Hard8	Segment treeSorting+2	No attempts yet	0.5s	256 MB	Judgeable
Hotter-colderAn interactive problem: locate a hidden point in a d-dimensional integer grid using at most 100d queries that only report whether the latest Chebyshev distance got smaller or larger.	Hard8	Binary searchImplementation+2	No attempts yet	1s	256 MB	Judgeable
OnesFor each k up to 1e9, output a 1-expression using only ones, +, *, and parentheses that evaluates to k with at most 100 ones, or NO.	Hard8	Dynamic programmingMath+2	No attempts yet	1s	512 MB	Judgeable
SeatsGiven n prize values, choose one probability distribution over seats so that a player's expected prize, accounting for random contests at each seat, is maximized.	Hard8	ProbabilityMath+2	No attempts yet	1.5s	256 MB	Judgeable
PrimesAnswer online queries that ask for the sum of shared distinct prime counts over all pairs in a range [a, b] up to 10^6.	Hard8	Number theoryPrefix sum+2	No attempts yet	8s	256 MB	Judgeable
Vertex coversFor each query with n vertices and k, count simple graphs whose minimum vertex cover has size exactly k, printed modulo 2.	Hard8	CombinatoricsMath+1	No attempts yet	3s	512 MB	Judgeable
Boring GameDecide the winner of a coin-flipping game on a huge N by N board where each move flips a rectangle whose bottom-right corner is heads, with heads cells given as a union of M rectangles.	Hard8	Game theoryCombinatorics+2	No attempts yet	4s	512 MB	Judgeable
Brother and SisterGiven a functional graph on n labeled girls plus node 0, compute the expected number of queries before reaching 0 under a randomized probing process, modulo 1e9+7.	Hard8	GraphMath+2	No attempts yet	1.5s	512 MB	Judgeable
Rotating LineSimulate a line rotating counter-clockwise around its center through up to 3000 integer points, and report the q-th rotation center for each query.	Hard8	GeometrySorting+1	No attempts yet	1s	512 MB	Judgeable
Master Zhu and Math ProblemCount quadruples (a,b,c,d) within given bounds that satisfy two linear inequalities, modulo 1e9+7, with bounds up to 1e18.	Hard8	MathCombinatorics+2	No attempts yet	3s	512 MB	Judgeable
Binomial CoefficientGiven n (up to 10^18) and k, compute the binomial coefficient C(n, k) modulo 2^32.	Hard8	MathNumber theory+1	No attempts yet	2s	512 MB	Judgeable
Bipartite Graph ColoringSum, over all 2^n black/white colorings of a bipartite graph, the product of per-edge weights that depend on the colors of each edge's endpoints, modulo 1e9+7.	Hard8	MathDynamic programming+2	No attempts yet	12s	512 MB	Judgeable
Control PointCount the subsets of tree vertices where every special vertex has a chosen control point within r edges, modulo 1e9+7.	Hard8	Dynamic programmingTree+1	No attempts yet	5s	512 MB	Judgeable
Three PointsGiven three points A, B, C, find a point P minimizing \|PA\| + 2\|PB\| + 3\|PC\| and output that minimum distance.	Hard8	GeometryMath+2	No attempts yet	1s	512 MB	Judgeable
Independent SetCount vectors of n nonnegative integers summing to m where positions flagged by a and parent-child pairs in the implicit binary heap cannot both be positive, modulo 1e9+7.	Hard8	Dynamic programmingTree+2	No attempts yet	2s	512 MB	Judgeable
Subset SumGiven n integers, output the k smallest sums over all non-empty subsets, in ascending order.	Hard8	HeapSorting+2	No attempts yet	5s	512 MB	Judgeable
2x+2Given n up to 10^100, choose the largest subset of {1,...,n} with no x and 2x+2 both present.	Hard8	MathGreedy+2	No attempts yet	1s	512 MB	Judgeable
Escape SequencesFor a morphism f that replaces a with aa and b with ab, find the smallest k such that t is a substring of the k-fold iterate f^k(s).	Hard8	StringDivide and conquer+2	No attempts yet	1s	512 MB	Judgeable
Balls and HolesGiven n small sets of integers, count pairs (i<j) where pushing balls at S_i into holes at half-integers of S_j leaves an odd number of occupied holes.	Hard8	CombinatoricsBit manipulation+2	No attempts yet	0.5s	512 MB	Judgeable
Simple PolygonGiven a perimeter l and area s, construct a simple rectilinear polygon with exactly that perimeter and area, or report that none exists.	Hard8	GeometryMath+2	No attempts yet	1s	512 MB	Judgeable
Saddle PointCount the n by m matrices with entries in 1..k that contain at least one position that is a strict maximum of both its row and its column, modulo 1e9+7.	Hard8	CombinatoricsDynamic programming+2	No attempts yet	1s	512 MB	Judgeable
BanachAssign N vectors to N points so that no pairwise distance shrinks after translation, maximizing the sum of squared pairwise distances.	Hard8	GeometryMath	No attempts yet	3s	512 MB	Judgeable
ConwayRoland and Patrick take turns toggling switch pairs wired to bulbs, and the task is to decide whether Roland can keep the lit bulbs' total power at least K.	Hard8	Game theoryBit manipulation+2	No attempts yet	5s	512 MB	Judgeable
GaloisGiven a permutation p, count permutations q with p(q(i)) = q(p(i)) for all i, that have an even number of inversions, modulo 1e9+7.	Hard8	CombinatoricsMath+2	No attempts yet	1s	512 MB	Judgeable
HararyCount directed graphs on N vertices that have exactly one, two, and three topological orderings, modulo 10^9+7.	Hard8	CombinatoricsGraph+2	No attempts yet	1s	512 MB	Judgeable
ItoEach valuable's next-year price is uniform between a and b, and each client wants the maximum expected money while keeping at least l in the worst case.	Hard8	GeometryBinary search+1	No attempts yet	1s	512 MB	Judgeable
KolmogorovIn a connected undirected graph where each minute one random edge lights up, find the minimum expected time for an optimal walker to travel from node 1 to node N.	Hard8	GraphDynamic programming+2	No attempts yet	1s	512 MB	Judgeable
Cleaning RobotsCount the ways to partition all vertices of a tree into vertex-disjoint paths such that no two paths can be merged into a longer path.	Hard8	TreeDynamic programming+2	No attempts yet	1s	512 MB	Judgeable
Mission PossibleGiven up to 50 disjoint circular sensors inside a rectangle, output at most 1000 waypoints for a polyline from start to target that stays inside the rectangle and never enters any sensor disk.	Hard8	GeometryGraph+1	No attempts yet	1s	512 MB	Judgeable
Yet Another Problem About PermutationsGiven a permutation, write it as a product of the fewest simple permutations, where each simple permutation has only cycles of length one or two, and output one optimal factorization.	Hard8	CombinatoricsGreedy+2	No attempts yet	3s	256 MB	Judgeable
Ambitious PlanCount the sets of a drone, a fort, and two towers where the drone-to-fort segment crosses the segment between the two towers.	Hard8	GeometrySorting+1	No attempts yet	4s	512 MB	Judgeable
Fibonacci's NightmareFor a random sequence built by summing two earlier terms, find the variance of the n-th term modulo 10^9+7.	Hard8	ProbabilityDynamic programming+2	No attempts yet	2s	256 MB	Judgeable
Infinite Binary EmbeddingCount the ways to embed a finite binary tree into the infinite binary tree so that each leaf lands at a prescribed height, modulo 1e9+7.	Hard8	TreeDynamic programming+2	No attempts yet	2s	256 MB	Judgeable
Key StorageFor each key, count how many other positive integers produce the same multiset of remainders when repeatedly divided by 2, 3, 4, and so on.	Hard8	CombinatoricsMath+2	No attempts yet	3s	512 MB	Judgeable
TrenerCount ways to pick one surname from each length bucket so every shorter surname is a substring of every longer one, modulo 1e9+7.	Hard8	StringDynamic programming+2	No attempts yet	2s	512 MB	Judgeable
Enumeration of TournamentsGiven n players in a single-elimination bracket with random pairings each round, count the distinct possible tournaments modulo 2^64 for n up to 10^18.	Hard8	CombinatoricsRecursion+1	No attempts yet	1s	256 MB	Judgeable
Game of ChairsChoose a starting chair to minimize the expected distance to the nearest chair of a uniformly random color, and output the expectation as a reduced fraction.	Hard8	MathPrefix sum+2	No attempts yet	2s	512 MB	Judgeable
Lazy StudentGiven k exam days, find the minimum expected fraction of topics Raccoon must learn, where each attempt passes with probability equal to the fraction learned, modulo 1000000007.	Hard8	ProbabilityMath+1	No attempts yet	1s	256 MB	Judgeable
Construct PointFor each counterclockwise triangle with integer vertices up to 1e9, find one grid point strictly inside it, or report -1 -1 if none exists.	Hard8	Number theoryGeometry+1	No attempts yet	2s	256 MB	Judgeable
Antennas On TreeFind the smallest set of tree vertices whose distance vectors distinguish every vertex from every other vertex.	Hard8	TreeDFS+2	No attempts yet	2s	256 MB	Judgeable
ADD, DIV, MAXMaintain an array under range add, range floor-divide, and range maximum queries, with N and Q up to 200000.	Hard8	Segment treeLinked list+2	No attempts yet	5s	256 MB	Judgeable
Simple APSP ProblemGiven a huge H by W grid with at most 30 black squares, find the sum of shortest path distances over all pairs of white squares, modulo 10^9+7.	Hard8	CombinatoricsMath+2	No attempts yet	3s	256 MB	Judgeable
Ability DraftGiven a pick order and ability strengths, find the optimal difference between two teams' total strengths when players draft standard and ultimate abilities in turn.	Hard8	Bit manipulationDynamic programming+1	No attempts yet	2s	512 MB	Judgeable
OnenessGiven an l-digit number n generated by a pseudo-random generator, sum the count of repunit divisors greater than 1 over all integers from 1 to n.	Hard8	Number theoryMath+1	No attempts yet	2s	512 MB	Judgeable
Piecewise LinearityDecide whether a piecewise linear function given by n+1 increasing x-coordinates can be written as a real linear combination of absolute value terms \|x - a_i\|.	Hard8	MathGeometry+1	No attempts yet	1s	512 MB	Judgeable
Donut-shaped EnclosurePlace a Chebyshev-distance donut with inner radius L and outer radius R at a lattice center to maximize the total weight of covered points.	Hard8	GeometryPrefix sum+2	No attempts yet	3s	1024 MB	Judgeable
Sum of Circular Sequence ScoresGiven counts C_a of each value 1 to N in a circular sequence, sum the product of run lengths over all distinct circular arrangements, modulo 1e9+7.	Hard8	CombinatoricsDynamic programming+1	No attempts yet	1s	1024 MB	Judgeable
Number of CyclesGiven N, construct at most 12 segments whose graph of endpoints and intersection points has exactly N simple cycles.	Hard8	GeometryGraph+1	No attempts yet	2s	512 MB	Judgeable
Game of SortingFor each query range, decide the winner of the end-removal game where a player wins by leaving a monotone sequence.	Hard8	Game theoryPrefix sum+1	No attempts yet	2s	512 MB	Judgeable
AftermathGiven the integer arithmetic mean a and integer harmonic mean h of the divisors of an unknown n up to 10^15, recover any valid n.	Hard8	Number theoryMath+2	No attempts yet	2s	512 MB	Judgeable
BelieverFor each n up to 1e18, find the maximum over all positive-integer sequences summing to n of the total popcount of the multiplicities of the distinct values.	Hard8	Dynamic programmingGreedy+2	No attempts yet	2s	512 MB	Judgeable
Gate 21Count the straight lines that pass through exactly one integer checkpoint at each gate i, where gate i covers y from l_i to r_i.	Hard8	MathGeometry	No attempts yet	2s	512 MB	Judgeable
Kids Aren't AlrightGiven m up to 1e18, count the non-empty sets of positive integers whose gcd is 1 and lcm is m, modulo 998244353.	Hard8	Number theoryCombinatorics+2	No attempts yet	2s	512 MB	Judgeable
SwapCount the undirected graphs on n labeled vertices for which the given DFS swap procedure leaves the permutation a, modulo 998244353.	Hard8	GraphDFS+2	No attempts yet	2s	256 MB	Judgeable
HanoiCount the distinct move sequences that turn the Tower of Hanoi configuration S into T in at most m moves, modulo 998244353.	Hard8	Dynamic programmingRecursion+1	No attempts yet	1s	256 MB	Judgeable
Pattern MatchingGiven n letter sets and a pattern of length m, find the expected number of random add operations until the pattern matches consecutive sets, or print -1 if it never does.	Hard8	Dynamic programmingBit manipulation+1	No attempts yet	2s	256 MB	Judgeable
Very New YorkGiven up to 100,000 restaurant points on a grid, answer 100,000 queries counting how many points lie within Manhattan distance d of a query point.	Hard8	GeometryDivide and conquer+2	No attempts yet	2s	256 MB	Judgeable
SheepGiven n linear sheep trajectories on [0,T] and a shepherd that also moves linearly, minimize the maximum over sheep of (max(s-h))^2 + (min(s-h))^2.	Hard8	GeometryBinary search+2	No attempts yet	2s	256 MB	Judgeable
The Catcher in the RyeGiven a rectangle split into three vertical strips with different travel speeds, find the fastest route from the bottom-left to the top-right corner.	Hard8	GeometryBinary search+2	No attempts yet	1s	512 MB	Judgeable
DominoesPlace all n(n+1)/2 dominoes on a grid so that each number from 1 to n forms one connected region, or report impossible.	Hard8	ImplementationMatrix+1	No attempts yet	1s	512 MB	Judgeable
EvacuationDecide for each helicopter landing spot (t, x) whether an agent starting at position 0 at time 0, moving at speed 1, can reach it while staying outside lightning blast zones.	Hard8	GeometrySegment tree+1	No attempts yet	4s	512 MB	Judgeable
GrasshoppersEach grasshopper's new point is twice the next grasshopper's position minus its own, mod m, repeated t times. Output every grasshopper's position after t seconds.	Hard8	MatrixMath+1	No attempts yet	15s	512 MB	Judgeable
Even Three is OddSum the product over all sequences x_1..x_n with 1<=x_i<=n, where each window of three consecutive terms contributes w of its maximum, modulo 1e9+7.	Hard8	Dynamic programmingCombinatorics+2	No attempts yet	2s	512 MB	Judgeable
Welcome to ICPCCamp 2017Count the distinct team sets that the (X, Y)-rule can produce from n contest scoreboards and the final ranking, modulo 1e9+7.	Hard8	CombinatoricsGreedy+1	No attempts yet	1s	512 MB	Judgeable
Edge-Disjoint Spanning TreesGiven N and K, output K edge-disjoint spanning trees of the complete graph on N vertices, or -1 if impossible.	Hard8	GraphGreedy+2	No attempts yet	2s	512 MB	Judgeable
Randomized Binary Search TreeGiven N, find for each height h the probability that a treap built by inserting N random keys with random priorities ends with height h.	Hard8	Dynamic programmingProbability+1	No attempts yet	2.5s	512 MB	Judgeable
Random NumbersGiven random integers a and a shuffled list b, find m and k so that b is the multiset of (a_i + k) mod m.	Hard8	Number theoryMath+1	No attempts yet	5s	512 MB	Judgeable
Eulerian OrientationFor each undirected multigraph, sum x^2 over every edge subset with all even degrees, where x is the subset size, modulo 1e9+7.	Hard8	GraphMath+1	No attempts yet	2s	512 MB	Judgeable
Buggy Combination LockGiven start and target states of n cyclic discs where each rotation also turns the next disc, find the fewest rotations needed, or report -1 if impossible.	Hard8	MathSorting+1	No attempts yet	2s	512 MB	Judgeable
Cyclic ShiftsFor each prefix of a string, find the smallest index of its lexicographically minimal cyclic shift, then sum these indices weighted by powers of 8753 modulo 1000000123.	Hard8	StringString matching+1	No attempts yet	2s	512 MB	Judgeable
Jogging in the ParkExtend k walks that start at glade 1 so each ends at glade n with the same total length, or report -1 when that is impossible.	Hard8	GraphShortest path+2	No attempts yet	2s	512 MB	Judgeable
Crazy DreamoonGiven up to 2000 line segments in a 2000 by 2000 grid, count the grid squares whose interior is crossed by at least one segment.	Hard8	GeometryMath+2	No attempts yet	1s	512 MB	Judgeable
Forest GameGiven a tree, nodes are removed in random order and each removal adds its component size to the score. Output the expected total times N! mod 1e9+7.	Hard8	TreeDivide and conquer+1	No attempts yet	4s	512 MB	Judgeable
Lonely Dreamoon 2Reorder the given integers so that the smallest absolute difference between adjacent elements is as large as possible, and print any optimal ordering.	Hard8	SortingGreedy+2	No attempts yet	1s	512 MB	Judgeable
Order-Preserving PartitionCount the ways to split permutation P into four contiguous parts, each holding consecutive values, whose minima are ordered like Q.	Hard8	ArrayPrefix sum+1	No attempts yet	2s	512 MB	Judgeable
Prime TreeGiven a rooted tree with n nodes, find the largest number of prime trees whose tree product equals it.	Hard8	TreeNumber theory+1	No attempts yet	2s	512 MB	Judgeable
Helter SkelterGiven the run lengths of a binary string that starts with 0, answer for each query whether some substring has exactly a zeros and b ones.	Hard8	Two pointersPrefix sum+1	No attempts yet	2s	128 MB	Judgeable
Join The FutureGiven parity constraints on subarray sums and a lower and upper bound for each element, count the arrays that satisfy them and print the lexicographically smallest one.	Hard8	Union-findGreedy+1	No attempts yet	5s	64 MB	Judgeable
Alone in the CactusGiven a colored cactus, find the probability that a random walk from s without revisits ends at a red vertex, restarting at s on blue.	Hard8	DFSDynamic programming+2	No attempts yet	2s	256 MB	Judgeable
Izhevsk Training CampGiven nine contests, each a ranking of n teams, pick three contests so that the number of team pairs ordered the same way in all three is minimized.	Hard8	Bit manipulationBrute force+2	No attempts yet	3s	256 MB	Judgeable
Expected LCPCompute the expected length of the longest common prefix among n independent uniform random infinite binary strings, output as a fraction mod 1e9+7.	Hard8	ProbabilityCombinatorics+2	No attempts yet	1.5s	256 MB	Judgeable
Finite WalkingGiven a graph whose edges have counters taken modulo a_i, count the distinct final counter arrays reachable by walks from any start, modulo 10^9+7.	Hard8	GraphDFS+2	No attempts yet	2s	256 MB	Judgeable