cho.sh

Problems

Pick a problem and write your solution in the built-in editor. The judge runs it against real test cases while you watch, and the wider archive is open to read whenever you like.

Total results3,683 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
DramaCount the number of valid pyramid colourings of an H by N grid with exactly N black cells, modulo 10^9+7.Hard9CombinatoricsDynamic programming+1No attempts yet2s512 MBJudgeable
Revenge of the Endless BFSDecide whether a buggy BFS that forgets visited vertices ever terminates on a given directed graph, and if so output the loop count modulo 1e9+7.Hard9GraphBFS+2No attempts yet2s512 MBJudgeable
Conveyor BeltAfter each of Q delivery requests (a, b, p) is added, report the minimum time to finish all tasks, given plates arrive one per second and each plate carries one product.Hard9MathGreedy+2No attempts yet2s512 MBJudgeable
Pipe Fitter and the Fierce DogsIn a grid where every odd row and column holds a house, cover all houses with downhill chains, minimizing the cost of pipes through dog blocks, using at most K chains.Hard9Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
Blocks 2Count the ways to tile an N x M rectangle with rotated k x N blocks (k=1..N), modulo 1999, where M can be as large as 10^10.Hard9CombinatoricsDynamic programming+2No attempts yet1s256 MBJudgeable
Stamp PaintingCount the distinct colorings of an N-unit canvas obtainable by stamping K-wide colored stamps so every unit ends up painted, modulo 1e9+7.Hard9Dynamic programmingCombinatorics+1No attempts yet2s512 MBJudgeable
Maximal polygon brightnessGiven a convex polygon and a sequence of vertex deletions, compute after each deletion the largest total length of edges that a single external light point can illuminate.Hard9GeometryDynamic programming+2No attempts yet3s1024 MBJudgeable
Street TreesMaintain a minimum-cost coloring of N vertices with two colors under incremental equality/inequality constraints and point cost updates, reporting the optimum after each operation.Hard9Union-findGraph+2No attempts yet2s256 MBJudgeable
The Number of SequencesFor a given N and C, find the lexicographically smallest triple (X, Y, Z) such that exactly C ordered N-tuples of 31-bit integers have OR X, AND Y, XOR Z, or report none exists.Hard9Bit manipulationCombinatorics+2No attempts yet1s128 MBJudgeable
Uncrossed Knight's TourGiven an m by n board (m at most 8, n up to 1e15), find the maximum number of squares a closed knight tour can visit without crossing itself.Hard9GreedyDynamic programming+2No attempts yet2s1024 MBJudgeable
Maximum Weight Matching in a General GraphGiven a weighted undirected graph, find a matching with maximum total edge weight.Hard9GraphGreedy+1No attempts yet2s512 MBJudgeable
United States of EurasiaSplit N points sorted by x into at most K contiguous groups, minimizing the largest squared diameter within any group.Hard9Binary searchDynamic programming+2No attempts yet20s1024 MBJudgeable
Xtreme NP-hard Problem?!Find the minimum-weight simple path from vertex 1 to vertex n that uses exactly k edges, or report -1; with n, m, k up to 10^6 this is explicitly NP-hard.Hard9GraphShortest path+2No attempts yet5s1024 MBJudgeable
Travelling MerchantGiven a directed weighted graph and per-market buy/sell prices for K items, find the maximum profit-to-duration ratio of a closed walk trading at most one item at a time, floor it.Hard9GraphShortest path+2No attempts yet2s512 MBJudgeable
Tree EscapeOn a rooted tree where each leaf starts with one piece, players alternately move a piece to its parent and remove it at the root; decide if the first player wins.Hard9Game theoryTree+2No attempts yet2s512 MBJudgeable
Cloud computingChoose a set of orders and a set of computers to buy so every accepted order gets enough cores at its minimum clock rate, maximizing payments minus computer costs.Hard9Dynamic programmingGreedy+2No attempts yet2s512 MBJudgeable
SatellitesSatellites appear and disappear above a half-disc planet; for each query decide whether two satellites have a common coverage point outside the planet that no other live satellite covers.Hard9GeometryDynamic programming+2No attempts yet4s512 MBJudgeable
Delivery DelaysCompute all-pairs shortest paths, then use dynamic programming over delivery-order subsets to find the delivery schedule that minimizes the worst order-to-delivery waiting time.Hard9Shortest pathDynamic programming+2No attempts yet5s512 MBJudgeable
EscalatorsChoose unordered paths on a tree and pay V[u] plus every other endpoint's complemented value to maximize total tokens.Hard9TreeDynamic programming+2No attempts yet3s512 MBJudgeable
GameChoose the order in which balls are manually removed so chain reactions of merging equal neighbors delete as many other balls as possible; output that maximum count.Hard9Dynamic programmingStack+2No attempts yet2s512 MBJudgeable
CryptoCount permutations of 1..N whose window-product multiset, taken as the K smallest primes, has exactly P distinct values, modulo 1e9+7.Hard9CombinatoricsNumber theory+2No attempts yet2s512 MBJudgeable
Forgotten LandSum over all partitions of a tree's vertices into arbitrary sets of the total language difficulty, where a set's difficulty depends on the union of languages on its vertices and on paths between them.Hard9Dynamic programmingTree+2No attempts yet3s512 MBJudgeable
The Bridge on the River KawaiiMaintain a graph under bridge insertions and deletions, and for each query answer the minimum possible maximum edge weight on a path between two islands, where weights are single digits.Hard9Dynamic programmingUnion-find+2No attempts yet5s512 MBJudgeable
Colored Tiles 2Place given 1x1 and 1x2 tiles on an H by W board without overlap to maximize the total score of edges between neighboring tiles, then output every tile's coordinates.Hard9Dynamic programmingImplementation+2No attempts yet1s512 MBJudgeable
Low Range-Sum MatrixFlip signs of at most K cells in an N by M matrix (both at most 10) so that no horizontal or vertical contiguous segment sums to more than S.Hard9Brute forceDynamic programming+2No attempts yet2s512 MBJudgeable
Nim Game Without RepeatsNim with piles of size up to 60, but each specific removal size can be used at most once per pile; decide the winner under optimal play.Hard9Game theoryDynamic programming+2No attempts yet2s512 MBJudgeable
Moorio KartCount and sum the lengths of simple cycles (at least Y) formed by joining every tree in a forest with one X-length edge between consecutive trees and a chosen path inside each tree.Hard9TreeDynamic programming+2No attempts yet3s512 MBJudgeable
Mowing MischiefGiven flowers on a grid, pick a longest chain of flowers both paths must visit, then find the minimum area the two monotone paths can sweep.Hard9Dynamic programmingSorting+2No attempts yet2s512 MBJudgeable
MessageCount length-n lowercase strings that contain a given pattern p as a substring, modulo m, where n can reach 10^12 and p has length at most 50.Hard9Dynamic programmingString matching+2No attempts yet5s512 MBJudgeable
Build a WorkbookMaintain a dynamic precedence relation among N problems under edge inserts and deletes, and answer whether the subgraph induced by problems x through y is acyclic.Hard9GraphDynamic programming+2No attempts yet2s512 MBJudgeable
Overflowing UncertaintyFor each interval [i,j] compute the probability that the gcd of j-i+1 independent uniform values in [1,Y] is coprime with Y, sum over all intervals, and report the numerator modulo 1e9+9 with denominator Y^N.Hard9Number theoryDynamic programming+2No attempts yet1s256 MBJudgeable
Maintaining a SequenceMaintain a sequence under insert, delete, range assign, reverse, range sum, and global maximum subarray queries.Hard9Dynamic programmingImplementation+2No attempts yet2s256 MBJudgeable
Working CellsGiven T periodic N-vertex weighted digraphs, count modulo 1e9+7 the number of D-step walks from every hub i to every hub j.Hard9MatrixDivide and conquer+2No attempts yet1s512 MBJudgeable
The Tallest and Widest CastleChoose which signposts serve as vertices of each floor so the castle has the most floors, then the largest total floor area, then the fewest signposts used, and report each signpost's floor number.Hard9GeometryDynamic programming+2No attempts yet1s512 MBJudgeable
Sequence and Queries 26Maintain a sequence under range chmin updates, range maximum queries, and range sum queries, with up to a million elements and queries.Hard9Segment treeDynamic programming+2No attempts yet4s512 MBJudgeable
Dynamic DiameterMaintain a weighted tree under edge weight updates and report the diameter after each of q updates, decoding each query with the previous answer.Hard9TreeDivide and conquer+2No attempts yet5s512 MBJudgeable
AsceticismCount permutations of 1..N such that an optimal daily reading schedule (reading consecutive sentences within each day's time slots) finishes the sutra in exactly K days.Hard9Dynamic programmingCombinatorics+2No attempts yet0.6s256 MBJudgeable
CandiesFor each j, find the maximum sum of j non-adjacent values chosen from N candies in a row.Hard9Dynamic programmingGreedy+2No attempts yet5s512 MBJudgeable
Road DevelopmentGiven N cities and Q plans, some carried out, find for each abandoned plan how many unpaved roads on shortest paths in the current graph it would have paved, or -1 if it builds a new road.Hard9GraphUnion-find+2No attempts yet2s256 MBJudgeable
Sequence and Queries 32Maintain a sequence under point updates and answer whether it can be split into contiguous blocks whose xors all lie in a small given set.Hard9Dynamic programmingPrefix sum+2No attempts yet10s512 MBJudgeable
Be Geeks!Sum gcd(a_i..a_j) * max(a_i..a_j) over all subarrays, modulo 1e9+7, with N up to 2e5.Hard9MathNumber theory+2No attempts yet2s512 MBJudgeable
Regarding How a Simple DFS Problem I Thought Was Problem A Became Problem E in This Contest (Easy)Given a perfect binary tree with N = 2^k - 1 weighted nodes numbered in heap order and an implied axis-aligned layout, find the maximum sum of weights inside any axis-parallel rectangle whose sides don't cross a node.Hard9Divide and conquerDynamic programming+2No attempts yet2s512 MBJudgeable
Tree DepthFor each node i, sum its depth over all permutations of 1..N with exactly K inversions, using the Cartesian-tree BST built by recursively taking the minimum. Output each sum mod a large prime.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Chessboard MovementCount paths from row 1 to row N on an N x M chessboard where odd rows restrict moves to same-colored adjacent cells and even rows allow any adjacent move, modulo 1e9+7.Hard9Dynamic programmingMatrix+2No attempts yet2s512 MBJudgeable
Patrol RouteFind the minimum closed walk covering every edge of a connected weighted undirected multigraph at least once, with at most 15 vertices.Hard9GraphDynamic programming+2No attempts yet2s512 MBJudgeable
TenkeyFind the minimum number of keypad operations (cursor moves plus key presses) to type a positive integer congruent to R modulo M, starting from the 0 key.Hard9GraphBFS+2No attempts yet2s512 MBJudgeable
KnowledgeCount strings of length x reachable from s by inserting or deleting the blocks aa, bbb, and ababab, modulo 998244353.Hard9StringCombinatorics+2No attempts yet1s512 MBJudgeable
Seven NeversFor every window of k consecutive elements in a permutation, compute the LIS length after deleting that window.Hard9Dynamic programmingSegment tree+2No attempts yet2s512 MBJudgeable
One RootCount pairs (p, q) with |p|, |q| <= m for which x^n + px + q has exactly one real root.Hard9MathNumber theory+2No attempts yet2s512 MBJudgeable
Counting Edit DistancesCount the number of distinct strings over 'A' to 'Z' whose Levenshtein distance from a given string s is exactly d, modulo 998244353.Hard9Dynamic programmingString+2No attempts yet10s512 MBJudgeable
KaleidoscopeCount colorings of the 60 faces of a rhombic hexecontahedron with n colors, each color i used at least c_i times, where colorings are identified under the rotational symmetry group, modulo p.Hard9CombinatoricsMath+2No attempts yet2s512 MBJudgeable
Expected CostPick a labeled tree on n vertices uniformly at random and find the expected value of the minimum sum of distances from any vertex to all others, modulo a prime.Hard9CombinatoricsTree+2No attempts yet3s512 MBJudgeable
Count the GraphsCount labeled connected undirected graphs on N nodes with exactly K bridges, modulo a possibly composite M, for up to 100 test cases.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Greatest Chicken DishCount, for each query range [L, R] and value D, the number of contiguous subarrays inside [L, R] whose GCD equals D.Hard9Dynamic programmingNumber theory+2No attempts yet15s512 MBJudgeable
The HalfwittersFor each start permutation, compute the minimum expected time to reach the identity order using adjacent swaps (cost a), a full reversal (cost b), or a random reshuffle (cost c).Hard9Dynamic programmingGraph+2No attempts yet5s512 MBJudgeable
Help Yourself (Platinum)Sum the K-th power of the number of connected components of the union over all 2^N subsets of N intervals, modulo 1e9+7.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Sprinklers 2: Return of the AlfalfaCount the ways to place sweet corn and alfalfa sprinklers on an N by N grid, with some blocked squares, so that every square is covered by exactly one sprinkler type.Hard9Dynamic programmingPrefix sum+2No attempts yet2s512 MBJudgeable
ExerciseGiven N and prime M, compute modulo M the product over all N! permutations of the order (number of iterations until identity) of each permutation.Hard9CombinatoricsNumber theory+2No attempts yet2s512 MBJudgeable
Cow ExerciseGiven N and prime M, sum every positive integer K for which some permutation of length N has order K, then output the sum modulo M.Hard9MathNumber theory+2No attempts yet1s512 MBJudgeable
Deja VuMaintain an array under point updates and answer queries asking for the earliest position d that ends an increasing subsequence of length 4 starting at or after l.Hard9Segment treeDynamic programming+2No attempts yet5s512 MBJudgeable
Yet Another Problem on EmpodiaCount, for each length i up to N, the number of equivalence classes of permutations of length i under the relation that agrees on which intervals are framed (max minus min equals length minus one), modulo a prime.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
Tree Average WeightGiven a degree sequence with some free entries, pick a labeled tree uniformly at random and find the integer part of its expected weight, where weight sums u*sz(u)+v*sz(v) over edges.Hard9CombinatoricsTree+2No attempts yet1s256 MBJudgeable
Counting Different SummandsSum f(a) over all ordered partitions of n into m positive parts, where f counts distinct part values, modulo 998244353, with n up to 1e18 and m up to 500.Hard9CombinatoricsMath+2No attempts yet2s256 MBJudgeable
Chiaki Sequence RevisitedSum the first n terms of the self-referential Chiaki sequence, where each term depends on earlier terms via a_{n-a_{n-1}} + a_{n-1-a_{n-2}}, modulo 1e9+7.Hard9MathCombinatorics+2No attempts yet1s256 MBJudgeable
Good GameCount monotone lattice paths in n dimensions from the origin to a target, avoiding m forbidden points, modulo 1e9+7.Hard9CombinatoricsDynamic programming+2No attempts yet2s512 MBJudgeable
DoublindromesCount distinct substrings of s that are palindromes and split into two non-empty palindromes, with length at least k.Hard9StringString matching+2No attempts yet3s512 MBJudgeable
TaxiSum over all ways to place M taxis and M customers on a weighted tree of the maximum-weight perfect matching cost, modulo 1e9+7.Hard9TreeDynamic programming+2No attempts yet1.5s256 MBJudgeable
Nice NumbersCount numbers in [L, R] that are pandigital (a permutation of all digits) in some base d, modulo 998244353, with L and R up to 5000-digit integers.Hard9CombinatoricsNumber theory+2No attempts yet1s512 MBJudgeable
Master Zhu and the LeaperCount monotone leaper paths from (1,1) to (n,m) on a huge board with at most 100 blocked cells, modulo 110119.Hard9Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
Power of XORGiven n integers, compute the sum over all 2^n subsets of the k-th power of the popcount of the XOR of the subset, modulo 1e9+7.Hard9Bit manipulationMath+2No attempts yet6s512 MBJudgeable
JokeGiven a text and up to ten patterns with per-letter erasure costs, delete letters so that no pattern occurs, minimizing total cost.Hard9String matchingDynamic programming+2No attempts yet1s512 MBJudgeable
EarthquakeEach route is usable only if all its bridges survive; pick an adaptive inspection order of bridges to minimize the expected number of inspections before deciding whether any route connects the two lands.Hard9ProbabilityDynamic programming+2No attempts yet1s512 MBJudgeable
Flip a CoinTwo players each pick a heads/tails string of length up to 20; a fair coin is flipped until one or both strings appear, and we must output the probabilities of Alice winning, Bob winning, and a tie.Hard9ProbabilityDynamic programming+2No attempts yet1s256 MBJudgeable
Ascent Sequences Avoiding Pattern 201Count ascent sequences of length n that avoid the pattern 201, modulo a prime p, with n up to 500.Hard9Dynamic programmingCombinatorics+2No attempts yet2s512 MBJudgeable
Maximum FlowGiven two paths of n vertices each plus 2n+1 cross edges with huge capacities, find the max flow from (0,0) to (1,n).Hard9GraphShortest path+2No attempts yet2s512 MBJudgeable
Less Time, More ProfitChoose a subset of plants to build; a shop pays off only when every plant it needs is built. Minimize the maximum build time, then maximize profit within that time.Hard9Dynamic programmingGraph+2No attempts yet1s256 MBJudgeable
Pet TreeCount assignments of edge lengths (each within its own interval) to a tree's edges so the resulting tree diameter falls between S and E, modulo 1e9+7.Hard9Dynamic programmingTree+2No attempts yet8s1024 MBJudgeable
Human ErrorGiven a grid of Justin and Donald pieces where each turn a player must capture an adjacent piece, and each player may restrict their candidate moves to a set of fixed size, compute Justin's win probability under optimal play with random move choice.Hard9Game theoryBit manipulation+2No attempts yet1s512 MBJudgeable
Wrong AnswerConstruct a cost matrix that makes a greedy two-character solution as far from optimal as possible, maximizing the ratio of its output to the true minimum.Hard9GreedyDynamic programming+2No attempts yet1s512 MBJudgeable
AtomsMaintain a sequence of charges under range add updates, and after restricting to a query segment, report the longest run of consecutive positions where each next charge exceeds the previous by exactly one.Hard9Segment treeDynamic programming+2No attempts yet2s512 MBJudgeable
Fibonacci Digit CountCount occurrences of the substring "11" within the first N characters of the infinite string formed by writing 1, 2, 3, ... in Fibonacci (Zeckendorf) representation.Hard9MathDynamic programming+2No attempts yet2s1024 MBJudgeable
LogoGiven up to five polyomino patch shapes (each a subset of a 3x3 grid, flippable and rotatable) and up to three grid designs up to 55x5, decide if each design can be tiled exactly by non-overlapping patches and find the minimum patch count, or report NIE.Hard10Dynamic programmingBit manipulation+2No attempts yet1s128 MBJudgeable
HyperrectangleCompute d!V for the volume of a box with side lengths li where sum xi <= s via characteristic polynomials and Lenstra inclusion of capped orthants.Hard10MathDivide and conquer+2No attempts yet2s512 MBJudgeable