graphs | brain

Practice › Codeforces Solutions › Codeforces Round 1091 (Div. 2) and CodeCraft 26 ›

CF 2217E - Definitely Larger

CF 2217E - Definitely Larger Rating: 2000 Tags: binary search, constructive algorithms, data structures, graphs, greedy, sortings Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a fixed permutation p of size n . Alongside it, we must construct another permutation q of the same size. The interaction between p and q defines a dominance relation: an index j is said to dominate an index i if...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.17 Edge-Disjoint Paths

12.17 Edge-Disjoint Paths Problem Suppose you are designing a communication network between two data centers. A single path between the source and destination may be sufficient under normal conditions. But if one cable fails, communication stops. A more reliable design uses multiple independent routes. Example: s -> A -> t s -> B -> t s -> C -> t Even if one route fails, traffic can continue using the...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.9 Bipartite Matching

12.9 Bipartite Matching Problem Suppose you have a set of workers and a set of tasks. Each worker can perform only certain tasks. Worker Tasks Alice A, B Bob B, C Carol A, C You want to assign as many workers as possible such that: Each worker receives at most one task. Each task is assigned to at most one worker. This problem appears in many domains: Job assignment Course...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.8 Max-Flow Min-Cut Theorem

12.8 Max-Flow Min-Cut Theorem Problem A maximum-flow algorithm returns a number. That number tells you how much flow can be sent from the source to the sink. But an algorithmic answer alone is not enough. You also need a reason why the answer is optimal. Suppose an algorithm returns: maximum flow = 37 How do you know that 38 is impossible? A minimum cut provides the certificate. The max-flow min-cut...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.15 Lower Bounds on Edges

12.15 Lower Bounds on Edges Problem A normal flow edge has only an upper capacity: 0 ≤ f(u, v) ≤ c(u, v) Many practical models need a minimum commitment as well. A truck route may need at least 3 shipments per day to justify operating. A contract may require a supplier to deliver at least 100 units. A shift may require a minimum staffing level. A network reservation may require...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.25 Common Flow Modeling Patterns

12.25 Common Flow Modeling Patterns Problem Many optimization problems appear completely different on the surface. Consider these examples: Assign nurses to hospital shifts. Match students to courses. Route packages through warehouses. Allocate cloud resources to applications. Schedule manufacturing jobs. Select profitable projects. Segment an image. Verify network reliability. The problem statements use different terminology and come from different domains. Yet experienced algorithm designers often solve all of them with network...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.1 Flow Networks

12.1 Flow Networks Problem You need to model the movement of resources through a constrained system. The resources may represent data packets, water, vehicles, products, workers, money, electricity, or any quantity that moves between locations. Each connection has a limited capacity, and the objective is to determine how much can be transported from a source to a destination while respecting all constraints. Examples include: Delivering products from warehouses to stores...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.23 Complexity Analysis

12.23 Complexity Analysis Problem Flow algorithms solve the same abstract problem, but their running times differ sharply. A small network can be solved with almost any implementation. A large scheduling system, matching engine, or transportation model may require careful algorithm selection. The wrong choice can turn a feasible computation into an unusable one. You need a way to compare flow algorithms by graph size, capacity size, density, and problem structure....

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.4 Edmonds-Karp Algorithm

12.4 Edmonds-Karp Algorithm Problem The Ford-Fulkerson method provides a simple framework for computing maximum flow, but its performance depends heavily on the choice of augmenting paths. Different path selections can lead to dramatically different running times. Consider a network where one path increases flow by 100 units while another increases flow by only 1 unit. A poor path selection strategy may require thousands of augmentations before reaching the optimum. Even...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.19 Project Selection

12.19 Project Selection Problem You have a set of possible projects. Each project has a profit or a cost. Some projects depend on other projects. Example: Project Value Build API +10 Build Database Layer -4 Build Auth -3 Build Dashboard +8 Dependencies: Build API requires Build Database Layer Build Dashboard requires Build API Build Dashboard requires Build Auth You want to choose a subset of projects that maximizes total value...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.10 Hopcroft-Karp Algorithm

12.10 Hopcroft-Karp Algorithm Problem You need to find a maximum matching in a bipartite graph. A generic max-flow algorithm works, but bipartite matching has extra structure. Every augmenting path alternates between unmatched and matched edges. Instead of finding one augmenting path at a time, we can find many shortest augmenting paths in phases. This is the same performance idea used by Dinic: build layers, then augment through many disjoint paths...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.3 Ford-Fulkerson Algorithm

12.3 Ford-Fulkerson Algorithm Problem Given a flow network with capacities on every edge, determine the maximum amount of flow that can be sent from the source to the sink. For small networks, it is often possible to find a solution manually. For larger networks, the number of possible flow assignments becomes enormous. Exhaustively searching all assignments quickly becomes impractical. We need a systematic method that starts from an empty flow...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.6 Push-Relabel Algorithm

12.6 Push-Relabel Algorithm Problem The algorithms developed so far share a common strategy. They search for augmenting paths from the source to the sink and then push additional flow along those paths. This approach works well, but it has an important limitation. Every augmentation requires discovering a complete path through the residual network before any progress can be made. In large networks, repeatedly searching for source-to-sink paths can become expensive....

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.24 Testing Flow Code

12.24 Testing Flow Code Problem Flow implementations are compact, but bugs are easy to hide. A wrong residual update may still return a plausible value on small examples. A missing reverse edge may pass tests where no rerouting is needed. A sign error in lower-bound circulation may work on balanced toy inputs and fail on real cases. Flow code needs tests that check both the final answer and the internal...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.20 Image Segmentation with Graph Cuts

12.20 Image Segmentation with Graph Cuts Problem Suppose you have an image and want to separate the foreground from the background. Examples include: Removing a background from a photograph Identifying tumors in medical images Detecting roads in satellite imagery Isolating objects in computer vision systems Separating products from backgrounds in e-commerce photos At first glance, image segmentation appears completely unrelated to network flow. An image consists of pixels. Maximum flow...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.2 Residual Graphs

12.2 Residual Graphs Problem Suppose you have already constructed a valid flow in a network. You discover another path from the source to the sink and want to increase the total flow. A natural approach is to send additional flow through the newly discovered path. Unfortunately, previous decisions may block better solutions. Consider the network: Edge Capacity S → A 10 S → B 10 A → B 5 A...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.22 Correctness Proofs

12.22 Correctness Proofs Problem Flow algorithms are easy to implement incorrectly because their state changes over time. Residual capacities change. Reverse edges appear. Flow may be pushed forward, canceled backward, or rerouted through a different path. A program can return a plausible number while violating conservation, exceeding capacity, or stopping too early. A correctness proof gives you a disciplined way to reason about the algorithm: What is preserved after every...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.21 Scheduling Applications

12.21 Scheduling Applications Problem Scheduling problems often look different from flow problems. You may need to assign: Workers to shifts Jobs to machines Students to exams Nurses to hospital wards Deliveries to time windows Courses to rooms Tasks to processors Each assignment must respect constraints: availability, capacity, minimum coverage, maximum workload, skill requirements, time windows, and sometimes fairness rules. The challenge is to recognize when a scheduling problem is really...

Programming › Algorithm Cookbook ›

Chapter 12. Network Flow and Matching

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.5 Dinic's Algorithm

12.5 Dinic's Algorithm Problem Edmonds-Karp guarantees polynomial running time, but it still performs only one augmentation per BFS search. Consider a network containing thousands of shortest augmenting paths. Edmonds-Karp may discover: Path 1 augment Path 2 augment Path 3 augment ... even though all paths belong to the same shortest-path structure. The repeated BFS traversals become expensive. We need an algorithm that can exploit many shortest augmenting paths at once....

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.7 Minimum Cut

12.7 Minimum Cut Problem Maximum flow asks how much can be sent from a source to a sink. Minimum cut asks a complementary question: what is the smallest amount of capacity that must be removed to separate the source from the sink? At first these sound like different problems. One measures throughput. The other measures vulnerability. In a transportation network, maximum flow tells you how many trucks can move from...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.12 Hungarian Algorithm

12.12 Hungarian Algorithm Problem You need to solve an assignment problem exactly. There are n workers and n tasks. Each worker can be assigned to exactly one task, and each task can be assigned to exactly one worker. Every worker-task pair has a cost. The goal is to minimize total cost. Example: Worker Job A Job B Job C Alice 8 2 7 Bob 6 4 3 Carol 5 8...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.16 Vertex Capacities

12.16 Vertex Capacities Problem Standard flow networks place capacity constraints on edges. That works when the limiting resource is a road, pipe, cable, route, or connection. But in many problems, the bottleneck belongs to a vertex. Examples: A warehouse can process at most 500 packages per hour. A router can forward at most 10 Gbps. A machine can handle at most 12 jobs. A hospital can admit at most 40...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.18 Vertex-Disjoint Paths

12.18 Vertex-Disjoint Paths Problem Edge-disjoint paths are allowed to share vertices. In some applications, that is not enough. Consider two communication routes: s -> A -> C -> t s -> B -> C -> t These paths do not share their first edges, but both depend on vertex C . If C is a router, checkpoint, warehouse, switch, bridge, or processing station, then C is still a single point...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.11 Assignment Problem

12.11 Assignment Problem Problem In maximum bipartite matching, every assignment has the same value. The goal is simply to maximize the number of matches. Many real-world allocation problems are more complicated. Every assignment has a cost, profit, distance, or score. Consider assigning workers to jobs: Worker Job A Job B Job C Alice 8 2 7 Bob 6 4 3 Carol 5 8 1 The numbers may represent: Time required...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.14 Circulation with Demands

12.14 Circulation with Demands Problem So far, flow networks have had a source and a sink. Flow starts at s , moves through the graph, and ends at t . Many real systems are not organized that way. A supply network may contain several producers and several consumers. A transportation system may require certain minimum shipments on specific routes. A scheduling model may require every department to receive a fixed...

Programming › Algorithm Cookbook › Chapter 12. Network Flow and Matching ›

12.13 Minimum-Cost Maximum-Flow

12.13 Minimum-Cost Maximum-Flow Problem Traditional maximum-flow algorithms answer a single question: How much flow can be sent from the source to the sink? They do not care where that flow travels. Consider the network: cost=1 A ----------> T / S \\n B ----------> T cost=10 Both paths have capacity: 10 A maximum-flow algorithm sees no difference between them. However, in practice the paths may represent: Transportation routes Communication links Manufacturing...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.16 Sparse Graph Handling

11.16 Sparse Graph Handling Problem Minimum spanning tree algorithms are usually described in terms of V vertices and E edges. That notation hides an important engineering detail: the graph’s density strongly affects which representation and algorithm are best. A sparse graph has relatively few edges compared with the number of vertices. In many real systems, each vertex connects only to a small number of neighbors. Examples include: road intersections computer...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.10 Offline Connectivity

11.10 Offline Connectivity Problem Suppose you are given a graph and thousands or millions of connectivity queries: Are vertices u and v connected? A straightforward approach runs DFS or BFS for every query. Example: Query 1: connected(A,D)? Query 2: connected(B,F)? Query 3: connected(C,E)? ... If the graph contains: $$ V = 100,000 $$ vertices and: $$ Q = 1,000,000 $$ queries, repeatedly traversing the graph becomes extremely expensive. In many...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.6 Borůvka's Algorithm

11.6 Borůvka's Algorithm Problem Kruskal's algorithm grows a forest by processing edges globally. Prim's algorithm grows a single tree from a starting vertex. Both approaches are highly effective, but neither was the first minimum spanning tree algorithm. In 1926, before modern computers existed, the Czech mathematician entity["people","Otakar Borůvka","Czech mathematician"] developed an algorithm for designing an efficient electrical network. His solution became one of the earliest graph optimization algorithms and remains...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.17 Dense Graph Handling

11.17 Dense Graph Handling Problem Sparse graphs reward algorithms that touch only existing edges. Dense graphs are different. When most vertex pairs have an edge, avoiding non-existent edges no longer helps much because there are few non-existent edges to avoid. A dense graph has edge count close to: V² Examples include: complete distance graphs small fully connected networks correlation graphs similarity graphs dense cost matrices In these settings, representation choices...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.14 Clustering

11.14 Clustering Problem You have a set of objects and pairwise distances between them. You want to divide the objects into groups so that nearby objects stay together and distant objects fall into different groups. This is a clustering problem. Minimum spanning trees provide a simple and effective clustering method when the data can be represented as a weighted undirected graph: vertex = object edge weight = distance or dissimilarity...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.13 Second-Best Spanning Tree

11.13 Second-Best Spanning Tree Problem A minimum spanning tree gives the cheapest way to connect all vertices. In practice, the cheapest tree may not be the only tree worth knowing. A cable route may become unavailable. A road segment may be blocked by regulation. A network design may need a backup plan. A contest problem may ask for the next larger spanning tree cost. In each case, you need the...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.24 Common Bugs

11.24 Common Bugs Problem Minimum spanning tree code often fails for reasons that are easy to miss in clean textbook examples. The graph is disconnected. The edge list has parallel edges. The total cost overflows. The implementation forgets to store reverse edges. The priority queue contains stale entries. The union-find structure compares vertices instead of roots. These bugs are common because MST algorithms combine several moving pieces: graph representation edge...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.2 Cut Property

11.2 Cut Property Problem Minimum spanning tree algorithms repeatedly make local decisions. At each step, they select one edge from many available choices. The challenge is determining whether a locally attractive edge can safely become part of a globally optimal solution. Suppose a graph contains thousands or millions of edges. Testing every possible spanning tree is computationally infeasible. We need a rule that identifies edges that must belong to some...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.21 Implementation Patterns

11.21 Implementation Patterns Problem After studying cut properties, union-find, Kruskal, Prim, Borůvka, clustering, network design, and complexity analysis, a practical question remains: How should MST algorithms actually be implemented? Many algorithm failures are not caused by incorrect theory. They are caused by small implementation mistakes: incorrect edge sorting bad union-find duplicate edge handling disconnected graph assumptions overflow bugs This section collects implementation patterns that appear repeatedly in production-quality MST code....

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.11 Dynamic Connectivity Overview

11.11 Dynamic Connectivity Overview Problem Offline connectivity works well when edges are fixed, or when all updates can be processed in a convenient order. Real systems are messier. Networks gain and lose links. Roads close. Machines fail. Social connections appear and disappear. A graph changes over time, and we still need to answer questions such as: Are u and v connected right now? This is the dynamic connectivity problem. The...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.23 Choosing the Right MST Algorithm

11.23 Choosing the Right MST Algorithm Problem By this point, you have seen three major minimum spanning tree algorithms: Kruskal Prim Borůvka All produce the same result. All are correct. All are efficient. This naturally raises a practical question: Which one should you use? Many developers learn all three algorithms but never develop a framework for selecting between them. As a result, they either use the same algorithm everywhere or...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.22 Testing MST Code

11.22 Testing MST Code Problem Minimum spanning tree implementations can look correct while failing on small edge cases. The usual failures are not in the theorem. They are in details such as input handling, duplicate edges, disconnected graphs, integer overflow, and incorrect component updates. A good test suite should verify more than the happy path. It should answer: Does the algorithm return a tree? Does it have minimum cost? Does...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.7 Union-Find

11.7 Union-Find Problem Many graph algorithms repeatedly ask the same question: Do these two vertices already belong to the same connected component? Consider Kruskal's algorithm. Before adding an edge: (u,v) we must determine whether the edge creates a cycle. A naïve solution performs DFS or BFS every time an edge is considered. For a graph with millions of edges, repeatedly traversing the graph becomes prohibitively expensive. We need a data...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.15 Network Design

11.15 Network Design Problem Many real-world optimization problems can be modeled as graphs. Cities become vertices. Roads become edges. Data centers become vertices. Network links become edges. Water treatment facilities, electrical substations, pipelines, rail systems, and communication towers can all be represented in the same way. The challenge is rarely to connect everything. The challenge is to connect everything at an acceptable cost. Consider a telecommunications company deploying fiber across...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.25 Case Study: Building a Production-Quality MST Service

11.25 Case Study: Building a Production-Quality MST Service Problem Throughout this chapter, we have studied minimum spanning trees from multiple perspectives: Graph theory Greedy algorithms Union-find Kruskal Prim Borůvka Clustering Network design Performance analysis Testing The final challenge is bringing these ideas together into a real system. Suppose you are building a service that receives infrastructure graphs and computes minimum spanning trees for customers. The service must: accept large inputs...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.1 Spanning Trees

11.1 Spanning Trees Problem You are given a connected undirected graph. You need a subset of edges that keeps every vertex reachable from every other vertex while using the smallest possible number of edges. This problem appears in communication networks, road systems, electrical distribution, dependency management, clustering, and many optimization problems. Before searching for the minimum-cost solution, we must understand the structure called a spanning tree. Solution A spanning tree...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.20 Complexity Analysis

11.20 Complexity Analysis Problem Minimum spanning tree algorithms are easy to state, but their performance depends heavily on representation and data structure choices. The same graph problem can produce different costs depending on whether you use: edge list adjacency list adjacency matrix binary heap union-find sorting A useful complexity analysis must therefore answer more than: What is the Big O? It should answer: Which operation dominates? Which representation is assumed?...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.26 Practice Exercises

11.26 Practice Exercises Problem Minimum spanning tree algorithms become useful only after you can recognize the pattern in unfamiliar problems. The core ideas are simple: connect all vertices minimize edge cost avoid cycles merge components But problem statements rarely say “use Kruskal” or “use Prim.” They describe networks, roads, cables, clusters, islands, sensors, or regions. Your task is to translate the story into a graph and then choose the right...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.5 Prim's Algorithm

11.5 Prim's Algorithm Problem Kruskal's algorithm builds a minimum spanning tree by selecting edges globally. It sorts every edge in the graph and repeatedly connects separate components. There is another approach. Instead of constructing many small trees and merging them, we can start with a single vertex and grow one tree until it spans the entire graph. This idea leads to Prim's algorithm. Like Kruskal, Prim produces a minimum spanning...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.8 Path Compression

11.8 Path Compression Problem The basic union-find structure can become highly unbalanced. Consider the sequence: union(A,B) union(B,C) union(C,D) union(D,E) union(E,F) A naïve implementation may produce: A | B | C | D | E | F Now evaluate: find(F) The search follows: F → E → D → C → B → A Every operation traverses the entire chain. For (n) vertices: $$ O(n) $$ time may be required for...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.19 Correctness Proofs

11.19 Correctness Proofs Problem Minimum spanning tree algorithms are short. Their correctness proofs are not optional. Kruskal, Prim, and Borůvka all make greedy choices. A greedy algorithm is risky unless each local decision can be shown to preserve a globally optimal solution. Without a proof, the algorithm may look plausible while silently failing on edge cases. The goal of this section is to give reusable proof templates for MST algorithms....

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.18 Parallel and Distributed MST Algorithms

11.18 Parallel and Distributed MST Algorithms Problem The classical MST algorithms were designed for a single machine processing a graph stored in local memory. Modern graph-processing systems often face very different constraints. Consider: 10 billion edges hundreds of machines streaming input distributed storage A graph may be too large to fit into memory on a single server. Even when it fits, processing it sequentially can become a bottleneck. The challenge...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.12 Minimum Bottleneck Spanning Trees

11.12 Minimum Bottleneck Spanning Trees Problem Minimum spanning trees minimize the total weight of selected edges. In some applications, however, the largest edge matters more than the total cost. Consider a communication network. A spanning tree with total cost: 100 and largest edge: 50 may be less desirable than a spanning tree with total cost: 110 and largest edge: 20 The second network has a smaller worst-case link. Similar situations...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.4 Kruskal's Algorithm

