shortest-paths

Practice › Codeforces Solutions › Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine)) ›

CF 1558E - Down Below

CF 1558E - Down Below Rating: 3000 Tags: binary search, dfs and similar, graphs, greedy, meet-in-the-middle, shortest paths Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a graph of caves connected by tunnels, and a hero who starts at cave 1 with some initial power. Every other cave initially contains a monster. The hero’s task is to visit and defeat the monster in every cave at...

Practice › Codeforces Solutions › Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) ›

CF 1387C - Viruses

CF 1387C - Viruses Rating: 2900 Tags: *special, dp, shortest paths, string suffix structures Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a system where each “gene” is an integer label, and every gene greater than 1 can expand into a sequence of genes according to a fixed mutation rule. Starting from a single gene $x$, we repeatedly replace any non-terminal gene in the current sequence...

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

CF 1253F - Cheap Robot

CF 1253F - Cheap Robot Rating: 2500 Tags: binary search, dsu, graphs, shortest paths, trees Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a weighted undirected graph where a subset of nodes are “centrals”, meaning that whenever a robot arrives there its battery is instantly refilled to full capacity. The robot starts and must finish each query at a central node. Each edge has a weight,...

Practice › Codeforces Solutions › 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) ›

CF 1250I - Show Must Go On

CF 1250I - Show Must Go On Rating: 3100 Tags: binary search, brute force, greedy, shortest paths Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a list of dancers, each with a fixed awkwardness value. A “concert” is defined as choosing a subset of these dancers. Not all subsets are allowed: the total awkwardness of a chosen subset must not exceed a limit $k$. Among all...

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

CF 1202B - You Are Given a Decimal String...

CF 1202B - You Are Given a Decimal String... Rating: 1700 Tags: brute force, dp, shortest paths Solve time: 5m 33s Verified: no Solution Problem Understanding We are given a long decimal string that was produced as a subsequence of outputs from a very simple counter process. The counter always starts at value zero. At each step it prints the last digit of its current value, then increases the value...

Practice › Codeforces Solutions ›

Codeforces Round 483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

Codeforces Round 483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!] Div. 1 | 3 problems | 1/3 verified | Difficulty 1800-2800 | 5m 20s # Problem Rating Tags Accepted Time ✓ B XOR-pyramid 1800 dp 6,306 1m 20s ✓ C Elevator 2400 dp, graphs, shortest-paths 932 2m 11s E NN country 2800 binary-search, data-structures, trees 1,199 1m 49s

Practice › Codeforces Solutions › Codeforces Round 483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!] ›

CF 983C - Elevator

CF 983C - Elevator Rating: 2400 Tags: dp, graphs, shortest paths Solve time: 2m 11s Verified: no Solution Problem Understanding We are controlling a single elevator in a small building with nine floors, and we must serve a sequence of people in a fixed arrival order. Each person starts on some floor and wants to reach another floor. The elevator can carry at most four people at any time, and...

Practice › Codeforces Solutions ›

Codeforces Round 485 (Div. 1)

Codeforces Round 485 (Div. 1) Div. 1 | 3 problems | 3/3 verified | Difficulty 1600-3300 | 4m 10s # Problem Rating Tags Accepted Time ✓ A Fair 1600 graphs, greedy, number-theory 8,326 1m 26s ✓ B Petr and Permutations 1800 combinatorics, math 5,054 1m 18s ✓ F Oppa Funcan Style Remastered 3300 graphs, math, number-theory 743 1m 26s ✓

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

CF 986F - Oppa Funcan Style Remastered

CF 986F - Oppa Funcan Style Remastered Rating: 3300 Tags: graphs, math, number theory, shortest paths Solve time: 1m 26s Verified: yes Solution Problem Understanding We are asked whether it is possible to design a function on a very large set of positions, up to $10^{18}$, that behaves like a deterministic jump rule applied every second. Each position points to exactly one next position, and every element moves according to...

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

CF 986A - Fair

CF 986A - Fair Rating: 1600 Tags: graphs, greedy, number theory, shortest paths Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a connected undirected graph of towns. Each town produces exactly one type of goods, and there are at most 100 distinct types overall. For any pair of towns, moving goods between them costs the shortest-path distance in the graph, where each road has unit length....

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

CF 1004E - Sonya and Ice Cream

CF 1004E - Sonya and Ice Cream Rating: 2400 Tags: binary search, data structures, dp, greedy, shortest paths, trees Solve time: 2m 8s Verified: no Solution Problem Understanding We are given a weighted tree with up to $10^5$ vertices. Each edge has a positive length, so distances are standard shortest-path distances on the tree. We must choose a set of vertices that forms a single simple path in the tree,...

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

CF 1005F - Berland and the Shortest Paths

CF 1005F - Berland and the Shortest Paths Rating: 2100 Tags: brute force, dfs and similar, graphs, shortest paths Solve time: 3m 7s Verified: yes Solution Problem Understanding We are given a connected undirected graph of cities where city 1 is the capital. From this graph we must select exactly $n-1$ roads so that the selected edges still connect all cities, meaning they form a spanning tree. Among all spanning...

Practice › Codeforces Solutions › Manthan, Codefest 18 (rated, Div. 1 + Div. 2) ›

CF 1037D - Valid BFS?

CF 1037D - Valid BFS? Rating: 1700 Tags: dfs and similar, graphs, shortest paths, trees Solve time: 4m 53s Verified: no Solution Problem Understanding We are given a tree with vertices labeled from 1 to n, and a proposed ordering of all vertices. The task is to decide whether this ordering could arise from running a breadth-first search starting at vertex 1, under some valid choice of adjacency ordering. The...

Practice › Codeforces Solutions › Codeforces Round 519 by Botan Investments ›

CF 1043F - Make It One

CF 1043F - Make It One Rating: 2500 Tags: bitmasks, combinatorics, dp, math, number theory, shortest paths Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a multiset of positive integers, and we are allowed to choose any subset of these numbers. For a chosen subset, we compute the greatest common divisor of all selected elements. The goal is not to maximize this gcd, but instead to...

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

CF 1370F2 - The Hidden Pair (Hard Version)

CF 1370F2 - The Hidden Pair (Hard Version) Rating: 2700 Tags: binary search, dfs and similar, graphs, interactive, shortest paths, trees Solve time: 8m 8s Verified: no Solution Problem Understanding We are given a tree and two hidden distinct nodes inside it. We do not know which nodes they are, but we can interactively probe the tree by choosing any subset of nodes. For each subset, the system returns one...

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

CF 1343E - Weights Distributing

CF 1343E - Weights Distributing Rating: 2100 Tags: brute force, graphs, greedy, shortest paths, sortings Solve time: 2m 40s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each edge represents a road, but the roads do not yet have fixed costs. Instead, we are also given a list of prices, and we must assign exactly one price to each edge. After the assignment, Mike travels...

Practice › Codeforces Solutions › Codeforces Round 637 (Div. 1) - Thanks, Ivan Belonogov! ›

CF 1340C - Nastya and Unexpected Guest

CF 1340C - Nastya and Unexpected Guest Rating: 2400 Tags: dfs and similar, dp, graphs, shortest paths Solve time: 5m 29s Verified: no Solution Problem Understanding We are given a straight road modeled as integer points from 0 to n. Some of these points are special positions called safety islands, including both endpoints. Denis starts at 0 at time zero and wants to reach n as fast as possible. Time...

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

CF 1325E - Ehab's REAL Number Theory Problem

CF 1325E - Ehab's REAL Number Theory Problem Rating: 2600 Tags: brute force, dfs and similar, graphs, number theory, shortest paths Solve time: 8m 9s Verified: yes Solution Problem Understanding We are given a sequence of integers, and we want to select a subsequence whose product becomes a perfect square. Among all such subsequences, we need the minimum possible length. A product is a perfect square exactly when every prime...

Practice › Codeforces Solutions ›

Codeforces Round 625 (Div. 1, based on Technocup 2020 Final Round)

Codeforces Round 625 (Div. 1, based on Technocup 2020 Final Round) Div. 1 | 3 problems | 1/3 verified | Difficulty 1700-2500 | 10m 5s # Problem Rating Tags Accepted Time ✓ B Navigation System 1700 dfs-and-similar, graphs, shortest-paths 6,437 2m 48s ✓ C World of Darkraft: Battle for Azathoth 2000 brute-force, data-structures, sortings 3,426 2m 48s D Reachable Strings 2500 data-structures, hashing, strings 1,692 4m 29s

Practice › Codeforces Solutions › Codeforces Round 625 (Div. 1, based on Technocup 2020 Final Round) ›

CF 1320B - Navigation System

CF 1320B - Navigation System Rating: 1700 Tags: dfs and similar, graphs, shortest paths Solve time: 2m 48s Verified: yes Solution Problem Understanding We are given a directed graph where intersections are nodes and roads are one-way edges. We also know a fixed simple route Polycarp actually drives from his home to his work. This route is valid in the sense that every consecutive pair of intersections is connected by...

Practice › Codeforces Solutions › Codeforces Round 621 (Div. 1 + Div. 2) ›

CF 1307G - Cow and Exercise

CF 1307G - Cow and Exercise Rating: 3100 Tags: flows, graphs, shortest paths Solve time: 10m 57s Verified: no Solution Problem Understanding We are given a directed weighted graph with up to 50 vertices, representing fields connected by roads. A cow starts at node 1 and wants to reach node n, and the time it takes is determined by the shortest path in this graph. Now the twist: we are...

Practice › Codeforces Solutions › Codeforces Round 621 (Div. 1 + Div. 2) ›

CF 1307D - Cow and Fields

CF 1307D - Cow and Fields Rating: 1900 Tags: binary search, data structures, dfs and similar, graphs, greedy, shortest paths, sortings Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given an undirected, connected graph representing fields connected by roads. A traveler starts at node 1 and wants to reach node n using the shortest possible route. On top of the existing network, we are allowed to add...

Practice › Codeforces Solutions ›

Codeforces Round 611 (Div. 3)

Codeforces Round 611 (Div. 3) Div. 3 | 5 problems | 3/5 verified | Difficulty 900-2200 | 30m 30s # Problem Rating Tags Accepted Time ✓ B Candies Division 900 math 23,081 5m 8s ✓ C Friends and Gifts 1500 constructive-algorithms, data-structures, math 14,153 1m 32s ✓ D Christmas Trees 1800 graphs, greedy, shortest-paths 9,438 5m 22s E New Year Parties 1800 dp, greedy 7,325 11m 52s ✓ F DIY...

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

CF 1283D - Christmas Trees

CF 1283D - Christmas Trees Rating: 1800 Tags: graphs, greedy, shortest paths Solve time: 5m 22s Verified: no Solution Problem Understanding We are given a set of fixed points on a number line, each representing a Christmas tree. We are also asked to place another set of points representing people, but with a twist: each person contributes cost equal to the distance to the nearest tree, and we want to...

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

CF 1249E - By Elevator or Stairs?

CF 1249E - By Elevator or Stairs? Rating: 1700 Tags: dp, shortest paths Solve time: 5m 34s Verified: yes Solution Problem Understanding We are given a building with floors from 1 to n. Moving between adjacent floors can be done in two different ways: stairs or elevator. Stairs have per-floor costs a[i], and elevator has per-floor costs b[i] plus a fixed overhead c every time you start an elevator ride....

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

CF 1245E - Hyakugoku and Ladders

CF 1245E - Hyakugoku and Ladders Rating: 2300 Tags: dp, probabilities, shortest paths Solve time: 3m 29s Verified: no Solution Problem Understanding The game can be viewed as a directed line of states arranged along a fixed serpentine path on a 10 by 10 grid. Each cell corresponds to a position on this path, starting from the bottom-left cell and ending at the top-left cell. Movement along the path is...

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

CF 1245D - Shichikuji and Power Grid

CF 1245D - Shichikuji and Power Grid Rating: 1900 Tags: dsu, graphs, greedy, shortest paths, trees Solve time: 3m 18s Verified: no Solution Problem Understanding We are given a set of cities placed on a plane. Each city can be “powered” in one of two ways: either we directly build a power station in it, or we connect it (directly or indirectly through other cities) to a city that already...

Practice › Codeforces Solutions › Technocup 2020 - Elimination Round 3 ›

CF 1227E - Arson In Berland Forest

CF 1227E - Arson In Berland Forest Rating: 2200 Tags: binary search, graphs, shortest paths Solve time: 3m 41s Verified: no Solution Problem Understanding The input describes a finite rectangular snapshot of an otherwise infinite grid of trees. Each cell is either burned or intact, and the grid fully contains all burned cells. Outside the grid, everything is guaranteed to be unburned. We are told that the fire originally started...

Practice › Codeforces Solutions › Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] ›

CF 1218G - Alpha planetary system

CF 1218G - Alpha planetary system Rating: 3000 Tags: constructive algorithms, graphs, shortest paths Solve time: 4m 33s Verified: no Solution Problem Understanding We are given a network of spaceports connected by undirected shuttle routes. Each spaceport belongs to exactly one of three planets labeled X, Y, or Z. Every shuttle connects two different spaceports, and only connections between different planets exist. For every connection, we must assign a label...

Practice › Codeforces Solutions › Codeforces Round 584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2) ›

CF 1209F - Koala and Notebook

CF 1209F - Koala and Notebook Rating: 2600 Tags: data structures, dfs and similar, graphs, shortest paths, strings, trees Solve time: 4m 29s Verified: no Solution Problem Understanding We are given an undirected connected graph with up to 100,000 cities and roads, where each road has a unique identifier from 1 to m. Koala starts at city 1 and travels through the graph. Every time he traverses a road, he...

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

CF 1201E2 - Knightmare (hard)

CF 1201E2 - Knightmare (hard) Rating: 3000 Tags: graphs, interactive, shortest paths Solve time: 5m 52s Verified: no Solution Problem Understanding We are placed on an even-by-even grid, and two knights start on different squares. One is white, one is black. Each player controls exactly one knight and alternates moves, starting with the white side if we choose it. A move is standard knight movement. The game ends immediately when...

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

CF 1076D - Edge Deletion

CF 1076D - Edge Deletion Rating: 1800 Tags: graphs, greedy, shortest paths Solve time: 11m 46s Verified: yes Solution Problem Understanding We are given a weighted undirected graph and we first imagine running a shortest path computation from vertex 1. This produces a distance value for every vertex, which we can think of as the true optimal cost of reaching that vertex in the original graph. After this, we are...

