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 results837 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
Geohash GridFor a rectilinear polygon inside a 2^n by 2^n grid, answer up to 1e5 queries asking the smallest cell count of a union of at most t geohash intervals covering it.Hard9Divide and conquerTree+2No attempts yet5s512 MBJudgeable
Mole TunnelsOn a binary-heap-shaped tree, each newly woken mole (in a fixed order) must be assigned to a hole with remaining food capacity, minimizing total walking distance; report the minimum for every prefix k.Hard9TreeGreedy+2No attempts yet2s512 MBJudgeable
Cactus giftIn a cactus graph with up to 4000 vertices, count directed simple paths of each length 1 to N, modulo 1e9+7.Hard9Dynamic programmingTree+2No attempts yet1.5s512 MBJudgeable
Bracket PathsGiven a tree with '(' or ')' on each node, count ordered pairs (a,b) whose path string w_{a,b} is a properly matched bracket expression.Hard9TreeDivide and conquer+2No attempts yet3s1024 MBJudgeable
Good triples of pathsCount triples of simple paths in a tree that are either node-disjoint or pairwise intersecting, modulo 1e9+7.Hard9CombinatoricsTree+2No attempts yet2s512 MBJudgeable
Fractal TreeFor a recursively defined fractal tree F_k, answer queries giving the distance between two DFS-labeled vertices.Hard9TreeRecursion+2No attempts yet7s512 MBJudgeable
Laminar FamilyGiven an undirected tree and f vertex sets, each a simple path, decide whether the family of paths is laminar.Hard9TreeDFS+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
Growing TreesGiven a tree whose edge weights change linearly with the day, find the day in [0, D] that minimizes the diameter, and report that diameter.Hard9TreeGreedy+2No attempts yet5s768 MBJudgeable
Octoppang CountryGiven a connected unweighted graph with K infected vertices and threshold T, compute for every vertex the number of uninfected vertices left when it is deleted and each component with at least T infected vertices spreads infection fully.Hard9TreeDFS+2No attempts yet1s1024 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
Prime Tree - 2This output-only task asks for labels 1 to n on a tree's vertices so that as few edges as possible join two labels sharing a common divisor greater than 1.Hard9Number theoryTree+2No attempts yet10s512 MBJudgeable
Prime Tree - 4Relabel every vertex of each tree with 1 to n so the edges whose two labels share a divisor exceed 1 are as few as possible.Hard9GreedyNumber theory+2No attempts yet10s512 MBJudgeable
Prime Tree - 7Relabel the vertices of each given tree with 1..n so that the number of edges whose endpoints share a common divisor above 1 is minimized, and submit the answer file.Hard9GreedyNumber theory+2No attempts yet10s512 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
XOR SequencesCount, modulo 1e9+7, the ordered sequences of n distinct m-bit integers consistent with a given nearest-XOR-label map over all 2^m query values.Hard9Bit manipulationDivide and conquer+2No attempts yet2s512 MBJudgeable
Moorio KartCount and sum the lengths of simple cycles (at least Y) formed by joining every tree in a forest with one X-length edge between consecutive trees and a chosen path inside each tree.Hard9TreeDynamic programming+2No attempts yet3s512 MBJudgeable
Beautiful ManyeongroCount directed paths in a rooted tree whose edge-label string equals a given pattern P.Hard9TrieDFS+2No attempts yet2s512 MBJudgeable
Fruit TreeGiven a tree whose vertices hold fruit types, answer queries asking whether one type is a strict majority on the path between two vertices, and which type it is.Hard9TreeBinary search+2No attempts yet3s1024 MBJudgeable
Wind of ChangeTwo weighted trees on the same vertex labels define a distance as the sum of both tree distances; for every vertex find the nearest other vertex under that combined metric.Hard9TreeDivide and conquer+2No attempts yet10s1024 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
MeetingsGiven only an oracle that returns the meeting point (tree median) of any three vertices, reconstruct the tree of N vertices with maximum degree 18.Hard9TreeDivide and conquer+2No attempts yet2s256 MBJudgeable
CityAssign small integer codes to nodes of a tree where depth from node 0 is at most 18, so that a decoder with only the two codes can tell which of two cities lies on the path from 0 to the other.Hard9TreeBit manipulation+2No attempts yet2s512 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
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
Rooted SubtreesFor each query with two roots r and p, count the distinct non-empty sets that are the intersection of a subtree of the tree rooted at r and a subtree of the tree rooted at p.Hard9TreeDFS+2No attempts yet11s512 MBJudgeable
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
Karaoke MeetupIn a weighted tree, some vertices are marked as houses. For each vertex compute the ratio of the nearest marked vertex distance to the farthest, and output the maximum ratio as a reduced fraction.Hard9TreeDFS+2No attempts yet8s512 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
Phone CallA tree of houses has m phone lines, each letting any two vertices in the union of two tree paths call at cost w. Find the maximum number of reachable houses from house 1 and the minimum cost.Hard9GraphMinimum spanning tree+2No attempts yet1s512 MBJudgeable
RMQ Similar SequenceGiven sequence A, count the expected sum of a random real sequence B in [0,1] that has identical RMQ answers to A for every subarray, modulo 1e9+7.Hard9TreeCombinatorics+2No attempts yet2s256 MBJudgeable
Rikka with Tree GameOn a rooted tree where players alternately move a token to a child and the score is the final depth, repeatedly attach leaves and find the limit of f(k)/k, where f(k) is the fewest additions making the optimal score exactly k.Hard9Game theoryTree+2No attempts yet2s512 MBJudgeable
TaxiSum over all ways to place M taxis and M customers on a weighted tree of the maximum-weight perfect matching cost, modulo 1e9+7.Hard9TreeDynamic programming+2No attempts yet1.5s256 MBJudgeable
Master Zhu and RikkaGiven a rooted tree with values on vertices, answer queries that ask for the GCD of sums of values occurring exactly a times and exactly b times in a subtree or on a path.Hard9TreeDFS+2No attempts yet3s512 MBJudgeable
Pet TreeCount assignments of edge lengths (each within its own interval) to a tree's edges so the resulting tree diameter falls between S and E, modulo 1e9+7.Hard9Dynamic programmingTree+2No attempts yet8s1024 MBJudgeable
IslandGiven the edge list of a tree whose N leaves are towns and whose internal nodes all have degree at least 3, count the distinct circular orderings of the leaves realizable as the outer face, and print the count as a product of prime powers.Hard9TreeDFS+2No attempts yet1s512 MBJudgeable
Tree and Queries 20Maintain a dynamic forest with link/cut and weighted edges, supporting toggling a vertex weight and querying the minimum weighted sum of tree distances from any vertex, with encrypted vertex indices.Hard10TreeSegment tree+1No attempts yet5s512 MBJudgeable