11.4 Kruskal's Algorithm Problem Given a connected weighted undirected graph, find a spanning tree whose total edge weight is minimum. A brute-force approach would generate every possible spanning tree and compute its cost. Unfortunately, the number of spanning trees grows exponentially with graph size, making exhaustive search impractical even for moderately sized graphs. We need an efficient algorithm that constructs a minimum spanning tree directly. Solution Kruskal's algorithm is a...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.3 Cycle Property

11.3 Cycle Property Problem The cut property identifies edges that can safely be added to a minimum spanning tree. An equally important question is the reverse: How can we identify edges that can safely be discarded? In large graphs, many edges obviously appear unnecessary. If we can prove that certain edges never belong to any minimum spanning tree, we can eliminate them immediately and reduce the search space. The cycle...

Programming › Algorithm Cookbook ›

Chapter 11. Minimum Spanning Trees and Connectivity

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.9 Union by Rank

11.9 Union by Rank Problem Path compression makes existing trees flatter, but it does not prevent bad trees from being created. Consider the following sequence: union(A,B) union(B,C) union(C,D) union(D,E) union(E,F) A naïve implementation might repeatedly attach one root beneath another: A | B | C | D | E | F Path compression eventually fixes this structure, but the first few operations may still be expensive. Can we avoid creating...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.6 Detecting Negative Cycles with Bellman-Ford

10.6 Detecting Negative Cycles with Bellman-Ford In the previous recipe, Bellman-Ford was used to compute shortest paths in graphs that contain negative edge weights. The algorithm included an additional pass that detected negative cycles, but the detection itself deserves a closer look. Negative cycles are fundamentally different from ordinary graph structures. A shortest path normally represents a minimum cost route between two vertices. A negative cycle destroys that concept. If...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.14 Using Distance Labels and Relaxation Correctly

10.14 Using Distance Labels and Relaxation Correctly Every shortest-path algorithm in this chapter appears different on the surface. BFS uses a queue. Dijkstra uses a priority queue. Bellman-Ford repeatedly scans edges. Floyd-Warshall uses dynamic programming. A* uses heuristics. Despite these differences, they all rely on the same fundamental idea: Distance labels are gradually improved through relaxation. Understanding this idea provides a unified framework for reasoning about shortest-path algorithms. Instead of...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.2 Finding Shortest Paths with BFS

10.2 Finding Shortest Paths with BFS Use BFS when every edge has the same cost. In that setting, the shortest path is the path with the fewest edges, and BFS finds it by exploring the graph one distance layer at a time. This recipe focuses on the standard single-source BFS form: given a source vertex, compute the shortest distance to every reachable vertex. Problem Given an unweighted graph and a...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.9 Computing Multi-Source Shortest Paths

10.9 Computing Multi-Source Shortest Paths Most shortest-path problems begin with a single source vertex. We start at one location and ask for the shortest distance to every other location. Some problems are naturally different. A city may contain multiple hospitals, and we want the nearest hospital for every neighborhood. A game map may contain multiple spawn points, and we want the closest one for each position. A logistics network may...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.23 Common Shortest-Path Patterns and Interview Problems

10.23 Common Shortest-Path Patterns and Interview Problems Learning shortest-path algorithms is only the first step. The next challenge is recognizing when a problem can be solved using them. Many interview questions, programming contests, and production systems disguise shortest-path problems behind different stories: Mazes Transformations Scheduling Navigation Resource optimization State exploration The underlying graph is often hidden. This recipe presents the most common shortest-path patterns and shows how to identify them...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.18 Solving Shortest Paths on Grids

10.18 Solving Shortest Paths on Grids Many shortest-path problems are not given as explicit graph structures. Instead, they appear as grids. A grid may represent a maze, a game map, a warehouse floor, a robot workspace, an image, or a terrain model. Cells are vertices. Valid moves between neighboring cells are edges. Once you make that translation, ordinary graph algorithms apply directly. This recipe shows how to model grid shortest-path...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.11 Accelerating Search with A

10.11 Accelerating Search with A Dijkstra's algorithm finds shortest paths by expanding vertices in order of increasing distance from the source. This guarantees correctness, but it often explores large portions of the graph that are irrelevant to the final answer. Suppose you want driving directions from one city to another. Dijkstra expands outward in every direction, including areas that move away from the destination. Many of those vertices will never...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.12 Accelerating Searches with Bidirectional Search

10.12 Accelerating Searches with Bidirectional Search Many shortest-path algorithms begin at the source and gradually expand outward until the target is reached. This works well, but it often explores far more of the graph than necessary. Consider finding a route between two cities on opposite sides of a large road network. A traditional search expands a growing region from the source. Much of that exploration occurs far from the destination....

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.15 Using Potentials to Reweight Graphs

10.15 Using Potentials to Reweight Graphs Negative edge weights complicate shortest-path algorithms. Dijkstra's algorithm is efficient because it assumes that once a vertex receives the smallest tentative distance, that distance can never improve. Negative edges break this assumption. A path that appears expensive today may become cheaper tomorrow after traversing a negative edge. Bellman-Ford handles negative edges correctly, but its running time is significantly higher than Dijkstra's. This raises an...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm

10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm The shortest-path algorithms studied so far naturally divide into two groups. Single-source algorithms: BFS Dijkstra Bellman-Ford DAG shortest paths A* All-pairs algorithms: Floyd-Warshall When a graph contains thousands or millions of vertices, Floyd-Warshall's cubic running time often becomes impractical. Running Dijkstra from every vertex can be much faster for sparse graphs, but negative edge weights create complications. Johnson's algorithm combines several...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.21 Proving Correctness of Shortest-Path Algorithms

10.21 Proving Correctness of Shortest-Path Algorithms Shortest-path algorithms are easy to implement incorrectly. A program may pass small examples while failing on edge cases involving cycles, unreachable vertices, zero-weight edges, or negative weights. Correctness proofs prevent this kind of accidental confidence. This recipe develops the proof patterns used for shortest-path algorithms. The goal is not formal theorem proving. The goal is to learn the invariants that explain why an algorithm...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.20 Choosing the Right Shortest-Path Algorithm

10.20 Choosing the Right Shortest-Path Algorithm This chapter introduced a substantial collection of shortest-path algorithms. At first glance, the algorithms may appear unrelated. Some use queues. Some use priority queues. Some use dynamic programming. Some rely on graph transformations. Some use heuristics. In practice, the most important skill is not memorizing every algorithm. It is recognizing which algorithm fits a particular problem. This recipe summarizes the major shortest-path techniques and...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.22 Analyzing Complexity of Shortest-Path Algorithms

10.22 Analyzing Complexity of Shortest-Path Algorithms Shortest-path algorithms are often chosen by correctness first, then by complexity. Once the graph model and edge weights determine which algorithms are valid, the next question is performance. This recipe explains how to analyze shortest-path algorithms using the two standard graph parameters: V = number of vertices E = number of edges The goal is to understand where the running time comes from, not...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.13 Reconstructing Shortest Paths

10.13 Reconstructing Shortest Paths Most shortest-path algorithms compute distances. They tell us that the minimum cost from a source to a destination is: 17 or: 42 In practice, this information is often insufficient. A navigation system must display the route. A network router must know which links to traverse. A workflow engine must know which sequence of tasks leads to the optimal outcome. The actual path is frequently more important...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.25 Debugging and Optimizing Shortest-Path Code

10.25 Debugging and Optimizing Shortest-Path Code Shortest-path code usually fails in predictable ways. The algorithm may be conceptually correct, but the implementation mishandles the queue, marks vertices at the wrong time, overflows an integer, reconstructs paths incorrectly, or applies the algorithm outside its assumptions. This final recipe provides a practical checklist for debugging and optimizing shortest-path implementations. Problem Given a shortest-path implementation that is wrong, slow, or memory-heavy, identify the...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search

10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search Breadth-first search (BFS) is the simplest shortest path algorithm. When every edge in a graph has the same cost, BFS discovers vertices in increasing order of distance from the starting vertex. The first time a vertex is reached, the algorithm has already found the shortest possible path to it. This property makes BFS one of the most important graph algorithms....

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.5 Detecting Negative Edges with Bellman-Ford

10.5 Detecting Negative Edges with Bellman-Ford Dijkstra's algorithm depends on a crucial assumption: edge weights must be nonnegative. Once negative edges enter the graph, the greedy strategy that makes Dijkstra efficient no longer works. A path that appears optimal today may become cheaper tomorrow through a negative-weight edge discovered later. Bellman-Ford takes a different approach. Instead of greedily finalizing distances, it repeatedly relaxes every edge in the graph until no...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm

10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm Breadth-first search works because every edge contributes the same cost. Once edge weights become arbitrary positive values, distance layers disappear. A path containing fewer edges may be more expensive than a path containing many edges. Consider the following graph: A --1-- B --1-- D \ ^ \ / 5 1 \ / C ----- The path: A -> C -> D...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.19 Modeling State-Space Problems as Shortest Paths

10.19 Modeling State-Space Problems as Shortest Paths One of the most powerful ideas in algorithm design is that many problems that do not look like graph problems can be transformed into shortest-path problems. A maze is obviously a graph. A puzzle is less obvious. A scheduling problem is even less obvious. A string transformation problem may not appear graph-related at all. Yet many of these problems become straightforward once we...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.7 Computing All-Pairs Shortest Paths with Floyd-Warshall

10.7 Computing All-Pairs Shortest Paths with Floyd-Warshall The algorithms covered so far solve the single-source shortest path problem. Given a source vertex, they compute the shortest distance to every other vertex. Sometimes that is not enough. A routing system may need distances between every pair of cities. A graph analytics engine may need the shortest distance between every pair of users. A database optimizer may repeatedly ask shortest-path questions between...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.4 Implementing Dijkstra with Priority Queue Variants

10.4 Implementing Dijkstra with Priority Queue Variants The previous recipe used Dijkstra’s algorithm with a binary heap and lazy deletion. That version is the usual choice in production code because it is simple, fast enough for most sparse graphs, and available in standard libraries. This recipe compares three implementation variants: Linear scan Binary heap with lazy deletion Indexed priority queue with decrease-key The algorithmic idea remains the same. The difference...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS

10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS Between ordinary BFS and Dijkstra lies an interesting class of shortest-path problems. Suppose edge weights are restricted to only two values: 0 1 Many practical problems naturally have this structure. A routing system may assign cost 0 to preferred roads and cost 1 to secondary roads. A state-space search may assign cost 0 to free transitions and cost 1 to costly...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.8 Finding Shortest Paths in Directed Acyclic Graphs

10.8 Finding Shortest Paths in Directed Acyclic Graphs Many shortest-path algorithms are designed to handle arbitrary graphs. They must deal with cycles, repeated visits, and complex path structures. Directed acyclic graphs (DAGs) are different. Since DAGs contain no cycles, shortest paths become significantly easier to compute. In fact, shortest paths in a DAG can be found in linear time. This is faster than Dijkstra, faster than Bellman-Ford, and often simpler...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.24 Testing Shortest-Path Implementations

10.24 Testing Shortest-Path Implementations Shortest-path implementations are prone to subtle errors. A small example may pass even when the algorithm mishandles unreachable vertices, duplicate edges, zero-weight edges, negative edges, or path reconstruction. Testing shortest-path code requires more than checking one happy path. Good tests should exercise the assumptions of the algorithm and the invariants used in its correctness proof. This recipe presents a practical testing strategy for BFS, Dijkstra, Bellman-Ford,...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.17 Finding K Shortest Paths

10.17 Finding K Shortest Paths Most shortest-path algorithms answer a single question: What is the shortest path from the source to the destination? In many practical systems, one path is not enough. A navigation application may want alternative routes. A logistics system may need backup delivery plans. A network router may require secondary paths in case of failures. A recommendation engine may want multiple high-quality options rather than a single...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.2 Adjacency Lists

9.2 Adjacency Lists Problem You need a graph representation that supports efficient traversal, scales to large datasets, and works naturally with algorithms such as depth-first search, breadth-first search, topological sorting, shortest paths, and connected component analysis. Most real-world graphs are sparse. A road network contains far fewer roads than the total number of possible city-to-city connections. A social network user knows only a tiny fraction of all users. A source...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.17 Bridges

9.17 Bridges Problem You need to find edges whose removal disconnects a graph. In Chapter 9.16, you learned how to identify articulation points, which are critical vertices. Sometimes the failure point is not a vertex but a connection itself. Examples include: A network cable connecting two data centers A highway connecting two regions A communication link between clusters A transmission line connecting power grids A dependency edge connecting subsystems You...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.23 Shortest Path Fundamentals

9.23 Shortest Path Fundamentals Problem You need to find the cheapest route between vertices. Many graph applications revolve around finding paths: Driving directions between cities Network packet routing Flight planning Robot navigation Supply chain optimization Dependency analysis The question is usually not: Can I reach the destination? but: What is the best way to reach it? The definition of "best" depends on the problem. It may mean: Minimum distance Minimum...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.20 Graph Coloring Basics

9.20 Graph Coloring Basics Problem You need to assign labels, colors, or resources to vertices so that adjacent vertices do not conflict. Many problems involve incompatibility: A meeting cannot use the same room as an overlapping meeting. Two neighboring regions on a map should not use the same color. Two variables that are live at the same time should not use the same register. Two exams taken by the same...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.24 Testing Graph Code

9.24 Testing Graph Code Problem You need confidence that a graph algorithm handles real inputs, edge cases, and malformed assumptions correctly. Graph code is easy to get almost right. A DFS may work on connected graphs but fail on disconnected ones. A cycle detector may work for directed graphs but be wrong for undirected graphs. A shortest-path implementation may pass small examples but fail when vertices are isolated, labels are...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.15 Strongly Connected Components

9.15 Strongly Connected Components Problem You need to identify groups of vertices that are mutually reachable. In an undirected graph, connected components answer the question: Which vertices belong to the same connected region? In a directed graph, the situation is more subtle. Consider: A → B → C Vertex A can reach C . However: C cannot reach: A The vertices are connected in one direction but not the other....

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.11 Connected Components

9.11 Connected Components Problem You need to identify independent regions within a graph. Many graphs are not fully connected. A social network may contain separate communities. A transportation network may contain isolated islands. A computer network may contain disconnected segments. A dataset may contain several unrelated clusters. Before solving higher-level problems, it is often necessary to determine which vertices belong together. You need a way to partition the graph into...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.6 Undirected Graphs

9.6 Undirected Graphs Problem You need to model relationships that are naturally symmetric. Many connections do not have a meaningful direction. If two cities are connected by a road, travel is often possible in both directions. If two computers share a network cable, both endpoints can communicate. If two users are friends in a social network, the relationship is mutual. Representing these relationships as directed edges introduces unnecessary complexity and...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.21 Minimum Spanning Trees

9.21 Minimum Spanning Trees Problem You need to connect all vertices in a graph while minimizing total cost. Many real-world systems involve building networks: Connecting cities with roads Connecting offices with fiber cables Connecting servers with network links Connecting power stations with transmission lines Connecting sensors with communication channels Each connection has a cost. You want a network that: Connects every vertex. Uses the minimum possible total cost. Avoids unnecessary...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.13 Cycle Detection

9.13 Cycle Detection Problem You need to determine whether a graph contains a cycle. Many graph algorithms assume certain structural properties. A build system expects dependency graphs to be acyclic. A workflow engine expects tasks to form a valid execution order. A routing system may need to identify loops. A compiler may need to reject circular imports. Before applying higher-level algorithms, it is often necessary to answer a simple question:...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.8 Degree and Connectivity

9.8 Degree and Connectivity Problem You need basic measurements that describe the local and global structure of a graph. Before choosing an advanced algorithm, it is often useful to ask simple structural questions: How many edges touch this vertex? Is the graph connected? Which vertices form separate regions? Are there isolated vertices? Which vertices act as hubs? These questions are answered by degree and connectivity analysis. Solution Use degree to...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.7 Weighted Graphs

9.7 Weighted Graphs Problem You need to model relationships where connections have different costs. In many graph problems, not all edges are equal. A flight between two cities may take three hours while another takes ten. One network link may have high bandwidth while another is slow. One road may be short while another is long. Treating every edge as identical loses information that is essential for finding optimal solutions....

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.12 Topological Sort

9.12 Topological Sort Problem You need to arrange tasks in an order that respects dependencies. Many real-world systems contain precedence constraints: A compiler must parse before type checking. Type checking must complete before code generation. A package manager must install dependencies before dependent packages. A build system must compile libraries before applications. A workflow engine must run upstream jobs before downstream jobs. These problems share a common structure. Some actions...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.3 Adjacency Matrices

9.3 Adjacency Matrices Problem You need a graph representation that can answer edge-existence queries quickly. An adjacency list is efficient for traversal, but checking whether an edge exists can require scanning a neighbor list. If your algorithm repeatedly asks questions such as: Is there an edge from u to v? then an adjacency matrix may be a better representation. Solution Represent the graph as a two-dimensional table. For a graph...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.19 Hamiltonian Paths

9.19 Hamiltonian Paths Problem You need to visit every vertex exactly once. Many graph problems focus on covering all vertices rather than all edges. Examples include: Visiting every city in a tour Scheduling visits to every location Traversing every checkpoint Planning routes through attractions Sequencing tasks with transition constraints Unlike Euler paths, which use every edge exactly once, these problems care about vertices. You need to determine whether a traversal...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.16 Articulation Points

9.16 Articulation Points Problem You need to find vertices whose removal disconnects an undirected graph. In many networks, some vertices are structurally more important than others. A router may connect two regions of a network. A bridge station may connect two subway lines. A person may connect two otherwise separate social groups. A package may sit between independent parts of a dependency graph. You need to identify vertices that act...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.5 Directed Graphs

9.5 Directed Graphs Problem You need to model relationships that have direction. Many real-world connections are not symmetric. If one task depends on another, the dependency works in only one direction. If a web page links to another page, the reverse link does not automatically exist. If a package imports another package, the imported package does not necessarily import the first one. Treating these relationships as undirected often produces incorrect...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.4 Edge Lists

9.4 Edge Lists Problem You need a graph representation that is simple to construct, compact to store, and efficient for algorithms that process edges directly. Not every graph algorithm spends most of its time traversing neighbors. Some algorithms repeatedly sort edges, scan edges, filter edges, or process edges as independent objects. In these situations, adjacency lists and adjacency matrices may introduce unnecessary complexity. You need a representation that treats the...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.10 Breadth-First Search (BFS)

9.10 Breadth-First Search (BFS) Problem You need to explore a graph in order of increasing distance from a starting vertex. Many graph problems are fundamentally questions about proximity: What vertices can be reached in one step? What vertices can be reached in two steps? What is the shortest path in an unweighted graph? How many hops separate two users in a social network? Which routers are closest to a destination?...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.22 Graph Representation Tradeoffs

9.22 Graph Representation Tradeoffs Problem You need to choose the right in-memory representation for a graph. Most graph algorithms assume some representation, but the best choice depends on the workload. A graph used for BFS has different needs from a graph used for all-pairs shortest paths. A graph stored on disk has different needs from a graph processed interactively. A sparse graph with billions of edges has different constraints from...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.14 Bipartite Graphs

9.14 Bipartite Graphs Problem You need to divide vertices into two groups such that every edge connects vertices from different groups. Many real-world systems naturally have this structure: Students and courses Workers and jobs Users and roles Buyers and products Actors and movies Customers and orders The vertices belong to two distinct categories, and relationships exist only across categories. You need a way to recognize and validate this structure. Solution...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.25 Graph Algorithm Patterns and Interview Strategies