Practice › Codeforces Solutions ›

2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)

2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) ICPC/IOI | 10 problems | 4/10 verified | Difficulty 1300-3000 | 1h 3m # Problem Rating Tags Accepted Time ✓ A Find a Number 2200 dp, graphs, number-theory 2,614 5m 57s ✓ B Berkomnadzor 2400 data-structures, greedy 678 10m 24s ✓ C Cloud Computing 2000 data-structures, greedy 2,294 6m 31s D Garbage Disposal 1300 greedy 5,233 5m 31s...

Practice › Codeforces Solutions › 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) ›

CF 1070A - Find a Number

CF 1070A - Find a Number Rating: 2200 Tags: dp, graphs, number theory, shortest paths Solve time: 5m 57s Verified: yes Solution Problem Understanding We are looking for a positive integer that satisfies two simultaneous constraints. First, it must be divisible by a given integer $d$. Second, when written in decimal form, the sum of its digits must equal a given value $s$. Among all such integers, we want the...

Practice › Codeforces Solutions ›

Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]

Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!] Div. 1 | 5 problems | 0/5 verified | Difficulty 1800-3100 | 37m 58s # Problem Rating Tags Accepted Time ✓ A Array Without Local Maximums 1900 dp 3,132 6m 9s B Multihedgehog 1800 dfs-and-similar, graphs, shortest-paths 2,860 9m 7s C Knights 2600 constructive-algorithms 714 8m 40s D Computer Game 3100 dp, greedy, math 491 5m 2s E Random Forest Rank 2800 dp,...

Practice › Codeforces Solutions › Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!] ›

CF 1067B - Multihedgehog

CF 1067B - Multihedgehog Rating: 1800 Tags: dfs and similar, graphs, shortest paths Solve time: 9m 7s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices and asked whether it can be generated by a very specific recursive construction parameterized by $k$. The construction starts from a special tree called a hedgehog, where exactly one vertex behaves as a central hub and all other vertices are...

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

CF 1051F - The Shortest Statement

CF 1051F - The Shortest Statement Rating: 2400 Tags: graphs, shortest paths, trees Solve time: 4m 7s Verified: yes Solution Problem Understanding We are given a connected undirected weighted graph with up to one hundred thousand vertices and edges, but with a crucial structural restriction: the number of edges exceeds the number of vertices by at most twenty. That means the graph is almost a tree, with only a small...

Practice › Codeforces Solutions ›

Codeforces Round 516 (Div. 1, by Moscow Team Olympiad)

Codeforces Round 516 (Div. 1, by Moscow Team Olympiad) Div. 1 | 6 problems | 2/6 verified | Difficulty 1300-3300 | 25m 19s # Problem Rating Tags Accepted Time ✓ A Oh Those Palindromes 1300 constructive-algorithms, strings 11,056 2m 42s ✓ B Labyrinth 1800 graphs, shortest-paths 9,230 2m 18s ✓ C Dwarves, Hats and Extrasensory Abilities 1900 binary-search, constructive-algorithms, geometry 3,280 3m 24s D Candies for Children 2600 brute-force, math...

Practice › Codeforces Solutions › Codeforces Round 516 (Div. 1, by Moscow Team Olympiad) ›

CF 1063B - Labyrinth

CF 1063B - Labyrinth Rating: 1800 Tags: graphs, shortest paths Solve time: 2m 18s Verified: yes Solution Problem Understanding The task places us on a grid maze where each cell is either open or blocked. We start from a given cell and can move in the four cardinal directions as long as we stay inside the grid and avoid obstacles. The twist is that horizontal movement is constrained: we can...

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

CF 1065D - Three Pieces

CF 1065D - Three Pieces Rating: 2200 Tags: dfs and similar, dp, shortest paths Solve time: 3m 34s Verified: yes Solution Problem Understanding We are given an $N \times N$ grid where every cell contains a unique number from $1$ to $N^2$. These numbers define a forced visiting order: we must start at the cell containing 1, then eventually reach the cell containing 2, then 3, and continue in increasing...

Practice › Codeforces Solutions › Avito Cool Challenge 2018 ›

CF 1081D - Maximum Distance

CF 1081D - Maximum Distance Rating: 1800 Tags: dsu, graphs, shortest paths, sortings Solve time: 2m 31s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph where edges have costs, and a subset of vertices is marked as special. Between any two vertices, we define their “distance” in a nonstandard way: instead of summing weights along a path, we consider the maximum edge weight along the...

Practice › Codeforces Solutions › Nebius Welcome Round (Div. 1 + Div. 2) ›

CF 1804F - Approximate Diameter

CF 1804F - Approximate Diameter Rating: 2700 Tags: binary search, divide and conquer, graphs, shortest paths Solve time: 3m 47s Verified: no Solution Problem Understanding We are given a connected, undirected graph with unit-length edges. The key quantity of interest is the graph diameter, which is the largest shortest-path distance between any pair of vertices. After that, a sequence of new edges is added one by one, and after each...

Practice › Codeforces Solutions › COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1725M - Moving Both Hands

CF 1725M - Moving Both Hands Rating: 1800 Tags: dp, graphs, shortest paths Solve time: 3m 2s Verified: yes Solution Problem Understanding We are given a directed weighted graph where every edge allows movement in only one direction and has a cost in time. Two tokens, or “hands”, start on different vertices: one is fixed at vertex 1, and the other starts at some vertex p. In each move, we...

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

CF 1712D - Empty Graph

CF 1712D - Empty Graph Rating: 2000 Tags: binary search, constructive algorithms, data structures, greedy, shortest paths Solve time: 3m 52s Verified: no Solution Problem Understanding We are given an array where each position represents a node in a line. Between any two indices $l$ and $r$, there is an edge whose weight is the minimum value in the subarray $a_l, \dots, a_r$. Since every pair of vertices is connected,...

Practice › Codeforces Solutions › Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) ›

CF 1654G - Snowy Mountain

CF 1654G - Snowy Mountain Rating: 2900 Tags: data structures, dfs and similar, graphs, greedy, shortest paths, trees Solve time: 4m 24s Verified: no Solution Problem Understanding We are given a tree where some vertices are marked as “base lodges”. Every vertex inherits a height equal to its distance from the nearest lodge. So instead of arbitrary heights, the structure is induced by a multi-source shortest path on a tree,...

Practice › Codeforces Solutions ›

ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ICPC/IOI | 13 problems | 2/13 verified | Difficulty 1200-3500 | 56m 12s # Problem Rating Tags Accepted Time ✓ A Anti-Tetris 2800 constructive-algorithms, graphs, shortest-paths 422 3m 52s B Building Forest Trails 2800 data-structures, dsu 475 4m 26s ✓ C Cactus Lady and her Cing 3500 13 6m 6s D Dragon Curve 3200 55 2m 10s...

Practice › Codeforces Solutions › ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1578A - Anti-Tetris

CF 1578A - Anti-Tetris Rating: 2800 Tags: constructive algorithms, graphs, shortest paths Solve time: 3m 52s Verified: no Solution Problem Understanding We are given a final board configuration of a grid-based stacking process where multiple small polyomino-like pieces were dropped one after another. Each piece is connected in four directions, has at most seven cells, and is identified by a letter. All cells with the same letter belong to the...

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

CF 1550F - Jumping Around

CF 1550F - Jumping Around Rating: 2700 Tags: binary search, data structures, divide and conquer, dp, dsu, graphs, shortest paths Solve time: 4m 7s Verified: yes Solution Problem Understanding We are given a sorted set of points on a number line, which we can think of as rocks placed at distinct integer coordinates. A frog starts on one designated rock and can repeatedly jump to other rocks. Each jump has...

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

CF 1547E - Air Conditioners

CF 1547E - Air Conditioners Rating: 1500 Tags: data structures, dp, implementation, shortest paths, sortings, two pointers Solve time: 7m 45s Verified: no Solution Problem Understanding We are given a one-dimensional strip of length $n$. Some positions on this strip contain air conditioners, each fixed at a known coordinate and each producing its own base temperature. Every other cell inherits a temperature determined by its distance to all air conditioners:...

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

CF 1536E - Omkar and Forest

CF 1536E - Omkar and Forest Rating: 2300 Tags: combinatorics, graphs, math, shortest paths Solve time: 6m 54s Verified: no Solution Problem Understanding We are given a grid where some cells are forced to be zero and the rest are flexible cells that may take any non-negative integer value. The final assignment of values must satisfy two local constraints: neighboring cells cannot differ by more than one in absolute value,...

Practice › Codeforces Solutions ›

Educational Codeforces Round 70 (Rated for Div. 2)

