Talos EvalSign in

400 formal specifications

Problems

Each problem is a Lean specification of what a correct answer is, at the byte level: parsing, printing and all. The summaries below are ours; the official statements live with their authors and are linked, never reproduced.

No problem accepts submissions yet. A problem only opens once every judge has a copy of its full test data — otherwise a correct solution would be judged against nothing.

ProblemSourceCan you submit?SolversBest
Acyclic Graph EdgesOrient every edge so that the resulting directed graph has no cycle.cses 1756not yet
AdvertisementThe largest axis-aligned rectangle fitting under the board heights.cses 1142not yet
All Letter Subgrid Count IThe number of square subgrids containing every one of the `k` letters.cses 3415not yet
All Letter Subgrid Count IIThe number of rectangular subgrids containing every one of the `k` letters.cses 3416not yet
All Manhattan DistancesSum of the Manhattan distances over all point pairs.cses 3411not yet
All PalindromesFor each position, the length of the longest palindrome ending there.cses 3138not yet
All Subarray XorsEvery value that is the xor of some non-empty subarray, in increasing order.cses 3233not yet
And Subset CountFor each `k` in `0..n`, the number of non-empty subsets whose bitwise and is `k`, modulo `10^9 + 7`.cses 3141not yet
Another GameRemove one coin from each of a chosen non-empty set of non-empty heaps.cses 2208not yet
ApartmentsMaximum number of applicants that can be matched to distinct apartments whose size is within `k` of the applicant's wish.cses 1084not yet
Apple DivisionSplit the apples into two groups minimising the difference of total weights.cses 1623not yet
Apples and BananasFor each combined weight `2..2k`, the number of apple/banana pairs with that total.cses 2111not yet
Area of RectanglesTotal area covered by the union of axis-aligned rectangles.cses 1741not yet
Array DescriptionNumber of arrays with values in `1..m`, adjacent values differing by at most 1, matching a description where `0` means unknown, modulo `10^9 + 7`.cses 1746not yet
Array DivisionSplit the array into `k` consecutive pieces minimising the largest piece sum. Pieces may be empty; since `k ≤ n` this does not change the optimum.cses 1085not yet
Beautiful Permutation IIThe lexicographically least permutation of `1..n` with no two adjacent elements differing by one, or `NO SOLUTION`.cses 3175not yet
Binary SubsequencesA shortest bit string with exactly `n` distinct non-empty subsequences.cses 2430not yet
Binomial Coefficients`a choose b` modulo `10^9 + 7`.cses 1079not yet
Bit InversionsAfter each bit flip, the length of the longest run of equal bits.cses 1188not yet
Bit StringsThe number of bit strings of length `n`, modulo `10^9 + 7`.cses 1617not yet
Bit SubstringsFor each `k`, the number of non-empty substrings containing exactly `k` ones.cses 2115not yet
Book ShopMaximum total pages of a set of books with total price at most `x`.cses 1158not yet
Book Shop IIMaximum total pages buying at most `k i` copies of each book within budget `x`.cses 1159not yet
Border Subgrid Count IFor each letter, the number of square subgrids whose border is entirely that letter.cses 3417not yet
Border Subgrid Count IIFor each letter, the number of rectangular subgrids whose border is entirely that letter.cses 3418not yet
Bouncing Ball CycleAfter how many steps the ball returns to its starting cell, and how many distinct cells it visits.cses 3216not yet
Bouncing Ball StepsWhere the ball is after `k` steps, and how many times it has changed direction.cses 3215not yet
Bracket Sequences INumber of balanced bracket sequences of length `n`, modulo `10^9 + 7`.cses 2064not yet
Bracket Sequences IINumber of balanced bracket sequences of length `n` extending a given prefix, modulo `10^9 + 7`.cses 2187not yet
Bubble Sort Rounds INumber of bubble sort rounds needed to sort the array.cses 3151not yet
Bubble Sort Rounds IIThe array after `k` bubble sort rounds.cses 3152not yet
Building RoadsFewest new roads making the road network connected, and such a set of roads.cses 1666not yet
Building TeamsTwo-colour the pupils so that friends are on different teams, or `IMPOSSIBLE`.cses 1668not yet
Bus CompaniesCheapest travel cost from city `1` to every city; one ticket lets you move between any two cities that company serves.cses 3158not yet
Candy LotteryExpected maximum when `n` children each get a uniform value in `1..k`, to six decimal places.cses 1727not yet
Chess TournamentGames so that each player plays exactly the number they asked for, with at most one game per pair.cses 1697not yet
Chessboard and QueensCount placements of eight mutually non-attacking queens on free squares of an `8 × 8` board. The input is the reservation predicate on squares.cses 1624not yet
Christmas PartyNumber of derangements of `n` gifts, modulo `10^9 + 7`.cses 1717not yet
Coding CompanyNumber of ways to split the coders into teams whose total penalty, the sum over teams of the skill spread, is at most `x`, modulo `10^9 + 7`.cses 1665not yet
Coin ArrangementFewest single-cell coin moves leaving exactly one coin per cell of a `2 × n` grid.cses 2180not yet
Coin CollectorMaximum total of coins in the distinct rooms visited along some walk.cses 1686not yet
Coin Combinations INumber of ordered sequences of coins summing to `x`, modulo `10^9 + 7`.cses 1635not yet
Coin Combinations IINumber of multisets of coins summing to `x` (sequences counted up to order, represented by their sorted form), modulo `10^9 + 7`.cses 1636not yet
Coin GridFewest row and column removals clearing every coin, and which lines to remove.cses 1709not yet
Coin PilesPiles of `a` and `b` coins; a move removes `(1, 2)` or `(2, 1)`. Can both be emptied? Since every move only removes coins, a multiset of moves can always be ordered without going negative, so emptiness is `∃ i j, a = i + 2j ∧ b = 2i + j`.cses 1754not yet
Collecting NumbersNumber of left-to-right passes needed to collect `1..n` in order from a permutation.cses 2216not yet
Collecting Numbers DistributionFor each `k`, how many permutations of `1..n` need exactly `k` collecting rounds, modulo `10^9 + 7`.cses 3157not yet
Collecting Numbers IIAfter each swap of two positions, the number of passes needed (see Collecting Numbers).cses 2217not yet
Colored Chairs`n` chairs in a circle, `n` odd, each red or blue. Find neighbouring chairs of the same colour by asking at most 20 chair colours.cses 3273no — interactive
Common DivisorsThe largest greatest common divisor of two elements at distinct positions.cses 1081not yet
Company Queries IThe boss `k` levels above employee `x`, or `-1`.cses 1687not yet
Company Queries IIThe lowest common boss of two employees.cses 1688not yet
Concert TicketsCustomers arrive in order; each takes the most expensive remaining ticket not above their limit, or nothing (`-1`).cses 1091not yet
Convex HullAll input points lying on the convex hull, in any order.cses 2195not yet
Corner Subgrid CheckFor each of the first `k` capital letters, whether some subgrid of height and width at least two has that letter at all four corners.cses 3360not yet
Corner Subgrid CountNumber of subgrids of height and width at least two whose four corners are black.cses 2137not yet
Counting BishopsNumber of ways to place `k` bishops on an `n × n` board with no two on a common diagonal, modulo `10^9 + 7`.cses 2176not yet
Counting BitsTotal number of one bits in the binary representations of `1..n`.cses 1146not yet
Counting Coprime PairsNumber of position pairs whose values are coprime.cses 2417not yet
Counting DivisorsThe number of divisors of each given integer.cses 1713not yet
Counting GridsNumber of black/white `n × n` grids up to rotation, modulo `10^9 + 7`.cses 2210not yet
Counting LCM ArraysNumber of positive arrays of length `n` with `lcm (a i) (a (i+1)) = k` throughout, modulo `10^9 + 7`.cses 3169not yet
Counting NecklacesNumber of colourings of `n` pearls with `m` colours up to rotation, modulo `10^9 + 7`.cses 2209not yet
Counting NumbersNumber of integers in `[a, b]` with no two equal adjacent decimal digits.cses 2220not yet
Counting PathsFor each node, how many of the given paths pass through it.cses 1136not yet
Counting PatternsNumber of positions where each pattern occurs in the string.cses 2103not yet
Counting PermutationsNumber of permutations of `1..n` with no two adjacent elements differing by one, modulo `10^9 + 7`.cses 1075not yet
Counting ReordersNumber of rearrangements with no two equal adjacent characters, counting rearrangements of equal characters separately, modulo `10^9 + 7`.cses 2421not yet
Counting RoomsNumber of connected components of floor squares under side adjacency.cses 1192not yet
Counting SequencesNumber of length-`n` sequences over `1..k` using every value at least once, modulo `10^9 + 7`.cses 2228not yet
Counting TilingsNumber of domino tilings of an `n × m` grid, modulo `10^9 + 7`. A domino is an anchor cell plus an orientation (`true` = horizontal, covering the cell to the right; `false` = vertical, covering the cell below).cses 2181not yet
Counting TowersNumber of ways to tile a `2 × n` tower with axis-aligned rectangular blocks of integer sizes, modulo `10^9 + 7`. A tiling is a set of blocks whose cells partition the tower.cses 2413not yet
Course ScheduleAn order of all courses respecting every "a before b" requirement, or `IMPOSSIBLE`.cses 1679not yet
Course Schedule IIThe lexicographically least topological order: finish course 1 as early as possible, then course 2, and so on.cses 1757not yet
Creating OfficesMost offices placeable in a tree so that any two are at distance at least `d`.cses 1752not yet
Creating StringsAll distinct rearrangements of a string, in alphabetical order, preceded by their count.cses 1622not yet
Creating Strings IINumber of distinct rearrangements of a string, modulo `10^9 + 7`.cses 1715not yet
Critical CitiesThe cities lying on every route from city `1` to city `n`, in increasing order.cses 1703not yet
Cut and PasteRepeatedly cut the substring from `a` to `b` and append it at the end.cses 2072not yet
Cycle FindingA closed walk of negative total length, printed as its vertices with the start repeated, or `NO`.cses 1197not yet
Cyclic ArrayFewest cyclic segments each of sum at most `k`.cses 1191not yet
De Bruijn SequenceA shortest bit string containing every bit string of length `n` as a substring.cses 1692not yet
Dice CombinationsNumber of sequences of dice throws (values `1..6`) summing to `n`, modulo `10^9 + 7`.cses 1633not yet
Dice ProbabilityProbability that `n` dice sum to a value in `[a, b]`, to six decimal places.cses 1725not yet
Digit QueriesThe digit at 1-indexed position `k` of the infinite string `123456789101112…`.cses 2431not yet
Distance QueriesDistance between two nodes of a tree.cses 1135not yet
Distinct ColorsFor each node, the number of distinct colours in its subtree (root `1`).cses 1139not yet
Distinct NumbersThe number of distinct values in a list.cses 1621not yet
Distinct RoutesMaximum number of routes from `1` to `n` that pairwise share no teleporter, and such routes.cses 1711not yet
Distinct Routes II`k` routes from room `1` to room `n` sharing no teleporter, using as few teleporters in total as possible, or `-1`.cses 2130not yet
Distinct SubsequencesNumber of distinct non-empty subsequences, modulo `10^9 + 7`.cses 1149not yet
Distinct SubstringsNumber of distinct non-empty substrings.cses 2105not yet
Distinct Sums GridAn `n × n` grid where every value `1..n` occurs `n` times and the `2n` row and column sums are all different.cses 3424not yet
Distinct Values QueriesNumber of distinct values at positions `a..b`.cses 1734not yet
Distinct Values Queries IIPoint updates; whether all values at positions `a..b` are distinct.cses 3356not yet
Distinct Values SplitsNumber of ways to cut the array into segments each of whose values are distinct, modulo `10^9 + 7`.cses 3190not yet
Distinct Values SubarraysNumber of (position-distinguished) non-empty subarrays whose elements are pairwise distinct.cses 3420not yet
Distinct Values Subarrays IINumber of subarrays with at most `k` distinct values.cses 2428not yet
Distinct Values SubsequencesNumber of non-empty index subsets whose values are pairwise distinct, modulo `10^9 + 7`.cses 3421not yet
Distinct Values SumSum, over every subarray, of the number of distinct values it contains.cses 3150not yet
Distributing ApplesNumber of ways to give `m` identical apples to `n` distinguishable children, modulo `10^9 + 7`.cses 1716not yet
Divisor AnalysisFor the number given by its prime factorisation, the count, sum and product of its divisors, each modulo `10^9 + 7`.cses 2182not yet
Download SpeedMaximum flow from computer `1` to computer `n` with the connections as capacities.cses 1694not yet
Dynamic ConnectivityThe number of components before the first event and after each edge insertion or deletion.cses 2133not yet
Dynamic Range Minimum QueriesPoint updates and minima over positions `a..b`.cses 1649not yet
Dynamic Range Sum QueriesPoint updates and sums over positions `a..b`.cses 1648not yet
Edit DistanceFewest single-character insertions, deletions and replacements turning one string into another.cses 1639not yet
Elevator RidesFewest elevator rides carrying everyone, each ride's total weight at most `x`.cses 1653not yet
Empty StringNumber of ways to delete the string by repeatedly removing two equal adjacent characters, modulo `10^9 + 7`.cses 1080not yet
Eulerian SubgraphsNumber of edge subsets in which every node has even degree, modulo `10^9 + 7`.cses 2078not yet
Even Outdegree EdgesOrient every edge so that every node has even outdegree.cses 2179not yet
Exponentiation`a^b` modulo `10^9 + 7`, with `0^0 = 1`.cses 1095not yet
Exponentiation II`a^(b^c)` modulo `10^9 + 7`, with `0^0 = 1`.cses 1712not yet
Factory MachinesLeast time `T` in which machines with per-product times `k_i` make `t` products in total; in time `T` machine `i` makes `⌊T / k_i⌋` products.cses 1620not yet
Ferris WheelFewest gondolas, each holding at most two children with total weight at most `x`.cses 1090not yet
Fibonacci Numbers`F n` modulo `10^9 + 7`, with `F 0 = 0` and `F 1 = 1`.cses 1722not yet
Filled Subgrid Count IFor each letter, the number of square subgrids in which every cell holds that letter.cses 3413not yet
Filled Subgrid Count IIFor each letter, the number of rectangular subgrids in which every cell holds that letter.cses 3414not yet
Filling TrominosTile an `n × m` grid with L-trominoes; neighbouring squares carry the same letter exactly when they belong to the same piece.cses 2423not yet
Finding a CentroidA node whose removal leaves components of at most `⌊n/2⌋` nodes.cses 2079not yet
Finding BordersAll border lengths in increasing order, a border being a proper prefix that is also a suffix.cses 1732not yet
Finding PatternsWhether each pattern occurs in the string.cses 2102not yet
Finding PeriodsAll period lengths in increasing order, a period being a prefix whose repetition yields the string.cses 1733not yet
Fixed-Length Paths INumber of (unordered) pairs of nodes at distance exactly `k`.cses 2080not yet
Fixed-Length Paths IINumber of (unordered) pairs of nodes at distance between `k₁` and `k₂`.cses 2081not yet
Fixed Length Walk QueriesWhether a walk of exactly `x` steps goes from `a` to `b`.cses 3357not yet
Flight DiscountCheapest route from `1` to `n` when exactly one flight on it is charged at half price (rounded down).cses 1195not yet
Flight Route RequestsFewest one-way flights making every requested route possible.cses 1699not yet
Flight RoutesPrices of the `k` cheapest routes (walks, possibly repeating cities) from `1` to `n`, sorted.cses 1196not yet
Flight Routes Check`YES` if every city reaches every other; otherwise `NO` and a pair `a b` with no route from `a` to `b`.cses 1682not yet
Food DivisionFewest single-unit passes between neighbours around a round table turning the current amounts into the wanted ones.cses 1189not yet
Forbidden CitiesWhether a route from `a` to `b` avoids city `c`.cses 1705not yet
Forest QueriesNumber of trees inside a rectangle given by its corners `(y1, x1)`, `(y2, x2)` (1-based).cses 1652not yet
Forest Queries IIToggle a square; count trees inside a rectangle.cses 1739not yet
Functional Graph DistributionFor each `k`, the number of functional graphs on `n` nodes with exactly `k` connected components, modulo `10^9 + 7`.cses 2415not yet
GCD SubsetsFor each `k`, the number of non-empty subsets whose greatest common divisor is `k`, modulo `10^9 + 7`.cses 3161not yet
Game RoutesNumber of routes from level `1` to level `n` in an acyclic network, modulo `10^9 + 7`.cses 1681not yet
Giant PizzaChoose toppings so that each family member gets at least one wish satisfied.cses 1684not yet
Graph ColoringA proper colouring using the fewest colours, and the colour of each node.cses 3308not yet
Graph GirthThe length of a shortest cycle, or `-1`.cses 1707not yet
Graph Paths INumber of walks from node `1` to node `n` using exactly `k` edges, modulo `10^9 + 7`.cses 1723not yet
Graph Paths IIMinimum total weight of a walk from node `1` to node `n` using exactly `k` edges, or `-1`.cses 1724not yet
Gray CodeList all `2^n` bit strings of length `n` so that successive strings differ in exactly one bit.cses 2205not yet
Grid Coloring IRecolour every cell of an `A`–`D` grid to a different letter so that no two side-adjacent cells share a letter, or report `IMPOSSIBLE`.cses 3311not yet
Grid Coloring IIRecolour every cell of an `A`–`C` grid to a different letter so that no two side-adjacent cells match, or `IMPOSSIBLE`.cses 3312not yet
Grid CompletionNumber of ways to complete the grid so that every row and column holds exactly one `A` and one `B`, modulo `10^9 + 7`.cses 2429not yet
Grid Path ConstructionA path from `a` to `b` in an `n × m` grid visiting every square exactly once.cses 2418not yet
Grid Path DescriptionCount the paths in a `7 × 7` grid from the upper-left to the lower-left square that visit every square once and match a 48-character pattern over `D U L R ?`.cses 1625not yet
Grid Paths INumber of right/down paths from the upper-left to the lower-right square of an `n × n` grid avoiding traps, modulo `10^9 + 7`. Input: `trap[i][j]`.cses 1638not yet
Grid Paths IINumber of right/down paths from `(1,1)` to `(n,n)` avoiding the traps, modulo `10^9 + 7`.cses 1078not yet
Grid Puzzle IChoose exactly `a i` squares in row `i` and `b j` squares in column `j`.cses 2432not yet
Grid Puzzle IIChoose exactly `a i` squares in row `i` and `b j` squares in column `j`, collecting as many coins as possible.cses 2131not yet
Grundy's GameSplit a heap into two non-empty heaps of different sizes; the player moving last wins.cses 2207not yet
Hamiltonian FlightsNumber of flight sequences from `1` to `n` visiting every city exactly once, modulo `10^9 + 7`. Parallel flights give distinct routes.cses 1690not yet
Hamming DistanceSmallest number of differing positions between two of the given bit strings.cses 2136not yet
Hidden IntegerFind a hidden `x` by asking whether `y < x`, in at most 30 questions.cses 3112no — interactive
Hidden PermutationFind a hidden permutation of `1..n` by asking whether `a i < a j`, in at most `10^4` questions.cses 3139no — interactive
High ScoreMaximum total of tunnel scores on a walk from room `1` to room `n`, or `-1` if unbounded.cses 1673not yet
Hotel QueriesEach group takes the first hotel with enough free rooms (or `0` if none).cses 1143not yet
Houses and SchoolsPlace `k` schools in houses minimising the total walking distance, each child going to the nearest school.cses 2087not yet
Increasing ArrayYou are given an array of `n` integers. On each move you may increase one element by one. What is the minimum number of moves to make the array non-decreasing? Modelling choice: a sequence of unit increments from `xs` reaching `ys` exists iff `xs ≤ ys` pointwise, and its length is `Σ (ys[i] - xs[i])`. We take that as the definition of "moves", so the answer is the minimum of `cost xs ys` over reachable non-decreasing `ys`.cses 1094not yet
Increasing Array IILeast total change, up or down, making the array non-decreasing.cses 2132not yet
Increasing Array QueriesMinimum unit increments making positions `a..b` non-decreasing (see Increasing Array).cses 2416not yet
Increasing SubsequenceLength of a longest strictly increasing subsequence.cses 1145not yet
Increasing Subsequence IINumber of non-empty index subsets whose values are strictly increasing in index order, modulo `10^9 + 7`.cses 1748not yet
Intersection PointsNumber of points where a horizontal and a vertical segment meet.cses 1740not yet
Inverse InversionsA permutation of `1..n` with exactly `k` inversions.cses 2214not yet
Inverse Suffix ArrayA string over `a`–`z` whose suffix array is the given permutation, or `-1`.cses 3225not yet
Inversion ProbabilityExpected number of inversions when position `i` holds a uniform value in `1..r_i`, to six decimal places.cses 1728not yet
Inversion SortingSort a hidden permutation by reversing subarrays; after each reversal you are told the number of inversions, and you win when it reaches zero. At most `4n` reversals are allowed.cses 3140no — interactive
InvestigationFor routes from `1` to `n`: the minimum price, the number of minimum-price routes modulo `10^9 + 7`, and the fewest and most flights on a minimum-price route.cses 1202not yet
Josephus Problem IChildren `1..n` in a circle; every other child is removed. The removal order.cses 2162not yet
Josephus Problem IIChildren `1..n` in a circle; repeatedly skip `k` and remove the next. The removal order.cses 2163not yet
Josephus QueriesWith `n` children in a circle and every second child removed, who is removed `k`-th.cses 2164not yet
K Subset Sums IThe `k` smallest sums over all `2^n` subsets.cses 3108not yet
K Subset Sums IIThe `k` smallest sums over the subsets of exactly `m` elements.cses 3109not yet
K Subset XorsThe `k` smallest subset xors, counting each of the `2^n` subsets separately.cses 3192not yet
Knight Moves GridFor every square of an `n × n` board, the least number of knight moves to the top-left corner.cses 3217not yet
Knight Moves QueriesFewest knight moves from `(x, y)` to `(1, 1)` on an infinite board.cses 3218not yet
Knight's TourNumber the squares `1..64` in the order a knight visits them, starting at column `x`, row `y`.cses 1689not yet
Knuth DivisionRepeatedly split a piece into two; each split costs the sum of that piece. The least total cost of splitting the array into single elements.cses 2088not yet
K-th Highest ScoreTwo countries each have `n` distinct scores. Asking for the `i`-th highest score of one country, find the `k`-th highest overall in at most 100 questions.cses 3305no — interactive
LabyrinthA shortest path from `A` to `B` through floor squares, as a move string.cses 1193not yet
Letter Pair Move GameMove adjacent letter pairs into the two empty boxes until every `A` precedes every `B`; the output lists the configuration after each turn.cses 2427not yet
Line Segment IntersectionWhether two segments share at least one point.cses 2190not yet
Line Segments Trace IFor each integer `x` in `0..m`, the highest point on any segment from `(0, y₁)` to `(m, y₂)`.cses 3427not yet
Line Segments Trace IIFor each integer `x` in `0..m`, the highest point on any segment covering `x`, or `-1`.cses 3428not yet
Lines and Queries IAdd lines `a x + b`; report the largest value of any added line at `x`.cses 3429not yet
Lines and Queries IIAdd lines active on a range; report the largest value of any active line at `x`, or `NO`.cses 3430not yet
List of SumsRecover a list from the multiset of its pairwise sums.cses 2414not yet
List RemovalsRemove the element at the given (current) position each time; report the removed elements.cses 1749not yet
Longest Common SubsequenceLength of a longest common subsequence of two arrays, and one such subsequence.cses 3403not yet
Longest Flight RouteA route from `1` to `n` in an acyclic flight network visiting the most cities.cses 1680not yet
Longest PalindromeA longest palindromic substring.cses 1111not yet
MST Edge CheckFor each edge, whether some minimum spanning tree contains it.cses 3407not yet
MST Edge CostFor each edge, the least spanning tree cost among trees containing that edge.cses 3409not yet
MST Edge Set CheckFor each set of edges, whether some minimum spanning tree contains all of them.cses 3408not yet
Mail DeliveryA closed route from crossing `1` using every street exactly once (an Eulerian circuit).cses 1691not yet
Maximum Average SubarraysFor each end position, the length of the longest subarray ending there with the greatest average.cses 3301not yet
Maximum Building IThe largest rectangle of tree-free squares.cses 1147not yet
Maximum Building IIFor every building size, the number of placements avoiding all trees.cses 1148not yet
Maximum Manhattan DistancesAfter each point is added, the largest Manhattan distance between two of them.cses 3410not yet
Maximum Subarray SumLargest sum of a non-empty contiguous subarray.cses 1643not yet
Maximum Subarray Sum IILargest sum of a contiguous subarray whose length is between `a` and `b`.cses 1644not yet
Maximum Xor SubarrayLargest xor of a contiguous subarray.cses 1655not yet
Maximum Xor SubsetLargest xor of a subset of the elements.cses 3191not yet
Meet in the MiddleNumber of index subsets whose values sum to `x`.cses 1628not yet
Message RouteA route from computer `1` to computer `n` through the fewest computers.cses 1667not yet
Mex Grid ConstructionAn `n × n` grid where each cell holds the least non-negative integer absent from the cells to its left in its row and above it in its column.cses 3419not yet
Mex Grid QueriesThe value at square `(y, x)` of the infinite mex grid.cses 1157not yet
Minimal Grid PathLexicographically least string read along a right/down path from the upper-left to the lower-right square of a letter grid.cses 3359not yet
Minimal RotationThe lexicographically least rotation of the string.cses 1110not yet
Minimizing CoinsFewest coins (with repetition) from the given denominations summing to `x`, or `-1`.cses 1634not yet
Minimum Cost PairsFor each `k`, the least total `|a - b|` over `k` disjoint pairs.cses 3402not yet
Minimum Euclidean DistanceThe square of the least distance between two distinct points.cses 2194not yet
Missing Coin SumThe smallest positive sum not obtainable from a sub-multiset of the coins.cses 2183not yet
Missing Coin Sum QueriesSmallest sum not obtainable from coins `a..b` (see Missing Coin Sum).cses 2184not yet
Missing NumberGiven `n - 1` distinct numbers from `1..n`, find the one that is missing. The input object is the list of given numbers; `n` is its length plus one.cses 1083not yet
Money SumsAll positive sums obtainable from a sub-multiset of the coins, in increasing order.cses 1745not yet
Monotone SubsequencesA permutation of `1..n` whose longest monotone subsequence has exactly `k` elements.cses 2215not yet
Monster Game IKill a subset of the monsters, always including the last; killing monster `i` with current skill factor `f` costs `s i * f`, and afterwards the skill factor becomes `f i`. The least total time.cses 2084not yet
Monster Game IIKill a subset of the monsters, always including the last; killing monster `i` with current skill factor `f` costs `s i * f`, and afterwards the skill factor becomes `f i`. The least total time.cses 2085not yet
MonstersEscape to the boundary so that at every time `t` no monster could be on your square (monsters move at most one step per turn and may wait).cses 1194not yet
Mountain RangeGlide from `a` to `b` when `a` is taller than `b` and than everything between. Maximum number of mountains on a route.cses 3314not yet
Movie FestivalMaximum number of movies one person can watch entirely.cses 1629not yet
Movie Festival II`k` club members; maximum total number of movies watched entirely, each member watching pairwise non-overlapping movies.cses 1632not yet
Movie Festival QueriesMaximum number of pairwise compatible movies entirely inside the time window `[arrive, leave]`.cses 1664not yet
Moving RobotsExpected number of empty squares of an `8 × 8` board after every robot takes `k` uniformly random steps, to six decimal places.cses 1726not yet
Multiplication TableThe middle value of the `n × n` multiplication table sorted in increasing order.cses 2422not yet
Nearest Campsites IThe largest distance from a free campsite to its nearest reserved campsite.cses 3306not yet
Nearest Campsites IIFor each free campsite, the distance to its nearest reserved campsite.cses 3307not yet
Nearest ShopsFor each city, the distance to the nearest *other* city with a shop, or `-1`.cses 3303not yet
Nearest Smaller ValuesFor each position, the nearest position to its left with a smaller value (1-based), or 0.cses 1645not yet
Necessary CitiesThe articulation points: cities whose removal disconnects some other pair.cses 2077not yet
Necessary RoadsThe bridges: roads whose removal disconnects some pair of cities.cses 2076not yet
Nested Ranges CheckFor each range: does it contain another range, and is it contained in another range.cses 2168not yet
Nested Ranges CountFor each range: how many other ranges it contains, and how many contain it.cses 2169not yet
Network BreakdownThe number of components after each connection breaks.cses 1677not yet
Network RenovationFewest new connections making the tree survive any single connection failure, that is, making the graph bridgeless.cses 1704not yet
New Flight RoutesFewest new one-way flights making the whole network strongly connected.cses 1685not yet
New Roads QueriesAfter how many days two cities are first connected, or `-1`.cses 2101not yet
Next PrimeThe smallest prime strictly greater than each given number.cses 3396not yet
Nim Game IRemove any number of sticks from one heap; the player taking the last stick wins.cses 1730not yet
Nim Game IIRemove one, two or three sticks from one heap; the player taking the last stick wins.cses 1098not yet
Number of Subset XorsHow many distinct values arise as the xor of a subset.cses 3211not yet
Number SpiralFor each query `(y, x)` report the number at row `y`, column `x` of the spiral. The statement defines the spiral by a picture. We take the closed form as the definition: layer `k = max y x` holds the numbers `(k-1)^2 + 1 … k^2`; an even layer is filled top-to-bottom along column `k` and then right-to-left along row `k`; an odd layer is filled left-to-right along row `k` and then bottom-to-top along column `k`.cses 1071not yet
One Bit PositionsFor each distance `k`, the number of position pairs `i - j = k` that both hold a one.cses 2112not yet
Palindrome QueriesCharacter updates; whether the substring from `a` to `b` is a palindrome.cses 2420not yet
Palindrome ReorderReorder the letters of a string into a palindrome, or report that none exists.cses 1755not yet
Parcel DeliveryCheapest way to send `k` parcels from city `1` to city `n` respecting route capacities, or `-1`. This is a minimum-cost flow of value `k`.cses 2121not yet
Path QueriesNode value updates; sum of values on the path from the root `1` to a node.cses 1138not yet
Path Queries IINode value updates; maximum value on the path between two nodes.cses 2134not yet
Pattern PositionsFirst (1-based) occurrence position of each pattern, or `-1`.cses 2104not yet
Permutation InversionsNumber of permutations of `1..n` with exactly `k` inversions, modulo `10^9 + 7`.cses 2229not yet
Permutation OrderEither the `k`-th permutation of `1..n` in lexicographic order, or the index of a given permutation.cses 3397not yet
Permutation Prime SumsTwo permutations of `1..n` whose position-wise sums are all prime.cses 3423not yet
Permutation RoundsRounds until repeatedly applying the permutation restores sorted order, modulo `10^9 + 7`.cses 3398not yet
Permutation SubsequenceA longest common subsequence of two permutations, with its length.cses 3404not yet
PermutationsConstruct a permutation of `1..n` with no two adjacent elements differing by one, or report that none exists.cses 1070not yet
Permuted Binary StringsFind a hidden permutation `a` of `1..n` by sending bit strings `b` and receiving `b` permuted by `a`, in at most 10 questions.cses 3228no — interactive
Pizzeria QueriesPrice updates; cheapest delivered pizza to building `k`, price `p_a + |a - k|`.cses 2206not yet
Planets and KingdomsLabel planets by strongly connected component with labels `1..k`, `k` the number of kingdoms.cses 1683not yet
Planets CyclesFrom each planet, the number of teleportations until a planet is revisited.cses 1751not yet
Planets Queries IWhere you end up after `k` teleportations from planet `x`.cses 1750not yet
Planets Queries IIFewest teleportations from planet `a` to planet `b`, or `-1`.cses 1160not yet
PlaylistLength of the longest contiguous run of pairwise distinct songs.cses 1141not yet
Point in PolygonFor each query point: inside, outside, or on the boundary of a simple polygon.cses 2192not yet
Point Location TestWhether `p₃` lies left of, right of, or on the directed line from `p₁` to `p₂`.cses 2189not yet
Police ChaseFewest streets whose closure separates crossing `1` from crossing `n`, and such a set.cses 1695not yet
Polygon AreaTwice the area of a simple polygon.cses 2191not yet
Polygon Lattice PointsThe number of integer points strictly inside a simple polygon and on its boundary.cses 2193not yet
Polynomial QueriesAdd `1, 2, 3, …` to positions `a..b` in order; range sums.cses 1736not yet
Prefix Sum QueriesPoint updates; maximum prefix sum (empty prefix allowed) of positions `a..b`.cses 2166not yet
Prime MultiplesHow many of `1..n` are divisible by at least one of the given primes.cses 2185not yet
Programmers and ArtistsHire `a` programmers and `b` artists maximising the total of the relevant skills.cses 2426not yet
ProjectsMaximum total reward of a set of projects with pairwise disjoint day ranges.cses 1140not yet
Prüfer CodeRebuild the tree whose Prüfer code is given. The code is produced by repeatedly removing the smallest-labelled leaf and recording its neighbour, so we state correctness as: the answer is a tree on `n` nodes whose code is the given one.cses 1134not yet
Pyramid ArrayFewest adjacent swaps making the array increase and then decrease.cses 1747not yet
Raab Game ITwo players each play cards `1..n` in some order; the higher card scores a point per round. Given `(n, a, b)`, exhibit orders producing scores `a` and `b`, or report that none exist.cses 3399not yet
Raab Game IINumber of card games producing the given scores, modulo `10^9 + 7`.cses 3400not yet
Range Interval QueriesNumber of positions `i ∈ [a, b]` whose value lies in `[c, d]`.cses 3163not yet
Range Queries and CopiesA growing list of arrays: point set in array `k`, range sum in array `k`, and copying array `k`.cses 1737not yet
Range Update QueriesAdd `u` to every position in `a..b`; report the value at position `k`.cses 1651not yet
Range Updates and SumsRange increase, range assignment, and range sum.cses 1735not yet
Range Xor QueriesXor of the values at positions `a..b`.cses 1650not yet
Reachability QueriesWhether node `b` is reachable from node `a`.cses 2143not yet
Reachable NodesFor each node of an acyclic graph, how many nodes it reaches, itself included.cses 2138not yet
Reading BooksTwo readers each read every book; a book cannot be read by both at once and a reader reads one book at a time. Minimum time until both have finished.cses 1631not yet
Rectangle CuttingFewest straight integer cuts turning an `a × b` rectangle into squares. The state is the multiset of current rectangles.cses 1744not yet
Removal GameTwo players alternately take the first or last number; each maximises their own total. The first player's total under optimal play. `margin l` is the best achievable (mover's total − other's total) from list `l`, the minimax value; the first player's total then satisfies `2·s = sum + margin`.cses 1097not yet
Removing DigitsFewest steps to reach `0` from `n`, each step subtracting one of the current number's digits.cses 1637not yet
Removing Digits IIFewest steps to reach `0`, each step subtracting a digit occurring in the number.cses 2174not yet
Repeating SubstringA longest substring occurring at two or more positions, or `-1`.cses 2106not yet
RepetitionsLength of the longest substring consisting of a single repeated character.cses 1069not yet
Replace with DifferenceRepeatedly replace two values by their absolute difference so that `0` remains.cses 3159not yet
Required SubstringNumber of length-`n` strings over `A`–`Z` containing the pattern, modulo `10^9 + 7`.cses 1112not yet
Restaurant CustomersMaximum number of customers present at the same time.cses 1619not yet
Reversal SortingSort the permutation with at most `n` subarray reversals.cses 2075not yet
Reversals and SumsReverse a subarray, or report the sum of a subarray.cses 2074not yet
Road ConstructionAfter each new road: the number of components and the size of the largest one.cses 1676not yet
Road ReparationMinimum total cost of a set of roads connecting all cities, or `IMPOSSIBLE`.cses 1675not yet
Robot PathThe robot walks the given moves from the origin and stops as soon as it revisits a point it has already been at; the total distance it travels.cses 1742not yet
Room AllocationMinimum number of hotel rooms for customers with arrival/departure days, and an allocation achieving it. Two customers may share a room iff one departs strictly before the other arrives.cses 1164not yet
Round TripA simple cycle through at least three cities, printed with the start repeated at the end.cses 1669not yet
Round Trip IIA directed simple cycle through at least two cities, printed with the start repeated at the end.cses 1678not yet
SOS Bit ProblemFor each element `x`, how many elements `y` satisfy `x ||| y = x`, `x &&& y = x` and `x &&& y ≠ 0`.cses 1654not yet
Salary QueriesSalary changes (`! k x`) and counts of employees with salary in `[a, b]` (`? a b`).cses 1144not yet
Same Sum SubsetsTwo disjoint non-empty subsets with equal sums, given as their elements.cses 3425not yet
School DanceA maximum set of disjoint dance pairs among the potential pairs.cses 1696not yet
School ExcursionWhich counts of children can visit the zoo, given that friends must go together.cses 1706not yet
Shortest Routes IShortest route lengths from city `1` to every city along one-way flights.cses 1671not yet
Shortest Routes IIShortest route length between two cities along two-way roads, or `-1`.cses 1672not yet
Shortest SubsequenceA shortest DNA string that is not a subsequence of the given one.cses 1087not yet
Signal ProcessingThe convolution of the signal with the mask.cses 2113not yet
Sliding Window AdvertisementThe largest axis-aligned rectangle fitting under the board heights of a window.cses 3227not yet
Sliding Window CostLeast total change making all elements of a window equal.cses 1077not yet
Sliding Window Distinct ValuesNumber of distinct values in each window.cses 3222not yet
Sliding Window InversionsNumber of pairs in a window whose left element exceeds the right one.cses 3223not yet
Sliding Window MedianThe middle element of each sorted window, the smaller one when the width is even.cses 1076not yet
Sliding Window MexThe least non-negative integer missing from each window.cses 3219not yet
Sliding Window MinimumThe minimum of each window of `k` elements; print the xor of those minima. The array is produced by the linear generator in the input.cses 3221not yet
Sliding Window ModeThe most frequent value in each window, the smallest one if several tie.cses 3224not yet
Sliding Window OrThe bitwise or of each window of `k` elements; print the xor of those values. The array is produced by the linear generator in the input.cses 3405not yet
Sliding Window SumThe sum of each window of `k` elements; print the xor of those values. The array is produced by the linear generator in the input.cses 3220not yet
Sliding Window XorThe bitwise xor of each window of `k` elements; print the xor of those values. The array is produced by the linear generator in the input.cses 3426not yet
Sorting MethodsFewest steps to sort the permutation under four move sets: adjacent swaps, any swap, moving an element anywhere, and moving an element to the front.cses 1162not yet
Special SubstringsSubstrings in which every character that occurs does so equally often.cses 2186not yet
Split into Two PathsTwo directed paths covering every node exactly once between them.cses 3358not yet
Square SubsetsNumber of subsets whose product is a perfect square, the empty subset included, modulo `10^9 + 7`.cses 3193not yet
Stack WeightsAfter each move, which stack is certainly heavier, given only that coin weights increase with coin number.cses 2425not yet
Stair GameMove balls from stair `k ≠ 1` down to stair `k - 1`; the player moving last wins.cses 1099not yet
Static Range Minimum QueriesMinimum of the values at positions `a..b`.cses 1647not yet
Static Range Sum QueriesSum of the values at positions `a..b`.cses 1646not yet
Stick DifferenceFor each `k`, the least possible spread of stick lengths after exactly `k` cuts.cses 3401not yet
Stick DivisionsLeast total cost of cutting one stick into the required pieces, a cut costing the length of the stick being cut.cses 1161not yet
Stick GameFor each heap size `1..n`, whether the player to move wins when the allowed moves remove `p` sticks for `p` in the given set.cses 1729not yet
Stick LengthsMinimum total cost of making all sticks the same length, cost being the absolute change per stick.cses 1074not yet
String FunctionsThe Z function and the KMP prefix function of the string.cses 2107not yet
String MatchingNumber of positions where the pattern occurs in the string.cses 1753not yet
String ReorderThe lexicographically least rearrangement with no two equal adjacent characters, or `-1`.cses 1743not yet
String TransformInvert the Burrows-Wheeler transform: recover the string whose transform is the input. The transform appends `#`, sorts all rotations, and reads off their last characters.cses 1113not yet
Strongly Connected EdgesOrient every edge so that the directed graph is strongly connected.cses 2177not yet
Subarray DivisibilityNumber of subarrays whose sum is divisible by `n`, the array length.cses 1662not yet
Subarray SquaresSplit the array into `k` consecutive pieces minimising the sum of squared piece sums.cses 2086not yet
Subarray Sum ConstraintsAn integer array meeting every constraint "the sum over `l..r` is `s`".cses 3294not yet
Subarray Sum QueriesAfter each point update, the maximum subarray sum of the whole array (empty allowed).cses 1190not yet
Subarray Sum Queries IIMaximum subarray sum (empty allowed) within positions `a..b`.cses 3226not yet
Subarray Sums INumber of subarrays of positive integers with sum exactly `x`.cses 1660not yet
Subarray Sums IINumber of subarrays of integers with sum exactly `x`.cses 1661not yet
SubordinatesFor each employee, the number of employees below them in the hierarchy.cses 1674not yet
Subsets with Fixed AverageNumber of non-empty subsets whose average equals `a`, modulo `10^9 + 7`.cses 3302not yet
Substring DistributionFor each length `1..n`, the number of distinct substrings of that length.cses 2110not yet
Substring Order IThe `k`-th smallest distinct substring in lexicographic order.cses 2108not yet
Substring Order IIThe `k`-th smallest substring counting repeats, i.e. over all `(start, length)` pairs.cses 2109not yet
Substring ReversalsRepeatedly reverse the substring from `a` to `b`.cses 2073not yet
Subtree QueriesNode value updates; sum of values in the subtree of a node (root `1`).cses 1137not yet
Sum of Divisors`∑_{i=1}^n σ(i)` modulo `10^9 + 7`, where `σ` sums the divisors.cses 1082not yet
Sum of Four SquaresFour non-negative integers whose squares sum to `n`.cses 3355not yet
Sum of Four Values4 distinct positions (1-based) whose values sum to `x`, or `IMPOSSIBLE`.cses 1642not yet
Sum of Three Values3 distinct positions (1-based) whose values sum to `x`, or `IMPOSSIBLE`.cses 1641not yet
Sum of Two ValuesTwo distinct positions (1-based) whose values sum to `x`, or `IMPOSSIBLE`.cses 1640not yet
Swap GameFewest adjacent swaps turning the `3 × 3` grid into `1..9` in order.cses 1670not yet
Swap Round SortingFewest rounds sorting the permutation, each round performing any set of disjoint swaps, together with the swaps of each round.cses 1698not yet
System of Linear EquationsAny solution of `n` linear equations in `m` variables modulo `10^9 + 7`, or `-1`.cses 3154not yet
Task AssignmentA least-cost perfect matching of employees to tasks, with its cost.cses 2129not yet
Tasks and DeadlinesProcess tasks `(duration, deadline)` back to back from time 0 in some order; reward per task is `deadline - finish`. Maximum total reward.cses 1630not yet
Teleporters PathA route from `1` to `n` using every teleporter exactly once (an Eulerian path).cses 1693not yet
Third PermutationA permutation differing from both given permutations at every position.cses 3422not yet
Throwing DiceNumber of sequences of dice throws (values `1..6`) summing to `n`, modulo `10^9 + 7`.cses 1096not yet
Tournament Graph DistributionFor each `k`, the number of tournaments on `n` nodes with exactly `k` strongly connected components, modulo `10^9 + 7`.cses 3232not yet
Tower of HanoiMove `n` disks from stack 1 to stack 3 with the fewest moves; print the moves. The game is modelled operationally: a state is three stacks (top first, disks numbered by size), a move pops from one stack and pushes on another, and is legal only if the source is non-empty and the destination is empty or has a larger disk on top.cses 2165not yet
TowersMinimum number of towers when cubes are stacked in order, each on a strictly larger cube. Each tower is a strictly decreasing subsequence, so the answer is the fewest strictly decreasing subsequences that partition the sequence.cses 1073not yet
Traffic LightsAfter each traffic light is added, the longest stretch of street between consecutive lights (the ends of the street count as boundaries).cses 1163not yet
Trailing ZerosThe number of trailing zeros of `n!`.cses 1618not yet
Transfer Speeds SumSum over all computer pairs of the slowest connection on the route between them.cses 3111not yet
Tree Coin Collecting IShortest walk from `a` to `b` visiting at least one node holding a coin.cses 3114not yet
Tree Coin Collecting IIShortest walk from `a` to `b` visiting every node holding a coin.cses 3149not yet
Tree DiameterMaximum distance between two nodes.cses 1131not yet
Tree Distances IFor each node, the maximum distance to another node.cses 1132not yet
Tree Distances IIFor each node, the sum of its distances to all nodes.cses 1133not yet
Tree Isomorphism IWhether two trees rooted at node 1 are isomorphic.cses 1700not yet
Tree Isomorphism IIWhether two unrooted trees are isomorphic.cses 1701not yet
Tree MatchingMaximum number of edges no two of which share a node.cses 1130not yet
Tree TraversalsGiven the preorder and inorder traversals of a binary tree, print its postorder traversal.cses 1702not yet
Triangle Number SumsFewest triangle numbers summing to `n`.cses 3406not yet
Two Array AverageNon-empty prefixes of both arrays maximising the average of everything chosen.cses 3361not yet
Two KnightsFor every `k = 1..n`, the number of ways to place two knights on a `k × k` board so that they do not attack each other (unordered pairs of squares).cses 1072not yet
Two SetsSplit `1..n` into two sets of equal sum, or report that it is impossible.cses 1092not yet
Two Sets IINumber of ways to split `1..n` into two sets of equal sum (unordered pairs of sets), modulo `10^9 + 7`.cses 1093not yet
Two Stacks SortingAssign each input number to one of two stacks so that popping them produces `1..n` in order.cses 2402not yet
Visible Buildings QueriesAmong buildings `a..b`, those taller than every building before them in the range.cses 3304not yet
Visiting CitiesThe cities appearing on every cheapest route from `1` to `n`, in increasing order.cses 1203not yet
Water Containers MovesA sequence of moves leaving `x` units in container `A`, minimising the total water moved, or `-1`.cses 3213not yet
Water Containers QueriesWhether `x` units can be measured in container `A`.cses 3214not yet
Weird AlgorithmSimulate the Collatz process from `n` until it reaches `1`, printing every value.cses 1068not yet
Word CombinationsNumber of ways to write the string as a concatenation of dictionary words, modulo `10^9 + 7`.cses 1731not yet
Writing NumbersThe last number writable when each digit key may be pressed at most `n` times.cses 1086not yet
Xor Pyramid DiagonalThe leftmost number of each row, from the bottom row upwards.cses 3194not yet
Xor Pyramid PeakEach number is the xor of the two below it; find the top of the pyramid.cses 2419not yet
Xor Pyramid RowThe `k`-th row counted from the top, which has `k` numbers.cses 3195not yet