9.25 Graph Algorithm Patterns and Interview Strategies Problem You are given a graph problem and need to quickly identify the correct algorithmic approach. Many graph problems look different on the surface: Find the shortest route between cities. Schedule tasks with dependencies. Detect circular imports. Connect data centers at minimum cost. Assign workers to jobs. Determine whether a network remains connected after failures. Despite their variety, most graph problems belong to...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.18 Euler Paths

9.18 Euler Paths Problem You need to traverse every edge in a graph exactly once. Some problems care about edges rather than vertices. A delivery route may need to use every street segment. A drawing puzzle may require tracing every line without lifting the pen. A network diagnostic tool may need to test every link. A genome assembly algorithm may need to walk through every overlap edge. You need to...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.1 Graph Models

9.1 Graph Models Problem You need to turn a real problem into a graph before choosing an algorithm. The hard part is usually not writing DFS or BFS. The hard part is deciding what the vertices mean, what the edges mean, whether direction matters, whether weights matter, and what special cases the model must preserve. A poor graph model can make a simple problem look difficult. A good model usually...

Programming › Algorithm Cookbook › Chapter 9. Graph Fundamentals ›

9.9 Depth-First Search (DFS)

9.9 Depth-First Search (DFS) Problem You need to explore a graph systematically. Many graph problems can be reduced to a simple question: Starting from a vertex, what can I reach? Examples include: Finding connected components Detecting cycles Validating dependencies Exploring game states Traversing file systems Finding paths Computing graph properties You need a traversal strategy that follows paths deeply before backtracking. Solution Use Depth-First Search (DFS). DFS explores one path...

Programming › Algorithm Cookbook ›

Chapter 9. Graph Fundamentals

Programming › Algorithm Cookbook ›

Chapter 10. Shortest Paths

Practice › Codeforces Solutions › Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2) ›

CF 2222G - Statistics on Tree

CF 2222G - Statistics on Tree Rating: - Tags: binary search, brute force, dfs and similar, divide and conquer, graphs, trees Solve time: 6m 33s Verified: no Solution Problem Understanding We are given a tree. For a pair of vertices $(u,v)$, we remove every edge belonging to the unique simple path between them. After those edges are deleted, the tree breaks into several connected components. The value of the pair...

Practice › Codeforces Solutions › Educational Codeforces Round 163 (Rated for Div. 2) ›

CF 1948C - Arrow Path

CF 1948C - Arrow Path Rating: 1300 Tags: brute force, constructive algorithms, dfs and similar, dp, graphs, shortest paths Solve time: 56s Verified: yes Solution Problem Understanding We have a 2-row grid with $n$ columns, and each cell contains an arrow pointing either left or right. The robot starts at the top-left corner, and each second it first moves to an adjacent cell (up, down, left, right) and then follows...

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967D - Long Way to be Non-decreasing

CF 1967D - Long Way to be Non-decreasing Rating: 2800 Tags: binary search, dfs and similar, graphs, implementation, shortest paths, two pointers Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given an array where each position contains a value in the range $1$ to $m$, and a second array that defines a deterministic transformation on values: every value $x$ has a fixed replacement $b_x$. One operation, called...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951I - Growing Trees

CF 1951I - Growing Trees Rating: 3200 Tags: binary search, constructive algorithms, flows, graphs, greedy Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a connected simple undirected graph with up to 50 vertices and at most 50 edges. Each edge can be used multiple times in a constructed multigraph, and we control how many copies of each edge we create through a non-negative integer array $x$....

Practice › Codeforces Solutions › Codeforces Round 934 (Div. 2) ›

CF 1944A - Destroying Bridges

CF 1944A - Destroying Bridges Rating: 800 Tags: graphs, greedy, math Solve time: 55s Verified: yes Solution Problem Understanding We are asked to consider a network of islands where initially every pair of islands is connected by a bridge. There are n islands, numbered from 1 to n , and Everule lives on island 1. Dominater can destroy up to k bridges to reduce the number of islands that Everule...

Practice › Codeforces Solutions › Kotlin Heroes: Episode 10 ›

CF 1958I - Equal Trees

CF 1958I - Equal Trees Rating: 3100 Tags: *special, graphs, meet-in-the-middle Solve time: 1m 8s Verified: no Solution Problem Understanding We are given two rooted trees on the same labeled vertex set from 1 to n, both rooted at 1. Each tree is described by its parent array, so every node knows its immediate parent except the root. We are allowed to perform a single kind of structural operation: pick...

Practice › Codeforces Solutions › Codeforces Round 939 (Div. 2) ›

CF 1956F - Nene and the Passing Game

CF 1956F - Nene and the Passing Game Rating: 3000 Tags: constructive algorithms, data structures, dsu, graphs, sortings Solve time: 1m 18s Verified: no Solution Problem Understanding We are given a sequence of basketball players, each with a passing range expressed as an interval $[l_i, r_i]$. The players are numbered from 1 to $n$. Two players $i$ and $j$ can pass the ball between them if the distance between them,...

Practice › Codeforces Solutions › Codeforces Round 945 (Div. 2) ›

CF 1973E - Cat, Fox and Swaps

CF 1973E - Cat, Fox and Swaps Rating: 2500 Tags: graphs, math, sortings Solve time: 5m 15s Verified: no Solution

Practice › Codeforces Solutions › European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1949J - Amanda the Amoeba

CF 1949J - Amanda the Amoeba Rating: 2600 Tags: graphs, implementation, trees, two pointers Solve time: 1m 3s Verified: no Solution Problem Understanding We are asked to guide Amanda the Amoeba from an initial configuration to a target configuration on a rectangular grid. Each configuration marks Amanda's body with * , free pixels with . , and blocked pixels with X . Her body is connected and contains at least...

Practice › Codeforces Solutions › Codeforces Round 937 (Div. 4) ›

CF 1950G - Shuffling Songs

CF 1950G - Shuffling Songs Rating: 1900 Tags: bitmasks, dfs and similar, dp, graphs, hashing, implementation, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding Each song has two attributes, a genre and a writer. After removing some songs, we are allowed to reorder the remaining songs arbitrarily. The goal is to arrange them so that every pair of neighboring songs shares at least one attribute: either the same...

Practice › Codeforces Solutions › Codeforces Round 278 (Div. 1) ›

CF 487E - Tourists

CF 487E - Tourists Rating: 3200 Tags: data structures, dfs and similar, graphs, trees Solve time: 10m 55s Verified: no Solution Problem Understanding We are given a network of cities connected by roads, where each city sells a souvenir at a certain price. Queries can either change the souvenir price in a city or ask for the minimum possible price a tourist can pay when traveling from one city to...

Practice › Codeforces Solutions › European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1949G - Scooter

CF 1949G - Scooter Rating: 2300 Tags: graphs, greedy Solve time: 3m 15s Verified: no Solution Problem Understanding Each building has two independent pieces of information. The first string describes what class is held there. A building may need a mathematics professor, a computer science professor, or no professor at all. The second string describes which professor is initially located there. A building may contain a mathematics professor, a computer...

Practice › Codeforces Solutions › Educational Codeforces Round 163 (Rated for Div. 2) ›

CF 1948E - Clique Partition

CF 1948E - Clique Partition Rating: 2100 Tags: brute force, constructive algorithms, graphs, greedy, implementation Solve time: 2m 41s Verified: no Solution Problem Understanding We are given a problem where we need to assign integers to vertices of an initially empty graph and then construct edges based on a Manhattan-like distance metric. Specifically, for vertices labeled $1$ through $n$, each vertex receives a distinct integer from $1$ to $n$. After...

Practice › Codeforces Solutions ›

Educational Codeforces Round 163 (Rated for Div. 2)

Educational Codeforces Round 163 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-3100 | Time: 11m 57s Problem Name Rating Tags Solve Time Verified A Special Characters 800 brute-force, constructive-algorithms 1m 17s ✗ C Arrow Path 1300 brute-force, constructive-algorithms, dfs-and-similar 56s ✓ D Tandem Repeats? 1700 brute-force, strings, two-pointers 2m 48s ✗ E Clique Partition 2100 brute-force, constructive-algorithms, graphs 2m 41s ✗...

Practice › Codeforces Solutions ›

Codeforces Round 934 (Div. 2)

Codeforces Round 934 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 800-1100 | Time: 2m 14s Problem Name Rating Tags Solve Time Verified A Destroying Bridges 800 graphs, greedy, math 55s ✓ B Equal XOR 1100 bitmasks, constructive-algorithms 1m 19s ✗

Practice › Codeforces Solutions ›

Kotlin Heroes: Episode 10

Kotlin Heroes: Episode 10 Type: Kotlin | Problems: 10 | Verified: 7/10 | Rating range: 1100-3200 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A 1-3-5 1100 *special, dp 47s ✓ B Clock in the Pool 1400 *special, math 44s ✓ C Firewood 1500 *special 1m ✓ D Staircase 1600 *special 1m 14s ✗ E Yet Another Permutation Constructive 1900 *special, constructive-algorithms 1m 4s ✗ F Narrow...

Practice › Codeforces Solutions › Codeforces Round 259 (Div. 1) ›

CF 453C - Little Pony and Summer Sun Celebration

CF 453C - Little Pony and Summer Sun Celebration Rating: 2200 Tags: constructive algorithms, dfs and similar, graphs Solve time: 2m 13s Verified: no Solution Problem Understanding We are given an undirected graph and, for every vertex, the parity of how many times that vertex must appear in a walk. A walk is represented by a sequence of vertices. Consecutive vertices in the sequence must be connected by an edge....

Practice › Codeforces Solutions ›

Codeforces Round 257 (Div. 1)

Codeforces Round 257 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1700-2900 | Time: 9m 38s Problem Name Rating Tags Solve Time Verified A Jzzhu and Chocolate 1700 greedy, math 2m 1s ✓ B Jzzhu and Cities 2000 graphs, greedy, shortest-paths 1m 26s ✓ C Jzzhu and Apples 2500 constructive-algorithms, number-theory 1m 44s ✗ D Jzzhu and Numbers 2400 bitmasks, combinatorics, dp 1m 54s...

Practice › Codeforces Solutions › Codeforces Round 266 (Div. 2) ›

CF 466E - Information Graph

CF 466E - Information Graph Rating: 2100 Tags: dfs and similar, dsu, graphs, trees Solve time: 1m 41s Verified: no Solution Problem Understanding We are dealing with a dynamic company hierarchy problem. We have n employees, initially without any reporting structure. Over m days, three types of events can occur: first, an employee x gets a new boss y ; second, an employee receives a document packet, signs it, and...

Practice › Codeforces Solutions › Codeforces Round 265 (Div. 1) ›

CF 464E - The Classic Problem

CF 464E - The Classic Problem Rating: 3000 Tags: data structures, graphs, shortest paths Solve time: 5m 14s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 264 (Div. 2) ›

CF 463D - Gargari and Permutations

CF 463D - Gargari and Permutations Rating: 1900 Tags: dfs and similar, dp, graphs, implementation Solve time: 58s Verified: yes Solution Problem Understanding We are given k permutations of the numbers from 1 to n . A permutation is simply a rearrangement of these numbers. Our goal is to find the length of the longest sequence of numbers that appears in the same relative order in all k permutations. In...

Practice › Codeforces Solutions ›

Codeforces Round 274 (Div. 1)

Codeforces Round 274 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 2600-2800 | Time: 7m 16s Problem Name Rating Tags Solve Time Verified D Parcels 2600 dp, graphs 1m 52s ✓ E Parking Lot 2800 data-structures, divide-and-conquer 5m 24s ✗

Practice › Codeforces Solutions › Codeforces Round 274 (Div. 1) ›

CF 480D - Parcels

CF 480D - Parcels Rating: 2600 Tags: dp, graphs Solve time: 1m 52s Verified: yes Solution Problem Understanding We are given a collection of parcels, each arriving at a specific time and leaving at another specific time. Each parcel carries a weight, a strength, and a value. We can either ignore a parcel completely or temporarily store it on a special structure that behaves like a stack of boxes. The...

Practice › Codeforces Solutions › Codeforces Round 257 (Div. 1) ›

CF 449B - Jzzhu and Cities

CF 449B - Jzzhu and Cities Rating: 2000 Tags: graphs, greedy, shortest paths Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given an undirected weighted graph representing cities and roads. City 1 is the capital. In addition to normal roads, there are special train routes that connect the capital directly to some city. The government wants to close as many train routes as possible. The restriction is...

Practice › Codeforces Solutions › Bayan 2015 Contest Warm Up ›

CF 475B - Strongly Connected City

CF 475B - Strongly Connected City Rating: 1400 Tags: brute force, dfs and similar, graphs, implementation Solve time: 59s Verified: yes Solution Problem Understanding We are asked to determine if a city with a grid of horizontal and vertical streets is "strongly connected" once each street is made one-way. The city can be visualized as a grid of intersections, with n horizontal streets and m vertical streets forming n ×...

Practice › Codeforces Solutions ›

Bayan 2015 Contest Warm Up

Bayan 2015 Contest Warm Up Type: Special | Problems: 6 | Verified: 4/6 | Rating range: 1100-2900 | Time: 11m 19s Problem Name Rating Tags Solve Time Verified A Bayan Bus 1100 implementation 1m 59s ✓ B Strongly Connected City 1400 brute-force, dfs-and-similar, graphs 59s ✓ C Kamal-ol-molk's Painting 2100 brute-force, constructive-algorithms, greedy 2m 56s ✗ D CGCDSSQ 2000 brute-force, data-structures, math 1m 11s ✓ E Strongly Connected City 2...

Practice › Codeforces Solutions › Codeforces Round 267 (Div. 2) ›

CF 467D - Fedor and Essay

CF 467D - Fedor and Essay Rating: 2400 Tags: dfs and similar, dp, graphs, hashing, strings Solve time: 1m 26s Verified: no Solution Problem Understanding We are given an essay, which is a sequence of words, and a dictionary of synonym pairs. Each synonym pair allows us to replace one word with another, but only in the direction specified. Fedor wants to modify his essay to minimize the number of...

Practice › Codeforces Solutions ›

Codeforces Round 265 (Div. 1)

Codeforces Round 265 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 0/3 | Rating range: 2000-3000 | Time: 15m 43s Problem Name Rating Tags Solve Time Verified B Restore Cube 2000 brute-force, geometry 5m 14s ✗ D World of Darkraft - 2 2700 dp, probabilities 5m 15s ✗ E The Classic Problem 3000 data-structures, graphs, shortest-paths 5m 14s ✗

Practice › Codeforces Solutions › Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) ›

CF 241E - Flights

CF 241E - Flights Rating: 2600 Tags: graphs, shortest paths Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given a directed acyclic graph of cities and one-way flights. Every flight initially takes 1 hour. We may independently change any flight duration to either 1 or 2 hours. The goal is to assign durations so that every possible path from city 1 to city n has exactly the...

Practice › Codeforces Solutions ›

Codeforces Round 179 (Div. 1)

Codeforces Round 179 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 4/4 | Rating range: 1700-2500 | Time: 11m 55s Problem Name Rating Tags Solve Time Verified B Greg and Graph 1700 dp, graphs, shortest-paths 6m 5s ✓ C Greg and Friends 2100 combinatorics, dp, graphs 2m 44s ✓ D Greg and Caves 2400 combinatorics, dp 1m 37s ✓ E Yaroslav and Points 2500 data-structures 1m 29s ✓

Practice › Codeforces Solutions ›

Codeforces Testing Round 5

Codeforces Testing Round 5 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 900-2000 | Time: 4m 20s Problem Name Rating Tags Solve Time Verified A Subtractions 900 math, number-theory 2m 41s ✓ B Dominoes 2000 dfs-and-similar, graphs 1m 39s ✓

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232C - Doe Graphs

CF 232C - Doe Graphs Rating: 2600 Tags: constructive algorithms, divide and conquer, dp, graphs, shortest paths Solve time: 2m 23s Verified: yes Solution Problem Understanding The graph family is built recursively. D(0) is a single vertex. D(1) is a single edge. For every larger order, D(n) is formed by taking a copy of D(n-1) and a shifted copy of D(n-2) , then connecting them with two extra edges. The...

Practice › Codeforces Solutions › Codeforces Testing Round 4 ›

CF 147B - Smile House

CF 147B - Smile House Rating: 2500 Tags: binary search, graphs, matrices Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given a set of rooms connected by doors, where each door has two mood values: one for each direction. Petya can move from room to room, and every move adds to his mood according to the direction-specific value. The task is to determine whether Petya can increase...

Practice › Codeforces Solutions › Codeforces Round 147 (Div. 2) ›

CF 237D - T-decomposition

CF 237D - T-decomposition Rating: 2000 Tags: dfs and similar, graphs, greedy, trees Solve time: 2m 14s Verified: yes Solution Problem Understanding We are given a tree $s$ with $n$ vertices. We must construct another tree $t$, whose nodes are subsets of vertices of $s$. Each subset is usually called a bag. The decomposition must satisfy three conditions. First, every original vertex must appear in at least one bag. Second,...

Practice › Codeforces Solutions › Codeforces Round 185 (Div. 1) ›

CF 311C - Fetch the Treasure

CF 311C - Fetch the Treasure Rating: 2500 Tags: brute force, data structures, graphs, shortest paths Solve time: 1m 7s Verified: yes Solution Problem Understanding We have a linear arrangement of h cells, numbered from 1 to h . Some of these cells contain treasures, each with a positive dollar value. Freda starts at the first cell and initially has only one step size, k , allowing her to move...

Practice › Codeforces Solutions › Codeforces Round 191 (Div. 2) ›

CF 327D - Block Tower

CF 327D - Block Tower Rating: 1900 Tags: constructive algorithms, dfs and similar, graphs Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a grid where some cells are blocked and the rest are usable land. On each usable cell we may place one building, either a blue tower worth 100 population or a red tower worth 200 population. The restriction is that a red tower is...

Practice › Codeforces Solutions ›

Codeforces Round 149 (Div. 2)

Codeforces Round 149 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2100 | Time: 12m 58s Problem Name Rating Tags Solve Time Verified A Heads or Tails 1100 brute-force, implementation 3m 26s ✓ B Big Segment 1100 implementation, sortings 1m 12s ✓ C King's Path 1800 dfs-and-similar, graphs, hashing 3m 11s ✗ D Dispute 2100 dfs-and-similar, graphs, greedy 1m 37s ✗ E XOR on...

Practice › Codeforces Solutions ›

ABBYY Cup 3.0 - Finals (online version)

ABBYY Cup 3.0 - Finals (online version) Type: Special | Problems: 7 | Verified: 3/7 | Rating range: 1100-2900 | Time: 27m 55s Problem Name Rating Tags Solve Time Verified B1 Shave Beaver! 1700 implementation 2m 32s ✓ C1 The Great Julya Calendar 1100 dp 4m 55s ✓ C2 The Great Julya Calendar 2400 dp 5m 52s ✗ C3 The Great Julya Calendar 2500 dp 1m 53s ✓ D1 Escaping...

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C2 - Party

CF 177C2 - Party Rating: 1500 Tags: brute force, dfs and similar, dsu, graphs Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a social graph of people. Some pairs are friends, and some pairs dislike each other. Friendship and dislike are both undirected relations. The Beaver wants to invite a set of people satisfying three conditions at the same time. Every invited person must bring all...

Practice › Codeforces Solutions ›

Codeforces Round 121 (Div. 1)

Codeforces Round 121 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2700 | Time: 8m 55s Problem Name Rating Tags Solve Time Verified A Dynasty Puzzles 1500 dp 1m 42s ✓ B Demonstration 1700 greedy 1m 33s ✓ C Fools and Roads 1900 data-structures, dfs-and-similar, trees 1m 55s ✓ D Metro Scheme 2700 graphs, greedy 1m 59s ✓ E Thwarting Demonstrations 2200 binary-search, data-structures,...

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