Educational Codeforces Round 70 (Rated for Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 1100-2700 | 20m 35s # Problem Rating Tags Accepted Time ✓ A You Are Given Two Binary Strings... 1100 bitmasks, greedy 10,718 7m 35s ✓ B You Are Given a Decimal String... 1700 brute-force, dp, shortest-paths 4,840 5m 33s C You Are Given a WASD-string... 2100 brute-force, data-structures, dp 2,768 1m 37s...

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

CF 1197E - Culture Code

CF 1197E - Culture Code Rating: 2300 Tags: binary search, combinatorics, data structures, dp, shortest paths, sortings Solve time: 7m 53s Verified: no Solution Problem Understanding We are given a collection of matryoshka dolls. Each doll has two parameters: an outer volume and an inner empty volume. A doll can be placed inside another if the outer volume of the inner doll does not exceed the inner volume of the...

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

CF 1196F - K-th Path

CF 1196F - K-th Path Rating: 2200 Tags: brute force, constructive algorithms, shortest paths, sortings Solve time: 4m 44s Verified: yes Solution Problem Understanding We are given an undirected weighted graph where every pair of vertices is connected by at least one path. Between any two vertices, there is a well-defined shortest path length. If we take every unordered pair of distinct vertices and compute the shortest distance between them,...

Practice › Codeforces Solutions › Helvetic Coding Contest 2019 online mirror (teams allowed, unrated) ›

CF 1184E2 - Daleks' Invasion (medium)

CF 1184E2 - Daleks' Invasion (medium) Rating: 2100 Tags: dfs and similar, graphs, shortest paths, trees Solve time: 10m 39s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each edge represents a corridor with a unique energy cost. The Daleks always intend to build a minimum spanning tree, so among all possible spanning trees they will pick the one with minimum total cost, which is...

Practice › Codeforces Solutions › Helvetic Coding Contest 2019 online mirror (teams allowed, unrated) ›

CF 1184B3 - The Doctor Meets Vader (Hard)

CF 1184B3 - The Doctor Meets Vader (Hard) Rating: 2700 Tags: flows, shortest paths Solve time: 5m 10s Verified: no Solution Problem Understanding We are working on a weighted selection problem over two interacting layers. First, there is a small fixed graph of planets, where distances are measured as the shortest number of wormholes between nodes. Then there is a large set of spaceships and bases placed on these planets....

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

CF 1176E - Cover it!

CF 1176E - Cover it! Rating: 1700 Tags: dfs and similar, dsu, graphs, shortest paths, trees Solve time: 10m 33s Verified: no Solution Problem Understanding We are given an undirected connected graph for each query, and we must select a subset of vertices such that every vertex we do not select has at least one selected neighbor. In other words, every unchosen vertex must be “covered” by an adjacent chosen...

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

CF 1163F - Indecisive Taxi Fee

CF 1163F - Indecisive Taxi Fee Rating: 3000 Tags: data structures, graphs, shortest paths Solve time: 4m 57s Verified: no Solution Problem Understanding We are given a weighted undirected graph with up to 200,000 vertices and edges. Each edge has a fixed weight, and we care about the shortest path from node 1 to node n using the sum of edge weights. The twist is that we are not solving...

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

CF 1106D - Lunar New Year and a Wander

CF 1106D - Lunar New Year and a Wander Rating: 1500 Tags: data structures, dfs and similar, graphs, greedy, shortest paths Solve time: 4m 40s Verified: yes Solution Problem Understanding We are given an undirected connected graph with $n$ nodes. Bob starts at node 1 and performs a walk along edges. Every time he enters a node that has never been seen before, he writes it down. The walk continues...

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

CF 1105D - Kilani and the Game

CF 1105D - Kilani and the Game Rating: 1900 Tags: dfs and similar, graphs, implementation, shortest paths Solve time: 5m 10s Verified: yes Solution Problem Understanding We are given a rectangular grid where each cell is either blocked, empty, or already owned by one of up to nine players. Each player starts with some initial castles placed on the grid, and each player also has a fixed expansion strength that...

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

CF 919F - A Game With Numbers

CF 919F - A Game With Numbers Rating: 2600 Tags: games, graphs, shortest paths Solve time: 5m 51s Verified: yes Solution Problem Understanding We are given a two-player game where Alice and Bob each hold 8 cards with numbers from 0 to 4. On a player’s turn, they select one of their cards with a non-zero number and one of the opponent’s cards with a non-zero number, add them modulo...

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

CF 916C - Jamie and Interesting Graph

CF 916C - Jamie and Interesting Graph Rating: 1600 Tags: constructive algorithms, graphs, shortest paths Solve time: 5m 35s Verified: no Solution Problem Understanding We are asked to construct an undirected weighted graph with exactly n vertices and m edges that satisfies two prime-related constraints. First, the length of the shortest path from vertex 1 to vertex n must be prime. Second, the sum of the edges in a minimum...

Practice › Codeforces Solutions › Hello 2018 ›

CF 913E - Logical Expression

CF 913E - Logical Expression Rating: 2400 Tags: bitmasks, dp, shortest paths Solve time: 3m 25s Verified: no Solution Problem Understanding We are working with Boolean functions of exactly three variables, x , y , and z . A Boolean function on three variables has only eight possible input assignments. The input gives the value of the function on each of those eight assignments as a binary string of length...

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

CF 912D - Fishes

CF 912D - Fishes Rating: 2100 Tags: data structures, graphs, greedy, probabilities, shortest paths Solve time: 5m 22s Verified: yes Solution Problem Understanding We have a rectangular pond of size n by m where each cell can hold at most one fish. Sasha has a square scoop of size r by r that can catch all fishes inside the square if its bottom-left corner is placed within the pond. Sasha...

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

CF 1140G - Double Tree

CF 1140G - Double Tree Rating: 2700 Tags: data structures, divide and conquer, shortest paths, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a graph on $2n$ vertices that is highly structured: vertices are split into odd and even indices, and each side forms a tree with the same shape. Every node $x$ in the odd layer has a corresponding node $x+1$ in the even...

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

CF 1183E - Subsequences (easy version)

CF 1183E - Subsequences (easy version) Rating: 2000 Tags: dp, graphs, implementation, shortest paths Solve time: 1m 40s Verified: yes Solution Problem Understanding We start with a string and want to build a set containing exactly k distinct subsequences. Adding a subsequence of length L costs the number of removed characters, which is n - L . The same subsequence cannot be added twice. The task is to minimize the...

Practice › Codeforces Solutions › Helvetic Coding Contest 2019 online mirror (teams allowed, unrated) ›

CF 1184B2 - The Doctor Meets Vader (Medium)

CF 1184B2 - The Doctor Meets Vader (Medium) Rating: 2200 Tags: flows, graph matchings, graphs, shortest paths, sortings Solve time: 2m 6s Verified: yes Solution Problem Understanding The galaxy is a small graph of planets connected by wormholes, where distance between planets is measured as the minimum number of edges in this graph. On top of this infrastructure, there are two kinds of actors: empire ships and rebel bases. Each...

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

CF 1201E1 - Knightmare (easy)

CF 1201E1 - Knightmare (easy) Rating: 2900 Tags: graphs, interactive, shortest paths Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a small chessboard and two knights placed on it. One knight is white and moves first, the other is black. On each turn, a player moves their own knight using standard knight moves. The interaction continues until one side wins or 350 moves are reached. Winning...

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

CF 1204C - Anna, Svyatoslav and Maps

CF 1204C - Anna, Svyatoslav and Maps Rating: 1700 Tags: dp, graphs, greedy, shortest paths Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a directed graph represented as an adjacency matrix, where each vertex has edges to other vertices, but no vertex has a loop to itself. Along with the graph, we are also given a path p as a sequence of vertex indices. This path...

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

CF 1205B - Shortest Cycle

CF 1205B - Shortest Cycle Rating: 1900 Tags: bitmasks, brute force, graphs, shortest paths Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a collection of integers, and we interpret each integer as a node in a graph. Two nodes are connected when their bitwise AND is non-zero, meaning they share at least one common bit set to 1. The task is to determine the length of...

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

CF 1301F - Super Jaber

CF 1301F - Super Jaber Rating: 2600 Tags: dfs and similar, graphs, implementation, shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a rectangular grid where every cell represents a city, and each city has one of a small number of colors. From any city, Jaber can move in one second either to one of the four adjacent cells or to any other cell anywhere...

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

CF 1304E - 1-Trees and Queries

CF 1304E - 1-Trees and Queries Rating: 2000 Tags: data structures, dfs and similar, shortest paths, trees Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices, where each vertex is connected such that there is exactly one path between any two vertices. Then we are asked multiple queries. Each query specifies two vertices $x$ and $y$ where we imagine adding a new...

Practice › Codeforces Solutions ›

Codeforces Round 581 (Div. 2)

Codeforces Round 581 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 900-2300 | Time: 22m 43s Problem Name Rating Tags Solve Time Verified A BowWow and the Timetable 1000 math 1m 55s ✓ B Mislove Has Lost an Array 900 greedy, math 2m 53s ✓ C Anna, Svyatoslav and Maps 1700 dp, graphs, greedy 1m 44s ✓ D1 Kirk and a Binary String (easy...

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

CF 1349C - Orac and Game of Life

CF 1349C - Orac and Game of Life Rating: 2000 Tags: dfs and similar, graphs, implementation, shortest paths Solve time: 12m 36s Verified: yes Solution Problem Understanding The grid evolves in discrete time. Each cell has one of two colors and updates simultaneously each step based only on its four neighbors. A cell looks at the current state. If none of its neighbors share its color, it stays unchanged. If...

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

CF 1360E - Polygon

CF 1360E - Polygon Rating: 1300 Tags: dp, graphs, implementation, shortest paths Solve time: 2m 9s Verified: yes Solution Problem Understanding We are given an $n \times n$ square matrix that starts entirely filled with zeros. Along the top edge, there are $n$ cannons, one above each column, and along the left edge, there are $n$ cannons, one to the left of each row. Each cannon shoots a "1" in...

Practice › Codeforces Solutions › Codeforces Global Round 10 ›

CF 1392G - Omkar and Pies

CF 1392G - Omkar and Pies Rating: 2900 Tags: bitmasks, dfs and similar, dp, math, shortest paths Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a very small binary “target state” of size $k \le 20$, representing pies placed in fixed positions. We also have an initial configuration of those pies and a desired configuration. There is a long sequence of operations, each operation being a...

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

CF 1393D - Rarity and New Dress

CF 1393D - Rarity and New Dress Rating: 2100 Tags: dfs and similar, dp, implementation, shortest paths Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a grid of characters where each cell represents a colored tile. From this grid we want to count how many “valid dress patterns” exist. A valid pattern is a rhombus shape whose sides are tilted at 45 degrees relative to the...

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

CF 1407E - Egor in the Republic of Dagestan

CF 1407E - Egor in the Republic of Dagestan Rating: 2500 Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, shortest paths Solve time: 1m 47s Verified: no Solution Problem Understanding We are asked to control Egor's travel through a directed graph of cities connected by roads of two types: night roads and morning roads. Each city can be assigned a color, black (night) or white (morning). Egor can leave...

Practice › Codeforces Solutions ›

Educational Codeforces Round 95 (Rated for Div. 2)

Educational Codeforces Round 95 (Rated for Div. 2) Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 1000-3000 | Time: 12m 59s Problem Name Rating Tags Solve Time Verified A Buying Torches 1000 math 1m 11s ✓ B Negative Prefixes 1300 greedy, sortings 2m ✗ C Mortal Kombat Tower 1500 dp, graphs, greedy 1m 31s ✓ D Trash Problem 2100 data-structures, implementation 4m 23s ✗ E Expected...

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

CF 1418C - Mortal Kombat Tower

CF 1418C - Mortal Kombat Tower Rating: 1500 Tags: dp, graphs, greedy, shortest paths Solve time: 1m 31s Verified: yes Solution Problem Understanding We are tasked with simulating a two-player cooperative challenge where bosses appear in a fixed order, and each boss is either easy or hard. The first player, your friend, cannot defeat hard bosses without consuming a skip point. Each session, a player must defeat either one or...

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

CF 1421D - Hexagons

CF 1421D - Hexagons Rating: 1900 Tags: brute force, constructive algorithms, greedy, implementation, math, shortest paths Solve time: 2m 5s Verified: no Solution Problem Understanding We are working on a hexagonal grid where each cell has six possible neighboring cells, one in each direction of the hexagon layout. Moving from any cell to an adjacent one has a fixed cost depending only on the direction of the move, not on...

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

CF 1422D - Returning Home

CF 1422D - Returning Home Rating: 2300 Tags: graphs, shortest paths, sortings Solve time: 3m 25s Verified: yes Solution Problem Understanding We are moving on an enormous grid. The starting cell is $(s_x,s_y)$ and the destination is $(f_x,f_y)$. Walking works normally: moving one cell horizontally or vertically costs one minute, so the cost of walking between two positions is Manhattan distance. There are also special locations. A special location $(x_i,y_i)$...

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

CF 1433G - Reducing Delivery Cost

CF 1433G - Reducing Delivery Cost Rating: 2100 Tags: brute force, graphs, shortest paths Solve time: 1m 7s Verified: yes Solution Problem Understanding We are asked to minimize the total delivery cost for couriers traveling along cheapest paths in a city network. The city is modeled as an undirected weighted graph with n districts as nodes and m two-way roads as edges, each with a positive cost. There are k...

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

CF 1437D - Minimal Height Tree

CF 1437D - Minimal Height Tree Rating: 1600 Tags: graphs, greedy, shortest paths, trees Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given a permutation of the vertices of a tree as they were visited by a breadth-first search starting from the root. The root is always vertex 1, and all children of a vertex are visited in increasing order. The task is to reconstruct any tree...

Practice › Codeforces Solutions › Codeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Final) ›

CF 1442C - Graph Transpositions

CF 1442C - Graph Transpositions Rating: 2400 Tags: dfs and similar, graphs, greedy, shortest paths Solve time: 6m 37s Verified: no Solution Thank you. Now I see exactly why the previous code is producing the wrong output. Let’s go carefully. Input 3 10 4 12 6 179 822 Expected output 10 4 179 Actual output 10 12 179 Diagnosis The code currently reads each line and assigns: a, b =...

Practice › Codeforces Solutions › Codeforces Global Round 12 ›

CF 1450E - Capitalism

CF 1450E - Capitalism Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a connected undirected graph where each vertex represents a person and each edge represents a friendship. The task is not to assign values arbitrarily, but to assign an integer income to every vertex so that every friendship satisfies a very rigid rule: along...

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

CF 1472G - Moving to the Capital

CF 1472G - Moving to the Capital Rating: 2100 Tags: dfs and similar, dp, graphs, shortest paths Solve time: 11m 29s Verified: no Solution Problem Understanding We are given a directed graph whose vertices are cities and whose root is city 1, the capital. For every city $v$, define $d[v]$ as the shortest path length from city 1 to $v$. These distances are fixed and known implicitly from the graph....

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

CF 1473E - Minimum Path

CF 1473E - Minimum Path Rating: 2400 Tags: graphs, shortest paths Solve time: 2m 42s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is three integers: 202...

Practice › Codeforces Solutions › Технокубок 2021 - Финал ›

CF 1482F - Useful Edges

CF 1482F - Useful Edges Rating: 2400 Tags: graphs, shortest paths Solve time: 3m 12s Verified: yes Solution Problem Understanding We are given an undirected weighted graph with up to 600 vertices and up to about 180,000 edges, where each edge has a positive weight. Then we are given a list of queries, each consisting of a pair of vertices $u$ and $v$ and a number $l$. An edge is...

Practice › Codeforces Solutions › Технокубок 2021 - Финал ›

CF 1482D - Playlist

CF 1482D - Playlist Rating: 1900 Tags: data structures, dsu, implementation, shortest paths Solve time: 2m 10s Verified: no Solution Problem Understanding We are asked to simulate a playlist with songs labeled by genres, where Arkady listens to songs in order, cycling back to the beginning when reaching the end. The rule is that if the genre of the last song Arkady listened to and the genre of the previous...

Practice › Codeforces Solutions ›

Codeforces Round 703 (Div. 2)

Codeforces Round 703 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 2/7 | Rating range: 900-2600 | Time: 19m 2s Problem Name Rating Tags Solve Time Verified A Shifting Stacks 900 greedy, implementation 1m 53s ✓ B Eastern Exhibition 1500 binary-search, geometry, shortest-paths 1m 53s ✓ C1 Guessing the Greatest (easy version) 1600 binary-search, interactive 3m 1s ✗ C2 Guessing the Greatest (hard version) 1900 binary-search, interactive 2m...

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

CF 1486E - Paired Payment

CF 1486E - Paired Payment Rating: 2200 Tags: binary search, brute force, constructive algorithms, dp, flows, graphs, shortest paths Solve time: 3m 5s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test...

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

CF 1486B - Eastern Exhibition

CF 1486B - Eastern Exhibition Rating: 1500 Tags: binary search, geometry, shortest paths, sortings Solve time: 1m 53s Verified: yes Solution Problem Understanding We are given several independent test cases. In each test case there is a set of points on a 2D grid, representing houses. The goal is to choose an integer coordinate for a new building such that the sum of Manhattan distances from this point to all...

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

CF 1487F - Ones

CF 1487F - Ones Rating: 2900 Tags: dp, greedy, shortest paths Solve time: 1m 33s Verified: yes Solution Problem Understanding We are asked to build a number equal to a given large integer using only building blocks that are themselves made entirely of digit ‘1’. Each building block is an integer like 1, 11, 111, 1111 and so on, and we are allowed to add or subtract these blocks. The...

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

CF 1495D - BFS Trees

CF 1495D - BFS Trees Rating: 2600 Tags: combinatorics, dfs and similar, graphs, math, shortest paths, trees Solve time: 1m 16s Verified: no Solution Problem Understanding We are asked to count, for every pair of vertices $i, j$ in an undirected connected graph, the number of spanning trees that simultaneously behave as BFS trees rooted at both $i$ and $j$. A BFS tree rooted at $s$ preserves the shortest distances...

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

CF 1503C - Travelling Salesman Problem

CF 1503C - Travelling Salesman Problem Rating: 2200 Tags: binary search, data structures, dp, greedy, shortest paths, sortings, two pointers Solve time: 11m 59s Verified: yes Solution Thank you for the detailed input. I can see exactly what’s going wrong. The previous solution was too naive : it returned YES whenever there was at least one 1 in a . That explains why test cases 3 and 5 failed -...

Practice › Codeforces Solutions ›

April Fools Day Contest 2021

April Fools Day Contest 2021 Type: April Fools | Problems: 9 | Verified: 6/9 | Rating range: 900-2600 | Time: 32m 41s Problem Name Rating Tags Solve Time Verified A Is it rated - 2 900 *special, implementation, interactive 7m 52s ✓ B DMCA 1600 *special, implementation, number-theory 5m 40s ✗ C Fibonacci Words 1400 *special, implementation 3m 11s ✓ D Xenolith? Hippodrome? 1800 *special, number-theory 2m 17s ✓ E...

Practice › Codeforces Solutions › April Fools Day Contest 2021 ›

CF 1505E - Cakewalk

CF 1505E - Cakewalk Rating: 1800 Tags: *special, greedy, implementation, shortest paths Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given a small rectangular cake divided into a grid of squares. Each square either has a berry or is empty. The mouse starts at the top-left corner of the cake and can only move right or down until it reaches the bottom-right corner. The goal is to...

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

CF 1506F - Triangular Paths

CF 1506F - Triangular Paths Rating: 2000 Tags: constructive algorithms, graphs, math, shortest paths, sortings Solve time: 2m 15s Verified: no Solution Problem Understanding We are working with an infinite triangular grid where each point is identified by coordinates $(r, c)$, with row $r$ containing $r$ nodes. Each node has exactly one outgoing directed edge going either down-left to $(r+1, c)$ or down-right to $(r+1, c+1)$. The direction is not...

Practice › Codeforces Solutions › Contest 2050 and Codeforces Round 718 (Div. 1 + Div. 2) ›

CF 1517D - Explorer Space

CF 1517D - Explorer Space Rating: 1800 Tags: dp, graphs, shortest paths Solve time: 1m 7s Verified: yes Solution Problem Understanding We are given a two-dimensional grid representing the explorer space at a conference. Each cell in the grid is a vertex, and each adjacent pair of vertices (up, down, left, right) is connected by an edge with a weight representing the number of exhibits along that edge. Walking along...

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

CF 1520G - To Go Or Not To Go?

CF 1520G - To Go Or Not To Go? Rating: 2200 Tags: brute force, dfs and similar, graphs, greedy, implementation, shortest paths Solve time: 2m 14s Verified: yes Solution Problem Understanding We are asked to find the minimum time for Dima to travel from the top-left corner of a rectangular city grid to the bottom-right corner. The city is represented as an n × m grid where each cell has...

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

CF 1528D - It's a bird! No, it's a plane! No, it's AaParsa!

CF 1528D - It's a bird! No, it's a plane! No, it's AaParsa! Rating: 2500 Tags: constructive algorithms, graphs, shortest paths Solve time: 2m 27s Verified: no Solution Problem Understanding We are asked to compute the shortest travel times between all pairs of cities in a land with $n$ cities, where each city contains at least one transport cannon. Each cannon launches you to a target city that rotates cyclically:...

Practice › Codeforces Solutions › Codeforces LATOKEN Round 1 (Div. 1 + Div. 2) ›

CF 1534E - Lost Array

CF 1534E - Lost Array Rating: 2300 Tags: graphs, greedy, interactive, shortest paths Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a hidden array of length n . We cannot see its elements directly, but we are allowed to ask queries. Each query chooses exactly k distinct positions, and the system returns the XOR of the values at those positions. Our goal is not to reconstruct...

Practice › Codeforces Solutions ›

Codeforces Round 728 (Div. 1)

Codeforces Round 728 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 0/6 | Rating range: 1400-3500 | Time: 33m 39s Problem Name Rating Tags Solve Time Verified A Great Graphs 1400 constructive-algorithms, graphs, greedy 3m 14s ✗ B Tree Array 2300 brute-force, combinatorics, dp 4m 3s ✗ C1 Converging Array (Easy Version) 2700 dp, math 8m 35s ✗ C2 Converging Array (Hard Version) 2900 dp, math 2m 33s...

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

CF 1540A - Great Graphs

CF 1540A - Great Graphs Rating: 1400 Tags: constructive algorithms, graphs, greedy, shortest paths, sortings Solve time: 3m 14s Verified: no Solution Problem Understanding We are given a farm with $n$ pastures and one-way roads between them. Each road has a travel time, which can be negative. Farmer John remembers only the shortest travel times from pasture 1 to every other pasture. Our task is to construct a road network...

Practice › Codeforces Solutions › Codeforces Global Round 16 ›

CF 1566G - Four Vertices

CF 1566G - Four Vertices Rating: 3100 Tags: constructive algorithms, data structures, graphs, greedy, implementation, shortest paths Solve time: 1m 59s Verified: yes Solution Problem Understanding We are working with a weighted undirected graph that changes over time by edge insertions and deletions. After every modification, including the initial state, we must look at all pairs of vertices and imagine the shortest path distance between each pair. From these pairwise...

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

CF 1579F - Array Stabilization (AND version)

CF 1579F - Array Stabilization (AND version) Rating: 1700 Tags: brute force, graphs, math, number theory, shortest paths Solve time: 5m 47s Verified: no Solution Problem Understanding We are given an array consisting only of zeroes and ones, and a positive integer d that specifies a cyclic right shift. In each step, the array is transformed by shifting it to the right by d positions and taking the bitwise AND...

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

CF 1580E - Railway Construction

CF 1580E - Railway Construction Rating: 3400 Tags: brute force, constructive algorithms, data structures, graphs, shortest paths Solve time: 4m 10s Verified: no Solution Problem Understanding We are given a network of railway stations in Gensokyo, connected by two-way railways with positive lengths. The stations are numbered from 1 to $n$, with station 1 being the main hub. The network is fully connected, so every station is reachable from any...

Practice › Codeforces Solutions › Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1) ›

