Problems

Pick a problem, code in the editor, and watch the judge run real test cases. The archive is open to browse

Under construction

Still being built. Things may change

Total results29,408 problems

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
Scheduling
Hard8
Greedy, Sorting+2
No attempts yet
Time limit
1s
Memory limit
256 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
Monkeys
Hard8
Tree, Dynamic programming+2
No attempts yet
Time limit
4s
Memory limit
512 MB
Judgeable
Rotating Line
Hard8
Geometry, Sorting+1
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Schedule
Hard8
Intervals, Greedy+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Master Zhu and Palindromes
Hard8
String, Trie+2
No attempts yet
Time limit
2s
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
Substring Query
Hard8
String matching, Trie+1
No attempts yet
Time limit
10s
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
Or Max
Hard8
Bit manipulation, Array+1
No attempts yet
Time limit
2s
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
Addition Robot
Hard8
Segment tree, Matrix+2
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Garden
Hard8
Dynamic programming, Sorting+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Hamilton
Hard8
Tree, DFS+1
No attempts yet
Time limit
2s
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
Aarelia Mountains
Hard8
Graph, Shortest path+1
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
1D Spreadsheet
Hard8
Tree, Array+1
No attempts yet
Time limit
10s
Memory limit
512 MB
Judgeable
Fibonacci's Nightmare
Hard8
Probability, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Hilbert's Maze
Hard8
Divide and conquer, Recursion+1
No attempts yet
Time limit
5s
Memory limit
256 MB
Judgeable
Infinite Binary Embedding
Hard8
Tree, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Apprentice Learning Trajectory
Hard8
Dynamic programming, Intervals+1
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Key Storage
Hard8
Combinatorics, Math+2
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Birmingham
Hard8
Graph, BFS+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Trener
Hard8
String, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Teenage Shark
Hard8
Simulation, Backtracking+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
min-xor
Hard8
Trie, Bit manipulation+2
No attempts yet
Time limit
0.4s
Memory limit
8 MB
Judgeable
Related Languages
Hard8
Binary search, Dynamic programming+2
No attempts yet
Time limit
10s
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
Knapsack and Queries
Hard8
Dynamic programming, Queue
No attempts yet
Time limit
10s
Memory limit
1024 MB
Judgeable
Antennas On Tree
Hard8
Tree, DFS+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Generalized Insertion Sort
Hard8
Tree, Simulation+1
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
Lunch Queue
Hard8
Implementation, Segment tree+1
No attempts yet
Time limit
2.5s
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
Dynamic Input Tool
Hard8
Dynamic programming, String+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Computing MDSST
Hard8
Graph, Minimum spanning tree+2
No attempts yet
Time limit
1s
Memory limit
512 MB
Judgeable
Number of Cycles
Hard8
Geometry, Graph+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
New Occurrences
Hard8
String matching, Tree+1
No attempts yet
Time limit
1s
Memory limit
1024 MB
Judgeable
Game of Sorting
Hard8
Game theory, Prefix sum+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Repeating Subsequence Tests
Hard8
String, Prefix sum+2
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
Interval Tree
Hard8
Dynamic programming, Tree+1
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Cover the Paths
Hard8
Tree, Greedy+2
No attempts yet
Time limit
1s
Memory limit
256 MB
Judgeable
Consistent Occurrences
Hard8
String, String matching+2
No attempts yet
Time limit
4s
Memory limit
512 MB
Judgeable
Increasing Costs
Hard8
Graph, Shortest path+2
No attempts yet
Time limit
2s
Memory limit
256 MB
Judgeable
Mines
Hard8
Dynamic programming, Segment tree+1
No attempts yet
Time limit
3s
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
Dissertation
Hard8
Dynamic programming, String+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
A Text Problem
Hard8
String matching, Hash map+1
No attempts yet
Time limit
6s
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
City United
Hard8
Dynamic programming, Bit manipulation+1
No attempts yet
Time limit
3s
Memory limit
512 MB
Judgeable
Lowest Common Ancestor
Hard8
Tree, DFS+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
HDRF
Hard8
Tree, Simulation+1
No attempts yet
Time limit
1s
Memory limit
256 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
Tube Master II
Hard8
Dynamic programming, Bit manipulation+1
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable
Median on Binary Tree
Hard8
Tree, Dynamic programming+2
No attempts yet
Time limit
2s
Memory limit
512 MB
Judgeable