CF 212A - Privatization

CF 212A - Privatization Rating: 3000 Tags: flows, graphs Solve time: 2m 20s Verified: no Solution Problem Understanding We are given a bipartite graph. One side contains Berland cities, the other side contains Beerland cities, and every flight is an undirected edge between the two countries. Each edge must be assigned to one of t private companies. For every city, we count how many incident edges belong to each company....

Practice › Codeforces Solutions › Codeforces Round 189 (Div. 2) ›

CF 320B - Ping-Pong (Easy Version)

CF 320B - Ping-Pong (Easy Version) Rating: 1500 Tags: dfs and similar, graphs Solve time: 3m 52s Verified: no Solution Problem Understanding We are maintaining a growing collection of intervals, each interval identified by its insertion order. Along with building this collection, we also define a directed reachability relation between intervals. From an interval $(a, b)$, you are allowed to move to another interval $(c, d)$ if either endpoint of...

Practice › Codeforces Solutions › ABBYY Cup 3.0 - Finals (online version) ›

CF 331E1 - Deja Vu

CF 331E1 - Deja Vu Rating: 2900 Tags: constructive algorithms, graphs, implementation Solve time: 6m 28s Verified: no Solution Problem Understanding We are given a directed graph of shops and streets. Every directed edge has an attached sequence of shop numbers called a vision. Whenever Neo traverses that edge, he sees exactly that sequence. Suppose Neo walks through a path $$p_0 \to p_1 \to p_2 \to \dots \to p_k$$ The...

Practice › Codeforces Solutions › Codeforces Round 146 (Div. 1) ›

CF 235D - Graph Game

CF 235D - Graph Game Rating: 3000 Tags: graphs Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a connected graph with $n$ nodes and $n$ edges, meaning it is a single connected component with exactly one cycle. The problem defines a recursive deletion process where we repeatedly pick a node at random, add the current number of nodes to a running total called totalCost , delete...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 1) ›

CF 196E - Opening Portals

CF 196E - Opening Portals Rating: 2600 Tags: dsu, graphs, shortest paths Solve time: 2m 19s Verified: yes Solution Problem Understanding We are asked to compute the minimum time needed for a player to open all portals in a country modeled as a graph. The country consists of n cities connected by m bidirectional roads with positive travel times. Some subset of cities, k of them, have portals. Initially, all...

Practice › Codeforces Solutions › Codeforces Round 115 ›

CF 175F - Gnomes of Might and Magic

CF 175F - Gnomes of Might and Magic Rating: 3000 Tags: data structures, graphs, implementation, shortest paths Solve time: 1m 50s Verified: yes Solution Problem Understanding The kingdom of gnomes consists of castles connected by a very specific graph structure. There is a cycle of m castles called the Good Path, connected sequentially with roads and forming a closed loop. Between every pair of consecutive castles on this cycle, there...

Practice › Codeforces Solutions › Codeforces Round 179 (Div. 1) ›

CF 295B - Greg and Graph

CF 295B - Greg and Graph Rating: 1700 Tags: dp, graphs, shortest paths Solve time: 6m 5s Verified: yes Solution Problem Understanding We are given a fully connected directed graph with weighted edges, represented as an adjacency matrix. Each vertex has an edge to every other vertex, including a zero-weight self-loop. Greg wants to play a game where he removes vertices one by one according to a given sequence. Before...

Practice › Codeforces Solutions ›

Codeforces Round 142 (Div. 1)

Codeforces Round 142 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 10m 59s Problem Name Rating Tags Solve Time Verified A Shifts 1500 brute-force, two-pointers 1m 34s ✓ B Planets 1700 binary-search, data-structures, graphs 1m 37s ✓ C Triangles 1900 combinatorics, graphs, math 2m 5s ✓ D Towers 2100 dp, greedy, two-pointers 2m 55s ✓ E Gifts 2600 combinatorics, dp, math...

Practice › Codeforces Solutions ›

Codeforces Testing Round 4

Codeforces Testing Round 4 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1300-2500 | Time: 2m 45s Problem Name Rating Tags Solve Time Verified A Punctuation 1300 implementation, strings 1m 18s ✓ B Smile House 2500 binary-search, graphs, matrices 1m 27s ✓

Practice › Codeforces Solutions ›

Codeforces Round 167 (Div. 2)

Codeforces Round 167 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1400-2200 | Time: 5m 30s Problem Name Rating Tags Solve Time Verified B Dima and Sequence 1400 implementation, math 1m 30s ✓ C Dima and Staircase 1500 data-structures, implementation 1m 28s ✓ E Dima and Horses 2200 combinatorics, constructive-algorithms, graphs 2m 32s ✗

Practice › Codeforces Solutions › Codeforces Round 145 (Div. 1, ACM-ICPC Rules) ›

CF 240E - Road Repairs

CF 240E - Road Repairs Rating: 2800 Tags: dfs and similar, graphs, greedy Solve time: 1m 58s Verified: yes Solution Problem Understanding We have a directed graph of cities and roads. City 1 is the capital. Every road is either already usable or broken. A broken road may be repaired, after which it behaves like a normal directed edge. The government wants every city to become reachable from the capital....

Practice › Codeforces Solutions › Codeforces Round 109 (Div. 1) ›

CF 154C - Double Profiles

CF 154C - Double Profiles Rating: 2300 Tags: graphs, hashing, sortings Solve time: 1m 37s Verified: yes Solution Problem Understanding We are working with an undirected graph where each vertex represents a social network profile. Two profiles are considered "doubles" if every other profile sees them identically. For any third vertex k , either both i and j are connected to k , or neither is connected to k ....

Practice › Codeforces Solutions › Codeforces Round 237 (Div. 2) ›

CF 404C - Restore Graph

CF 404C - Restore Graph Rating: 1800 Tags: dfs and similar, graphs, sortings Solve time: 3m 31s Verified: no Solution Problem Understanding We are given a sequence of distances from a single unknown root vertex in an unknown undirected simple graph. Each vertex has a known shortest-path distance to that root, and we are also told that in the original graph every vertex had degree at most k. The task...

Practice › Codeforces Solutions › Codeforces Round 142 (Div. 1) ›

CF 229B - Planets

CF 229B - Planets Rating: 1700 Tags: binary search, data structures, graphs, shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given an undirected weighted graph of planets connected by stargates. Jack starts on planet 1 at time 0 and wants to reach planet n as early as possible. Moving through a stargate takes a fixed positive amount of time. The unusual part is the waiting...

Practice › Codeforces Solutions › Codeforces Round 181 (Div. 2) ›

CF 300B - Coach

CF 300B - Coach Rating: 1500 Tags: brute force, dfs and similar, graphs Solve time: 2m 18s Verified: yes Solution Problem Understanding We can think of the students as vertices of an undirected graph. Every friendship relation means two students must belong to the same team. Since each team has exactly three students, every connected component of this graph must fit entirely inside one team. The task is to partition...

Practice › Codeforces Solutions › Codeforces Round 139 (Div. 2) ›

CF 225D - Snake

CF 225D - Snake Rating: 2200 Tags: bitmasks, dfs and similar, graphs, implementation Solve time: 58s Verified: yes Solution Problem Understanding We are asked to simulate the movement of a snake on a small grid and determine the minimal number of moves required for the snake to reach an apple. The grid contains walls, empty squares, the snake itself, and one apple. The snake is represented as consecutive numbered segments...

Practice › Codeforces Solutions ›

Codeforces Round 189 (Div. 2)

Codeforces Round 189 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 0/1 | Rating range: 1500-1500 | Time: 3m 52s Problem Name Rating Tags Solve Time Verified B Ping-Pong (Easy Version) 1500 dfs-and-similar, graphs 3m 52s ✗

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 1)

Codeforces Round 124 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1100-2600 | Time: 6m 40s Problem Name Rating Tags Solve Time Verified A Lexicographically Maximum Subsequence 1100 greedy, strings 1m 2s ✓ B Infinite Maze 2000 dfs-and-similar, graphs 1m 39s ✓ C Paint Tree 2200 constructive-algorithms, divide-and-conquer, geometry 1m 40s ✗ E Opening Portals 2600 dsu, graphs, shortest-paths 2m 19s ✓

Practice › Codeforces Solutions ›

ABBYY Cup 2.0 - Easy

ABBYY Cup 2.0 - Easy Type: Special | Problems: 11 | Verified: 10/11 | Rating range: 800-2600 | Time: 24m 43s Problem Name Rating Tags Solve Time Verified A1 Good Matrix Elements 800 implementation 1m 37s ✗ A2 Good Matrix Elements 800 implementation 3m 13s ✓ B1 Rectangular Game 1000 number-theory 1m 36s ✓ B2 Rectangular Game 1200 number-theory 2m 20s ✓ C1 Party 1500 dfs-and-similar, dsu, graphs 3m 2s...

Practice › Codeforces Solutions ›

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) Type: ICPC/IOI | Problems: 4 | Verified: 3/4 | Rating range: 1900-2900 | Time: 7m 47s Problem Name Rating Tags Solve Time Verified D Numbers 2900 - 2m 21s ✗ E Flights 2600 graphs, shortest-paths 1m 54s ✓ F Race 2300 brute-force, implementation 2m 26s ✓ G Challenging Balloons 1900 constructive-algorithms 1m 6s ✓

Practice › Codeforces Solutions ›

VK Cup 2012 Round 3

VK Cup 2012 Round 3 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1700-3100 | Time: 9m 50s Problem Name Rating Tags Solve Time Verified A Variable, or There and Back Again 1700 dfs-and-similar, graphs 1m 51s ✓ B Ancient Berland Hieroglyphs 2000 two-pointers 1m 30s ✓ C Machine Programming 2400 flows, graphs 2m 16s ✓ D Minimum Diameter 3100 binary-search, brute-force 2m 18s ✗ E Polycarpus...

Practice › Codeforces Solutions › Codeforces Round 103 (Div. 2) ›

CF 144D - Missile Silos

CF 144D - Missile Silos Rating: 1900 Tags: data structures, dfs and similar, graphs, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph representing cities and roads. City s is the capital. A missile silo may be located either exactly on a city or at some interior point of a road. A position is valid if its shortest-path distance to...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232A - Cycles

CF 232A - Cycles Rating: 1600 Tags: binary search, constructive algorithms, graphs, greedy Solve time: 3m 45s Verified: yes Solution Problem Understanding We need to construct an undirected graph that contains exactly k triangles. A triangle means three different vertices where every pair is connected by an edge. The graph may contain any number of other structures, but the total number of triangles must be exactly k . We are...

Practice › Codeforces Solutions › Codeforces Round 150 (Div. 1) ›

CF 243B - Hydra

CF 243B - Hydra Rating: 2000 Tags: graphs, sortings Solve time: 3m 20s Verified: no Solution Problem Understanding We are given an undirected simple graph and two small integers $h$ and $t$. We are asked to determine whether inside this graph there exists a very specific structure consisting of two special vertices connected by an edge. One of these vertices acts as a central “chest” node, and the other acts...

Practice › Codeforces Solutions › Codeforces Round 149 (Div. 2) ›

CF 242D - Dispute

CF 242D - Dispute Rating: 2100 Tags: dfs and similar, graphs, greedy Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a graph of counters, where each counter starts at zero and is connected by undirected wires. Pressing a button on a counter increases its own value by one, and also increases the value of every directly connected neighbor by one. We are allowed to choose a...

Practice › Codeforces Solutions ›

Codeforces Round 150 (Div. 1)

Codeforces Round 150 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1600-3000 | Time: 11m 4s Problem Name Rating Tags Solve Time Verified A The Brand New Function 1600 bitmasks 1m 27s ✓ B Hydra 2000 graphs, sortings 3m 20s ✗ C Colorado Potato Beetle 2200 dfs-and-similar, implementation 1m 37s ✗ D Cubes 2700 data-structures, dp, geometry 3m 9s ✓ E Matrix 3000 data-structures...

Practice › Codeforces Solutions › Codeforces Round 148 (Div. 1) ›

CF 238E - Meeting Her

CF 238E - Meeting Her Rating: 2600 Tags: dp, graphs, shortest paths Solve time: 3m 19s Verified: no Solution Problem Understanding We are given a directed graph representing a city with junctions and streets. Urpal starts at junction a and wants to reach junction b using buses. Each bus is controlled by a company and at every second, it randomly chooses a shortest path from its start junction s_i to...

Practice › Codeforces Solutions › Codeforces Round 101 (Div. 2) ›

CF 141D - Take-off Ramps

CF 141D - Take-off Ramps Rating: 2300 Tags: graphs, shortest paths Solve time: 2m 15s Verified: yes Solution Problem Understanding We are moving on a one-dimensional track from position 0 to position L . Walking is simple, one meter costs exactly one second, and we may move in either direction as long as we never go below 0 . A ramp gives a shortcut, but using it has a strict...

Practice › Codeforces Solutions › Codeforces Round 182 (Div. 1) ›

CF 301B - Yaroslav and Time

CF 301B - Yaroslav and Time Rating: 2100 Tags: binary search, graphs, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a set of stations placed on a 2D grid. Moving between any two stations takes time proportional to their Manhattan distance multiplied by a constant factor $d$. Each station $i$ (except the first and last) provides a one-time bonus that increases our available time...

Practice › Codeforces Solutions ›

Codeforces Round 237 (Div. 2)

Codeforces Round 237 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 1000-1900 | Time: 12m 42s Problem Name Rating Tags Solve Time Verified A Valera and X 1000 implementation 4m 55s ✗ B Marathon 1500 implementation, math 2m 40s ✗ C Restore Graph 1800 dfs-and-similar, graphs, sortings 3m 31s ✗ D Minesweeper 1D 1900 dp, implementation 1m 36s ✗

Practice › Codeforces Solutions › RCC 2014 Warmup (Div. 2) ›

CF 417C - Football

CF 417C - Football Rating: 1400 Tags: constructive algorithms, graphs, implementation Solve time: 1m 49s Verified: yes Solution Problem Understanding We are asked to construct a complete record of matches between n teams, where every match has a winner and a loser, and no pair of teams plays more than once. The final condition we must satisfy is global: for every ordered pair of distinct teams (i, j) , team...

Practice › Codeforces Solutions ›

Codeforces Round 158 (Div. 2)

Codeforces Round 158 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 0/3 | Rating range: 1400-2100 | Time: 5m 48s Problem Name Rating Tags Solve Time Verified A Adding Digits 1400 implementation, math 1m 21s ✗ C Balls and Boxes 1700 constructive-algorithms, greedy, implementation 1m 20s ✗ D Black and White Tree 2100 constructive-algorithms, dsu, graphs 3m 7s ✗

Practice › Codeforces Solutions › Codeforces Round 114 (Div. 1) ›

CF 167D - Wizards and Roads

CF 167D - Wizards and Roads Rating: 3000 Tags: data structures, divide and conquer, graph matchings, graphs, greedy Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a set of cities on the plane. Every city has a unique x coordinate and a unique y coordinate. The first k cities are given explicitly, and the remaining cities are generated by two linear recurrences. For every query interval...

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 1

MemSQL start[c]up Round 1 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1500-2800 | Time: 6m 17s Problem Name Rating Tags Solve Time Verified A Square and Rectangles 1500 implementation 4m 20s ✓ E The Red Button 2800 combinatorics, dfs-and-similar, dsu 1m 57s ✓

Practice › Codeforces Solutions › Codeforces Round 165 (Div. 1) ›

CF 269C - Flawed Flow

CF 269C - Flawed Flow Rating: 2100 Tags: constructive algorithms, flows, graphs, greedy Solve time: 2m Verified: yes Solution Problem Understanding We are given an undirected graph where every edge already has a flow amount attached to it. The graph is supposed to represent a valid maximum flow from vertex 1 to vertex n , but the directions of the edges were lost. Our task is to recover directions for...

Practice › Codeforces Solutions › Codeforces Round 111 (Div. 2) ›

CF 160D - Edges in MST

CF 160D - Edges in MST Rating: 2300 Tags: dfs and similar, dsu, graphs, sortings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph with no loops or multiple edges. Each edge has a positive weight. The task is to classify each edge according to whether it belongs to all minimum spanning trees, at least one minimum spanning tree, or no minimum...

Practice › Codeforces Solutions ›

Codeforces Round 146 (Div. 1)

Codeforces Round 146 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1600-3000 | Time: 11m 16s Problem Name Rating Tags Solve Time Verified A LCM Challenge 1600 number-theory 3m 2s ✓ C Cyclical Quest 2700 data-structures, string-suffix-structures, strings 2m 55s ✓ D Graph Game 3000 graphs 1m 37s ✗ E Number Challenge 2600 combinatorics, dp, implementation 3m 42s ✓

Practice › Codeforces Solutions ›

Coder-Strike 2014 - Finals (online edition, Div. 1)