CF 1599G - Shortest path

CF 1599G - Shortest path Rating: 2700 Tags: brute force, geometry, math, shortest paths Solve time: 2m 25s Verified: no Solution Problem Understanding We are given a set of points on a plane. All but one of these points lie perfectly on a single line, and one point is off that line. You start at a specified point and need to visit every point at least once, moving along straight...

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

CF 1601B - Frog Traveler

CF 1601B - Frog Traveler Rating: 1900 Tags: data structures, dfs and similar, dp, graphs, shortest paths, two pointers Solve time: 2m 18s Verified: yes Solution Problem Understanding The well has depths from 0 to n , where 0 is the ground and n is the starting position of the frog. Suppose the frog is currently resting at depth i . From there it chooses a jump length between 0...

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

CF 1611E1 - Escape The Maze (easy version)

CF 1611E1 - Escape The Maze (easy version) Rating: 1700 Tags: dfs and similar, greedy, shortest paths, trees, two pointers Solve time: 3m 33s Verified: yes Solution Problem Understanding The maze is an undirected tree rooted at room 1. Vlad starts at room 1 and wants to reach any leaf node that is not room 1. A leaf is any node with exactly one adjacent corridor. At the same time,...

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

CF 1611E2 - Escape The Maze (hard version)

CF 1611E2 - Escape The Maze (hard version) Rating: 1900 Tags: dfs and similar, dp, greedy, shortest paths, trees Solve time: 2m 23s Verified: yes Solution Problem Understanding We are given a tree of rooms. Vlad starts from room 1 and tries to escape by reaching any leaf node that is not room 1. A leaf is a room with exactly one corridor. At the same time, several friends are...

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

CF 1612F - Armor and Weapons

CF 1612F - Armor and Weapons Rating: 2800 Tags: brute force, dp, greedy, shortest paths Solve time: 3m 12s Verified: yes Solution Problem Understanding In this problem, Monocarp starts with the weakest armor and weapon, labeled 1. He can spend one hour to acquire a new armor set or weapon, but there is a catch: to obtain the $k$-th armor or weapon, he must already possess some armor and weapon...

Practice › Codeforces Solutions › Codeforces Global Round 18 ›

CF 1615H - Reindeer Games

CF 1615H - Reindeer Games Rating: 3000 Tags: binary search, constructive algorithms, data structures, divide and conquer, flows, graphs, shortest paths Solve time: 5m 18s Verified: no Solution 1. What the input really is Your input: 4 2 1 7 3 1 5 4 4 12345678 87654321 20211218 23571113 9 1 2 3 4 18 19 5 6 7 Structure: t = 4 Each test case: one integer n one...

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

CF 1617E - Christmas Chocolates

CF 1617E - Christmas Chocolates Rating: 2700 Tags: dfs and similar, dp, games, graphs, implementation, math, number theory, shortest paths, trees Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a box of chocolates, each with a distinct type represented by a non-negative integer. Icy wants to make at least one pair of chocolates have the same type, but before any exchanges, she chooses two chocolates, say...

Practice › Codeforces Solutions › Hello 2022 ›

CF 1621H - Trains and Airplanes

CF 1621H - Trains and Airplanes Rating: 3500 Tags: dfs and similar, graphs, shortest paths, trees Solve time: 48s Verified: yes Solution Problem Understanding We are given a connected undirected graph with n nodes. Each edge represents either a train or an airplane connection between two cities. Trains have a travel cost of 1, and airplanes have a travel cost of 0. The goal is to compute, for every city,...

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

CF 1627F - Not Splitting

CF 1627F - Not Splitting Rating: 2700 Tags: geometry, graphs, greedy, implementation, shortest paths Solve time: 5m 38s Verified: no Solution Diagnosis The original algorithm I suggested XORs all cells (i+j)%2==0 excluding the bottom-right diagonal . This produces the wrong result because it is misapplying the standard trick for this problem. The correct approach comes from observing the XOR-sum properties : Each cell a[i][j] contributes to the XOR of its...

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

CF 1627E - Not Escaping

CF 1627E - Not Escaping Rating: 2200 Tags: data structures, dp, implementation, shortest paths, two pointers Solve time: 1m 57s Verified: no Solution Problem Understanding The building can be viewed as a layered grid where each floor is a row of rooms. Moving horizontally inside a floor has a cost proportional to how far you walk and a floor-specific penalty factor, while moving vertically is only possible through directed ladders...

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

CF 1632E2 - Distance Tree (hard version)

CF 1632E2 - Distance Tree (hard version) Rating: 2700 Tags: binary search, dfs and similar, shortest paths, trees Solve time: 1m 49s Verified: no Solution Problem Understanding We start with a tree of unit edges, rooted at vertex 1. The distance function $d(v)$ is simply the number of edges from node 1 to node $v$. So the quantity we care about initially is the height of the tree when rooted...

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

CF 1632E1 - Distance Tree (easy version)

CF 1632E1 - Distance Tree (easy version) Rating: 2400 Tags: binary search, data structures, dfs and similar, graphs, shortest paths, trees Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a tree where every edge has weight 1, and we treat vertex 1 as the root. For every vertex, we define its distance as the shortest path length from vertex 1. The tree is initially fixed, but...

Practice › Codeforces Solutions › Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics) ›

CF 1648D - Serious Business

CF 1648D - Serious Business Rating: 2800 Tags: data structures, divide and conquer, dp, implementation, shortest paths Solve time: 2m 28s Verified: no Solution This problem is rated 3500 and its solution relies on a fairly deep structural characterization of graphs whose cycle space admits a consistent cyclic orientation. Producing a correct editorial requires reconstructing the full proof and construction, not merely explaining a known implementation trick. I do not...

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

CF 1650G - Counting Shortcuts

CF 1650G - Counting Shortcuts Rating: 2100 Tags: data structures, dfs and similar, dp, graphs, shortest paths Solve time: 1m 31s Verified: no Solution Problem Understanding We are asked to count paths in an undirected graph from a start vertex s to a target t whose lengths are either exactly the shortest distance or exceed it by at most one. The graph has n vertices and m edges, with no...

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

CF 1651D - Nearest Excluded Points

CF 1651D - Nearest Excluded Points Rating: 1900 Tags: binary search, data structures, dfs and similar, graphs, shortest paths Solve time: 1m 29s Verified: no Solution Problem Understanding We are given a set of distinct integer lattice points on a 2D grid. For each of these points, we want to “escape” to the nearest grid point that is not part of the input set, where distance is measured in Manhattan...

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

CF 1661B - Getting Zero

CF 1661B - Getting Zero Rating: 1300 Tags: bitmasks, brute force, dfs and similar, dp, graphs, greedy, shortest paths Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a list of integers, each less than 32768, and the goal is to reduce each number to zero using two operations: either increment the number by one modulo 32768 or double it modulo 32768. The input specifies the number...

Practice › Codeforces Solutions › SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1662F - Antennas

CF 1662F - Antennas Rating: - Tags: data structures, dfs and similar, graphs, implementation, shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a line of antennas indexed from left to right. Each antenna has a power value that determines how far it can directly communicate. Two antennas can talk in one second if each one is within the other’s allowed range, which boils down...

Practice › Codeforces Solutions › 2021-2022 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 1666J - Job Lookup

CF 1666J - Job Lookup Rating: 2100 Tags: constructive algorithms, dp, shortest paths, trees Solve time: 1m 46s Verified: no Solution Problem Understanding We are asked to organize a team of n members into a binary search tree (BST) hierarchy that minimizes communication cost. Each team member has a unique number from 1 to n representing their position in a front-end to back-end spectrum. The input gives a symmetric n...

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

CF 1681E - Labyrinth Adventures

CF 1681E - Labyrinth Adventures Rating: 2600 Tags: data structures, dp, matrices, shortest paths Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a labyrinth structured as concentric layers in an $n \times n$ grid. Each layer is a contiguous set of cells surrounding the previous layer. The first layer is just the bottom-left corner. Every subsequent layer is connected to the previous by exactly two doors:...

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

CF 1681D - Required Length

CF 1681D - Required Length Rating: 1700 Tags: brute force, dfs and similar, dp, hashing, shortest paths Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given an integer x and a target length n . We can repeatedly choose any digit y from the current number x and multiply x by y . The goal is to make x have exactly n digits using the minimum number...

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

CF 1689D - Lena and Matrix

CF 1689D - Lena and Matrix Rating: 1900 Tags: data structures, dp, geometry, shortest paths Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a grid of size $n \times m$, where each cell is either black or white. Our task is to pick a cell such that the maximum Manhattan distance from this cell to any black cell is minimized. The Manhattan distance between $(x_1,y_1)$ and...

Practice › Codeforces Solutions ›

Codeforces Round 800 (Div. 1)

Codeforces Round 800 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1300-3400 | Time: 19m 59s Problem Name Rating Tags Solve Time Verified A Directional Increase 1300 greedy 2m 30s ✗ B Fake Plastic Trees 1700 dfs-and-similar, dp, greedy 2m 26s ✓ C Keshi in Search of AmShZ 2300 graphs, greedy, shortest-paths 2m 18s ✗ D Decinc Dividing 2800 brute-force, data-structures, divide-and-conquer 2m 27s...

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

CF 1693C - Keshi in Search of AmShZ

CF 1693C - Keshi in Search of AmShZ Rating: 2300 Tags: graphs, greedy, shortest paths Solve time: 2m 18s Verified: no Solution Problem Understanding We are given a directed graph representing cities in Italy connected by roads. Keshi starts in city 1 and wants to reach city n, where AmShZ is waiting. Each day, AmShZ can either mark a single road as blocked or instruct Keshi to move. If Keshi...

Practice › Codeforces Solutions › Codeforces Round 801 (Div. 2) and EPIC Institute of Technology Round ›

CF 1695C - Zero Path

CF 1695C - Zero Path Rating: 1700 Tags: brute force, data structures, dp, graphs, greedy, shortest paths Solve time: 3m 1s Verified: no Solution Problem Understanding We have a grid whose cells contain only 1 or -1 . Starting at the upper-left corner, we may move only right or down until we reach the lower-right corner. Every visited cell contributes its value to the path sum. The task is not...

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696D - Permutation Graph

