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 results166 problems
| Title | Level | Topics | Solved | Time limit | Memory limit | Judge |
|---|---|---|---|---|---|---|
| TteokgukPlace additional guards, subject to company office limits, so that the number of cooperation edges with exactly one guarded endpoint is minimized. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Kruskal's BallGiven a graph with unique edge weights, build a Kruskal reconstruction tree to answer queries about the minimum temperature needed to connect two vertices and the size of the reachable component at that temperature. | Hard8 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Second Smallest Spanning TreeFind the minimum spanning tree, then compute the smallest spanning tree whose weight is strictly greater than the MST weight, or report -1 if none exists. | Hard8 | Minimum spanning treeTree+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Clone RobotGiven a maze with a start and up to 250 keys, minimize the total moves of self-cloning robots (splitting only at start/key cells) needed to collect every key. | Hard8 | Shortest pathMinimum spanning tree+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Earthquake RecoveryGiven a graph with edge costs and times, choose a spanning tree maximizing (F minus total cost) divided by total time, requiring fractional binary search combined with MST computation. | Hard8 | Minimum spanning treeBinary search+2 | No attempts yet | 2s | 128 MB | Judgeable |
| CostGiven a weighted graph, compute the sum over all vertex pairs of the total weight removed when repeatedly deleting the smallest edge until the pair is disconnected, modulo 1e9. | Hard8 | Union-findMinimum spanning tree+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Planet TunnelsGiven N 3D points with edge cost equal to the minimum coordinate-axis distance between two points, find the minimum spanning tree cost connecting all of them efficiently. | Hard8 | Minimum spanning treeSorting+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Domestic NetworksChoose a spanning tree of apartments and assign each edge to one of two cable types with limited total lengths to minimize cost, or report impossibility. | Hard8 | Minimum spanning treeDynamic programming+1 | No attempts yet | 2s | 64 MB | Judgeable |
| Ticket to RideGiven a weighted graph and four pairs of terminal cities, find the minimum total edge cost of a subgraph connecting all four pairs simultaneously. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| "Shortest" Pair of PathsFind two vertex-disjoint (except endpoints) and edge-disjoint directed paths from node 0 to node N-1 minimizing total cost, or report impossibility. | Hard8 | GraphShortest path+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Reliable NetsFor each graph, find the minimum cost of a spanning subgraph that stays connected after removing any single edge, or report that none exists. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Power GridCount the minimum-size edge sets connecting all living quarters to the power station on an 8x8 grid, modulo 1e9. | Hard8 | Dynamic programmingGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Panic RoomGiven a house of rooms with directed doors, intruder positions, and a panic room, find the minimum number of doors to lock so no intruder reaches it, or report impossible. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| National TreasuresGiven a grid of artifacts with bitmask critical points and cells already holding guards, replace some artifacts with hired guards so every remaining artifact has a guard on each of its critical points, minimizing hires. | Hard8 | GreedyMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| No Smoking, PleaseGiven a grid whose adjacent rooms are joined by passages of known area, split rooms into two connected zones separating entrance from kitchen, paying 1000 per unit passage area plus 1000 per cut passage. | Hard8 | GraphMinimum spanning tree+1 | No attempts yet | 3s | 512 MB | Judgeable |
| SpiesChoose meetings so spies exchange information, plus a set of spies to send, so the sent spies know everything the unsent spies obtained; minimize total cost. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 5s | 128 MB | Judgeable |
| Surround the Islands with FenceGiven N edges that form disjoint polygon islands and a symmetric vertex-to-vertex boat cost matrix, find the minimum total cost of round trips needed to fence every island, starting anywhere. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Simon the SpiderPick a connected spanning subgraph minimizing total edge weight minus twice the heaviest chosen edge, or report that the graph is disconnected. | Hard8 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| TollA billionaire sets tolls on K new roads of his choosing so that the minimum spanning tree routing all traffic to town 1 maximizes his revenue, where K is at most 20. | Hard8 | Minimum spanning treeGreedy+2 | No attempts yet | 3s | 128 MB | Judgeable |
| Goat RopesAssign nonnegative radii to n points so that every pair satisfies r_i + r_j <= distance, and maximize the sum of all radii. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 8s | 128 MB | Judgeable |
| Grand TourChoose a spanning subgraph from state roads (gaining their sale price) and private roads (paying their buy price) so that all cities stay connected, minimizing the net treasury cost. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 1024 MB | Judgeable |
| Picnic PlanningFind a minimum-cost set of car routes so every brother reaches Park, with at most s cars parked there. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Evacuation PlanGiven buildings with worker counts, shelters with capacities, and a valid assignment plan, decide whether the plan minimizes total Manhattan-plus-one travel time over all valid plans. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Destroying the GraphFind the minimum cost to cover every arc of a directed graph by choosing, for each vertex, to delete its incoming or outgoing arcs. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Spanning TreeCount the minimum spanning trees of a connected weighted multigraph modulo 1000003, where any weight class has at most 4 edges. | Hard8 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Travel AgencyChoose customers for a trip; each unpaid social requirement between a chosen customer and an unchosen one costs a penalty. Maximize profit. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Indisputable RightGiven antennas on a ridge of triangular mountains, find the fewest extra antennas on the ridge that connect all of them by line of sight. | Hard8 | GeometryGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Absurdistan RoadsGiven all-pairs shortest distances, find the minimum total length of a connected N-edge road network that reproduces the table. | Hard8 | Minimum spanning treeGraph+1 | No attempts yet | 5s | 128 MB | Judgeable |
| Particle SwappingFor each queried start pair, swap two tokens along graph edges one move at a time so their closest approach stays as large as possible. | Hard8 | Minimum spanning treeGraph+2 | No attempts yet | 5s | 256 MB | Judgeable |
| Floating IslandsFind the cheapest connected bridge network where each bridge costs the position difference and each island has a degree limit, or report -1 when impossible. | Hard8 | Dynamic programmingMinimum spanning tree+1 | No attempts yet | 8s | 512 MB | Judgeable |
| Pangaea 2Starting from a given tree, each added road updates the minimum total length that keeps all cities connected, and each test case outputs the XOR of the answers. | Hard8 | Minimum spanning treeTree | No attempts yet | 20s | 256 MB | Judgeable |
| Tying All the CardsTie all N cards into one connected set where each tie costs the larger number modulo the smaller, with minimum total cost. | Hard8 | Minimum spanning treeNumber theory+1 | No attempts yet | 5s | 768 MB | Judgeable |
| Bridge Builders (Small)Connect all island cells on a grid with bridges, minimizing total cost, where each bridge's cost grows with the distance from the nearest forest already linked to the base camp. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 5s | 512 MB | Judgeable |
| Bridge Builders (Large)Connect all island cells with bridges from a forest, where each bridge costs the walking distance from the nearest forest, and minimize total man-hours. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 5s | 512 MB | Judgeable |
| Heroes Never DieChoose a subset of heroes to revive, gaining bond rewards when both endpoints are chosen, to maximize total reward minus revival cost. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Modern Announce NetworkThree grade groups each broadcast internally for free; pick a start student so the friend-link forest spanning all three groups uses the fewest edges. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 5s | 512 MB | Judgeable |
| Weeping FigSplit the vertices of a connected weighted undirected graph into two nonempty parts so that the total weight of edges crossing the cut is minimized. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 3s | 512 MB | Judgeable |
| Beautiful GraphOver all complete graphs on N vertices whose edges cost 1 or 2, sum the number of minimum spanning trees that are paths (every degree at most 2). | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Cutting edges one at a timeDelete edges of a weighted undirected graph one by one so that the total weight removed before s and t get disconnected is as large as possible. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| The Unscrupulous KingdomWith n points in the plane and m existing edges, add the fewest edges (segments that avoid other points) so the graph is connected while maximizing the sum of squared lengths. | Hard8 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Blazing New TrailsChoose a spanning tree of a graph whose edges each join a marked or unmarked vertex, with exactly w marked-unmarked edges, minimizing total cost. | Hard8 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Heaven's KitchenChoose match order and winners so a knockout tournament maximizes summed floor((Ci+Cj)/|Pi-Pj|), then output the unique bracket fixed by the stated tie-breaking rules. | Hard8 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Monday BluesGiven an N by M grid with costly buildable cells and blocked or unbuildable cells, find the minimum total cost to cut every path from (1,1) to (N,M), or report that no placement can do it. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Minimum Cost FlowGiven a spanning tree and extra edges, with a one-pipe discount available, find the minimum number of edge swaps to reach a minimum-cost spanning tree. | Hard8 | Minimum spanning treeGraph+2 | No attempts yet | 3s | 512 MB | Judgeable |
| Imperial roadsFor each road, report the cost of a minimum spanning tree forced to include that road. Queries are offline and non-repeating. | Hard8 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 1024 MB | Judgeable |
| Open-Pit MiningGiven blocks with values and digging costs plus precedence constraints, find the maximum profit subset closed under the dig-before relation. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 512 MB | Judgeable |
| New Country DivisionSplit the graph's vertices into two sides with vertex 1 and vertex n on opposite sides so the XOR of cut-edge weights is maximized. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Graph and Minimum Spanning TreeFor each edge of a connected weighted undirected graph, print the weight of a minimum spanning tree that is forced to include that edge. | Hard8 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Maximum Strategic SavingsGiven N planets each with M cities and edge sets shared across copies, find the maximum energy saved by keeping a spanning connected subgraph of the whole galaxy. | Hard8 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Cruise QuailFind the cheapest edge subset hitting every pair of edge-disjoint simple paths, equivalently place cameras inside each 2-edge-connected block. | Hard8 | GraphUnion-find+2 | No attempts yet | 3s | 512 MB | Judgeable |
| Joining CapitalsConnect all capitals with degree exactly one through Steiner points (non-capitals) at minimum Euclidean total cost. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| XOR MSTGiven N labeled vertices where the edge between any two has weight equal to the XOR of their labels, find the total cost of the minimum spanning tree. | Hard8 | TrieMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Maximum ProfitChoose relay stations to build so that revenue from served customer groups minus construction cost is maximized, where a group pays only if both of its stations are built. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Building Bridges 2On a small grid, connect all islands with straight length-2+ bridges over sea so the total bridge length is minimized, or print -1. | Hard8 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 512 MB | Judgeable |
| ResistancePlayers leave and return over time; after each change report the maximum value of a split into two teams, where friendship edges crossing the split are lost. | Hard8 | GraphMinimum spanning tree+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 |
| Asteroid RangersGiven n moving points, count how many times the minimum spanning tree over all future times changes, plus the initial build. | Hard9 | Minimum spanning treeGeometry+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Old Factory PlumbingChoose a water height so the flooded region avoids open holes unless plugged or piped, minimizing pipe distances plus 0.5 per plug. | Hard9 | GraphMinimum spanning tree+2 | No attempts yet | 5s | 128 MB | Judgeable |
| Simplifying the FarmGiven a weighted graph where each edge length occurs at most three times, find the minimum spanning tree weight and count distinct minimum spanning trees modulo 1e9+7. | Hard9 | Minimum spanning treeUnion-find+2 | No attempts yet | 1s | 128 MB | Judgeable |
| Pork barrelFor each query interval [l, h], build the cheapest forest using only roads with costs inside the interval that connects as many city pairs as possible. | Hard9 | Minimum spanning treeDivide and conquer+2 | No attempts yet | 30s | 256 MB | Judgeable |
| Highways and CountiesFind the smallest road length limit so cities joined by shorter roads form a group whose populations hold a subset summing to a multiple of K. | Hard9 | Minimum spanning treeDynamic programming+2 | No attempts yet | 2s | 64 MB | Judgeable |
| Fencing off the darknessGiven a grid of bulb strengths and a ceiling height, compute each square's light level, mark the dark ones, then find the cheapest set of interior squares that contains all dark squares and minimizes the perimeter cost. | Hard9 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| BoosterFor each query, decide whether the character can travel from checkpoint A to checkpoint B with maximum HP X, given walking drains HP and the booster moves only along axes. | Hard9 | GraphUnion-find+2 | No attempts yet | 8s | 512 MB | Judgeable |
| Construction ProjectPlace at most H airports among N towns and connect all towns with axis-parallel roads that avoid M rectangular obstacles, minimizing airport cost times count plus total road length. | Hard9 | Minimum spanning treeGeometry+2 | No attempts yet | 5s | 256 MB | Judgeable |
| Six WordsGiven a connected graph whose vertex i has potential i and edge i has weight i, find the total weight of a minimum spanning tree of the line graph of the line graph. | Hard9 | GraphMinimum spanning tree+2 | No attempts yet | 2s | 512 MB | Judgeable |
| 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. | Hard9 | GraphMinimum spanning tree+2 | No attempts yet | 1s | 512 MB | Judgeable |