Coder-Strike 2014 - Finals (online edition, Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2600 | Time: 8m 34s Problem Name Rating Tags Solve Time Verified A Start Up 1000 implementation 1m 24s ✓ B Online Meeting 1800 implementation 2m 4s ✗ C Bug in Code 1900 data-structures, graphs, implementation 1m 57s ✓ D Cup Trick 2200 data-structures 1m 9s ✓ E Playing the...

Practice › Codeforces Solutions › Codeforces Round 122 (Div. 1) ›

CF 193A - Cutting Figure

CF 193A - Cutting Figure Rating: 1700 Tags: constructive algorithms, graphs, trees Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a rectangular grid where some cells are painted with # . All painted cells initially form one connected component using 4-directional adjacency, meaning movement is allowed only through shared sides. We may delete painted cells one by one. Deleting a cell removes it completely from the...

Practice › Codeforces Solutions › ABBYY Cup 3.0 - Finals (online version) ›

CF 331D2 - Escaping on Beaveractor

CF 331D2 - Escaping on Beaveractor Rating: 2600 Tags: graphs Solve time: 3m 7s Verified: no Solution Problem Understanding We have a square campus with coordinates from (0, 0) to (b, b) . Inside the campus there are several directed axis-aligned segments, called arrows. Each arrow is either horizontal or vertical, and the arrows never intersect or touch. A Beaveractor starts at some position with an initial direction. It moves...

Practice › Codeforces Solutions ›

Codeforces Round 165 (Div. 1)

Codeforces Round 165 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 2/4 | Rating range: 1700-3100 | Time: 7m 2s Problem Name Rating Tags Solve Time Verified B Greenhouse Effect 1700 dp 1m 21s ✓ C Flawed Flow 2100 constructive-algorithms, flows, graphs 2m ✓ D Maximum Waterfall 2600 data-structures, dp, graphs 1m 43s ✗ E String Theory 3100 geometry, math, strings 1m 58s ✗

Practice › Codeforces Solutions ›

Codeforces Round 252 (Div. 2)

Codeforces Round 252 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 1000-2400 | Time: 4m 27s Problem Name Rating Tags Solve Time Verified A Valera and Antique Items 1000 implementation 1m 21s ✓ D Valera and Swaps 2100 constructive-algorithms, dsu, graphs 1m 26s ✗ E Valera and Number 2400 bitmasks, dp, math 1m 40s ✗

Practice › Codeforces Solutions › Codeforces Round 130 (Div. 2) ›

CF 208C - Police Station

CF 208C - Police Station Rating: 1900 Tags: dp, graphs, shortest paths Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given an undirected, connected graph representing cities and roads. Every pair of cities is reachable, and each road has equal travel time. Among all pairs of cities, we are especially interested in shortest routes between city 1 and city n. Every shortest route is treated as equally...

Practice › Codeforces Solutions ›

Codeforces Round 188 (Div. 1)

Codeforces Round 188 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 3/3 | Rating range: 2300-3100 | Time: 5m 58s Problem Name Rating Tags Solve Time Verified C Balance 2500 constructive-algorithms, dfs-and-similar, graphs 2m 14s ✓ D Game with Powers 2300 dp, games 1m 58s ✓ E Princess and Her Shadow 3100 constructive-algorithms, shortest-paths 1m 46s ✓

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164C - Machine Programming

CF 164C - Machine Programming Rating: 2400 Tags: flows, graphs Solve time: 2m 16s Verified: yes Solution Problem Understanding We have several jobs, each with a start time, a duration, and a profit. A machine that starts a job stays occupied for the entire interval from s through s + t - 1 . At most k jobs may run simultaneously because we only own k machines. The goal is...

Practice › Codeforces Solutions › Codeforces Round 141 (Div. 2) ›

CF 228E - The Road to Berland is Paved With Good Intentions

CF 228E - The Road to Berland is Paved With Good Intentions Rating: 1900 Tags: 2-sat, dfs and similar, dsu, graphs Solve time: 1m 15s Verified: no Solution Problem Understanding We are asked to bring all roads in Berland to an asphalted state using a special operation. Each road connects two cities and has an initial state: asphalted or not. The only operation allowed is to pick a city, and...

Practice › Codeforces Solutions ›

Codeforces Round 122 (Div. 1)

Codeforces Round 122 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1700-2900 | Time: 8m 3s Problem Name Rating Tags Solve Time Verified A Cutting Figure 1700 constructive-algorithms, graphs, trees 1m 41s ✓ B Xor 2000 brute-force 1m 53s ✓ C Hamming Distance 2400 constructive-algorithms, greedy, math 2m 31s ✗ D Two Segments 2900 data-structures 1m 58s ✓

Practice › Codeforces Solutions › Codeforces Round 167 (Div. 2) ›

CF 272E - Dima and Horses

CF 272E - Dima and Horses Rating: 2200 Tags: combinatorics, constructive algorithms, graphs Solve time: 2m 32s Verified: no Solution Problem Understanding We are given an undirected graph where each vertex represents a horse and each edge represents mutual enmity. We must color every vertex with one of two colors, corresponding to the two parties, such that every horse has at most one enemy inside its own party. Rephrased in...

Practice › Codeforces Solutions › MemSQL start[c]up Round 1 ›

CF 325E - The Red Button

CF 325E - The Red Button Rating: 2800 Tags: combinatorics, dfs and similar, dsu, graphs, greedy Solve time: 1m 57s Verified: yes Solution Problem Understanding We are asked to construct a walk on a directed functional graph defined by a very specific transition rule. Each state is a node from 0 to n − 1. From a current node i, the next state is not arbitrary: it must be either...

Practice › Codeforces Solutions › Codeforces Round 142 (Div. 1) ›

CF 229C - Triangles

CF 229C - Triangles Rating: 1900 Tags: combinatorics, graphs, math Solve time: 2m 5s Verified: yes Solution Problem Understanding We start with a complete undirected graph on n vertices. Every pair of vertices has exactly one edge between them. Alice keeps m of those edges, and Bob receives all remaining edges. The task is to count how many triangles exist in Alice's graph plus how many triangles exist in Bob's...

Practice › Codeforces Solutions › Codeforces Round 244 (Div. 2) ›

CF 427C - Checkposts

CF 427C - Checkposts Rating: 1700 Tags: dfs and similar, graphs, two pointers Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given a directed graph where each node represents a city junction, and each directed edge represents a one-way road. Each junction has a cost to build a police checkpost. A checkpost at junction i protects all junctions reachable from i and able to return to i...

Practice › Codeforces Solutions ›

Codeforces Round 130 (Div. 2)

Codeforces Round 130 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 900-2100 | Time: 4m 49s Problem Name Rating Tags Solve Time Verified A Dubstep 900 strings 59s ✓ C Police Station 1900 dp, graphs, shortest-paths 1m 18s ✓ D Prizes, Prizes, more Prizes 1200 implementation 1m 26s ✓ E Blood Cousins 2100 binary-search, data-structures, dfs-and-similar 1m 6s ✓

Practice › Codeforces Solutions › Codeforces Round 149 (Div. 2) ›

CF 242C - King's Path

CF 242C - King's Path Rating: 1800 Tags: dfs and similar, graphs, hashing, shortest paths Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a huge implicit grid, up to $10^9 \times 10^9$, but only a small subset of cells are usable. Each usable region is given as a horizontal segment: a row number and a contiguous interval of columns. Taken together, these segments define a sparse...

Practice › Codeforces Solutions › Codeforces Round 245 (Div. 1) ›

CF 429E - Points and Segments

CF 429E - Points and Segments Rating: 3000 Tags: graphs Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a collection of segments on a number line. Each segment spans from a left endpoint to a right endpoint, and we must assign each segment one of two colors. Once the coloring is chosen, imagine picking any point on the line and looking at all segments that cover...

Practice › Codeforces Solutions › Codeforces Round 203 (Div. 2) ›

CF 350E - Wrong Floyd

CF 350E - Wrong Floyd Rating: 2200 Tags: brute force, constructive algorithms, dfs and similar, graphs Solve time: 2m 18s Verified: no Solution Problem Understanding We are given an undirected, simple, connected graph with a fixed number of vertices and edges. On top of that, a subset of vertices is marked. Someone runs a modified Floyd-Warshall process: instead of iterating all intermediate vertices from 1 to n, they only use...

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C1 - Party

CF 177C1 - Party Rating: 1500 Tags: dfs and similar, dsu, graphs Solve time: 3m 2s Verified: yes Solution Problem Understanding The problem asks us to choose the largest possible set of people to invite to a party, subject to two conditions. First, if a person is invited, all their friends must also be invited. Second, no two people in the invited set may dislike each other. Friendships and dislikes...

Practice › Codeforces Solutions › Codeforces Round 179 (Div. 1) ›

CF 295C - Greg and Friends

CF 295C - Greg and Friends Rating: 2100 Tags: combinatorics, dp, graphs, shortest paths Solve time: 2m 44s Verified: yes Solution Problem Understanding We are given a group of $n$ people standing on one river bank. Each person has a weight of either 50 or 100, and a boat that can carry a limited total weight $k$. Every time the boat crosses the river, it must carry at least one...

Practice › Codeforces Solutions ›

Codeforces Round 161 (Div. 2)

Codeforces Round 161 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 800-2000 | Time: 5m 38s Problem Name Rating Tags Solve Time Verified A Beautiful Matrix 800 implementation 1m 31s ✗ C Circle of Numbers 2000 brute-force, dfs-and-similar, implementation 1m 10s ✓ D Cycle in Graph 1800 dfs-and-similar, graphs 2m 57s ✗

Practice › Codeforces Solutions › Codeforces Round 108 (Div. 2) ›

CF 152E - Garden

CF 152E - Garden Rating: 2500 Tags: bitmasks, dp, graphs, trees Solve time: 2m 24s Verified: yes Solution Problem Understanding We have a rectangular grid where every cell has a cost, the number of flowers destroyed if we pave that cell with concrete. Among all cells, there are up to seven special cells containing important buildings. We must choose a connected set of paved cells such that every important cell...

Practice › Codeforces Solutions › Codeforces Round 154 (Div. 2) ›

CF 253C - Text Editor

CF 253C - Text Editor Rating: 1600 Tags: data structures, dfs and similar, graphs, greedy, shortest paths Solve time: 53s Verified: yes Solution Problem Understanding We are given a text editor that stores several lines of text. Each line has a known length, and the cursor is allowed to sit not only on characters but also in the gap positions before the first character and after the last character. So...

Practice › Codeforces Solutions › Codeforces Round 107 (Div. 1) ›

CF 150B - Quantity of Strings

CF 150B - Quantity of Strings Rating: 1600 Tags: combinatorics, dfs and similar, graphs, math Solve time: 1m 40s Verified: yes Solution Problem Understanding We want to count strings of length n built from an alphabet of size m , under one strong restriction: every substring of length k must be a palindrome. A substring of length k starting at position i contains characters $$s_i, s_{i+1}, \dots, s_{i+k-1}$$ and being...

Practice › Codeforces Solutions › Codeforces Round 161 (Div. 2) ›

CF 263D - Cycle in Graph

CF 263D - Cycle in Graph Rating: 1800 Tags: dfs and similar, graphs Solve time: 2m 57s Verified: no Solution Problem Understanding We are given an undirected graph where every vertex has a very strong local condition: each node is connected to at least $k$ other distinct nodes. From this structure we are asked to extract a simple cycle whose length is not just positive, but at least $k+1$. The...

Practice › Codeforces Solutions › Codeforces Round 114 (Div. 1) ›

CF 167E - Wizards and Bets

CF 167E - Wizards and Bets Rating: 2900 Tags: dfs and similar, graphs, math, matrices Solve time: 3m 52s Verified: yes Solution Problem Understanding We are given a directed acyclic graph. Some vertices are sources, meaning no edge enters them. Some vertices are sinks, meaning no edge leaves them. The number of sources and sinks is guaranteed to be equal. A valid configuration consists of vertex-disjoint directed paths such that...

Practice › Codeforces Solutions › Codeforces Round 134 (Div. 1) ›

CF 217A - Ice Skating

CF 217A - Ice Skating Rating: 1200 Tags: brute force, dfs and similar, dsu, graphs Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a set of snow drifts on a 2D grid. Bajtek can move from one snow drift to another by sliding along the rows or columns until he reaches another snow drift, moving strictly in the north, south, east, or west directions. The goal...

Practice › Codeforces Solutions ›

Codeforces Round 147 (Div. 2)

Codeforces Round 147 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 1000-2000 | Time: 9m 35s Problem Name Rating Tags Solve Time Verified A Free Cash 1000 implementation 3m 17s ✓ C Primes on Interval 1600 binary-search, number-theory, two-pointers 4m 4s ✓ D T-decomposition 2000 dfs-and-similar, graphs, greedy 2m 14s ✓

Practice › Codeforces Solutions ›

Codeforces Round 183 (Div. 1)

Codeforces Round 183 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-3000 | Time: 15m 59s Problem Name Rating Tags Solve Time Verified A Lucky Permutation Triple 1300 constructive-algorithms, implementation, math 2m 15s ✗ B Rectangle Puzzle II 1700 implementation, math 3m 45s ✓ C Minimum Modular 2400 brute-force, graphs, math 4m 56s ✓ D Rotatable Number 2600 math, number-theory 1m 56s ✓ E...

Practice › Codeforces Solutions › Codeforces Round 188 (Div. 1) ›

CF 317C - Balance

CF 317C - Balance Rating: 2500 Tags: constructive algorithms, dfs and similar, graphs, trees Solve time: 2m 14s Verified: yes Solution Problem Understanding We are given a network of containers, each holding some amount of water, and a set of bidirectional pipes connecting them. Each container has a fixed capacity, and water can be moved through a pipe in integer amounts as long as we never exceed any container’s capacity...

Practice › Codeforces Solutions ›

Friday the 13th, Programmers Day

Friday the 13th, Programmers Day Type: Special | Problems: 3 | Verified: 2/3 | Rating range: 1500-2700 | Time: 5m 36s Problem Name Rating Tags Solve Time Verified A Expecting Trouble 1500 *special, probabilities 1m 31s ✓ D Chain Letter 2200 *special, dfs-and-similar, graphs 2m 12s ✓ F Superstitions Inspection 2700 *special 1m 53s ✗

Practice › Codeforces Solutions › Codeforces Round 236 (Div. 2) ›

CF 402E - Strictly Positive Matrix

CF 402E - Strictly Positive Matrix Rating: 2200 Tags: graphs, math Solve time: 3m 37s Verified: no Solution Problem Understanding We are given a square matrix with non-negative integer entries. You can think of it as a weighted directed graph with n nodes where the entry a[i][j] tells you how strongly node i influences node j . The key operation in the problem is matrix multiplication, so a^k[i][j] represents the...

Practice › Codeforces Solutions ›

Codeforces Round 181 (Div. 2)

Codeforces Round 181 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1500-2300 | Time: 5m 24s Problem Name Rating Tags Solve Time Verified B Coach 1500 brute-force, dfs-and-similar, graphs 2m 18s ✓ D Painting Square 2300 dp, fft 1m 49s ✗ E Empire Strikes Back 2300 binary-search, math, number-theory 1m 17s ✓

Practice › Codeforces Solutions › April Fools Day Contest 2013 ›

CF 290F - Greedy Petya

CF 290F - Greedy Petya Rating: 2800 Tags: *special, dfs and similar, graphs, greedy Solve time: 1m 19s Verified: yes Solution Problem Understanding The statement is intentionally misleading. We are not asked to solve the Hamiltonian path problem ourselves. Instead, we must reproduce the output of Petya’s supposedly correct program. That changes the task completely. The graph is undirected and may contain repeated edges or self-loops. We receive up to...

Practice › Codeforces Solutions ›

Codeforces Round 109 (Div. 1)

Codeforces Round 109 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 4/4 | Rating range: 1600-2400 | Time: 6m 30s Problem Name Rating Tags Solve Time Verified A Hometask 1600 greedy 1m 15s ✓ B Colliders 1600 math, number-theory 2m 4s ✓ C Double Profiles 2300 graphs, hashing, sortings 1m 37s ✓ D Flatland Fencing 2400 games, math 1m 34s ✓

Practice › Codeforces Solutions › Codeforces Round 252 (Div. 2) ›

CF 441D - Valera and Swaps

CF 441D - Valera and Swaps Rating: 2100 Tags: constructive algorithms, dsu, graphs, implementation, math, string suffix structures Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a permutation, which we can think of as a row of numbered positions, where each position contains a distinct value from 1 to n. A swap operation exchanges two positions, and after a sequence of swaps we obtain another permutation....

Practice › Codeforces Solutions › Codeforces Round 192 (Div. 2) ›

CF 330B - Road Construction

CF 330B - Road Construction Rating: 1300 Tags: constructive algorithms, graphs Solve time: 1m 46s Verified: no Solution Problem Understanding We are working with a set of cities and we are allowed to build undirected roads between some pairs of them, except for a set of forbidden pairs that are explicitly given. The goal is to choose a set of roads so that every city can reach every other city...

Practice › Codeforces Solutions ›

Codeforces Round 151 (Div. 2)

Codeforces Round 151 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 900-1600 | Time: 4m 21s Problem Name Rating Tags Solve Time Verified A Buggy Sorting 900 constructive-algorithms, greedy, sortings 1m 8s ✓ C Beauty Pageant 1600 brute-force, constructive-algorithms, greedy 1m 43s ✓ D Colorful Graph 1600 brute-force, dfs-and-similar, graphs 1m 30s ✓

Practice › Codeforces Solutions ›

Codeforces Round 107 (Div. 1)

Codeforces Round 107 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1400-3000 | Time: 11m 8s Problem Name Rating Tags Solve Time Verified A Win or Freeze 1400 games, math, number-theory 2m 2s ✗ B Quantity of Strings 1600 combinatorics, dfs-and-similar, graphs 1m 40s ✓ C Smart Cheater 2200 data-structures, math, probabilities 2m 11s ✓ D Mission Impassable 2600 dp, strings 2m 26s ✓...

Practice › Codeforces Solutions › Codeforces Round 158 (Div. 2) ›

CF 260D - Black and White Tree

CF 260D - Black and White Tree Rating: 2100 Tags: constructive algorithms, dsu, graphs, greedy, trees Solve time: 3m 7s Verified: no Solution Problem Understanding We are given a tree whose structure has been erased, but two pieces of information remain attached to each vertex: its color and a number that equals the total weight of all edges incident to it in the original tree. Every edge connects vertices of...

Practice › Codeforces Solutions ›

Codeforces Round 145 (Div. 1, ACM-ICPC Rules)

Codeforces Round 145 (Div. 1, ACM-ICPC Rules) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 2600-2800 | Time: 3m 3s Problem Name Rating Tags Solve Time Verified E Road Repairs 2800 dfs-and-similar, graphs, greedy 1m 58s ✓ F TorCoder 2600 data-structures 1m 5s ✓

Practice › Codeforces Solutions › Codeforces Round 101 (Div. 2) ›

CF 141E - Clearing Up

CF 141E - Clearing Up Rating: 2300 Tags: constructive algorithms, dp, dsu, graphs Solve time: 2m 51s Verified: yes Solution Problem Understanding We are given an undirected graph where every edge already belongs to one of two categories. Roads marked "S" are narrow roads that the Elf clears, and roads marked "M" are wide roads that Santa clears. We must choose a subset of roads satisfying two conditions at the...

Practice › Codeforces Solutions ›

Codeforces Round 192 (Div. 2)

Codeforces Round 192 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 0/1 | Rating range: 1300-1300 | Time: 1m 46s Problem Name Rating Tags Solve Time Verified B Road Construction 1300 constructive-algorithms, graphs 1m 46s ✗

Practice › Codeforces Solutions ›

VK Cup 2012 Finals, Practice Session

VK Cup 2012 Finals, Practice Session Type: Special | Problems: 3 | Verified: 3/3 | Rating range: 1600-2400 | Time: 11m 47s Problem Name Rating Tags Solve Time Verified A Multicolored Marbles 1600 dp, math 5m 3s ✓ B Pixels 2100 constructive-algorithms, math 1m 41s ✓ C Trails and Glades 2400 constructive-algorithms, dsu, graphs 5m 3s ✓

Practice › Codeforces Solutions › CROC-MBTU 2012, Elimination Round (ACM-ICPC) ›

CF 245G - Suggested Friends

CF 245G - Suggested Friends Rating: 2200 Tags: brute force, graphs Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given an undirected social network where each user is identified by a string name and friendships are given as pairs of names. From these friendships we must determine, for every user, which non-friends are the most “similar” to them, where similarity is measured by the number of mutual...

Practice › Codeforces Solutions ›

Codeforces Round 203 (Div. 2)

Codeforces Round 203 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 1/4 | Rating range: 1200-2200 | Time: 17m 31s Problem Name Rating Tags Solve Time Verified A TL 1200 brute-force, greedy, implementation 6m 57s ✗ B Resort 1500 graphs 4m 28s ✗ C Bombs 1600 greedy, implementation, sortings 3m 48s ✓ E Wrong Floyd 2200 brute-force, constructive-algorithms, dfs-and-similar 2m 18s ✗

Practice › Codeforces Solutions › Codeforces Round 163 (Div. 2) ›

CF 266D - BerDonalds

CF 266D - BerDonalds Rating: 2400 Tags: graphs, math, shortest paths Solve time: 2m 9s Verified: no Solution Problem Understanding We are given a connected weighted undirected graph representing a road network. Junctions are graph vertices, roads are weighted edges, and the restaurant may be placed anywhere, not only at vertices but also at any point along an edge. For a chosen location, its quality is determined by the distance...

Practice › Codeforces Solutions › Codeforces Round 151 (Div. 2) ›

CF 246D - Colorful Graph

CF 246D - Colorful Graph Rating: 1600 Tags: brute force, dfs and similar, graphs Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given an undirected graph where each vertex has a color, represented by an integer. The goal is to determine which color has the most diverse set of neighboring colors. Formally, for each color $k$, we look at all vertices of that color and collect the...

Practice › Codeforces Solutions › Croc Champ 2012 - Round 1 ›

CF 173D - Deputies

CF 173D - Deputies Rating: 2500 Tags: constructive algorithms, graphs, greedy, implementation Solve time: 3m 4s Verified: yes Solution Problem Understanding We are asked to assign k deputies to n cities, with the condition that each deputy manages exactly three cities. The cities are placed on two sides of a river, and some pairs of cities are connected by bridges that span the river. No deputy may manage two cities...

Practice › Codeforces Solutions › Friday the 13th, Programmers Day ›

CF 345D - Chain Letter

CF 345D - Chain Letter Rating: 2200 Tags: *special, dfs and similar, graphs Solve time: 2m 12s Verified: yes Solution Problem Understanding We are asked to simulate the spread of a chain letter through a network of friends. Each person is represented as a node in a graph, and the connections between people-who sends letters to whom-are given as an adjacency matrix of "0" and "1" characters. The graph is...

Practice › Codeforces Solutions ›

Codeforces Round 185 (Div. 1)

Codeforces Round 185 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1300-2500 | Time: 7m 26s Problem Name Rating Tags Solve Time Verified A The Closest Pair 1300 constructive-algorithms, implementation 3m 3s ✓ B Cats Transport 2400 data-structures, dp 56s ✓ C Fetch the Treasure 2500 brute-force, data-structures, graphs 1m 7s ✓ E Biologist 2300 flows 2m 20s ✗

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164A - Variable, or There and Back Again

CF 164A - Variable, or There and Back Again Rating: 1700 Tags: dfs and similar, graphs Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given a directed graph where every node represents a program state. Each state does one of three things to a variable: 0 means the variable is ignored. 1 means the variable is assigned a new value. 2 means the variable is used. A...

Practice › Codeforces Solutions › Codeforces Round 203 (Div. 2) ›

CF 350B - Resort

CF 350B - Resort Rating: 1500 Tags: graphs Solve time: 4m 28s Verified: no Solution Problem Understanding We are given a directed structure on n objects representing a ski resort. Each object is either a mountain or a hotel. Every object has at most one outgoing ski track leading to another object, and a hotel never has outgoing tracks at all. This means each node has outdegree at most one,...

Practice › Codeforces Solutions ›

RCC 2014 Warmup (Div. 1)

RCC 2014 Warmup (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 2800-3100 | Time: 3m 33s Problem Name Rating Tags Solve Time Verified D Big Problems for Organizers 2800 data-structures, graphs, trees 1m 40s ✓ E Tricky Password 3100 data-structures 1m 53s ✗

Practice › Codeforces Solutions ›

VK Cup 2012 Finals (unofficial online-version)

VK Cup 2012 Finals (unofficial online-version) Type: Special | Problems: 5 | Verified: 1/5 | Rating range: 1500-3000 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Privatization 3000 flows, graphs 2m 20s ✗ B Polycarpus is Looking for Good Substrings 2300 bitmasks, hashing, implementation 1m 54s ✓ C Cowboys 2100 combinatorics, dp, math 1m 28s ✗ D Cutting a Fence 2500 binary-search, data-structures, dsu 1m 8s...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 1) ›

CF 196B - Infinite Maze

CF 196B - Infinite Maze Rating: 2000 Tags: dfs and similar, graphs Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a finite maze of size n × m . Some cells are walls, some are open, and one cell contains the starting position S . The maze is not used only once. Instead, the entire grid is repeated infinitely in every direction, like tiling the plane...

Practice › Codeforces Solutions › Codeforces Round 165 (Div. 1) ›

CF 269D - Maximum Waterfall

CF 269D - Maximum Waterfall Rating: 2600 Tags: data structures, dp, graphs, sortings Solve time: 1m 43s Verified: no Solution Problem Understanding We are asked to simulate a waterfall that flows from the top of a wall to the bottom across horizontal panels. Each panel is a horizontal segment at some height, spanning a range along the x-axis. Water can fall from one panel to a lower panel if their...

Practice › Codeforces Solutions ›

Codeforces Round 144 (Div. 1)

Codeforces Round 144 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 2/4 | Rating range: 1600-2900 | Time: 17m 15s Problem Name Rating Tags Solve Time Verified A Cycles 1600 binary-search, constructive-algorithms, graphs 3m 45s ✓ B Table 1900 bitmasks, combinatorics, dp 8m 46s ✗ C Doe Graphs 2600 constructive-algorithms, divide-and-conquer, dp 2m 23s ✓ D Fence 2900 binary-search, data-structures, string-suffix-structures 2m 21s ✗

Practice › Codeforces Solutions › Codeforces Round 155 (Div. 2) ›

CF 254D - Rats

CF 254D - Rats Rating: 2300 Tags: brute force, dfs and similar, graphs, implementation, shortest paths Solve time: 3m 1s Verified: no Solution Problem Understanding The problem presents a rectangular basement of a store as an n × m grid, where some cells are walls, some are empty, and some contain sleeping rats. Vasily has two grenades, and when a grenade explodes in a cell, its blast propagates outward to...

Practice › Codeforces Solutions › VK Cup 2012 Finals, Practice Session ›

CF 209C - Trails and Glades

CF 209C - Trails and Glades Rating: 2400 Tags: constructive algorithms, dsu, graphs, greedy Solve time: 5m 3s Verified: yes Solution Problem Understanding The park is an undirected multigraph. Glades are vertices, trails are edges. Self-loops are allowed, and multiple edges between the same pair of vertices are also allowed. Vasya wants to start at vertex 1, traverse every edge exactly once, and return to vertex 1. This is exactly...

Practice › Codeforces Solutions › Codeforces Round 241 (Div. 2) ›

CF 416E - President's Path

CF 416E - President's Path Rating: 2500 Tags: dp, graphs, shortest paths Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a graph with n cities connected by m bidirectional roads, each with a positive length. The goal is to determine, for every pair of cities (s, t) with s < t , how many roads can appear on at least one shortest path from s to...

Practice › Codeforces Solutions ›

Codeforces Round 117 (Div. 2)

Codeforces Round 117 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2200 | Time: 11m 48s Problem Name Rating Tags Solve Time Verified A Battlefield 2200 geometry, graphs, implementation 3m 47s ✓ B Vasya's Calendar 1000 implementation 3m 18s ✗ C Optimal Sum 2000 data-structures, greedy 1m 50s ✓ D Common Divisors 1400 brute-force, hashing, implementation 1m 36s ✓ E Wooden Fence 1800 dp...

Practice › Codeforces Solutions › Codeforces Round 121 (Div. 1) ›

CF 191D - Metro Scheme

CF 191D - Metro Scheme Rating: 2700 Tags: graphs, greedy Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given an undirected connected graph describing a subway system. Every edge is a tunnel, every vertex is a station. The graph is guaranteed to be a vertex cactus, meaning each vertex belongs to at most one simple cycle. The subway is composed of lines of two possible types. A...

Practice › Codeforces Solutions › Codeforces Round 123 (Div. 2) ›

CF 195E - Building Forest

CF 195E - Building Forest Rating: 2000 Tags: data structures, dsu, graphs Solve time: 1m 40s Verified: yes Solution Problem Understanding We build a directed weighted forest incrementally. Every vertex has at most one outgoing edge, so if we start from any vertex and repeatedly follow outgoing edges, we eventually reach a root. When vertex i is added, the input gives several pairs (v, x) . For every pair, we...

Practice › Codeforces Solutions › Codeforces Round 138 (Div. 1) ›

CF 223D - Spider

CF 223D - Spider Rating: 3000 Tags: geometry, graphs Solve time: 3m 42s Verified: no Solution Problem Understanding We are given a simple polygon whose vertices are listed in counterclockwise order. A spider starts at vertex s and wants to reach vertex t . The spider has two kinds of movement. The first move is walking along the polygon boundary. It may travel clockwise or counterclockwise, and the cost is...

Practice › Codeforces Solutions ›

Codeforces Round 244 (Div. 2)

Codeforces Round 244 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 7m 50s Problem Name Rating Tags Solve Time Verified A Police Recruits 800 implementation 1m 22s ✓ B Prison Transfer 1100 data-structures, implementation 1m 33s ✓ C Checkposts 1700 dfs-and-similar, graphs, two-pointers 1m 34s ✓ D Match & Catch 2200 dp, string-suffix-structures, strings 1m 27s ✓ E Police Patrol 2000...

Practice › Codeforces Solutions › Codeforces Round 117 (Div. 2) ›

CF 182A - Battlefield

CF 182A - Battlefield Rating: 2200 Tags: geometry, graphs, implementation, shortest paths Solve time: 3m 47s Verified: yes Solution Problem Understanding We are asked to simulate movement across a 2D plane from a starting point $A$ to a destination $B$ while avoiding a periodic laser. The laser alternates between charging and firing, with durations $a$ and $b$ seconds, respectively. During the firing phase, Vasya must be inside a trench to...

Practice › Codeforces Solutions › Coder-Strike 2014 - Finals (online edition, Div. 1) ›

CF 420C - Bug in Code

CF 420C - Bug in Code Rating: 1900 Tags: data structures, graphs, implementation, two pointers Solve time: 1m 57s Verified: yes Solution Problem Understanding Each participant in the company meeting points to two other people and claims that the culprit is one of those two. From this we can think of the input as an array of length $n$, where each index $i$ stores an unordered pair $(x_i, y_i)$. This...

Practice › Codeforces Solutions ›

Codeforces Round 238 (Div. 2)

Codeforces Round 238 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 900-2300 | Time: 15m 46s Problem Name Rating Tags Solve Time Verified A Gravity Flip 900 greedy, implementation, sortings 6m 21s ✗ B Domino Effect 1100 - 1m 23s ✗ C Unusual Product 1600 implementation, math 1m 27s ✗ E Graph Cutting 2300 dfs-and-similar, graphs 6m 35s ✗

Practice › Codeforces Solutions ›

Codeforces Round 134 (Div. 1)

Codeforces Round 134 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1200-2900 | Time: 12m 51s Problem Name Rating Tags Solve Time Verified A Ice Skating 1200 brute-force, dfs-and-similar, dsu 1m 15s ✓ C Formurosa 2600 divide-and-conquer, dp, expression-parsing 1m 20s ✓ D Bitonix' Patrol 2900 bitmasks, brute-force, combinatorics 3m 51s ✗ E Alien DNA 2800 data-structures, dsu, trees 6m 25s ✓

Practice › Codeforces Solutions › Codeforces Round 238 (Div. 2) ›

CF 405E - Graph Cutting

CF 405E - Graph Cutting Rating: 2300 Tags: dfs and similar, graphs Solve time: 6m 35s Verified: no Solution Problem Understanding We are given a connected undirected simple graph and we need to break its edge set into groups of three vertices, where each group forms a path of length two. Each such group corresponds to two adjacent edges sharing a middle vertex, so every output line describes a triple...

Practice › Codeforces Solutions ›

Codeforces Round 191 (Div. 2)

Codeforces Round 191 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1200-2300 | Time: 7m 2s Problem Name Rating Tags Solve Time Verified A Flipping Game 1200 brute-force, dp, implementation 4m 3s ✓ D Block Tower 1900 constructive-algorithms, dfs-and-similar, graphs 1m 34s ✗ E Axis Walking 2300 bitmasks, combinatorics, constructive-algorithms 1m 25s ✓

Practice › Codeforces Solutions ›

Codeforces Round 103 (Div. 2)

Codeforces Round 103 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 8m 5s Problem Name Rating Tags Solve Time Verified A Arrival of the General 800 implementation 1m 52s ✓ B Meeting 1300 implementation 1m 15s ✓ C Anagram Search 1500 implementation, strings 1m 23s ✓ D Missile Silos 1900 data-structures, dfs-and-similar, graphs 2m 10s ✓ E Competition 2200 data-structures, greedy...

Practice › Codeforces Solutions ›

RCC 2014 Warmup (Div. 2)

RCC 2014 Warmup (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1400-2400 | Time: 7m 19s Problem Name Rating Tags Solve Time Verified A Elimination 1500 dp, implementation, math 1m 39s ✓ B Crash 1400 implementation 1m 29s ✓ C Football 1400 constructive-algorithms, graphs, implementation 1m 49s ✓ D Cunning Gena 1900 bitmasks, dp, greedy 34s ✗ E Square Table 2400 constructive-algorithms, math, probabilities...

Practice › Codeforces Solutions ›

Codeforces Round 182 (Div. 1)

Codeforces Round 182 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1800-2800 | Time: 17m 11s Problem Name Rating Tags Solve Time Verified A Yaroslav and Sequence 1800 constructive-algorithms 1m 30s ✓ B Yaroslav and Time 2100 binary-search, graphs, shortest-paths 2m 10s ✓ C Yaroslav and Algorithm 2500 constructive-algorithms 6m 58s ✓ D Yaroslav and Divisors 2200 data-structures 2m 55s ✓ E Yaroslav and...

Practice › Codeforces Solutions › Codeforces Testing Round 5 ›

CF 267B - Dominoes

CF 267B - Dominoes Rating: 2000 Tags: dfs and similar, graphs Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a set of domino tiles, each with two numbers on its halves. The task is to arrange all dominoes in a sequence so that the touching halves of adjacent dominoes have the same number. A domino can be flipped, which swaps its two numbers. The output is...

Practice › Codeforces Solutions › RCC 2014 Warmup (Div. 1) ›

CF 418D - Big Problems for Organizers

CF 418D - Big Problems for Organizers Rating: 2800 Tags: data structures, graphs, trees Solve time: 1m 40s Verified: yes Solution Problem Understanding The task gives a tree of hotels, where every road connects two hotels and moving along a road costs one unit of time. For each query, two hotels are chosen as main event locations. Every other hotel assigns itself to whichever of these two main hotels is...

Practice › Codeforces Solutions › Codeforces Round 183 (Div. 1) ›

CF 303C - Minimum Modular

CF 303C - Minimum Modular Rating: 2400 Tags: brute force, graphs, math, number theory Solve time: 4m 56s Verified: yes Solution Problem Understanding We are given a set of distinct integers. We may delete at most k of them, where k ≤ 4 . After deleting, we want all remaining numbers to produce different remainders modulo some positive integer m . Two numbers collide modulo m exactly when their difference...

Practice › Codeforces Solutions › All-Ukrainian School Olympiad in Informatics ›

CF 76A - Gift

CF 76A - Gift Rating: 2200 Tags: dsu, graphs, sortings, trees Solve time: 2m 12s Verified: yes Solution Problem Understanding We have an undirected graph where every road has two thresholds attached to it. For a road with values (g, s) , the road becomes safe only if the king gives at least g gold coins and at least s silver coins to the bandits. The total payment cost is:...

Practice › Codeforces Solutions › Codeforces Beta Round 25 (Div. 2 Only) ›

CF 25C - Roads in Berland

CF 25C - Roads in Berland Rating: 1900 Tags: graphs, shortest paths Solve time: 58s Verified: yes Solution Problem Understanding We are given a map of n cities in Berland, where the shortest distances between all pairs are already known. Conceptually, this means the country is fully connected via some unknown set of roads, and the distance matrix is already the all-pairs shortest path result. The government plans to add...

Practice › Codeforces Solutions › Codeforces Beta Round 34 (Div. 2) ›

CF 34D - Road Map

CF 34D - Road Map Rating: 1600 Tags: dfs and similar, graphs Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a tree with n cities. Originally, city r1 is considered the capital, and for every other city we know its parent in the rooted tree. The value p[i] means that if we walk from the old capital toward city i , the last city before reaching...

Practice › Codeforces Solutions › Codeforces Beta Round 11 ›

CF 11D - A Simple Task

CF 11D - A Simple Task Rating: 2200 Tags: bitmasks, dp, graphs Solve time: 1m 29s Verified: yes Solution Problem Understanding We are asked to count the number of simple cycles in an undirected graph. A simple cycle is a closed loop where no vertex or edge is repeated. The input gives us the number of vertices n and the number of edges m , followed by m pairs of...

Practice › Codeforces Solutions ›

Codeforces Beta Round 8

Codeforces Beta Round 8 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1200-2600 | Time: 6m 59s Problem Name Rating Tags Solve Time Verified A Train and Peter 1200 strings 1m 17s ✓ B Obsession with Robots 1400 constructive-algorithms, graphs, implementation 56s ✓ C Looking for Order 2000 bitmasks, dp 1m 48s ✓ D Two Friends 2600 binary-search, geometry 1m 54s ✓ E Beads 2600 dp, graphs...

Practice › Codeforces Solutions ›

Codeforces Beta Round 94 (Div. 2 Only)

Codeforces Beta Round 94 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1200 | Time: 3m 59s Problem Name Rating Tags Solve Time Verified A Cookies 900 implementation 1m 44s ✓ B Students and Shoelaces 1200 brute-force, dfs-and-similar, graphs 2m 15s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 66 ›

CF 73D - FreeDiv

CF 73D - FreeDiv Rating: 2200 Tags: dfs and similar, graphs, greedy Solve time: 2m 38s Verified: yes Solution Problem Understanding We are given an undirected graph where cities are vertices and roads are edges. Each connected component of the graph is called a province. Vasya may additionally build tunnels between cities, but tunnels have two restrictions. First, every city can participate in at most one tunnel. Second, every province...

Practice › Codeforces Solutions ›

Manthan 2011

Manthan 2011 Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1800-2600 | Time: 9m 26s Problem Name Rating Tags Solve Time Verified A Partial Teacher 1800 dp, graphs, greedy 2m 6s ✓ B Restoration of the Permutation 1800 greedy 1m 59s ✓ C Sequence of Balls 2600 dp 1m 24s ✓ D Optical Experiment 1900 binary-search, data-structures, dp 1m 53s ✓ E Save the City! 2500 geometry...

Practice › Codeforces Solutions › Codeforces Beta Round 57 (Div. 2) ›

CF 61D - Eternal Victory

CF 61D - Eternal Victory Rating: 1800 Tags: dfs and similar, graphs, greedy, shortest paths, trees Solve time: 1m 29s Verified: yes Solution Problem Understanding We are asked to find the minimum distance Shapur must travel to visit all cities at least once. The cities are connected in a tree structure, meaning there are exactly $n-1$ bidirectional roads and a unique path between any two cities. Shapur starts at city...

Practice › Codeforces Solutions › School Personal Contest #2 (Winter Computer School 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules) ›

CF 46F - Hercule Poirot Problem

CF 46F - Hercule Poirot Problem Rating: 2300 Tags: dsu, graphs Solve time: 1m 1s Verified: yes Solution Problem Understanding We are given a house with a certain number of rooms connected by doors, and each door has a unique key. There are several residents in the house, each initially in some room with some keys. We also know the positions and key holdings of every resident at a later...

Practice › Codeforces Solutions › Codeforces Beta Round 23 ›

CF 23B - Party

CF 23B - Party Rating: 1600 Tags: constructive algorithms, graphs, math Solve time: 3m 27s Verified: yes Solution Problem Understanding We can think of the party as an undirected friendship graph. Every person is a vertex, and an edge means two people are friends. The process removes people in rounds. First, everyone with degree 0 leaves. After those removals, some remaining people may now have degree 1 , so they...

Practice › Codeforces Solutions › School Team Contest 3 (Winter Computer School 2010/11) ›

CF 45H - Road Problem

CF 45H - Road Problem Rating: 2100 Tags: graphs Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a connected undirected graph representing a road network. Every junction is a vertex, every road is an edge, and there is at most one edge between any pair of vertices. The city wants the final graph to satisfy a stronger connectivity condition: between every pair of junctions, there must...

Practice › Codeforces Solutions ›

Codeforces Beta Round 87 (Div. 1 Only)

Codeforces Beta Round 87 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 900-2600 | Time: 11m 15s Problem Name Rating Tags Solve Time Verified A Party 900 dfs-and-similar, graphs, trees 1m 51s ✓ B Lawnmower 1500 greedy, sortings 1m 30s ✓ C Plumber 2200 math 2m 56s ✗ D Unambiguous Arithmetic Expression 2600 dp, expression-parsing 2m 6s ✓ E Linear Kingdom Races 2400...

Practice › Codeforces Solutions › Codeforces Beta Round 29 (Div. 2, Codeforces format) ›

CF 29C - Mail Stamps

CF 29C - Mail Stamps Rating: 1700 Tags: data structures, dfs and similar, graphs, implementation Solve time: 1m 37s Verified: no Solution Problem Understanding Each stamp describes a direct transfer between two cities. If the envelope contains n stamps, then the letter passed through exactly n + 1 cities in sequence. The route never revisits a city, so the entire journey forms a simple path. The stamps are unordered. We...

Practice › Codeforces Solutions › Codeforces Beta Round 77 (Div. 1 Only) ›

CF 95E - Lucky Country

CF 95E - Lucky Country Rating: 2500 Tags: dp, dsu, graphs Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given a set of islands connected by bidirectional roads. The islands form regions: each region is a connected component, and islands in different regions have no path between them. A region is called lucky if the number of islands in it is a lucky number - a number...

Practice › Codeforces Solutions ›

Codeforces Alpha Round 20 (Codeforces format)

Codeforces Alpha Round 20 (Codeforces format) Type: Special | Problems: 3 | Verified: 3/3 | Rating range: 1700-2000 | Time: 4m 1s Problem Name Rating Tags Solve Time Verified A BerOS file system 1700 implementation 1m 20s ✓ B Equation 2000 math 1m 5s ✓ C Dijkstra? 1900 graphs, shortest-paths 1m 36s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 22 (Div. 2 Only) ›

CF 22C - System Administrator

CF 22C - System Administrator Rating: 1700 Tags: graphs Solve time: 1m 25s Verified: no Solution Problem Understanding We are asked to design a network of servers where each server is a node, and each connection between two servers is an undirected edge. There are n servers and we are allowed exactly m connections. One particular server, with index v , must be critical to the network: if it fails...

Practice › Codeforces Solutions ›

Codeforces Beta Round 33 (Codeforces format)

Codeforces Beta Round 33 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1200-2600 | Time: 18m 29s Problem Name Rating Tags Solve Time Verified A What is for dinner? 1200 greedy, implementation 3m 53s ✓ B String Problem 1800 shortest-paths 7m 1s ✓ C Wonderful Randomized Sum 1800 greedy 3m 6s ✓ D Knights 2000 geometry, graphs, shortest-paths 1m 32s ✓ E Helper 2600 -...

Practice › Codeforces Solutions › Codeforces Beta Round 58 ›

CF 62D - Wormhouse

CF 62D - Wormhouse Rating: 2300 Tags: dfs and similar, graphs Solve time: 2m 15s Verified: no Solution Problem Understanding We are given a connected graph representing rooms in Arnie’s apple house. Each room is a node, corridors between rooms are edges, and the graph has no self-loops or multiple edges between the same pair of rooms. Arnie previously gnawed out a path that starts and ends at the main...

Practice › Codeforces Solutions ›

Codeforces Beta Round 86 (Div. 2 Only)

Codeforces Beta Round 86 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1000-1500 | Time: 4m 17s Problem Name Rating Tags Solve Time Verified A Cifera 1000 math 1m 58s ✓ B PFAST Inc. 1500 bitmasks, brute-force, graphs 2m 19s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 48 ›

CF 51F - Caterpillar

CF 51F - Caterpillar Rating: 2800 Tags: dfs and similar, dp, graphs, trees Solve time: 2m 12s Verified: yes Solution Problem Understanding We start with an undirected graph that may be disconnected and may contain cycles. We are allowed to repeatedly merge two vertices into one. Merging decreases the number of vertices by one, while the number of edges stays unchanged. Parallel edges and loops may appear during the process....

Practice › Codeforces Solutions › Codeforces Beta Round 72 (Div. 1 Only) ›

CF 83C - Track

CF 83C - Track Rating: 2400 Tags: graphs, greedy, shortest paths Solve time: 2m 22s Verified: yes Solution Problem Understanding We have a rectangular grid. Each cell contains either a terrain type represented by a lowercase letter, the start cell S , or the target cell T . We may move in four directions between side-adjacent cells. Every move costs exactly one minute. The path must start at S and...

Practice › Codeforces Solutions › Codeforces Beta Round 22 (Div. 2 Only) ›

CF 22E - Scheme

CF 22E - Scheme Rating: 2300 Tags: dfs and similar, graphs, trees Solve time: 1m 48s Verified: yes Solution Problem Understanding Each person points to exactly one other person. If someone learns the news, they call the person they point to, who then calls the next person, and so on. We may add extra directed edges of the form x -> y , meaning person x must also call y...

Practice › Codeforces Solutions › Codeforces Beta Round 37 ›

CF 37E - Trial for Chief

CF 37E - Trial for Chief Rating: 2600 Tags: graphs, greedy, shortest paths Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a rectangular slab divided into an $N \times M$ grid of squares. Each square is either black or white in the final design, which is provided as input. The slab initially starts entirely white. Every day, a pretender can repaint a connected region of squares...

Practice › Codeforces Solutions › Codeforces Beta Round 8 ›

CF 8B - Obsession with Robots

CF 8B - Obsession with Robots Rating: 1400 Tags: constructive algorithms, graphs, implementation Solve time: 56s Verified: yes Solution Problem Understanding We are asked to analyze a robot's path on an infinite 2D grid. The robot can move up, down, left, or right, and its moves are recorded as a string of the characters U, D, L, R. The challenge is to determine whether there exists any possible arrangement of...

Practice › Codeforces Solutions › Codeforces Beta Round 75 (Div. 1 Only) ›

CF 91C - Ski Base

CF 91C - Ski Base Rating: 2300 Tags: combinatorics, dsu, graphs Solve time: 3m 29s Verified: yes Solution Problem Understanding We are asked to count the number of valid ski bases after each road is added to an initially empty graph. The graph consists of junctions as vertices and roads as edges. A valid ski base is any non-empty set of edges such that each connected component of the set...

Practice › Codeforces Solutions ›

Codeforces Beta Round 83 (Div. 1 Only)

Codeforces Beta Round 83 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1400-2700 | Time: 11m 41s Problem Name Rating Tags Solve Time Verified A Dorm Water Supply 1400 dfs-and-similar, graphs 2m 19s ✓ B Basketball Team 1600 combinatorics, dp, math 2m 22s ✓ C Arrangement 2400 bitmasks, dp 2m 35s ✓ D Crime Management 2400 dp, graphs, matrices 2m 6s ✓ E...

Practice › Codeforces Solutions › Manthan 2011 ›

CF 67A - Partial Teacher

CF 67A - Partial Teacher Rating: 1800 Tags: dp, graphs, greedy, implementation Solve time: 2m 6s Verified: yes Solution Problem Understanding We have a line of students, and for every adjacent pair we know only the relative order of their marks. If the relation character between positions i and i + 1 is: L , then student i must receive strictly more toffees than student i + 1 R ,...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Finals

Yandex.Algorithm 2011: Finals Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 2200-2700 | Time: 11m 24s Problem Name Rating Tags Solve Time Verified A Domino 2400 brute-force, implementation 2m 46s ✗ B Superset 2300 constructive-algorithms, divide-and-conquer 2m 12s ✓ C Winning Strategy 2400 binary-search, graphs, math 1m 44s ✓ D Robot in Basement 2700 bitmasks, brute-force, implementation 2m 39s ✓ E Leaders 2200 dfs-and-similar, dsu, graphs 2m...

Practice › Codeforces Solutions › Codeforces Beta Round 40 (Div. 2) ›

CF 41E - 3-cycles

CF 41E - 3-cycles Rating: 1900 Tags: constructive algorithms, graphs, greedy Solve time: 1m 48s Verified: no Solution Problem Understanding We need to build an undirected graph on n cities such that no triangle exists. A triangle means three distinct cities where every pair is directly connected. Among all graphs with no 3-cycles, we want the one with the maximum possible number of roads, and we must also print one...

Practice › Codeforces Solutions ›

Codeforces Beta Round 48

Codeforces Beta Round 48 Type: Beta | Problems: 6 | Verified: 4/6 | Rating range: 1300-2800 | Time: 13m 36s Problem Name Rating Tags Solve Time Verified A Cheaterius's Problem 1300 implementation 1m 37s ✓ B bHTML Tables Analisys 1700 expression-parsing 3m 37s ✓ C Three Base Stations 1800 binary-search, greedy 2m 13s ✗ D Geometrical problem 2200 implementation 1m 55s ✓ E Pentagon 2400 combinatorics, graphs, matrices 2m 2s...

Practice › Codeforces Solutions › Codeforces Beta Round 68 ›

CF 74C - Chessboard Billiard

CF 74C - Chessboard Billiard Rating: 2100 Tags: dfs and similar, dsu, graphs, number theory Solve time: 1m 36s Verified: yes Solution Problem Understanding We have an n × m chessboard. A billiard ball moves diagonally like a bishop, but unlike a bishop it reflects off the borders of the board. When it hits a vertical wall, the horizontal component of the direction flips. When it hits a horizontal wall,...

Practice › Codeforces Solutions › Codeforces Beta Round 24 ›

CF 24A - Ring road

CF 24A - Ring road Rating: 1400 Tags: graphs Solve time: 3m 36s Verified: yes Solution Problem Understanding The problem describes a country, Berland, with n cities arranged in a perfect ring. Originally, each city had two-way roads connecting it to its two neighbors, so it was trivial to travel from any city to any other. Now, each road has been converted into a one-way road, but the directions may...

Practice › Codeforces Solutions ›

Codeforces Beta Round 72 (Div. 1 Only)

Codeforces Beta Round 72 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1300-2800 | Time: 9m 17s Problem Name Rating Tags Solve Time Verified A Magical Array 1300 math 1m 28s ✓ B Doctor 1800 binary-search, math, sortings 1m 37s ✓ C Track 2400 graphs, greedy, shortest-paths 2m 22s ✓ D Numbers 2400 dp, math, number-theory 2m 7s ✓ E Two Subsequences 2800...

Practice › Codeforces Solutions › Codeforces Testing Round 3 ›

CF 134C - Swaps

CF 134C - Swaps Rating: 2200 Tags: constructive algorithms, graphs, greedy Solve time: 2m 15s Verified: no Solution Problem Understanding Each player initially owns cards of exactly one color, their own color. Player i starts with a[i] cards, all of color i . During a swap, two players exchange one card each. A player may only give away cards of their own color, and may never receive a color they...

Practice › Codeforces Solutions › School Team Contest 2 (Winter Computer School 2010/11) ›

CF 44F - BerPaint

CF 44F - BerPaint Rating: 2700 Tags: geometry, graphs Solve time: 2m 57s Verified: no Solution Problem Understanding We have a rectangular canvas of size W × H . Initially the whole canvas is white. Then several black line segments are drawn on it. After that, a sequence of flood-fill operations is applied. A flood-fill chooses a point and a color. Every point connected to the chosen point through regions...

Practice › Codeforces Solutions ›

Codeforces Beta Round 11

Codeforces Beta Round 11 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 900-2800 | Time: 8m 46s Problem Name Rating Tags Solve Time Verified A Increasing Sequence 900 constructive-algorithms, implementation, math 1m 24s ✓ B Jumping Jack 1600 math 1m 26s ✓ C How Many Squares? 2200 implementation 2m 42s ✓ D A Simple Task 2200 bitmasks, dp, graphs 1m 29s ✓ E Forward, march! 2800 binary-search,...

Practice › Codeforces Solutions › Codeforces Beta Round 9 (Div. 2 Only) ›

CF 9E - Interestring graph and Apples

CF 9E - Interestring graph and Apples Rating: 2300 Tags: dfs and similar, dsu, graphs Solve time: 1m 48s Verified: yes Solution Problem Understanding We start with an undirected multigraph. Multiple edges are allowed, and loops are also allowed. We may add new edges, and the goal is to transform the graph into a very specific structure. A graph is called interesting when every vertex belongs to exactly one cycle....

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Finals ›

CF 97C - Winning Strategy

CF 97C - Winning Strategy Rating: 2400 Tags: binary search, graphs, math, shortest paths Solve time: 1m 44s Verified: yes Solution Problem Understanding Each year the university sends a team of exactly n students to the finals. Some of those students may already have participated once before, and the rest are newcomers. If exactly i members already have previous finals experience, the probability of winning a medal that year is...

Practice › Codeforces Solutions › Codeforces Beta Round 27 (Codeforces format, Div. 2) ›

CF 27D - Ring Road 2

CF 27D - Ring Road 2 Rating: 2200 Tags: 2-sat, dfs and similar, dsu, graphs Solve time: 1m 30s Verified: yes Solution Problem Understanding We have a cycle of n cities arranged on a ring. Every pair of consecutive cities is already connected by the outer ring road, and city n is also connected back to city 1 . We are additionally given m new roads. Each new road connects...

Practice › Codeforces Solutions › Codeforces Beta Round 80 (Div. 1 Only) ›

CF 103B - Cthulhu

CF 103B - Cthulhu Rating: 1500 Tags: dfs and similar, dsu, graphs Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given an undirected graph and need to decide whether it matches a very specific structure. The graph should contain exactly one simple cycle, and every other vertex must belong to a tree attached to some vertex on that cycle. Another way to describe it is that the...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 1 ›

CF 85E - Guard Towers

CF 85E - Guard Towers Rating: 2600 Tags: binary search, dsu, geometry, graphs, sortings Solve time: 3m 41s Verified: yes Solution Problem Understanding We have n towers on a 2D plane. Every tower must belong to exactly one of two generals. For each general, the cost he demands is the maximum Manhattan distance between any two towers assigned to him. The king only pays the larger of the two costs....

Practice › Codeforces Solutions ›

Codeforces Beta Round 96 (Div. 1)

Codeforces Beta Round 96 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-2700 | Time: 9m 16s Problem Name Rating Tags Solve Time Verified A Turing Tape 1300 implementation 1m 39s ✓ B Piet 2100 implementation 1m 56s ✓ C Logo Turtle 1800 dp 1m 52s ✓ D Constants in the language of Shakespeare 2100 constructive-algorithms, dp, greedy 2m 2s ✗ E Bits of...

Practice › Codeforces Solutions ›

Codeforces Beta Round 25 (Div. 2 Only)

Codeforces Beta Round 25 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2200 | Time: 6m 12s Problem Name Rating Tags Solve Time Verified A IQ test 1300 brute-force 1m 7s ✓ B Phone numbers 1100 implementation 1m 24s ✓ C Roads in Berland 1900 graphs, shortest-paths 58s ✓ D Roads not only in Berland 1900 dsu, graphs, trees 1m 15s ✓ E...

Practice › Codeforces Solutions › School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules) ›

CF 48E - Ivan the Fool VS Gorynych the Dragon

CF 48E - Ivan the Fool VS Gorynych the Dragon Rating: 2100 Tags: dp, games, graphs Solve time: 2m 21s Verified: yes Solution Problem Understanding The game state is completely described by two numbers: how many heads and how many tails the dragon currently has. From a state (h, t) Ivan may choose one of two move types. If he cuts i heads, where 1 ≤ i ≤ n and...

Practice › Codeforces Solutions › Codeforces Beta Round 75 (Div. 1 Only) ›

CF 91D - Grocer's Problem

CF 91D - Grocer's Problem Rating: 2600 Tags: constructive algorithms, graphs, greedy Solve time: 2m 25s Verified: yes Solution Problem Understanding We are given a permutation of jars. Jar i should finally stand at position i , but the current arrangement is shuffled. One operation allows us to choose any subset of at most five positions and permute the jars inside those positions arbitrarily. The positions do not need to...

Practice › Codeforces Solutions › Codeforces Beta Round 25 (Div. 2 Only) ›

CF 25D - Roads not only in Berland

CF 25D - Roads not only in Berland Rating: 1900 Tags: dsu, graphs, trees Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a collection of n cities connected by n-1 roads. This means the current network forms a forest: a set of trees, because in graph terms, a connected tree with n nodes has exactly n-1 edges. The problem requires transforming this forest into a single...

Practice › Codeforces Solutions › Codeforces Beta Round 55 (Div. 2) ›

CF 59E - Shortest Path

CF 59E - Shortest Path Rating: 2000 Tags: graphs, shortest paths Solve time: 1m 18s Verified: yes Solution Problem Understanding We are asked to navigate a graph of cities connected by bidirectional roads, with a twist: certain sequences of three consecutive cities are forbidden due to superstition. Formally, there are n nodes and m edges, all unweighted, representing cities and roads. We start at city 1 and want to reach...

Practice › Codeforces Solutions ›

All-Ukrainian School Olympiad in Informatics

All-Ukrainian School Olympiad in Informatics Type: Special | Problems: 6 | Verified: 5/6 | Rating range: 1700-2700 | Time: 12m 33s Problem Name Rating Tags Solve Time Verified A Gift 2200 dsu, graphs, sortings 2m 12s ✓ B Mice 2100 greedy, two-pointers 1m 53s ✗ C Mutation 2700 bitmasks, dp, math 2m 6s ✓ D Plus and xor 1700 dp, greedy, math 1m 46s ✓ E Points 1700 implementation, math...

Practice › Codeforces Solutions › Codeforces Round 933 (Div. 3) ›

CF 1941G - Rudolf and Subway

CF 1941G - Rudolf and Subway Rating: 2000 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 1m 8s Verified: yes Solution Problem Understanding The problem describes a subway system as an undirected graph where each vertex is a station and each edge represents a direct connection between two stations. Every edge is labeled with a color representing the subway line it belongs to. All edges of the...

Practice › Codeforces Solutions › Codeforces Beta Round 73 (Div. 1 Only) ›

CF 87D - Beautiful Road

CF 87D - Beautiful Road Rating: 2300 Tags: dfs and similar, dp, dsu, graphs, implementation, sortings, trees Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a weighted tree with n cities and n - 1 roads. Every ordered pair of distinct cities represents one military campaign, so there are n * (n - 1) total trips. For a trip from city u to city v ,...

Practice › Codeforces Solutions › Codeforces Beta Round 87 (Div. 1 Only) ›

CF 115A - Party

CF 115A - Party Rating: 900 Tags: dfs and similar, graphs, trees Solve time: 1m 51s Verified: yes Solution Problem Understanding We are asked to organize a company party such that no group contains both a manager and their subordinate, directly or indirectly. The input describes each employee's immediate manager: a number from 1 to n , or -1 if they have no manager. Our goal is to compute the...

Practice › Codeforces Solutions ›

Codeforces Beta Round 57 (Div. 2)

Codeforces Beta Round 57 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2000 | Time: 14m 51s Problem Name Rating Tags Solve Time Verified A Ultra-Fast Mathematician 800 implementation 2m 4s ✓ B Hard Work 1300 strings 6m 35s ✓ C Capture Valerian 2000 math 2m 49s ✓ D Eternal Victory 1800 dfs-and-similar, graphs, greedy 1m 29s ✓ E Enemy is weak 1900 data-structures,...

Practice › Codeforces Solutions › Codeforces Beta Round 29 (Div. 2, Codeforces format) ›

CF 29E - Quarrel

CF 29E - Quarrel Rating: 2400 Tags: graphs, shortest paths Solve time: 1m 16s Verified: no Solution Problem Understanding We are asked to route two people, Bob and Alex, across a town represented as an undirected graph with n crossroads and m roads. Bob starts at node 1 and wants to reach node n , while Alex starts at node n and wants to reach node 1. Both must travel...

Practice › Codeforces Solutions › Codeforces Beta Round 33 (Codeforces format) ›

CF 33D - Knights

CF 33D - Knights Rating: 2000 Tags: geometry, graphs, shortest paths, sortings Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a map of Berland with several control points and circular fences. Each knight occupies a control point. Fences separate the kingdom into regions, and a knight must cross fences to move between control points. For multiple queries, we need to determine the minimum number of fences...

Practice › Codeforces Solutions › Codeforces Beta Round 83 (Div. 1 Only) ›

CF 107A - Dorm Water Supply

CF 107A - Dorm Water Supply Rating: 1400 Tags: dfs and similar, graphs Solve time: 2m 19s Verified: yes Solution Problem Understanding The houses and pipes form a directed graph with a very special structure. Every house can have at most one incoming pipe and at most one outgoing pipe. That restriction changes the graph from a general directed graph into a collection of independent chains. A house with outgoing...

Practice › Codeforces Solutions › Yandex.Algorithm Open 2011: Qualification 1 ›

CF 81E - Pairs

CF 81E - Pairs Rating: 2700 Tags: dfs and similar, dp, dsu, graphs, implementation, trees Solve time: 3m 30s Verified: no Solution Problem Understanding Each student points to exactly one other student, the person they consider their best friend. We may create a pair (a, b) only if either a chose b or b chose a . Every student can belong to at most one pair. Among all valid sets...

Practice › Codeforces Solutions › Codeforces Beta Round 70 (Div. 2) ›

CF 78E - Evacuation

CF 78E - Evacuation Rating: 2300 Tags: flows, graphs, shortest paths Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given a laboratory grid of size n × n , representing a research station where some tiles are reactors and others are laboratories. One reactor is malfunctioning and will explode, causing toxic coolant to spread to neighboring labs. Each laboratory contains some number of scientists and some number...

Practice › Codeforces Solutions › Codeforces Beta Round 96 (Div. 1) ›

CF 132E - Bits of merry old England

CF 132E - Bits of merry old England Rating: 2700 Tags: flows, graphs Solve time: 1m 47s Verified: no Solution Problem Understanding The task is to print a given sequence of integers using a limited number of variables and two operations: assigning a variable to an integer, and printing a variable. Each assignment carries a cost equal to the number of set bits in the assigned number, while printing is...

Practice › Codeforces Solutions › Codeforces Beta Round 8 ›

CF 8E - Beads

CF 8E - Beads Rating: 2600 Tags: dp, graphs Solve time: 1m 4s Verified: yes Solution Problem Understanding We are asked to generate a specific string of beads of length n according to a Martian’s unique notion of string equivalence. Each bead is either red (0) or blue (1). A Martian considers two strings identical if one can be turned into the other by rotating it (cyclic shifts) or by...

Practice › Codeforces Solutions ›

School Team Contest 2 (Winter Computer School 2010/11)

School Team Contest 2 (Winter Computer School 2010/11) Type: Special | Problems: 10 | Verified: 6/10 | Rating range: 900-2700 | Time: 21m 26s Problem Name Rating Tags Solve Time Verified A Indian Summer 900 implementation 1m 23s ✓ B Cola 1500 implementation 1m 9s ✓ C Holidays 1300 implementation 1m 24s ✓ D Hyperdrive 1800 math 1m 5s ✓ E Anfisa the Monkey 1400 dp 2m 13s ✗ F...

Practice › Codeforces Solutions › Codeforces Alpha Round 21 (Codeforces format) ›

CF 21D - Traveling Graph

CF 21D - Traveling Graph Rating: 2400 Tags: bitmasks, graph matchings, graphs Solve time: 42s Verified: yes Solution Problem Understanding We are given a weighted undirected graph with up to 15 vertices and up to 2000 edges. Each edge has a positive weight, and there may be multiple edges connecting the same pair of vertices or edges that loop back to the same vertex. The task is to find the...

Practice › Codeforces Solutions › Codeforces Beta Round 86 (Div. 2 Only) ›

CF 114B - PFAST Inc.

CF 114B - PFAST Inc. Rating: 1500 Tags: bitmasks, brute force, graphs Solve time: 2m 19s Verified: yes Solution Problem Understanding We are given a small group of people and a list of pairs who cannot work together. We need to choose the largest possible subset such that every pair inside the chosen group is compatible. This is naturally a graph problem. Think of each volunteer as a vertex. If...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Finals ›

CF 97E - Leaders

CF 97E - Leaders Rating: 2200 Tags: dfs and similar, dsu, graphs, trees Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given an undirected graph where vertices represent people and edges represent relationships. For every query (u, v) , we must decide whether there exists a simple path from u to v whose length is odd. The keyword here is "simple". We are not allowed to revisit...

Practice › Codeforces Solutions › Codeforces Beta Round 95 (Div. 2) ›

CF 131D - Subway

CF 131D - Subway Rating: 1600 Tags: dfs and similar, graphs Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a subway system of n stations connected by exactly n passages, each passage connecting two distinct stations. The system forms a connected graph where each station can reach every other station. By graph theory, a connected graph with n nodes and n edges contains exactly one cycle....

Practice › Codeforces Solutions › Codeforces Beta Round 83 (Div. 1 Only) ›

CF 107D - Crime Management

CF 107D - Crime Management Rating: 2400 Tags: dp, graphs, matrices Solve time: 2m 6s Verified: yes Solution Problem Understanding Zeyad wants to commit exactly n crimes in a sequence so that he avoids any punishment. Each crime type is represented by a capital letter, and for some crimes there are conditions describing multiplicities: committing that crime a number of times divisible by its multiplicity results in no punishment for...

Practice › Codeforces Solutions › Codeforces Beta Round 76 (Div. 2 Only) ›

CF 94B - Friends

CF 94B - Friends Rating: 1300 Tags: graphs, implementation, math Solve time: 1m 37s Verified: yes Solution Problem Understanding We have exactly five people. Some pairs of people know each other, and the input lists all such acquaintance relations. The task is to determine whether there exists either: Three people where every pair knows each other. Three people where no pair knows each other. This is naturally a graph problem....

Practice › Codeforces Solutions ›

Codeforces Beta Round 23

Codeforces Beta Round 23 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1200-2600 | Time: 11m 15s Problem Name Rating Tags Solve Time Verified A You're Given a String... 1200 brute-force, greedy 1m 55s ✓ B Party 1600 constructive-algorithms, graphs, math 3m 27s ✓ C Oranges and Apples 2500 constructive-algorithms, sortings 2m 29s ✓ D Tetragon 2600 geometry, math 2m 11s ✗ E Tree 2500 dp 1m...

Practice › Codeforces Solutions ›

Codeforces Beta Round 36

Codeforces Beta Round 36 Type: Beta | Problems: 5 | Verified: 2/5 | Rating range: 1300-2600 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Extra-terrestrial Intelligence 1300 implementation 1m 21s ✓ B Fractal 1600 implementation 1m 52s ✓ C Bowls 2200 geometry, implementation 2m 5s ✗ D New Game with a Chess Piece 2300 games 1m 43s ✗ E Two Paths 2600 constructive-algorithms, dsu, graphs 2m...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117C - Cycle

CF 117C - Cycle Rating: 2000 Tags: dfs and similar, graphs Solve time: 3m Verified: yes Solution Problem Understanding We are given a tournament graph, which is a special type of directed graph where for every pair of distinct vertices, there is exactly one directed edge connecting them. In other words, for any two vertices u and v , either there is an edge from u to v or from...

Practice › Codeforces Solutions › Codeforces Beta Round 14 (Div. 2) ›

CF 14D - Two Paths

CF 14D - Two Paths Rating: 1900 Tags: dfs and similar, dp, graphs, shortest paths, trees, two pointers Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given a tree of n cities, meaning each city is connected in such a way that there is exactly one simple path between any two cities. Roads are undirected, and each road has a length of 1. The task is to...

Practice › Codeforces Solutions › Codeforces Beta Round 28 (Codeforces format) ›

CF 28B - pSort

CF 28B - pSort Rating: 1600 Tags: dfs and similar, dsu, graphs Solve time: 1m 33s Verified: yes Solution Problem Understanding We start with an array where position i initially contains value i . Each position also has a fixed jump distance d[i] . A swap is allowed between positions i and j only if |i - j| = d[i] . The target array is a permutation. We must decide...

Practice › Codeforces Solutions ›

Codeforces Beta Round 95 (Div. 2)

Codeforces Beta Round 95 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 5/6 | Rating range: 1000-2000 | Time: 10m 6s Problem Name Rating Tags Solve Time Verified A cAPS lOCK 1000 implementation, strings 1m 16s ✓ B Opposites Attract 1200 implementation, math 1m 34s ✓ C The World is a Theatre 1400 combinatorics, math 1m 35s ✓ D Subway 1600 dfs-and-similar, graphs 1m 14s ✓ E Yet...

Practice › Codeforces Solutions › Codeforces Beta Round 94 (Div. 2 Only) ›

CF 129B - Students and Shoelaces

CF 129B - Students and Shoelaces Rating: 1200 Tags: brute force, dfs and similar, graphs, implementation Solve time: 2m 15s Verified: yes Solution Problem Understanding We can model the students and shoelaces as an undirected graph. Each student is a vertex, and every shoelace between two students is an edge. In one round, every student whose degree is exactly 1 gets removed at the same time. When those students leave,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 24

Codeforces Beta Round 24 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1400-2400 | Time: 11m 12s Problem Name Rating Tags Solve Time Verified A Ring road 1400 graphs 3m 36s ✓ B F1 Champions 1500 implementation 2m 19s ✓ C Sequence of points 1800 geometry, implementation, math 2m 35s ✓ D Broken robot 2400 dp, math, probabilities 1m 34s ✓ E Berland collider 2300 binary-search 1m...

Practice › Codeforces Solutions › Codeforces Beta Round 36 ›

CF 36E - Two Paths

CF 36E - Two Paths Rating: 2600 Tags: constructive algorithms, dsu, graphs, implementation Solve time: 2m 35s Verified: no Solution Problem Understanding Each paper describes an undirected edge between two cities. We are told that all papers came from exactly two travel journals. Inside one journal, the traveler wrote down the sequence of roads they traversed, and a road may appear multiple times because the traveler could reuse it. The...

Practice › Codeforces Solutions › Codeforces Alpha Round 20 (Codeforces format) ›

CF 20C - Dijkstra?

CF 20C - Dijkstra? Rating: 1900 Tags: graphs, shortest paths Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given an undirected weighted graph. Every edge connects two vertices and has a positive cost. The task is to start at vertex 1 , reach vertex n , and print one shortest path. If no route exists, we print -1 . The graph is large enough that we cannot...

Practice › Codeforces Solutions ›

Codeforces Beta Round 22 (Div. 2 Only)

Codeforces Beta Round 22 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 7m 39s Problem Name Rating Tags Solve Time Verified A Second Order Statistics 800 brute-force 1m 21s ✓ B Bargaining Table 1500 brute-force, dp 1m 40s ✓ C System Administrator 1700 graphs 1m 25s ✗ D Segments 1900 greedy, sortings 1m 25s ✓ E Scheme 2300 dfs-and-similar, graphs,...

Practice › Codeforces Solutions › Codeforces Beta Round 89 (Div. 2) ›

CF 118E - Bertown roads

CF 118E - Bertown roads Rating: 2000 Tags: dfs and similar, graphs Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a connected undirected graph representing the road network of Bertown, where junctions are nodes and roads are edges. Each road currently allows two-way traffic, but we are tasked with assigning a direction to every road such that the resulting directed graph remains strongly connected. Strong connectivity...

Practice › Codeforces Solutions ›

Codeforces Beta Round 29 (Div. 2, Codeforces format)

Codeforces Beta Round 29 (Div. 2, Codeforces format) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1000-2400 | Time: 6m 47s Problem Name Rating Tags Solve Time Verified A Spit Problem 1000 brute-force 1m 12s ✓ B Traffic Lights 1500 implementation 1m 23s ✓ C Mail Stamps 1700 data-structures, dfs-and-similar, graphs 1m 37s ✗ D Ant on the Tree 2000 constructive-algorithms, dfs-and-similar, trees 1m 19s ✓...

Practice › Codeforces Solutions › Codeforces Beta Round 74 (Div. 1 Only) ›

CF 89B - Widget Library

CF 89B - Widget Library Rating: 2300 Tags: dp, expression parsing, graphs, implementation Solve time: 2m 3s Verified: yes Solution Problem Understanding We are asked to simulate a tiny GUI layout system. There are three kinds of widgets. A plain Widget has a fixed width and height. HBox and VBox are container widgets that can store other widgets. An HBox places children horizontally, while a VBox places them vertically. Each...

Practice › Codeforces Solutions › Codeforces Beta Round 41 ›

CF 42E - Baldman and the military

CF 42E - Baldman and the military Rating: 2700 Tags: dfs and similar, graphs, trees Solve time: 3m 53s Verified: yes Solution Problem Understanding We are asked to prepare a set of additional undirected edges, called wormholes, on top of an unknown tunnel system. The military base has n objects. The tunnel graph is unknown to us, except for two guarantees: First, the tunnel graph is connected. Second, exactly two...

Practice › Codeforces Solutions ›

Codeforces Beta Round 80 (Div. 1 Only)

Codeforces Beta Round 80 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2900 | Time: 10m 20s Problem Name Rating Tags Solve Time Verified A Testing Pants for Sadness 1100 greedy, implementation, math 1m 39s ✓ B Cthulhu 1500 dfs-and-similar, dsu, graphs 1m 43s ✓ C Russian Roulette 1900 constructive-algorithms, greedy 2m ✓ D Time to Raid Cowavans 2100 brute-force, data-structures, sortings 1m...

Practice › Codeforces Solutions ›

Codeforces Beta Round 74 (Div. 1 Only)

Codeforces Beta Round 74 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1800-2900 | Time: 12m 50s Problem Name Rating Tags Solve Time Verified A Robbery 1800 greedy 1m 54s ✓ B Widget Library 2300 dp, expression-parsing, graphs 2m 3s ✓ C Chip Play 2300 brute-force, data-structures, implementation 2m 14s ✓ D Space mines 2500 geometry 4m 9s ✓ E Fire and Ice...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117E - Tree or not Tree

CF 117E - Tree or not Tree Rating: 2900 Tags: data structures, divide and conquer, graphs, implementation, trees Solve time: 3m 13s Verified: yes Solution Problem Understanding The graph has exactly n vertices and n edges. A connected graph with n vertices and n edges contains exactly one simple cycle. Every other edge belongs to a tree attached to that cycle. Initially every edge is turned off. A query picks...

Practice › Codeforces Solutions ›

Codeforces Beta Round 28 (Codeforces format)

Codeforces Beta Round 28 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1600-2800 | Time: 8m 33s Problem Name Rating Tags Solve Time Verified A Bender Problem 1600 implementation 1m 17s ✓ B pSort 1600 dfs-and-similar, dsu, graphs 1m 33s ✓ C Bath Queue 2200 combinatorics, dp, probabilities 1m 44s ✓ D Don't fear, DravDe is kind 2400 binary-search, data-structures, dp 1m 40s ✓ E...

Practice › Codeforces Solutions ›

Codeforces Beta Round 88

Codeforces Beta Round 88 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2900 | Time: 13m 35s Problem Name Rating Tags Solve Time Verified A Elevator 1300 implementation, math 2m 31s ✓ B Very Interesting Game 1800 brute-force, number-theory 2m 31s ✓ C Cycle 2000 dfs-and-similar, graphs 3m ✓ D Not Quick Transformation 2500 divide-and-conquer, math 2m 20s ✓ E Tree or not Tree 2900 data-structures, divide-and-conquer,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 76 (Div. 2 Only)

Codeforces Beta Round 76 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1300 | Time: 3m 35s Problem Name Rating Tags Solve Time Verified A Restoring Password 900 implementation, strings 1m 58s ✓ B Friends 1300 graphs, implementation, math 1m 37s ✓

Maths › 00. General Mathematics ›

04.5 Examples

4.5 Examples: Groups, Spaces, Graphs Structural thinking becomes clearer through examples. This section shows how the same principles appear in different areas. We focus on three domains: groups, topological spaces, and graphs. Each has its own objects, morphisms, invariants, and classification problems. 1. Groups A group is a set $G$ with a binary operation satisfying associativity, identity, and inverses. Objects and maps Objects: groups $(G, \ast)$ Morphisms: group homomorphisms $$...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Online Topological Sort

Online Topological Sort Online topological sort maintains an ordering of a directed acyclic graph while updates arrive over time. Unlike ordinary topological sort, the graph is not fixed before the algorithm starts. You use it when dependencies are discovered incrementally, such as build systems, schedulers, package managers, and dynamic workflow engines. Problem Given a directed graph ( G = (V, E) ), maintain an ordering ( \pi ) such that...

#graphs

CF 2217E - Definitely Larger

12.17 Edge-Disjoint Paths

12.9 Bipartite Matching

12.8 Max-Flow Min-Cut Theorem

12.15 Lower Bounds on Edges

12.25 Common Flow Modeling Patterns

12.1 Flow Networks

12.23 Complexity Analysis

12.4 Edmonds-Karp Algorithm

12.19 Project Selection

12.10 Hopcroft-Karp Algorithm

12.3 Ford-Fulkerson Algorithm

12.6 Push-Relabel Algorithm

12.24 Testing Flow Code

12.20 Image Segmentation with Graph Cuts

12.2 Residual Graphs

12.22 Correctness Proofs

12.21 Scheduling Applications

Chapter 12. Network Flow and Matching

12.5 Dinic's Algorithm

12.7 Minimum Cut

12.12 Hungarian Algorithm

12.16 Vertex Capacities

12.18 Vertex-Disjoint Paths

12.11 Assignment Problem

12.14 Circulation with Demands

12.13 Minimum-Cost Maximum-Flow

11.16 Sparse Graph Handling

11.10 Offline Connectivity

11.6 Borůvka's Algorithm

11.17 Dense Graph Handling

11.14 Clustering

11.13 Second-Best Spanning Tree

11.24 Common Bugs

11.2 Cut Property

11.21 Implementation Patterns

11.11 Dynamic Connectivity Overview

11.23 Choosing the Right MST Algorithm

11.22 Testing MST Code

11.7 Union-Find

11.15 Network Design

11.25 Case Study: Building a Production-Quality MST Service

11.1 Spanning Trees

11.20 Complexity Analysis

11.26 Practice Exercises

11.5 Prim's Algorithm

11.8 Path Compression

11.19 Correctness Proofs

11.18 Parallel and Distributed MST Algorithms

11.12 Minimum Bottleneck Spanning Trees

11.4 Kruskal's Algorithm

11.3 Cycle Property

Chapter 11. Minimum Spanning Trees and Connectivity

11.9 Union by Rank

10.6 Detecting Negative Cycles with Bellman-Ford

10.14 Using Distance Labels and Relaxation Correctly

10.2 Finding Shortest Paths with BFS

10.9 Computing Multi-Source Shortest Paths

10.23 Common Shortest-Path Patterns and Interview Problems

10.18 Solving Shortest Paths on Grids

10.11 Accelerating Search with A

10.12 Accelerating Searches with Bidirectional Search

10.15 Using Potentials to Reweight Graphs

10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm

10.21 Proving Correctness of Shortest-Path Algorithms

10.20 Choosing the Right Shortest-Path Algorithm

10.22 Analyzing Complexity of Shortest-Path Algorithms

10.13 Reconstructing Shortest Paths

10.25 Debugging and Optimizing Shortest-Path Code

10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search

10.5 Detecting Negative Edges with Bellman-Ford

10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm

10.19 Modeling State-Space Problems as Shortest Paths

10.7 Computing All-Pairs Shortest Paths with Floyd-Warshall

10.4 Implementing Dijkstra with Priority Queue Variants

10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS

10.8 Finding Shortest Paths in Directed Acyclic Graphs

10.24 Testing Shortest-Path Implementations

10.17 Finding K Shortest Paths