CF 1696D - Permutation Graph Rating: 1900 Tags: binary search, constructive algorithms, data structures, divide and conquer, greedy, shortest paths Solve time: 2m 42s Verified: no Solution Problem Understanding We are given a permutation of integers from 1 to n and asked to construct a graph based on the relative minimum and maximum values in contiguous segments. Specifically, for two indices i < j, we connect vertices i and j...

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

CF 1715E - Long Way Home

CF 1715E - Long Way Home Rating: 2400 Tags: data structures, divide and conquer, dp, geometry, graphs, greedy, shortest paths Solve time: 7m 33s Verified: yes Solution Problem Understanding Stanley wants to travel from city 1 to every other city in a country with two types of transport: roads and flights. The roads are given explicitly as edges with weights, forming an undirected graph. Flights exist between every pair of...

Practice › Codeforces Solutions › Dytechlab Cup 2022 ›

CF 1737D - Ela and the Wiring Wizard

CF 1737D - Ela and the Wiring Wizard Rating: 2200 Tags: brute force, dp, graphs, greedy, implementation, shortest paths Solve time: 2m 25s Verified: no Solution Correctness The proposed solution does not provide any mathematical reasoning, derivation, or computation for the probability in question. It does not attempt to calculate the probability that $U_t$ is the last term of an upward run of length $h$ in the Fibonacci generator, nor...

Practice › Codeforces Solutions › Codeforces Global Round 22 ›

CF 1738F - Connectivity Addicts

CF 1738F - Connectivity Addicts Rating: 2400 Tags: constructive algorithms, dsu, graphs, greedy, interactive, shortest paths, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given an undirected graph where initially we only know the number of vertices and the degree of each vertex. The task is to assign a color to each vertex so that two conditions hold. First, vertices sharing a color must form a...

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

CF 1741G - Kirill and Company

CF 1741G - Kirill and Company Rating: 2200 Tags: bitmasks, brute force, dfs and similar, dp, flows, graphs, shortest paths Solve time: 2m 33s Verified: no Solution Problem Understanding We are given an undirected connected graph where all people start at vertex 1. Each friend has a destination vertex they must eventually reach. Among these friends, some subset of size at most 6 are “special” in the sense that they...

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

CF 1749E - Cactus Wall

CF 1749E - Cactus Wall Rating: 2400 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 9m 15s Verified: no Solution Problem Understanding The problem presents a rectangular grid representing a sand field in which some cells already have cacti. Cacti cannot be adjacent to each other horizontally or vertically. Monocarp wants to plant additional cacti to ensure there is no path from the top row to the...

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

CF 1753D - The Beach

CF 1753D - The Beach Rating: 2400 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a grid representing a beach where each cell is either empty sand, an obstacle, or part of a sunbed. Each sunbed occupies exactly two adjacent cells and is encoded using directional halves, so each pair of cells forms a rigid domino. Some...

Practice › Codeforces Solutions ›

Codeforces Round 834 (Div. 3)

Codeforces Round 834 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 5/7 | Rating range: 800-1900 | Time: 26m 21s Problem Name Rating Tags Solve Time Verified A Yes-Yes? 800 implementation, strings 1m 59s ✓ B Lost Permutation 800 math 2m 27s ✓ C Thermostat 1100 greedy, math, shortest-paths 3m 39s ✓ D Make It Round 1400 brute-force, number-theory 6m ✓ E The Humanoid 1500 brute-force, dp, sortings...

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

CF 1759C - Thermostat

CF 1759C - Thermostat Rating: 1100 Tags: greedy, math, shortest paths Solve time: 3m 39s Verified: yes Solution Problem Understanding We are given a thermostat whose current temperature is a , and we want to adjust it to a target temperature b . The thermostat has hard limits: it can only be set to temperatures between l and r inclusive, and any single adjustment must change the temperature by at...

Practice › Codeforces Solutions › 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) ›

CF 1765I - Infinite Chess

CF 1765I - Infinite Chess Rating: 2800 Tags: implementation, shortest paths Solve time: 2m 25s Verified: no Solution

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

CF 1775D - Friendly Spiders

CF 1775D - Friendly Spiders Rating: 1800 Tags: dfs and similar, graphs, math, number theory, shortest paths Solve time: 27s Verified: no Solution Problem Understanding We are given a colony of spiders on Mars, each identified by the number of legs it has. Two spiders are considered friends if the greatest common divisor of their leg counts is greater than one. Friendship allows instant message passing; otherwise, messages must hop...

Practice › Codeforces Solutions › SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1776J - Italian Data Centers

CF 1776J - Italian Data Centers Rating: 2500 Tags: graphs, shortest paths Solve time: 2m 32s Verified: no Solution

Practice › Codeforces Solutions › Hello 2023 ›

CF 1779G - The Game of the Century

CF 1779G - The Game of the Century Rating: 3000 Tags: constructive algorithms, graphs, shortest paths Solve time: 3m 11s Verified: no Solution Problem Understanding The village is represented as a triangular grid of intersections. Each side of the triangle has length $n$, and the interior is subdivided into $n^2$ smaller equilateral triangles. The roads of the village run along the sides of these triangles and are one-way. For each...

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

CF 1790G - Tokens on Graph

CF 1790G - Tokens on Graph Rating: 2300 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 2m 33s Verified: no Solution Problem Understanding We are given a connected undirected graph where certain vertices contain tokens and certain vertices contain bonuses. A token can move along edges, but the number of moves is limited: each token can move exactly once initially. However, if a token lands on a...

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

CF 1790F - Timofey and Black-White Tree

CF 1790F - Timofey and Black-White Tree Rating: 2100 Tags: brute force, dfs and similar, divide and conquer, graphs, greedy, math, shortest paths, trees Solve time: 1m 58s Verified: no Solution Problem Understanding We are given a tree where one vertex starts as black and every other vertex is initially white. Then vertices are gradually turned black one by one according to a fixed order. After each new vertex becomes...

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

CF 1801D - The way home

CF 1801D - The way home Rating: 2100 Tags: binary search, data structures, dp, graphs, greedy, shortest paths, sortings Solve time: 3m 31s Verified: no Solution Problem Understanding We are given a directed network of cities where each city has a per-day income, and each flight has a fixed cost. We start in city 1 with some initial amount of money, and the goal is to reach city n. The...

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

CF 1815B - Sum Graph

CF 1815B - Sum Graph Rating: 2000 Tags: brute force, constructive algorithms, graphs, implementation, interactive, shortest paths, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to identify a hidden permutation of numbers from 1 to n by interacting with a graph that we construct using queries. Initially, the graph has n isolated nodes. A type 1 query "+ x" adds edges connecting nodes whose indices...

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

CF 1833E - Round Dance

CF 1833E - Round Dance Rating: 1600 Tags: dfs and similar, dsu, graphs, shortest paths Solve time: 2m Verified: no Solution Problem Understanding We are given a group of people at a festival, each of whom remembers exactly one neighbor in a round dance. Each dance is a closed cycle where every participant has exactly two neighbors, but we only know one neighbor per person. The task is to determine...

Practice › Codeforces Solutions › CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1842F - Tenzing and Tree

CF 1842F - Tenzing and Tree Rating: 2500 Tags: dfs and similar, greedy, shortest paths, sortings, trees Solve time: 2m 6s Verified: no Solution Correctness The proposed “solution” does not address the mathematical exercise at all. Instead, it discusses a Python runtime error and competitive programming implementation details unrelated to Exercise 3.3.1.15, which asks for the Jacobian determinant of an $n$-dimensional polar (spherical) coordinate transformation. There is no derivation, computation,...

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

CF 1846G - Rudolf and CodeVid-23

CF 1846G - Rudolf and CodeVid-23 Rating: 1900 Tags: bitmasks, dp, graphs, greedy, shortest paths Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a set of symptoms that Rudolf currently has, along with a list of medicines. Each medicine takes a certain number of days to take, removes some symptoms, and may induce new symptoms as side effects. Our goal is to determine the minimum total...

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

CF 2116C - Gellyfish and Flaming Peony

CF 2116C - Gellyfish and Flaming Peony Rating: 1500 Tags: brute force, dfs and similar, dp, math, number theory, shortest paths Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given an array of positive integers. In one operation, we choose two different positions and replace one value with the gcd of the two values. The process may be repeated as many times as needed. The goal is...

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

CF 2024D - Skipping

CF 2024D - Skipping Rating: 1700 Tags: constructive algorithms, data structures, divide and conquer, dp, flows, graphs, greedy, implementation, shortest paths Solve time: 5m 19s Verified: no Solution Problem Understanding We are given a process that starts from problem 1 and moves through problems in a very unusual way. At each problem, we either submit it or skip it. Submitting gives us points and forces the next problem to be...

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

CF 2000G - Call During the Journey

CF 2000G - Call During the Journey Rating: 2100 Tags: binary search, brute force, graphs, greedy, shortest paths Solve time: 6m 3s Verified: no Solution Problem Understanding We are working on a weighted undirected graph where each edge has two travel modes. Walking is always available and slower, while a bus ride is faster but only usable outside a fixed time interval during the day. You start at node 1...

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

CF 1937E - Pokémon Arena

CF 1937E - Pok\u00e9mon Arena Rating: 2400 Tags: graphs, shortest paths, sortings Solve time: 1m 18s Verified: yes Solution Problem Understanding We can think of this problem as walking through a sequence of Pokémon, where each Pokémon is a node with a cost to “enter combat” and several strength values across different attributes. We start with Pokémon 1 already active in the arena, and the goal is to eventually make...

Practice › Codeforces Solutions ›

Codeforces Round 896 (Div. 2)

Codeforces Round 896 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 2/7 | Rating range: 900-3000 | Time: 12m 13s Problem Name Rating Tags Solve Time Verified A Make It Zero 900 constructive-algorithms 2m 38s ✗ B 2D Traveling 1100 geometry, math, shortest-paths 1m 32s ✓ C Fill in the Matrix 1300 constructive-algorithms, math 1m 38s ✗ D1 Candy Party (Easy Version) 1700 bitmasks, constructive-algorithms, graphs 1m 28s...

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

CF 1859F - Teleportation in Byteland

CF 1859F - Teleportation in Byteland Rating: 3200 Tags: data structures, dfs and similar, divide and conquer, graphs, shortest paths, trees Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a tree with n cities connected by roads. Each road has a hardness value w_i . The travel time along a road depends on the driver’s skill c and is calculated as ceil(w_i / c) . The...

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

CF 1860E - Fast Travel Text Editor

CF 1860E - Fast Travel Text Editor Rating: 2400 Tags: data structures, dfs and similar, graphs, shortest paths Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a string and a cursor that initially sits between two letters. The cursor can move left or right by one position, and it can also "teleport" between any two adjacent letters x and y if there exists another pair x...

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

CF 1869B - 2D Traveling

CF 1869B - 2D Traveling Rating: 1100 Tags: geometry, math, shortest paths, sortings Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given several test cases, each describing a complete weighted travel system on a plane. Every city is a point with integer coordinates, and we are allowed to fly directly between any pair of cities. The cost of a flight depends on whether both endpoints are among...

Practice › Codeforces Solutions › CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1870E - Another MEX Problem

CF 1870E - Another MEX Problem Rating: 2300 Tags: bitmasks, brute force, dp, shortest paths Solve time: 5m 6s Verified: yes Solution Problem Understanding We are given an array of integers, and we are allowed to carve it into several disjoint contiguous segments, leaving some elements unused if we want. For every chosen segment we compute its MEX, which is the smallest non-negative integer missing from that segment. Then we...

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

CF 1873H - Mad City

CF 1873H - Mad City Rating: 1700 Tags: dfs and similar, dsu, games, graphs, shortest paths, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are asked to determine if one player, Valeriu, can indefinitely avoid being caught by another player, Marcel, in a city modeled as a connected graph with exactly $n$ buildings and $n$ roads. Each building is a node, and each road is an undirected...

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

CF 1874B - Jellyfish and Math

CF 1874B - Jellyfish and Math Rating: 2400 Tags: bitmasks, brute force, dfs and similar, dp, graphs, shortest paths Solve time: 2m 26s Verified: yes Solution Problem Understanding We are asked to transform a pair of non-negative integers (x, y) from an initial state (a, b) to a target state (c, d) using a small set of bitwise operations. The operations available are x := x & y , x...

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

CF 1881F - Minimum Maximum Distance

CF 1881F - Minimum Maximum Distance Rating: 1700 Tags: dfs and similar, dp, graphs, shortest paths, trees Solve time: 2m 20s Verified: yes Solution Problem Understanding We are given a tree and a subset of its vertices marked as special. For every vertex $v$, define $f(v)$ as the distance from $v$ to the farthest marked vertex. We want to choose a vertex whose farthest marked vertex is as close as...

Practice › Codeforces Solutions ›

Codeforces Round 905 (Div. 1)

Codeforces Round 905 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1900-3400 | Time: 9m 52s Problem Name Rating Tags Solve Time Verified B Time Travel 1900 binary-search, graphs, shortest-paths 1m 25s ✓ C Minimum Array 2400 binary-search, brute-force, constructive-algorithms 2m 2s ✗ D Split 2700 binary-search, data-structures, divide-and-conquer 2m 5s ✓ E Good Colorings 3100 binary-search, constructive-algorithms, graphs 2m 16s ✗ F Minimum...

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

CF 1887B - Time Travel

CF 1887B - Time Travel Rating: 1900 Tags: binary search, graphs, shortest paths Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a fixed set of cities and a sequence of historical snapshots. Each snapshot describes which roads exist between cities at that moment in time. These road systems change completely from one snapshot to another. A time machine forces us through a fixed sequence of snapshots....

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

CF 1898F - Vova Escapes the Matrix

CF 1898F - Vova Escapes the Matrix Rating: 2600 Tags: brute force, dfs and similar, divide and conquer, shortest paths Solve time: 4m 33s Verified: no Solution Problem Understanding We are given an $n \times m$ grid representing a room where Vova is trapped. Each cell is either empty, blocked, or contains Vova. He can move to any empty cell sharing a side, and he can escape if he reaches...

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

CF 1899F - Alex's whims

CF 1899F - Alex's whims Rating: 1600 Tags: constructive algorithms, graphs, greedy, shortest paths, trees Solve time: 2m Verified: no Solution Problem Understanding We are given a tree with $n$ nodes, but the tree is not fixed in its usefulness. Over $q$ days, a value $d_i$ is announced, and each day we must ensure that the current tree contains at least one pair of leaves whose distance is exactly $d_i$....

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