Title	Level	Topics	Solved	Time limit	Memory limit	Judge
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
SchedulingDecide whether n preemptible tasks with release times, deadlines, and processing times can be scheduled on m identical processors within their windows.	Hard8	GreedySorting+2	No attempts yet	1s	256 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
MonkeysChoose K vertices of a tree and delete edges so every chosen monkey can reach another, minimizing the number of surviving edges.	Hard8	TreeDynamic programming+2	No attempts yet	4s	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
ScheduleAssign interval tasks to machines so no two overlapping tasks share a machine; minimize the number of machines, then the total working time (earliest start to latest finish) across those machines.	Hard8	IntervalsGreedy+2	No attempts yet	2s	512 MB	Judgeable
Master Zhu and PalindromesFor each query, count the distinct palindromic substrings of S[L..R] whose tail starts with the given string T.	Hard8	StringTrie+2	No attempts yet	2s	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
Substring QueryGiven n strings of a and b, answer q queries: how many strings with index in [l, r] contain the pattern P as a substring.	Hard8	String matchingTrie+1	No attempts yet	10s	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
Or MaxFor each k from 1 to n, find the largest value of a window's maximum plus the bitwise OR of its k consecutive elements.	Hard8	Bit manipulationArray+1	No attempts yet	2s	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
Addition RobotMaintain a binary string under range flips and answer queries that apply the range's A/B operations to a pair of numbers, modulo 1e9+7.	Hard8	Segment treeMatrix+2	No attempts yet	3s	512 MB	Judgeable
GardenChoose k indices in increasing order so the chosen heights are strictly increasing and form a convex sequence, or report NO if no such choice exists.	Hard8	Dynamic programmingSorting+1	No attempts yet	2s	512 MB	Judgeable
HamiltonGiven a tree of up to 100000 villages, find an order that visits each village once with consecutive villages at most 3 edges apart, or report NO.	Hard8	TreeDFS+1	No attempts yet	2s	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
Aarelia MountainsGiven n region heights and m Earthquake spells with lengths and costs, find the cheapest way to make the heights non-decreasing, or print -1 if it is impossible.	Hard8	GraphShortest path+1	No attempts yet	2s	256 MB	Judgeable
1D SpreadsheetGiven n cells that hold either a number or a link to another cell, process set, link, and range-sum queries on the resolved cell values.	Hard8	TreeArray+1	No attempts yet	10s	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
Hilbert's MazeGiven a maze built by k rounds of the Hilbert curve transformation, find the shortest path length between two cells for each of up to 300000 queries.	Hard8	Divide and conquerRecursion+1	No attempts yet	5s	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
Apprentice Learning TrajectoryGiven n masters, each with a work window [a_i, b_i] and a sword time t_i, find the most non-overlapping sword segments, each of length t_i inside one window.	Hard8	Dynamic programmingIntervals+1	No attempts yet	3s	512 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
BirminghamGiven a connected graph with Q starting houses, find for each house the smallest day X such that it lies within X*K edges of some starting house.	Hard8	GraphBFS+2	No attempts yet	1s	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
Teenage SharkSimulate a 4x4 board where numbered fish rotate and swap, and a shark moves along its direction eating fish; find the maximum total value eaten.	Hard8	SimulationBacktracking+2	No attempts yet	1s	512 MB	Judgeable
min-xorMaintain a dynamic set under insertions and deletions, and after each min-xor query report the smallest XOR of any two elements currently in the set.	Hard8	TrieBit manipulation+2	No attempts yet	0.4s	8 MB	Judgeable
Related LanguagesGiven strings A and B and an integer k, find the longest pair of equal-length substrings, one from each string, that differ in at most k positions.	Hard8	Binary searchDynamic programming+2	No attempts yet	10s	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
Knapsack and QueriesAfter each add or remove of the lightest cookie, find the max value of a subset whose weight sum mod MOD lies in [l, r], or -1.	Hard8	Dynamic programmingQueue	No attempts yet	10s	1024 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
Generalized Insertion SortGiven a rooted tree with a permutation on its vertices, sort the values using at most 25,000 path-rotation operations from the root to a chosen vertex.	Hard8	TreeSimulation+1	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
Lunch QueueEmployees join a queue one at a time, each taking the earliest allowed spot next to a teammate within an impudence limit. Print the final queue order.	Hard8	ImplementationSegment tree+1	No attempts yet	2.5s	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
Dynamic Input ToolFind the minimum number of append-character and append-subsequence-of-current-string operations needed to build a given string from empty.	Hard8	Dynamic programmingString+2	No attempts yet	2s	512 MB	Judgeable
Computing MDSSTGiven a complete weighted graph on at most 15 vertices, find the spanning tree whose sum of all pairwise shortest-path distances is smallest, and print that sum.	Hard8	GraphMinimum spanning tree+2	No attempts yet	1s	512 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
New OccurrencesFor each prefix of a string S, print the sum of squared occurrence counts over all distinct substrings of that prefix.	Hard8	String matchingTree+1	No attempts yet	1s	1024 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
Repeating Subsequence TestsGiven a string and up to 10^6 generated substring queries, count distinct subsequences of each substring modulo 10^9+7 and output the last answer.	Hard8	StringPrefix sum+2	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
Interval TreeGiven a fixed interval tree with node colors, find the fewest range queries that blacken exactly the marked nodes, or report OwO if impossible.	Hard8	Dynamic programmingTree+1	No attempts yet	2s	256 MB	Judgeable
Cover the PathsGiven a tree and m simple paths, find a minimum-size vertex set that intersects every path, and output its size and members.	Hard8	TreeGreedy+2	No attempts yet	1s	256 MB	Judgeable
Consistent OccurrencesGiven a string s and many query strings, for each query find the largest set of non-overlapping occurrences of that query string in s.	Hard8	StringString matching+2	No attempts yet	4s	512 MB	Judgeable
Increasing CostsFor each road, count how many cities lose all shortest paths from the capital when that road's cost is increased.	Hard8	GraphShortest path+2	No attempts yet	2s	256 MB	Judgeable
MinesGiven N mines with positions, radii, and detonation costs, print the minimum total cost to set off every mine after each cost update.	Hard8	Dynamic programmingSegment tree+1	No attempts yet	3s	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
DissertationFor each test case, compute the length of the longest common subsequence of a long book string and a short dissertation string.	Hard8	Dynamic programmingString+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
A Text ProblemFor each query string, count the positions in T where it occurs with at most one mismatched letter.	Hard8	String matchingHash map+1	No attempts yet	6s	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
City UnitedCount non-empty city subsets that form a connected induced subgraph, modulo 2. Roads join labels at most 13 apart; n is at most 50.	Hard8	Dynamic programmingBit manipulation+1	No attempts yet	3s	512 MB	Judgeable
Lowest Common AncestorFor a rooted tree with node weights, compute for each node i the sum of weights of LCA(i, j) over all j < i, where nodes are indexed by label order.	Hard8	TreeDFS+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
HDRFGiven a rooted tree with distinct vertex priorities, output the order in which leaves are removed when the walk always descends to the child whose subtree minimum is smallest.	Hard8	TreeSimulation+1	No attempts yet	1s	256 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
Tube Master IIPick tube segments so each crossing uses either nothing or one horizontal and one vertical tube, meeting every cell's required count at minimum total cost.	Hard8	Dynamic programmingBit manipulation+1	No attempts yet	2s	512 MB	Judgeable
Median on Binary TreeGiven a heap-shaped binary tree with distinct weights, for every a find the largest a-median, defined as the element at position floor((k-a+1)/2) of a subtree sorted by weight.	Hard8	TreeDynamic programming+2	No attempts yet	2s	512 MB	Judgeable