Curated sets
Graphs and traversal
BFS, DFS, shortest paths, and trees.
Total results3,710 problems
| Topics | Judge | |||||
|---|---|---|---|---|---|---|
| The Enemy of My EnemyDecide whether the N people can be split into two camps so that every given hostile pair lands on opposite sides, which is exactly bipartiteness. | Medium4 | GraphBFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Scrooge MinhoGiven a tree, place one fire station at the vertex minimizing the maximum distance to any other vertex, and output that distance. | Medium4 | TreeGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Teleport 3Find the shortest travel time on a grid where you can walk one unit per second or take any of three two-way teleports costing 10 seconds each. | Medium4 | GraphShortest path+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Tree and paths of length twoDecide whether some tree on N nodes has exactly S simple paths of length 2. | Medium4 | TreeCombinatorics+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Rational SequenceGiven p/q, find its index in the breadth-first ordering of the Calkin-Wilf tree, where each node p/q has children p/(p+q) and (p+q)/q. | Medium4 | MathNumber theory+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Correcting CheeseburgersGiven a permutation of 1 to n, find the minimum number of four-part shuffles (c,a,d,b) needed to sort it into 1,2,...,n. | Medium4 | BFSBrute force+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Nailro Rail Pass TripCompare the cheapest itinerary cost with and without a rail pass that discounts some fares, and decide if the pass is worth it. | Medium4 | Shortest pathGraph | No attempts yet | 1s | 512 MB | Judgeable |
| TreeGiven up to 10 graphs, decide for each whether it is a tree, allowing self-loops and duplicate edges. | Medium4 | GraphUnion-find+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Far Far AwayGiven a directed tree rooted at city 1 with weighted edges, find the maximum root-to-node path weight, or -1 if it stays below M. | Medium4 | TreeDFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Oil TrailsGiven an undirected multigraph of oil trails, decide whether all edges can be covered by a walk that never returns to a house without visiting another one first. | Medium4 | GraphImplementation | No attempts yet | 2s | 512 MB | Judgeable |
| Secret MeetingGiven a weighted undirected graph and K friends' rooms, pick the room minimizing the sum of shortest-path distances from all friends; break ties by smallest room. | Medium4 | Shortest pathGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| HamletGiven a DAG of plot states where each action gives a probability distribution over higher-numbered states, find the best expected value from state 1 and round it to two decimals. | Medium4 | Dynamic programmingProbability+2 | No attempts yet | 3s | 512 MB | Judgeable |
| A Series of TubesGiven a connected undirected graph, decide whether its edges can be oriented so that the result stays strongly connected. | Medium4 | GraphDFS | No attempts yet | 1s | 512 MB | Judgeable |
| DragsterGiven pairwise win probabilities and a binary elimination bracket, compute the probability that driver 1 wins the tournament. | Medium4 | ProbabilityTree+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Perfect CrimeFind the fewest moves to go from building S to D, where each move jumps F forward or B backward, avoiding police buildings. | Medium4 | BFSGraph | No attempts yet | 1s | 512 MB | Judgeable |
| Obfuscated TreesDecode a tree from its obfuscated token stream, where each internal node carries an ordering code and subtree count, then print its values in pre-order. | Medium4 | TreeRecursion+1 | No attempts yet | 2s | 512 MB | Judgeable |
| CoordinatesGiven differences in x and y between pairs of bases, reconstruct each base's coordinate, fixing base 1 at (0,0). | Medium4 | GraphBFS+2 | No attempts yet | 3s | 512 MB | Judgeable |
| Balls and NeedlesGiven K segments in 3D defined by endpoint triples, decide whether they form a closed cycle in space and whether their projections onto the xy-plane form a closed cycle. | Medium4 | GraphUnion-find+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Wheat HarvestFind each connected block of 1s, order blocks by area, and label every cell with its block's rank. | Medium4 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| MoocastEach cow has a point and a broadcast radius; find the starting cow whose one-way reachable set is largest. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Road work and the distance to the capitalAfter each of q edge insertions and deletions, output the shortest-path distance from every city to city 1, or -1 if unreachable. | Medium4 | BFSGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| The nearest convenience storeGiven an undirected weighted graph with some vertices marked as homes and others as stores, pick the home whose shortest-path distance to the nearest store is smallest, breaking ties by vertex number. | Medium4 | GraphShortest path+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Build a treeConstruct a tree on n nodes with exactly m leaves whose sorted edge list is lexicographically smallest, and print its n-1 edges. | Medium4 | TreeGreedy+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Jump JumpGiven jump distances on a row of n stones, count how many stones are reachable from a starting stone via left or right jumps that stay on the bridge. | Medium4 | GraphBFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Company culture 1Given each employee's manager and a list of praises, propagate every praise value down the whole subtree and print the total each employee receives. | Medium4 | TreeDFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Evaluation Order of Assignments (Small)Given assignment statements where each expression is a function call, decide whether some order evaluates every variable, which fails exactly when a dependency cycle exists. | Medium4 | GraphTopological sort+2 | No attempts yet | 5s | 1024 MB | Judgeable |
| EvaluationGiven assignment statements where each value depends on argument variables, decide whether some evaluation order resolves every dependency. | Medium4 | GraphTopological sort+1 | No attempts yet | 5s | 512 MB | Judgeable |
| Rebel Against The Empire (Small)Given stationary points in 3D, find the smallest jump radius that lets you reach asteroid 1 from asteroid 0, ignoring the time limit. | Medium4 | GraphUnion-find+2 | No attempts yet | 5s | 512 MB | Judgeable |
| When Geudae Becomes GeumeoGiven N characters and M replacement pairs, find the minimum number of substitutions needed to convert character a into character b. | Medium4 | GraphBFS+1 | No attempts yet | 2s | 512 MB | Judgeable |
| The fastest road to BanikoaraGiven towns joined by undirected weighted roads, find the shortest travel distance between a named departure town and destination town. | Medium4 | GraphShortest path+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Prerequisite CoursesGiven prerequisite pairs between courses, find the earliest semester each course can be completed when unlimited courses may be taken per semester. | Medium4 | GraphTopological sort+2 | No attempts yet | 5s | 256 MB | Judgeable |
| Club Room Project (Large)For each action, remove all walls between rooms x and y; print how many connected room blocks remain. | Medium4 | Union-findArray | No attempts yet | 1s | 512 MB | Judgeable |
| Chonggang ChonggangRun a single-source shortest path from Jinseo's house, find the nearest type A and type B house, and report the closer type (A wins ties). | Medium4 | Shortest pathGraph+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Secret Chamber at Mount RushmoreGiven directed letter translations, decide for each pair of words whether every letter of the first can reach the matching letter of the second. | Medium4 | GraphDFS+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Cut Vertices and BridgesGiven a tree with N vertices and queries, report for each query whether a specified vertex is a cut vertex or a specified edge is a bridge. | Medium4 | TreeDFS+2 | No attempts yet | 1s | 512 MB | Judgeable |
| Is Yeongwoo a cheater?Given building dependencies and a log of build and destroy events, decide whether every event is legal without the cheat key. | Medium4 | SimulationGraph+1 | No attempts yet | 1s | 512 MB | Judgeable |
| Sogang GroundGiven a weighted undirected graph, find a region whose total item count within distance m is largest. | Medium4 | GraphShortest path+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Dark Ride with MonstersGiven a permutation of misplaced monsters, find the minimum number of swaps needed to sort all monsters into their correct chambers. | Medium4 | ArrayGraph+2 | No attempts yet | 5s | 512 MB | Judgeable |
| Sheba's AmoebasCount the number of disjoint closed loops formed by black pixels on a grid, where each black pixel has exactly two black neighbors among its eight surrounding cells. | Medium4 | GraphDFS | No attempts yet | 2s | 512 MB | Judgeable |
| Police StationIn a directed graph, list every vertex from which all other vertices are reachable by following arrows forward. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 1024 MB | Judgeable |
| Wet Rock Peg PlanSimulate a sequence of peg placements and removals on a dependency DAG, tracking peak peg count and the first wet-rule violation. | Medium4 | SimulationGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Treasure HuntFollow a grid of arrows from the top-left cell and report the number of steps to the treasure, Out if you leave the grid, or Lost if you loop forever. | Medium4 | SimulationGraph+2 | No attempts yet | 2s | 512 MB | Judgeable |
| League of Overwatch at Moloco (Hard)Given n employees and m conflict pairs, decide whether the employees can be split into two non-empty groups so that no pair shares a group. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Trees and QueriesGiven an unrooted tree and a root R, answer queries asking for the size of the subtree rooted at each queried vertex. | Medium4 | TreeDFS+2 | No attempts yet | 1s | 128 MB | Judgeable |
| N-Step SyllogismEach premise says all a are b; for each conclusion x is y, decide whether following the implication chain from x reaches y. | Medium4 | GraphDFS+2 | No attempts yet | 2s | 128 MB | Judgeable |
| HoofballSort cows by position, then find the minimum number of starting balls so every cow receives the ball at least once under the nearest-cow passing rule. | Medium4 | SortingGraph+1 | No attempts yet | 2s | 512 MB | Judgeable |
| CocktailGiven a tree of N ingredients linked by N-1 known mass ratios, compute the smallest positive integer masses that satisfy every ratio. | Medium5 | TreeDFS+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Digit SwapGiven N and exactly K digit swaps that must never leave a leading zero, find the maximum resulting number or report -1 if impossible. | Medium5 | BFSBrute force+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Connecting a Road GraphGiven an adjacency matrix, find the minimum number of edge-swap operations needed to make the graph fully connected, or report -1 if impossible. | Medium5 | GraphUnion-find+1 | No attempts yet | 2s | 128 MB | Judgeable |
| PrefixGiven up to 50 words, find the largest subset where no word is a prefix of another, using a trie and tree DP. | Medium5 | TrieDynamic programming+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Tree DiameterGiven a weighted tree with up to 100,000 vertices, compute the diameter as the maximum distance between any two vertices. | Medium5 | TreeDFS+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Survivable Diagnostic RulesGiven up to 200,000 two-literal rules over 20,000 boolean symptoms, decide via 2-SAT whether an assignment exists that avoids triggering any rule. | Medium5 | GraphDFS+1 | No attempts yet | 5s | 128 MB | Judgeable |
| PartyGiven a directed weighted graph, compute for each village the round-trip shortest time to a fixed village X and return the maximum over all villages. | Medium5 | Shortest pathGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Farm ManagementCount 8-directionally connected groups of equal-height cells in a grid where every outside neighbor is strictly lower. | Medium5 | BFSDFS+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Wall-Breaking MazeFind the minimum number of walls to break on a grid path from the top-left to the bottom-right room, moving through 4 directions. | Medium5 | BFSShortest path+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Finding Notebook OwnersGiven student-laptop candidate pairs, compute the maximum bipartite matching to maximize the number of students who get a laptop they listed. | Medium5 | GraphDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Hopping FrogFind the minimum number of jumps for a frog moving between numbered stones, where each stone's value dictates allowed jump distances as multiples. | Medium5 | BFSGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Fixed-Length Reversal SortGiven a permutation of up to 8 numbers, find the minimum number of fixed-length K reversals needed to sort it, or report impossibility. | Medium5 | BFSGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Solving ProblemsGiven N interest values and a rule to move forward by 1 or 2 steps starting at problem 1, find the minimum number of problems solved before the range of solved values reaches at least V. | Medium5 | Dynamic programmingGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Watering FieldsGiven well-digging costs per field and pairwise pipe-connection costs, compute the minimum total cost to give every field water using an MST-style approach with a virtual water source. | Medium5 | Minimum spanning treeGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Minsik-First SearchImplement a DFS variant that picks the middle unvisited neighbor when their count is odd and the smallest when even, then print the first-visit order from vertex 1. | Medium5 | DFSImplementation+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Broken CalculatorStarting from 1 on a calculator limited to D digits, find the largest value reachable after exactly P multiplications by digits 2-9, or report -1 if impossible. | Medium5 | BacktrackingBrute force+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Sunday Morning DateFind a grid path from S to F that first minimizes the number of trash cells stepped on, then minimizes clean cells adjacent to trash along that path. | Medium5 | Shortest pathBFS+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Shortest Path Through Required VerticesGiven a weighted undirected graph, find the shortest path from vertex 1 to vertex N that must pass through two specified vertices. | Medium5 | Shortest pathGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Roads of the Northern CountryGiven the edges of a weighted tree of up to 10,000 cities, compute the length of the tree's diameter (the longest path between two nodes). | Medium5 | TreeGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| HistoryGiven directed precedence edges among up to 400 events, determine for each query pair whether one event's order relative to the other is fixed by transitivity. | Medium5 | GraphBFS+2 | No attempts yet | 1s | 128 MB | Judgeable |
| New Year PartyPick a maximum-score guest list from a company tree so no employee and their direct manager both attend, computed with and without the root. | Medium5 | Dynamic programmingTree+1 | No attempts yet | 2s | 128 MB | Judgeable |
| City Division PlanSplit a connected weighted graph into two connected subvillages by removing edges so that the total remaining maintenance cost is minimized. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 256 MB | Judgeable |
| Dog DaysGiven bunkers on a plane and a speed and survival-time limit, find the minimum number of intermediate bunkers a chicken must visit to reach a target bunker, or report it cannot escape. | Medium5 | GraphBFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| RobotFind the minimum number of move/turn commands for a grid robot to reach a target position and facing direction using BFS over states of position and direction. | Medium5 | BFSGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Distance Between VerticesGiven a weighted tree with up to 40,000 nodes, answer up to 10,000 queries about the path distance between two vertices, requiring an LCA-based approach for efficiency. | Medium5 | TreeBinary search+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Communicating with the Space GodsGiven points with some already connected, find the minimum total length of new passages needed to connect all points into one network. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Maal GatheringGiven a grid with K-Maal pieces that jump up to K knight moves per turn, find the minimum total moves to gather all pieces on one square. | Medium5 | BFSShortest path+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Designing a High-Speed Rail NetworkGiven a cost matrix where negative values mark already-built rail lines, compute the minimum spanning tree cost forcing existing lines and list the new lines to build. | Medium5 | Minimum spanning treeUnion-find+2 | No attempts yet | 2s | 128 MB | Judgeable |
| HighwayGiven a directed graph with edge lengths and tolls, find the minimum length path from city 1 to city N whose total toll does not exceed a budget K. | Medium5 | Dynamic programmingGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Word ExtensionGiven a dictionary and a starting 3-letter word, find the longest word reachable by repeatedly inserting one letter such that each intermediate word exists in the dictionary. | Medium5 | Dynamic programmingString+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Weight LimitGiven a weighted undirected graph, find the maximum possible minimum edge weight (bottleneck) along any path between two given nodes. | Medium5 | Union-findBinary search+1 | No attempts yet | 1s | 128 MB | Judgeable |
| The Famous Seven PrincessesCount connected 7-cell shapes on a 5x5 grid of S/Y students where at least 4 cells are S. | Medium5 | BacktrackingDFS+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Prime PathFind the minimum number of single-digit changes to transform one four-digit prime into another, keeping every intermediate number a four-digit prime, using BFS on the graph of primes. | Medium5 | BFSGraph+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Alphabet PathFind the longest path from the top-left cell of a grid moving to adjacent cells while never revisiting a letter already used, maximizing visited cells. | Medium5 | BacktrackingDFS+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Minimum Transfer RouteGiven several subway lines as sequences of stations, compute the minimum number of transfers to travel between two given stations using BFS over lines. | Medium5 | BFSGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Minimum Vertex CoverGiven a bipartite graph with adjacency lists, compute the size of the minimum vertex cover using König's theorem via bipartite matching. | Medium5 | GraphBFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Traveling Salesperson TourFind the minimum cost Hamiltonian cycle in a directed graph with up to 16 cities using bitmask dynamic programming. | Medium5 | Dynamic programmingBit manipulation+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Bug on a TreeGiven a tree with fruit values on vertices, find the maximum sum path (simple path) and its smallest-numbered starting endpoint. | Medium5 | TreeDynamic programming+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Building a BridgeGiven a grid of land and sea, find the shortest straight sea-cell bridge connecting two different islands. | Medium5 | BFSArray+1 | No attempts yet | 2s | 192 MB | Judgeable |
| In-Flight Meal TripFind the maximum-score path from city 1 to city N using at most M cities, moving only to strictly increasing city numbers along available flights. | Medium5 | Dynamic programmingGraph | No attempts yet | 2s | 128 MB | Judgeable |
| Mountain BikeFind the minimum travel time from top-left to bottom-right of a grid where each move's duration depends on cumulative speed changes from height differences, solvable via Dijkstra with speed encoded as exponent sums. | Medium5 | Shortest pathGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Field Mouse EscapeGiven mouse and tunnel coordinates plus a max travel distance, compute the minimum number of mice that cannot be matched to a distinct tunnel using bipartite matching. | Medium5 | GraphGreedy+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Moving a UnitFind the minimum BFS moves to slide an A by B rectangular unit across an N by M grid with obstacles from a start to a goal cell. | Medium5 | BFSMatrix+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Move by Breaking One WallFind the shortest path in a grid from top-left to bottom-right where you may break at most one wall along the way. | Medium5 | BFSGraph+1 | No attempts yet | 2s | 192 MB | Judgeable |
| Checking CausalityGiven send/receive events across computers with local clocks, detect whether the induced ordering constraints form a cycle indicating a causality violation. | Medium5 | GraphTopological sort+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Tree Height and WidthGiven a binary tree's parent-child structure, place nodes on a grid by binary tree layout rules and find the level with the maximum column width, breaking ties by smallest level. | Medium5 | TreeBFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Water JugsGiven three jug capacities with the third jug initially full, find all possible water amounts in the third jug when the first jug is empty, using pour-until-full-or-empty moves. | Medium5 | BFSSimulation+1 | No attempts yet | 2s | 128 MB | Judgeable |
| JumpFind the minimum number of jumps from stone 1 to stone N where jump lengths change by at most 1 each step and some stones are blocked. | Medium5 | Dynamic programmingBFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Recover Tree PreorderGiven a tree's inorder and postorder sequences, reconstruct the tree and output its preorder traversal. | Medium5 | TreeRecursion+1 | No attempts yet | 5s | 128 MB | Judgeable |
| Tree CuttingGiven a tree with n vertices, find the minimum number of edges to cut so some resulting piece has exactly m vertices, or report impossibility. | Medium5 | TreeDynamic programming+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Height OrderGiven pairwise shorter-than relations between students, count how many students have their exact height rank fully determined by transitivity. | Medium5 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Finding the Middle MarbleGiven pairwise heavier-than relations among N odd marbles, count marbles that must be eliminated as the possible median using transitive closure of the order. | Medium5 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| CheeseSimulate outside air spreading via BFS each hour to melt cheese cells touching air, and report total melting hours plus cheese count one hour before it fully disappears. | Medium5 | BFSSimulation+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Circuit RoutingFind the minimum-cost grid path between two given cells where empty cells cost 1 and cells already occupied by given rectilinear circuits cost k, then output the path in compressed turn-point form. | Medium5 | Shortest pathBFS+1 | No attempts yet | 1s | 128 MB | Judgeable |