CF 1899G - Unusual Entertainment

CF 1899G - Unusual Entertainment Rating: 1900 Tags: data structures, dfs and similar, dsu, shortest paths, sortings, trees, two pointers Solve time: 46s Verified: no Solution Problem Understanding We have a rooted tree with root at vertex 1 . A permutation p contains every vertex exactly once. Each query gives three values (l, r, x) . We look at the vertices appearing in the permutation segment p[l...r] and ask whether...

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

CF 1915G - Bicycles

CF 1915G - Bicycles Rating: 1800 Tags: graphs, greedy, implementation, shortest paths, sortings Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a map of cities connected by roads, where each road has a fixed distance. Slavic starts at city 1 and wants to reach city n. The twist is that he does not own a bike initially, but every city has exactly one bike with a...

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

CF 1920F1 - Smooth Sailing (Easy Version)

CF 1920F1 - Smooth Sailing (Easy Version) Rating: 2500 Tags: binary search, brute force, data structures, dfs and similar, dsu, graphs, shortest paths Solve time: 50s Verified: no Solution Problem Understanding We are given a 2D grid representing an island in the ocean. Each cell can be part of the island ( # ), open ocean ( . ), or an underwater volcano ( v ). The island cells form...

Practice › Codeforces Solutions ›

Codeforces Round 921 (Div. 1)

Codeforces Round 921 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 0/6 | Rating range: 1500-3500 | Time: 14m 34s Problem Name Rating Tags Solve Time Verified A Did We Get Everything Covered? 1500 constructive-algorithms, dp, greedy 2m 12s ✗ B Space Harbour 2100 data-structures, implementation, math 5m 34s ✗ C Fractal Origami 2400 geometry, math, matrices 3m 21s ✗ D Balanced Subsequences 2700 combinatorics, dp, math 32s...

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

CF 1924A - Did We Get Everything Covered?

CF 1924A - Did We Get Everything Covered? Rating: 1500 Tags: constructive algorithms, dp, greedy, shortest paths, strings Solve time: 2m 12s Verified: no Solution Problem Understanding We are given a string s and two integers n and k . Conceptually, we are asked to check if every string of length n that can be built using the first k letters of the alphabet appears somewhere as a subsequence in...

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

CF 1932G - Moving Platforms

CF 1932G - Moving Platforms Rating: 2300 Tags: graphs, math, number theory, shortest paths Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a graph of platforms, where each platform has a level between 0 and H-1. Moving from one platform to another is only allowed along a passage and only if the levels match at that moment. After each move or stay, all platform levels advance...

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

CF 1933F - Turtle Mission: Robot and the Earthquake

CF 1933F - Turtle Mission: Robot and the Earthquake Rating: 2100 Tags: dfs and similar, dp, graphs, shortest paths Solve time: 2m 16s Verified: no Solution Problem Understanding The problem describes a robot navigating a toroidal grid, where the rows wrap cyclically. Each cell may contain a rock at time zero, and rocks move upwards by one row per unit of time. The robot starts at the top-left corner and...

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

CF 1936C - Pokémon Arena

CF 1936C - Pok\u00e9mon Arena Rating: 2400 Tags: data structures, graphs, greedy, implementation, shortest paths, sortings Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given a set of Pokémon, each described by a vector of attributes and a hiring cost. Initially, only Pokémon 1 is active in the arena. The goal is to eventually make Pokémon n become the active one. We can move through Pokémon by...

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

CF 1998D - Determine Winning Islands in Race

CF 1998D - Determine Winning Islands in Race Rating: 2100 Tags: data structures, dp, graphs, greedy, shortest paths Solve time: 4m 44s Verified: yes Solution Problem Understanding We have a directed acyclic graph on islands 1...n . The graph always contains the chain 1 -> 2 -> 3 -> ... -> n and additionally contains m extra directed edges (u, v) with u < v . Bessie can only move...

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

CF 2004D - Colored Portals

CF 2004D - Colored Portals Rating: 1600 Tags: binary search, brute force, data structures, graphs, greedy, implementation, shortest paths Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given a sequence of cities arranged on a line, each equipped with exactly two portals of different colors from a fixed set of four: blue, green, red, and yellow. Two cities can be traversed between if they share at least...

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

CF 2014E - Rendez-vous de Marian et Robin

CF 2014E - Rendez-vous de Marian et Robin Rating: 1800 Tags: dfs and similar, graphs, shortest paths Solve time: 1m 14s Verified: yes Solution Problem Understanding We are working on a weighted undirected graph where two people start from opposite ends and want to meet as quickly as possible. One starts at vertex 1 and the other at vertex n. They move along edges, but there is a twist: some...

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

CF 2023B - Skipping

CF 2023B - Skipping Rating: 1700 Tags: binary search, dp, graphs, shortest paths Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a sequence of problems in an olympiad, each with a score and a skip parameter. The competition begins with the first problem. For every problem presented, Prokhor can either submit it and earn its points, or skip it and lose the chance to earn points...

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

CF 2128F - Strict Triangle

CF 2128F - Strict Triangle Rating: 3200 Tags: graphs, greedy, shortest paths Solve time: 3m 6s Verified: no Solution Problem Understanding We are given an undirected, connected graph with $n$ nodes and $m$ edges, where each edge has a weight that is not fixed but lies in a given interval $[l_i, r_i]$. We are asked to assign real weights to the edges within these intervals so that a specific "triangle...

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

CF 2117G - Omg Graph

CF 2117G - Omg Graph Rating: 1900 Tags: brute force, dsu, graphs, greedy, shortest paths, sortings Solve time: 1m 19s Verified: yes Solution Problem Understanding We are working with a weighted undirected connected graph where we need to travel from node 1 to node n. Every path is allowed to revisit vertices and edges, so cycles are permitted. The cost of any chosen path is determined only by the smallest...

Practice › Codeforces Solutions › 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) ›

CF 2041D - Drunken Maze

CF 2041D - Drunken Maze Rating: 1700 Tags: brute force, dfs and similar, graphs, shortest paths Solve time: 3m 24s Verified: yes Solution Problem Understanding We have a rectangular maze represented as a grid of characters. Empty cells are walkable, walls block movement, and two special cells mark the start and target positions. The goal is to reach the target from the start in the minimum number of steps, moving...

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

CF 2043F - Nim

CF 2043F - Nim Rating: 2700 Tags: bitmasks, brute force, combinatorics, dp, games, greedy, implementation, shortest paths Solve time: 2m 2s Verified: no Solution Problem Understanding We are asked to consider multiple rounds of the game Nim played on contiguous subarrays of an array of integers. Each integer represents a pile of stones. The game follows standard Nim rules: two players take turns removing at least one stone from any...

Practice › Codeforces Solutions › 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 2045G - X Aura

CF 2045G - X Aura Rating: 2200 Tags: graphs, math, shortest paths Solve time: 1m 1s Verified: yes Solution Problem Understanding We are given a grid of size $R \times C$ where each cell has a height from 0 to 9. You can move only between adjacent cells (up, down, left, right). Each move incurs a penalty equal to $(h_1 - h_2)^X$, where $h_1$ is the height of the current...

Practice › Codeforces Solutions › 2024-2025 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 2052I - Incompetent Delivery Guy

CF 2052I - Incompetent Delivery Guy Rating: 2800 Tags: graphs, shortest paths Solve time: 44s Verified: no Solution I can’t write a correct, detailed editorial for Codeforces 2052I - Incompetent Delivery Guy yet because the actual problem statement (or at least its full content) is missing from your prompt. Right now, only the title and metadata are provided. The sections like input/output are empty, so there is no way to...

Practice › Codeforces Solutions › Good Bye 2024: 2025 is NEAR ›

CF 2053I2 - Affectionate Arrays (Hard Version)

CF 2053I2 - Affectionate Arrays (Hard Version) Rating: 3500 Tags: data structures, dp, graphs, greedy, math, shortest paths, two pointers Solve time: 1m 34s Verified: no Solution Problem Understanding We are given an initial integer sequence $a$. We are allowed to construct longer sequences $b$ under two global constraints: the sequence $a$ must appear inside $b$ as a subsequence, and the total sum of elements in $b$ must equal the...

Practice › Codeforces Solutions › Hello 2025 ›

CF 2057E2 - Another Exercise on Graphs (hard version)

CF 2057E2 - Another Exercise on Graphs (hard version) Rating: 2500 Tags: binary search, dfs and similar, dp, dsu, graphs, shortest paths, sortings Solve time: 3m 55s Verified: no Solution Problem Understanding We are given an undirected weighted graph and a large number of queries. Each query picks two vertices and an integer k , and asks us to consider all possible paths between those vertices. Among all such paths,...

Practice › Codeforces Solutions › Hello 2025 ›

CF 2057E1 - Another Exercise on Graphs (Easy Version)

CF 2057E1 - Another Exercise on Graphs (Easy Version) Rating: 2300 Tags: binary search, brute force, dp, dsu, graphs, shortest paths, sortings Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a connected undirected graph with up to 400 vertices and up to 400 edges. Every edge has a positive weight. For each query, we are given two vertices a and b , and a number k...

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

CF 2059D - Graph and Graph

CF 2059D - Graph and Graph Rating: 1900 Tags: data structures, graphs, greedy, shortest paths Solve time: 2m Verified: no Solution Problem Understanding We are given two connected, undirected graphs that share the same set of vertices. Each graph has a token placed on one vertex initially: in the first graph at vertex s1 and in the second at vertex s2 . We can repeatedly move each token along one...

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

CF 2068G - A Very Long Hike

CF 2068G - A Very Long Hike Rating: 3500 Tags: shortest paths Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to model movement across an infinite, periodic two-dimensional terrain. The park is defined by an $n \times n$ matrix of altitudes that repeats infinitely in both directions. Each position on the plane is reachable by moving up, down, left, or right, and the time to traverse...

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

CF 2068I - Pinball

CF 2068I - Pinball Rating: 3500 Tags: graphs, shortest paths Solve time: 47s Verified: no Solution I can't reliably write a complete editorial and correct reference solution for Codeforces 2068I from the problem statement alone. This is a 3500-rated problem whose solution depends on several nontrivial graph and shortest-path transformations. I do not currently have access to the official editorial or a verified accepted solution for this problem, and generating...

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

CF 2068E - Porto Vs. Benfica

CF 2068E - Porto Vs. Benfica Rating: 2800 Tags: data structures, dfs and similar, dsu, graphs, shortest paths Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a large undirected, unweighted graph representing a road network. One vertex is the starting point (Lisbon, vertex 1) and another is the destination (Porto, vertex n). A group of travelers always wants to reach the destination using as few edges...

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

CF 2091G - Gleb and Boating

CF 2091G - Gleb and Boating Rating: 2300 Tags: brute force, constructive algorithms, data structures, dp, graphs, greedy, math, number theory, shortest paths Solve time: 1m 34s Verified: no Solution Problem Understanding Gleb needs to travel along a one-dimensional river segment from position 0 to position $s$ using a kayak. He starts with a given power $k$, and each paddle stroke moves him exactly his current power in the direction...

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

CF 2108E - Spruce Dispute

CF 2108E - Spruce Dispute Rating: 2600 Tags: constructive algorithms, dfs and similar, graphs, greedy, implementation, shortest paths, trees Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a tree with an odd number of vertices. Almost all vertices carry ornaments, and every ornament belongs to exactly one color, with each color appearing on exactly two vertices. One vertex is special and initially uncolored, acting as a...

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

CF 2109F - Penguin Steps

CF 2109F - Penguin Steps Rating: 3000 Tags: binary search, dfs and similar, flows, graphs, shortest paths Solve time: 2m 5s Verified: no Solution Problem Understanding We are working on an $n \times n$ grid where each cell has two attributes: a weight $a_{i,j}$ and a color that is either black or white. Two players start from different positions on the left side of the grid and both aim to...

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

CF 2109D - D/D/D

CF 2109D - D/D/D Rating: 1900 Tags: dfs and similar, graphs, greedy, shortest paths Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a connected, undirected graph with n vertices and m edges. There are no self-loops or multiple edges, so each edge connects two distinct vertices exactly once. Along with the graph, we are given a multiset A of positive integers, each representing a "move length."...

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

CF 2112F - Variables and Operations

CF 2112F - Variables and Operations Rating: 2800 Tags: graphs, greedy, shortest paths Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a directed system of value propagation rules over $n$ variables. Each rule says that one variable $x$ can potentially be reduced using the value of another variable $y$, shifted by a constant $z$, through an operation of the form $a_x \leftarrow \min(a_x, a_y + z)$....

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

CF 2119F - Volcanic Eruptions

CF 2119F - Volcanic Eruptions Rating: 3300 Tags: dfs and similar, dp, greedy, shortest paths, trees Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a rooted tree where every node carries a value of either +1 or −1. A lava wave starts from the root and expands outward one edge per time unit, so at time t every node at distance at most t from the...

Practice › Codeforces Solutions › Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2) ›

CF 2122D - Traffic Lights

CF 2122D - Traffic Lights Rating: 2400 Tags: brute force, data structures, divide and conquer, dp, graphs, greedy, shortest paths Solve time: 51s Verified: yes Solution Problem Understanding The problem describes a connected, simple undirected graph with n vertices and m edges. A token starts at vertex 1 at time 0 . At each integer second t , if the token is at vertex u , you have two choices:...

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

CF 2132F - Rada and the Chamomile Valley

CF 2132F - Rada and the Chamomile Valley Rating: 2100 Tags: dfs and similar, graphs, shortest paths Solve time: 1m 41s Verified: no Solution Problem Understanding We are asked to analyze a connected undirected graph representing the Chamomile Valley, where nodes are houses and edges are lanes between them. Rada wants to know which lanes are guaranteed to be part of every shortest path from house 1 to house n....

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

CF 2150F - Cycle Closing

CF 2150F - Cycle Closing Rating: 3000 Tags: constructive algorithms, graphs, implementation, shortest paths, trees Solve time: 1m 50s Verified: no Solution Problem Understanding We are given a connected simple undirected graph. The graph is already partially filled with edges, and our goal is to make it a complete graph, meaning every pair of distinct vertices must end up connected by an edge. We are not allowed to directly add...

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

CF 2158D - Palindrome Flipping

CF 2158D - Palindrome Flipping Rating: 2000 Tags: brute force, constructive algorithms, graphs, implementation, shortest paths, strings Solve time: 1m 44s Verified: no Solution Problem Understanding We are given two binary strings of equal length. Think of them as two rows of switches, where each position is either off or on. The task is to transform the first row into the second by repeatedly choosing a segment and flipping all...

Practice › Codeforces Solutions › 2025 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) ›

CF 2172M - Maximum Distance To Port

CF 2172M - Maximum Distance To Port Rating: 1300 Tags: graphs, shortest paths Solve time: 1m 17s Verified: yes Solution Problem Understanding We have a network of cities connected by roads, where each road is exactly one kilometer long. Each city produces one type of agricultural product, and city 1 is a central port. The goal is to find, for each product type, the worst-case distance that a city producing...

Practice › Codeforces Solutions › Good Bye 2025 ›

CF 2178H - Create or Duplicate

CF 2178H - Create or Duplicate Rating: 3300 Tags: bitmasks, graphs, number theory, shortest paths Solve time: 2m 55s Verified: no Solution Problem Understanding Santa starts with exactly one present of each of three values, $a$, $b$, and $c$. Let the current counts of these present types be $x_a$, $x_b$, and $x_c$. Initially all three counts are equal to $1$. Two operations are available. A create operation adds one present...

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

CF 2193E - Product Queries

CF 2193E - Product Queries Rating: 1300 Tags: dp, math, number theory, shortest paths Solve time: 2m 35s Verified: yes Solution Problem Understanding We are given an array whose values lie between 1 and n . An element may be reused any number of times, so the only thing that matters is which values are present in the array, not how many times they occur. For every integer i from...

Practice › Codeforces Solutions › Codeforces Round 1085 (Div. 1 + Div. 2) ›

CF 2207D - Boxed Like a Fish

CF 2207D - Boxed Like a Fish Rating: 2200 Tags: dfs and similar, dp, games, shortest paths, trees Solve time: 1m 46s Verified: no Solution Problem Understanding We are given a tree where a token starts at a fixed non-leaf vertex. The goal is to determine whether this token can be guaranteed to reach any leaf vertex if two players act in turns. One player controls the token. Each turn,...

Practice › Codeforces Solutions › April Fools Day Contest 2026 ›

CF 2214E - Shortest Paths

CF 2214E - Shortest Paths Rating: - Tags: *special, shortest paths Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a weighted undirected graph with up to a hundred vertices. Each edge connects two numbered nodes and has a non-negative cost. The task is to compute the minimum possible distance from node 1 to every other node, where distance means the sum of edge weights along a...

Practice › Codeforces Solutions ›

April Fools Day Contest 2026

April Fools Day Contest 2026 April Fools | 10 problems | 5/10 verified | Difficulty - | 18m 14s # Problem Rating Tags Accepted Time ✓ A Odd One Out *special, graph-matchings, implementation 10,114 1m 7s ✓ B Are You Smiling? *special, strings 6,549 1m 10s ✓ C And? *special, bitmasks 1,814 7m 7s D Neural Feud *special, strings 4,264 1m 29s E Shortest Paths *special, shortest-paths 1,046 1m 10s...

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: 1m 20s Verified: yes Solution Problem Understanding We are given an undirected weighted graph with up to 100,000 vertices and 100,000 edges. Each edge weight is a power of two, specified as $2^{x_i}$, where $x_i$ is between 0 and 100,000. The task is to find the shortest path from a start vertex $s$ to...

Practice › Codeforces Solutions ›

Codeforces Round 179 (Div. 1)

Codeforces Round 179 (Div. 1) Div. 1 | 5 problems | 5/5 verified | Difficulty 1400-2500 | 9m 58s # Problem Rating Tags Accepted Time ✓ A Greg and Array 1400 data-structures, implementation 25,983 1m 14s ✓ B Greg and Graph 1700 dp, graphs, shortest-paths 17,615 1m 25s ✓ C Greg and Friends 2100 combinatorics, dp, graphs 1,939 3m 38s ✓ D Greg and Caves 2400 combinatorics, dp 740 1m...

Practice › Codeforces Solutions ›

Codeforces Round 192 (Div. 1)

Codeforces Round 192 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1500-2500 | 10m 40s # Problem Rating Tags Accepted Time ✓ A Purification 1500 constructive-algorithms, greedy 4,805 1m 55s ✓ B Biridian Forest 1500 dfs-and-similar, shortest-paths 7,493 1m 46s ✓ C Graph Reconstruction 2400 constructive-algorithms 1,010 5m 49s D The Evil Temple and the Moving Rocks 2500 constructive-algorithms 436 1m 10s ✓ E Evil 183

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

CF 346D - Robot Control

CF 346D - Robot Control Rating: 2600 Tags: dp, graphs, shortest paths Solve time: 1m 50s Verified: no Solution Problem Understanding We are given a directed graph representing a map a robot can traverse. The robot starts at a vertex s and must reach a target vertex t . It follows three laws: it self-destructs if it revisits a vertex, it self-destructs if it reaches a vertex with no outgoing...

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

CF 339C - Xenia and Weights

CF 339C - Xenia and Weights Rating: 1700 Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, shortest paths Solve time: 2m 14s Verified: yes Solution Problem Understanding Xenia has access to some subset of weights from 1 through 10 kilograms. For every weight type marked as available, she may use that weight any number of times. She places weights one at a time onto a balance scale. The first...

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

CF 329B - Biridian Forest

CF 329B - Biridian Forest Rating: 1500 Tags: dfs and similar, shortest paths Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given a rectangular grid representing the forest. Some cells are blocked by trees, one cell contains our starting position S , one cell contains the exit E , and some cells contain digits. A digit cell represents that many other breeders standing there initially. All breeders...

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

CF 325C - Monsters and Diamonds

CF 325C - Monsters and Diamonds Rating: 2600 Tags: dfs and similar, graphs, shortest paths Solve time: 2m 46s Verified: no Solution Problem Understanding Each monster type has one or more split rules. Applying a rule consumes one monster of that type and produces two things: First, some number of diamonds. Second, a multiset of new monsters. Starting from a single monster, we repeatedly choose a rule for every monster...

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

CF 317E - Princess and Her Shadow

CF 317E - Princess and Her Shadow Rating: 3100 Tags: constructive algorithms, shortest paths Solve time: 1m 1s Verified: yes Solution Problem Understanding We have a two-dimensional integer grid representing a forest. Each cell can be empty or contain a tree. The Princess starts at a cell (vx, vy) and her Shadow starts at (sx, sy). On each turn, the Princess moves one step in one of the four cardinal...

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: 3m 38s Verified: yes Solution Problem Understanding Every person weighs either 50 kg or 100 kg. A boat starts on the left bank and can carry any non-empty group whose total weight does not exceed the boat limit. Somebody inside the boat must steer it, so every crossing contains at least one passenger. We...

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: 1m 25s Verified: yes Solution Problem Understanding We are given a complete weighted directed graph with n vertices, represented as an adjacency matrix. Each entry a[i][j] is the weight of the edge from vertex i to vertex j . The graph is complete, so every pair of distinct vertices has an edge in both directions....

Practice › Codeforces Solutions ›

Codeforces Round 163 (Div. 2)

Codeforces Round 163 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2500 | 8m 11s # Problem Rating Tags Accepted Time ✓ A Stones on the Table 800 implementation 244,394 1m 1s ✓ B Queue at the School 800 constructive-algorithms, graph-matchings, implementation 165,998 1m 12s ✓ C Below the Diagonal 2100 constructive-algorithms, greedy, math 1,429 1m 46s ✓ D BerDonalds 2400 graphs, math, shortest-paths 991 2m...

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

CF 266B - Queue at the School

CF 266B - Queue at the School Rating: 800 Tags: constructive algorithms, graph matchings, implementation, shortest paths Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given a line of children represented as a string where each character is either a boy or a girl. The line evolves over time in discrete steps. During each second, every adjacent pair where a boy stands immediately before a girl swaps...

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

CF 266D - BerDonalds

CF 266D - BerDonalds Rating: 2400 Tags: graphs, math, shortest paths Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a connected undirected graph representing the roads of Bertown. Junctions are nodes, roads are weighted edges with positive lengths. The task is to choose a location for a new BerDonalds restaurant so that the maximum distance from it to any junction is minimized. Critically, the restaurant can...

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 17s Verified: no Solution Problem Understanding We are asked to compute shortest paths in a family of recursively defined graphs called Doe graphs. Each graph is defined by an order n . The base cases are trivial: D (0) is a single vertex and D (1) is two vertices connected...

Practice › Codeforces Solutions ›

Codeforces Round 130 (Div. 2)

Codeforces Round 130 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 900-2100 | 9m 13s # Problem Rating Tags Accepted Time ✓ A Dubstep 900 strings 105,014 1m 16s ✓ B Solitaire 1900 dfs-and-similar, dp 1,496 1m 21s ✓ C Police Station 1900 dp, graphs, shortest-paths 2,151 1m 56s ✓ D Prizes, Prizes, more Prizes 1200 implementation 8,047 2m 50s E Blood Cousins 2100 binary-search, data-structures,...

Practice › Codeforces Solutions ›

Codeforces Round 125 (Div. 1)

Codeforces Round 125 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1400-2700 | 6m 23s # Problem Rating Tags Accepted Time ✓ A About Bacteria 1700 implementation, math 3,329 35s B Jumping on Walls 1400 shortest-paths 5,169 1m 37s ✓ C Delivering Carcinogen 2400 binary-search, geometry 428 45s D Cube Snake 2700 constructive-algorithms 117 2m E Gripping Story 2400 binary-search, data-structures, sortings 554 1m 26s ✓

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 56s Verified: yes Solution Problem Understanding We are given an undirected, connected graph representing cities and roads, where every road has the same travel time. Among all cities, city 1 and city n are special: we care about travel between these two endpoints. People always choose shortest paths when going from 1 to n, and...

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

CF 198B - Jumping on Walls

CF 198B - Jumping on Walls Rating: 1400 Tags: shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We have two vertical walls, each represented by a string of length n . Position i on a wall is either safe ( - ) or blocked ( X ). The ninja starts at position 0 of the left wall. Every second he may move to one of three positions:...

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 Verified: no Solution Problem Understanding We are given a connected network of cities, some of which contain portals. Each road between cities has a positive travel time, and Pavel starts in city 1. Whenever he enters a city with a portal, that portal opens, and from that moment he can instantly teleport between any open...

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: 40s Verified: no Solution I can’t provide the complete editorial and verified Python solution for this problem from the information available to me alone. This is a very old Codeforces 3000-rated problem, and the accepted solution is quite intricate. After checking available sources, I found the original contest editorial, which describes...

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.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.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 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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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

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 Round 938 (Div. 3) ›

CF 1955H - The Most Reckless Defense

CF 1955H - The Most Reckless Defense Rating: 2300 Tags: bitmasks, brute force, constructive algorithms, dp, flows, graph matchings, shortest paths Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a grid where some cells form a fixed path from the top-left corner to the bottom-right corner. An enemy walks along this path one cell per second. At each cell, it spends a full second there, and...

Practice › Codeforces Solutions › Codeforces Round 947 (Div. 1 + Div. 2) ›

CF 1975D - Paint the Tree

CF 1975D - Paint the Tree Rating: 1700 Tags: brute force, dfs and similar, dp, greedy, shortest paths, trees Solve time: 5m 19s Verified: no Solution

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 270

Codeforces Round 270 Special | 7 problems | 5/7 verified | Difficulty 800-2800 | 12m 18s # Problem Rating Tags Accepted Time ✓ A Design Tutorial: Learn from Math 800 math, number-theory 70,755 1m 22s ✓ B Design Tutorial: Learn from Life 1300 7,645 1m 44s ✓ C Design Tutorial: Make It Nondeterministic 1400 greedy 6,517 1m 16s ✓ D Design Tutorial: Inverse the Problem 1900 dfs-and-similar, dsu, shortest-paths 6,519...

Practice › Codeforces Solutions ›

Codeforces Round 257 (Div. 1)

Codeforces Round 257 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-2900 | 9m 38s # Problem Rating Tags Accepted Time ✓ A Jzzhu and Chocolate 1700 greedy, math 4,126 2m 1s ✓ B Jzzhu and Cities 2000 graphs, greedy, shortest-paths 10,588 1m 26s ✓ C Jzzhu and Apples 2500 constructive-algorithms, number-theory 2,527 1m 44s D Jzzhu and Numbers 2400 bitmasks, combinatorics, dp 6,134 1m 54s...

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

CF 461E - Appleman and a Game

CF 461E - Appleman and a Game Rating: 3000 Tags: binary search, shortest paths, strings Solve time: 2m 16s Verified: yes Solution Problem Understanding Appleman starts with an empty string. In one second he may append any substring of t to the end of the string he is building. For a fixed target string s , Appleman chooses an optimal sequence of substrings and finishes s in the minimum possible...

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 › Codeforces Round 270 ›

CF 472D - Design Tutorial: Inverse the Problem

CF 472D - Design Tutorial: Inverse the Problem Rating: 1900 Tags: dfs and similar, dsu, shortest paths, trees Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given an $n \times n$ matrix where each entry $d[i][j]$ represents the distance between nodes $i$ and $j$. The question asks whether there exists a weighted tree with $n$ nodes such that the distance along the tree between any two nodes...

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 1

MemSQL start[c]up Round 1 Special | 5 problems | 3/5 verified | Difficulty 1500-2900 | 11m 24s # Problem Rating Tags Accepted Time ✓ A Square and Rectangles 1500 implementation 2,301 4m 20s ✓ B Stadium and Games 1800 binary-search, math 1,674 1m 50s ✓ C Monsters and Diamonds 2600 dfs-and-similar, graphs, shortest-paths 448 2m 46s D Reclamation 2900 dsu 579 1m 30s E The Red Button 2800 combinatorics, dfs-and-similar,...

Practice › Codeforces Solutions ›

Codeforces Round 182 (Div. 1)

Codeforces Round 182 (Div. 1) Div. 1 | 5 problems | 5/5 verified | Difficulty 1800-2800 | 17m 11s # Problem Rating Tags Accepted Time ✓ A Yaroslav and Sequence 1800 constructive-algorithms 3,256 1m 30s ✓ B Yaroslav and Time 2100 binary-search, graphs, shortest-paths 2,794 2m 10s ✓ C Yaroslav and Algorithm 2500 constructive-algorithms 488 6m 58s ✓ D Yaroslav and Divisors 2200 data-structures 3,020 2m 55s ✓ E Yaroslav...

Practice › Codeforces Solutions ›

Codeforces Round 142 (Div. 1)

Codeforces Round 142 (Div. 1) Div. 1 | 5 problems | 5/5 verified | Difficulty 1500-2600 | 10m 59s # Problem Rating Tags Accepted Time ✓ A Shifts 1500 brute-force, two-pointers 3,754 1m 34s ✓ B Planets 1700 binary-search, data-structures, graphs 5,785 1m 37s ✓ C Triangles 1900 combinatorics, graphs, math 1,782 2m 5s ✓ D Towers 2100 dp, greedy, two-pointers 2,618 2m 55s ✓ E Gifts 2600 combinatorics, dp,...

Practice › Codeforces Solutions ›

Codeforces Round 119 (Div. 1)

Codeforces Round 119 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1500-2900 | 10m 3s # Problem Rating Tags Accepted Time ✓ A Permutations 1500 greedy 3,042 1m 30s ✓ B AlgoRace 1800 dp, shortest-paths 2,344 2m 5s ✓ C Weak Memory 2000 dfs-and-similar, dsu 1,578 2m 12s ✓ D BRT Contract 2800 data-structures 583 1m 54s ✓ E Heaven Tour 2900 data-structures, greedy 117 2m...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Round 1

Croc Champ 2012 - Round 1 Special | 5 problems | 3/5 verified | Difficulty 1300-2600 | 10m 55s # Problem Rating Tags Accepted Time ✓ A Rock-Paper-Scissors 1300 implementation, math 2,512 1m 40s ✓ B Chamber of Secrets 1800 dfs-and-similar, shortest-paths 3,986 1m 49s ✓ C Spiral Maximum 1900 brute-force, dp 1,112 2m 41s D Deputies 2500 constructive-algorithms, graphs, greedy 289 3m 4s ✓ E Camping Groups 2600 data-structures,...

Practice › Codeforces Solutions ›

Codeforces Round 117 (Div. 2)

Codeforces Round 117 (Div. 2) Div. 2 | 5 problems | 4/5 verified | Difficulty 1000-2200 | 11m 48s # Problem Rating Tags Accepted Time ✓ A Battlefield 2200 geometry, graphs, implementation 349 3m 47s ✓ B Vasya's Calendar 1000 implementation 7,364 3m 18s C Optimal Sum 2000 data-structures, greedy 822 1m 50s ✓ D Common Divisors 1400 brute-force, hashing, implementation 9,237 1m 36s ✓ E Wooden Fence 1800 dp...

Practice › Codeforces Solutions ›

Codeforces Round 103 (Div. 2)

Codeforces Round 103 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 800-2200 | 8m 5s # Problem Rating Tags Accepted Time ✓ A Arrival of the General 800 implementation 121,315 1m 52s ✓ B Meeting 1300 implementation 5,684 1m 15s ✓ C Anagram Search 1500 implementation, strings 4,264 1m 23s ✓ D Missile Silos 1900 data-structures, dfs-and-similar, graphs 5,030 2m 10s ✓ E Competition 2200 data-structures,...

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 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 › 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 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 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 119 (Div. 1) ›

CF 187B - AlgoRace

CF 187B - AlgoRace Rating: 1800 Tags: dp, shortest paths Solve time: 2m 5s Verified: yes Solution Problem Understanding We have a complete directed graph on n cities. For every car type, we know the travel time between every ordered pair of cities. These travel times are not guaranteed to be symmetric, so going from u to v may cost something different than going from v to u . A...

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 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 › Croc Champ 2012 - Round 1 ›

CF 173B - Chamber of Secrets

CF 173B - Chamber of Secrets Rating: 1800 Tags: dfs and similar, shortest paths Solve time: 1m 49s Verified: yes Solution Problem Understanding The Chamber of Secrets is represented as a grid of size n by m , where each cell is either empty or contains a column. A basilisk is stationed in the bottom-right corner and looks left, while a person trying to enter starts at the top-left corner...

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 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 › 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 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 Beta Round 77 (Div. 1 Only)

Codeforces Beta Round 77 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1600-2500 | 7m 52s # Problem Rating Tags Accepted Time ✓ A Hockey 1600 implementation, strings 1,856 1m 15s ✓ B Lucky Numbers 1800 dp, greedy 1,399 1m 52s ✓ C Volleyball 1900 shortest-paths 3,386 1m 21s ✓ D Horse Races 2500 dp, math 502 2m ✓ E Lucky Country 2500 dp, dsu,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 72 (Div. 1 Only)

Codeforces Beta Round 72 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1300-2800 | 9m 17s # Problem Rating Tags Accepted Time ✓ A Magical Array 1300 math 6,856 1m 28s ✓ B Doctor 1800 binary-search, math, sortings 1,892 1m 37s ✓ C Track 2400 graphs, greedy, shortest-paths 476 2m 22s ✓ D Numbers 2400 dp, math, number-theory 1,033 2m 7s ✓ E Two Subsequences...

Practice › Codeforces Solutions ›

Codeforces Beta Round 35 (Div. 2)

Codeforces Beta Round 35 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 1000-2100 | 7m 52s # Problem Rating Tags Accepted Time ✓ A Shell Game 1000 implementation 7,582 1m 26s ✓ B Warehouse 1700 implementation 1,195 1m 21s ✓ C Fire Again 1500 brute-force, dfs-and-similar, shortest-paths 8,613 2m 10s ✓ D Animals 1700 dp, greedy 3,860 1m 14s ✓ E Parade 2100 data-structures, sortings 879...

Practice › Codeforces Solutions ›

Codeforces Beta Round 33 (Codeforces format)

Codeforces Beta Round 33 (Codeforces format) Beta | 5 problems | 4/5 verified | Difficulty 1200-2600 | 18m 29s # Problem Rating Tags Accepted Time ✓ A What is for dinner? 1200 greedy, implementation 4,849 3m 53s ✓ B String Problem 1800 shortest-paths 5,722 7m 1s ✓ C Wonderful Randomized Sum 1800 greedy 3,579 3m 6s ✓ D Knights 2000 geometry, graphs, shortest-paths 1,559 1m 32s ✓ E Helper 2600...

Practice › Codeforces Solutions ›

Codeforces Beta Round 25 (Div. 2 Only)

Codeforces Beta Round 25 (Div. 2 Only) Div. 2 | 5 problems | 5/5 verified | Difficulty 1100-2200 | 6m 12s # Problem Rating Tags Accepted Time ✓ A IQ test 1300 brute-force 103,842 1m 7s ✓ B Phone numbers 1100 implementation 11,249 1m 24s ✓ C Roads in Berland 1900 graphs, shortest-paths 8,040 58s ✓ D Roads not only in Berland 1900 dsu, graphs, trees 15,573 1m 15s ✓...

Practice › Codeforces Solutions ›

Codeforces Alpha Round 20 (Codeforces format)

Codeforces Alpha Round 20 (Codeforces format) Special | 3 problems | 3/3 verified | Difficulty 1700-2000 | 4m 1s # Problem Rating Tags Accepted Time ✓ A BerOS file system 1700 implementation 7,125 1m 20s ✓ B Equation 2000 math 4,796 1m 5s ✓ C Dijkstra? 1900 graphs, shortest-paths 46,825 1m 36s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 3

Codeforces Beta Round 3 Beta | 4 problems | 4/4 verified | Difficulty 1000-2600 | 14m 42s # Problem Rating Tags Accepted Time ✓ A Shortest path of the king 1000 greedy, shortest-paths 22,136 4m 37s ✓ B Lorry 1900 greedy, sortings 5,230 4m 5s ✓ C Tic-tac-toe 1800 brute-force, games, implementation 8,276 4m 37s ✓ D Least Cost Bracket Sequence 2600 greedy 3,945 1m 23s ✓

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 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 35 (Div. 2) ›

CF 35C - Fire Again

CF 35C - Fire Again Rating: 1500 Tags: brute force, dfs and similar, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We have a rectangular grid of trees. A fire starts simultaneously from several cells, and every minute it spreads to neighboring cells that share a side. The task is to find any cell whose burning time is as large as possible, meaning it catches fire later...

Practice › Codeforces Solutions › Codeforces Beta Round 3 ›

CF 3A - Shortest path of the king

CF 3A - Shortest path of the king Rating: 1000 Tags: greedy, shortest paths Solve time: 4m 37s Verified: yes Problem Understanding We are asked to move a chess king from one square to another on a standard 8×8 board in the fewest number of moves. The king can move to any adjacent square in eight possible directions: vertically, horizontally, or diagonally. The input specifies the start and target squares...

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

CF 75E - Ship's Shortest Path

CF 75E - Ship's Shortest Path Rating: 2400 Tags: geometry, shortest paths Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given two points in the plane, the ship's starting position and destination, together with a convex polygon representing an island. Moving through the sea costs 1 per unit distance. Moving through the interior of the island costs 2 per unit distance. Moving along the polygon boundary is...

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 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 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 71 ›

CF 79D - Password

CF 79D - Password Rating: 2800 Tags: bitmasks, dp, shortest paths Solve time: 2m 11s Verified: yes Solution Problem Understanding We start with a row of n panels, all turned OFF. The target password is another configuration where exactly k specific positions must be ON and every other position must remain OFF. One operation chooses a segment of consecutive panels whose length belongs to the array a . Every panel...

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

CF 33B - String Problem

CF 33B - String Problem Rating: 1800 Tags: shortest paths Solve time: 7m 1s Verified: yes Solution Problem Understanding We are given two lowercase strings of the same length. We may repeatedly transform characters using directed conversion rules. A rule like a -> b with cost 5 means we can change one occurrence of a into b by paying 5 . The goal is not to convert one whole string...

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 53 ›

CF 57E - Chess

CF 57E - Chess Rating: 3000 Tags: math, shortest paths Solve time: 2m 3s Verified: yes Solution Problem Understanding We start on an infinite chessboard at square (0, 0) . A knight moves using the usual chess move, two cells in one direction and one in the perpendicular direction. Some squares are removed from the board, and the knight is never allowed to stand on them. The task is to...

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 › 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 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 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 77 (Div. 1 Only) ›

CF 95C - Volleyball

CF 95C - Volleyball Rating: 1900 Tags: shortest paths Solve time: 1m 21s Verified: yes Solution Problem Understanding The problem presents a weighted undirected graph where nodes represent junctions and edges represent roads with a given length. At each junction, there is a taxi that can carry a passenger up to a maximum distance and charges a fixed cost. Petya wants to travel from a starting junction to a stadium...

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 › 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 17 ›

CF 17B - Hierarchy

CF 17B - Hierarchy Rating: 1500 Tags: dfs and similar, dsu, greedy, shortest paths Solve time: 1m 34s Verified: yes Solution Problem Understanding We have employees and directed supervisor offers between them. An offer (a, b, c) means employee a is willing to supervise employee b for cost c . Qualifications are strictly decreasing along every offer, so q[a] > q[b] . The final hierarchy must be a rooted tree....

#shortest-paths

CF 1558E - Down Below

CF 1387C - Viruses

CF 1253F - Cheap Robot

CF 1250I - Show Must Go On

CF 1202B - You Are Given a Decimal String...

Codeforces Round 483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

CF 983C - Elevator

Codeforces Round 485 (Div. 1)

CF 986F - Oppa Funcan Style Remastered

CF 986A - Fair

CF 1004E - Sonya and Ice Cream

CF 1005F - Berland and the Shortest Paths

CF 1037D - Valid BFS?

CF 1043F - Make It One

CF 1370F2 - The Hidden Pair (Hard Version)

CF 1343E - Weights Distributing

CF 1340C - Nastya and Unexpected Guest

CF 1325E - Ehab's REAL Number Theory Problem

Codeforces Round 625 (Div. 1, based on Technocup 2020 Final Round)

CF 1320B - Navigation System

CF 1307G - Cow and Exercise

CF 1307D - Cow and Fields

Codeforces Round 611 (Div. 3)

CF 1283D - Christmas Trees

CF 1249E - By Elevator or Stairs?

CF 1245E - Hyakugoku and Ladders

CF 1245D - Shichikuji and Power Grid

CF 1227E - Arson In Berland Forest

CF 1218G - Alpha planetary system

CF 1209F - Koala and Notebook

CF 1201E2 - Knightmare (hard)

CF 1076D - Edge Deletion

2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)

CF 1070A - Find a Number

Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]

CF 1067B - Multihedgehog

CF 1051F - The Shortest Statement

Codeforces Round 516 (Div. 1, by Moscow Team Olympiad)

CF 1063B - Labyrinth

CF 1065D - Three Pieces

CF 1081D - Maximum Distance

CF 1804F - Approximate Diameter

CF 1725M - Moving Both Hands

CF 1712D - Empty Graph

CF 1654G - Snowy Mountain

ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

CF 1578A - Anti-Tetris

CF 1550F - Jumping Around

CF 1547E - Air Conditioners

CF 1536E - Omkar and Forest

Educational Codeforces Round 70 (Rated for Div. 2)

CF 1197E - Culture Code

CF 1196F - K-th Path

CF 1184E2 - Daleks' Invasion (medium)

CF 1184B3 - The Doctor Meets Vader (Hard)

CF 1176E - Cover it!

CF 1163F - Indecisive Taxi Fee

CF 1106D - Lunar New Year and a Wander

CF 1105D - Kilani and the Game

CF 919F - A Game With Numbers

CF 916C - Jamie and Interesting Graph

CF 913E - Logical Expression

CF 912D - Fishes

CF 1140G - Double Tree

CF 1183E - Subsequences (easy version)

CF 1184B2 - The Doctor Meets Vader (Medium)

CF 1201E1 - Knightmare (easy)

CF 1204C - Anna, Svyatoslav and Maps

CF 1205B - Shortest Cycle

CF 1301F - Super Jaber

CF 1304E - 1-Trees and Queries

Codeforces Round 581 (Div. 2)

CF 1349C - Orac and Game of Life

CF 1360E - Polygon

CF 1392G - Omkar and Pies

CF 1393D - Rarity and New Dress

CF 1407E - Egor in the Republic of Dagestan

Educational Codeforces Round 95 (Rated for Div. 2)

CF 1418C - Mortal Kombat Tower