#graphs

CF 1559D1 - Mocha and Diana (Easy Version)

CF 1559D1 - Mocha and Diana (Easy Version) Rating: 1400 Tags: brute force, constructive algorithms, dsu, graphs, greedy, trees Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given two forests on the same set of labeled nodes from 1 to n. Each forest is just a collection of edges that never forms a cycle, though each forest can be disconnected and consist of multiple trees. The operation...

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

CF 1552D - Array Differentiation

CF 1552D - Array Differentiation Rating: 1800 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dp, graphs, math Solve time: 5m 22s Verified: no Solution Problem Understanding We are given a list of integers, and we want to decide whether it is possible to assign another list of the same length, say $b_1, b_2, \dots, b_n$, such that every given number $a_i$ can be expressed as a difference between...

CF 1389G - Directing Edges

CF 1389G - Directing Edges Rating: 2800 Tags: dfs and similar, dp, graphs, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given an undirected connected graph where each edge can be turned into a one-way edge of our choosing or kept as a two-way edge. Keeping it two-way is expensive, since every such edge contributes its weight to the cost. Directed edges are free but only...

CF 1385E - Directing Edges

CF 1385E - Directing Edges Rating: 2000 Tags: constructive algorithms, dfs and similar, graphs Solve time: 5m 5s Verified: no Solution Problem Understanding We are given a graph where every edge already knows its endpoints, but not all edges are allowed to choose their direction freely. Some edges are already directed and must stay exactly as they are, while the remaining edges are undirected and can be oriented however we...

CF 1385G - Columns Swaps

CF 1385G - Columns Swaps Rating: 2300 Tags: 2-sat, dfs and similar, dsu, graphs, implementation Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a two-row table with $n$ columns, and every cell contains a number between $1$ and $n$. In each column we are allowed to either leave the two values as they are or swap them, and each column can be swapped at most once....

CF 1367E - Necklace Assembly

CF 1367E - Necklace Assembly Rating: 1900 Tags: brute force, dfs and similar, dp, graphs, greedy, number theory Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given a multiset of colored beads, where each bead is just a lowercase letter. From these beads, we want to choose some subset and arrange it in a circle, forming a necklace. The arrangement is circular, so rotations matter but there...

CF 1346E - Magic Tricks

CF 1346E - Magic Tricks Rating: 1700 Tags: *special, dp, graphs Solve time: 5m 2s Verified: no Solution Problem Understanding We start with a row of positions from 1 to n, and a special ball initially placed at position k. Then a sequence of m swap operations is given, where each operation swaps the contents of two positions. The twist is that Masha can choose to “fake” some swaps, meaning...

CF 1305G - Kuroni and Antihype

CF 1305G - Kuroni and Antihype Rating: 3500 Tags: bitmasks, brute force, dp, dsu, graphs Solve time: 3m 16s Verified: no Solution Problem Understanding We are given a group of people, each with an associated integer value that can be interpreted as a bitmask. These people can form a network by joining a system where actions produce profit: once someone has joined, they can “invite” a person who has not...

CF 1266F - Almost Same Distance

CF 1266F - Almost Same Distance Rating: 2900 Tags: dfs and similar, graphs Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a tree, and for every possible distance value $k$, we want to know how large a subset of vertices we can pick such that every pair of chosen vertices is “almost equidistant” in a very strict sense: if you pick any two vertices in the...

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

CF 1252L - Road Construction

CF 1252L - Road Construction Rating: 2300 Tags: flows, graphs Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a set of cities where each city proposes exactly one possible road. City $i$ wants to connect to a specific other city $A_i$, so each proposal is an undirected edge $(i, A_i)$. If we ignored all constraints about workers, these proposed edges already form a connected graph, so...

CF 1250N - Wires

CF 1250N - Wires Rating: 2000 Tags: dfs and similar, graphs, greedy Solve time: 2m Verified: no Solution Problem Understanding Each wire connects two contact points, and we say two wires are related if they share at least one endpoint, or if there is a chain of wires where consecutive wires share endpoints. This creates a notion of connectivity over the wires themselves: wires are nodes, and sharing a contact...

CF 1250K - Projectors

CF 1250K - Projectors Rating: 3100 Tags: flows, graphs Solve time: 1m 52s Verified: no Solution Problem Understanding We are given two sets of time intervals: one set represents lectures, the other represents seminars. Each lecture must be assigned a high-definition projector, while each seminar can use any projector, either HD or ordinary. Every projector can handle at most one event at a time, but can be reused later once...

CF 1250E - The Coronation

CF 1250E - The Coronation Rating: 2300 Tags: graphs, implementation Solve time: 1m 40s Verified: no Solution Problem Understanding We are given several binary strings, each representing a necklace. Each position in a string is either 0 or 1, and we interpret this as two types of gems. We are allowed to reverse some of these strings. After choosing which necklaces to reverse, we compare every pair of necklaces. Two...

CF 1242C - Sum Balance

CF 1242C - Sum Balance Rating: 2400 Tags: bitmasks, dfs and similar, dp, graphs Solve time: 1m 43s Verified: no Solution Problem Understanding We are given several containers, each holding a multiset of distinct integers. A single operation is performed exactly once: from every container, we must pick exactly one value, and then redistribute those chosen values back into the containers so that each container still ends up with the...

CF 1242E - Planar Perimeter

CF 1242E - Planar Perimeter Rating: 3200 Tags: constructive algorithms, graphs Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to construct a planar structure made of polygonal faces, where each face is a simple cycle in a shared graph. Each face i must have exactly a_i vertices on its boundary. Whenever two faces touch, they must share an entire edge, not just a vertex. The goal...

CF 1210D - Konrad and Company Evaluation

CF 1210D - Konrad and Company Evaluation Rating: 2400 Tags: graphs Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a group of employees and an undirected “dislike” relation between some pairs. At any moment, each employee has a salary, and this salary induces a directed view of every dislike edge: between two connected employees, the one with higher salary brags to the one with lower salary....

CF 1170G - Graph Decomposition

CF 1170G - Graph Decomposition Rating: - Tags: *special, graphs Solve time: 1m 41s Verified: no Solution Problem Understanding We are given an undirected multigraph where edges may repeat and self-loops are allowed. The task is to completely eliminate all edges by repeatedly choosing a simple cycle and removing all edges belonging to that cycle. A simple cycle here is a closed walk that does not repeat vertices except for...

CF 1000E - We Need More Bosses Rating: 2100 Tags: dfs and similar, graphs, trees Model: gpt-5-3-mini Solve time: 1m 14s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33b176-33dc-83ec-aa43-47f37c1f6b9a Solution Problem Understanding We are given an undirected connected graph that may contain cycles. We are allowed to choose two special vertices, call them $s$ and $t$, after seeing the graph. Once those endpoints are fixed, we consider all simple paths from $s$...

CF 977E - Cyclic Components Rating: 1500 Tags: dfs and similar, dsu, graphs Model: gpt-5-3-mini Solve time: 1m 1s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a501-2120-83ec-ad40-57e2d61c49fa Solution Problem Understanding We are given an undirected graph, and the task is to count how many of its connected components form a simple cycle. A component is considered a cycle when all of its vertices can be arranged in a ring so that every...

CF 1033E - Hidden Bipartite Graph Rating: 2800 Tags: binary search, constructive algorithms, dfs and similar, graphs, interactive Model: gpt-5-3-mini Solve time: 2m 27s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33b4bd-0d58-83ec-9581-09aa8217a4ba Solution Problem Understanding We are given an unknown connected simple graph with up to 600 vertices. We cannot see its edges directly. Instead, we can only ask questions of the form: choose a subset of vertices, and receive the number...

CF 982F - The Meeting Place Cannot Be Changed Rating: 2700 Tags: dfs and similar, graphs Model: gpt-5-3-mini Solve time: 1m 27s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a65c-a680-83ec-b683-c182360d8ebc Solution Problem Understanding We are given a directed graph representing intersections connected by one-way roads. A car starts from some unknown intersection and then keeps moving along outgoing roads forever. We are guaranteed that this movement never gets stuck, meaning from every...

CF 976F - Minimal k-covering Rating: 2500 Tags: flows, graphs Model: gpt-5-3-mini Solve time: 2m 5s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a4b9-3dac-83ec-87ac-1cbf084ec568 Solution Problem Understanding We are working with a bipartite graph where edges connect vertices on the left side to vertices on the right side, and multiple edges between the same pair are allowed. From this graph we are allowed to select some subset of edges. For a fixed...

CF 939D - Love Rescue Rating: 1600 Tags: dfs and similar, dsu, graphs, greedy, strings Model: gpt-5-3-mini Solve time: 1m 14s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a339873-b5b0-83ec-af64-de42c9d02b4a Solution Problem Understanding We are given two strings of equal length, one written on Valya’s pullover and one on Tolya’s T-shirt. The goal is to make the two strings identical using a set of allowed transformation rules. Each spell corresponds to a pair...

CF 933C - A Colourful Prospect Rating: 2700 Tags: geometry, graphs Model: gpt-5-3-mini Solve time: 1m 15s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32e409-8974-83ec-84a0-d270fc740e30 Solution Problem Understanding We are given up to three circles drawn on a plane, each defined by a center and a radius. These circles may overlap, intersect, or be completely separate. The task is to determine how many connected regions the plane is split into after all...

CF 1070I - Privatization of Roads in Berland Rating: 2400 Tags: flows, graph matchings, graphs Model: gpt-5-3-mini Solve time: 1m 21s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bf33-5374-83ec-9b48-0bc381466acc Solution Problem Understanding We are given a simple undirected graph with up to 600 vertices and 600 edges per test case. Each edge must be assigned a label, called a company index. The assignment has two constraints. First, every company is allowed to...

CF 960F - Pathwalks Rating: 2100 Tags: data structures, dp, graphs Model: gpt-5-3-mini Solve time: 4m 24s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a06c-a550-83ec-baf9-e569323b4a6a Solution Problem Understanding We are given a directed graph where each edge has an associated weight and also an implicit position given by its order in the input. A valid path is not constrained to be simple; vertices may repeat, and we may traverse edges multiple times...

CF 1042F - Leaf Sets Rating: 2400 Tags: data structures, dfs and similar, dsu, graphs, greedy, sortings, trees Model: gpt-5-5 Solve time: 1m 22s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bd15-e528-83ec-b5a4-de0286e26609 Solution Problem Understanding We are given a tree where only some vertices matter: those with degree exactly one, which we call leaves. The task is not about grouping all vertices, but only about grouping these leaves. Each group must satisfy...

CF 990D - Graph And Its Complement Rating: 1700 Tags: constructive algorithms, graphs, implementation Model: gpt-5-3-mini Solve time: 1m 42s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33ab50-41d4-83ec-a879-a911b1062878 Solution Problem Understanding We are asked to construct an undirected simple graph on $n$ vertices such that two independent structural properties hold at the same time: the graph itself must have exactly $a$ connected components, and its complement graph must have exactly $b$ connected...

CF 928C - Dependency management Rating: 1900 Tags: *special, graphs, implementation Model: gpt-5-3-mini Solve time: 1m 30s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a330317-3000-83ec-a44f-85b0de8c477a Solution Problem Understanding We are given a collection of software projects, where each project is identified not just by a name but also by a version number. Each project can depend on other projects, forming a directed acyclic dependency graph. The first project in the input is...

CF 976D - Degree Set Rating: 2500 Tags: constructive algorithms, graphs, implementation Model: gpt-5-3-mini Solve time: 1m 45s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a4a5-3e54-83ec-af99-7a1126bb5b7e Solution Problem Understanding We are asked to construct an undirected simple graph with a very specific property: if we look at the degrees of all vertices, the set of distinct degree values must match exactly a given sorted list $d_1 < d_2 < \dots < d_n$....

CF 986C - AND Graph Rating: 2500 Tags: bitmasks, dfs and similar, dsu, graphs Model: gpt-5-5 Solve time: 1m 5s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33779d-a8a4-83ec-af71-7ea6e697c632 Solution Problem Understanding We are given a collection of distinct integers, each of which can be viewed as an n-bit mask. We build a graph whose vertices are these numbers, and we connect two vertices whenever their bitwise AND is zero. In other words,...

CF 995E - Number Clicker Rating: 2700 Tags: divide and conquer, graphs, meet-in-the-middle, number theory Model: gpt-5-3-mini Solve time: 1m 18s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3295a7-dfbc-83ec-94b8-8dde43a79130 Solution Problem Understanding We are working in a system where the state is a single number on a circular modulo ring of size $p$, where $p$ is prime. The screen always shows a value between $0$ and $p-1$. We start from an initial...

CF 938D - Buy a Ticket Rating: 2000 Tags: data structures, graphs, shortest paths Model: gpt-5-3-mini Solve time: 2m Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32790c-167c-83ec-bdc2-cbedf9f20620 Solution Problem Understanding We are given a weighted undirected graph where cities are vertices and train routes are edges with travel costs. Each city also has a fixed price for buying a concert ticket in that city. For any starting city, a person may travel...

CF 899C - Dividing the numbers Rating: 1300 Tags: constructive algorithms, graphs, math Model: gpt-5-5 Solve time: 1m 36s Verified: yes (1/1 samples) Solution Problem Understanding We are given the first n positive integers, and we must split them into two non-empty groups. Every integer must go to exactly one group, and we want the sums of the two groups to be as close as possible. If we think in...

CF 1037E - Trips Rating: 2200 Tags: graphs Model: gpt-5-3-mini Solve time: 1m 20s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32a2fb-3504-83ec-844a-f6e3a70f29b3 Solution Problem Understanding We are given a dynamic system of friendships among $n$ people. Initially there are no edges between them. Each morning, a new undirected edge is added between two previously unconnected vertices. After each addition, we need to consider the current graph and answer a question about the...

CF 938G - Shortest Path Queries Rating: 2900 Tags: bitmasks, data structures, dsu, graphs Model: gpt-5-3-mini Solve time: 2m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32799a-0180-83ec-8ea1-490a97920b8d Solution Problem Understanding We are maintaining a graph whose edges carry integer weights, but distance is not defined in the usual additive sense. Instead, when you walk along a path, the cost of that path is the bitwise XOR of all edge weights along...

CF 954D - Fight Against Traffic Rating: 1600 Tags: dfs and similar, graphs, shortest paths Model: gpt-5-3-mini Solve time: 1m 12s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327cbb-fd5c-83ec-acef-a0a85d314a96 Solution Problem Understanding We are given an undirected connected graph representing junctions and roads, where each road has unit length. The shortest distance between any two junctions is defined as the minimum number of edges in a path. Two special nodes are highlighted,...

CF 923F - Public Service

CF 923F - Public Service Rating: 3200 Tags: constructive algorithms, graphs, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are given two different trees on the same number of cities. One tree describes bus connections between cities labeled from 1 to N. The other tree describes train connections between cities labeled from N+1 to 2N. Both are connected and have exactly N−1 edges, so each forms a...

VK Cup 2018 - Round 1

VK Cup 2018 - Round 1 Special | 2 problems | 1/2 verified | Difficulty 1700-3200 | 3m 7s # Problem Rating Tags Accepted Time ✓ A Primal Sport 1700 math, number-theory 5,419 1m 16s ✓ F Public Service 3200 constructive-algorithms, graphs, trees 131 1m 51s

Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round)

Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round) Div. 1 | 3 problems | 2/3 verified | Difficulty 1500-2900 | 4m 58s # Problem Rating Tags Accepted Time ✓ A Peculiar apple-tree 1500 dfs-and-similar, graphs, trees 8,386 1m 10s ✓ C Teodor is not a liar! 1900 data-structures, dp 2,373 1m 52s ✓ E Coins Exhibition 2900 data-structures, dp, math 519 1m 56s

CF 930A - Peculiar apple-tree

CF 930A - Peculiar apple-tree Rating: 1500 Tags: dfs and similar, graphs, trees Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a rooted tree with vertices numbered from 1 to n, where vertex 1 is the root. Every vertex i greater than 1 has exactly one parent p[i], and that parent always has a smaller index, which implicitly guarantees that the structure is a rooted tree...

Codeforces Round 467 (Div. 1)

Codeforces Round 467 (Div. 1) Div. 1 | 2 problems | 0/2 verified | Difficulty 2100-2300 | 4m 52s # Problem Rating Tags Accepted Time ✓ B Sleepy Game 2100 dfs-and-similar, dp, games 3,411 1m 40s C Lock Puzzle 2300 constructive-algorithms, implementation, strings 1,259 3m 12s

CF 936B - Sleepy Game

CF 936B - Sleepy Game Rating: 2100 Tags: dfs and similar, dp, games, graphs Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a directed graph where each vertex represents a state of a game token. A token starts at a fixed vertex, and two players alternate moving it along outgoing edges. A player loses immediately if they are to move from a vertex that has no...

Codeforces Round 464 (Div. 2)

Codeforces Round 464 (Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 800-2400 | 8m 3s # Problem Rating Tags Accepted Time ✓ A Love Triangle 800 graphs 29,697 1m 8s ✓ B Hamster Farm 1000 implementation 11,270 1m 6s ✓ E Maximize! 1800 binary-search, greedy, ternary-search 3,538 1m 44s F Cutlet 2400 data-structures, dp 1,198 4m 5s

CF 939A - Love Triangle

CF 939A - Love Triangle Rating: 800 Tags: graphs Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given a directed structure over $n$ nodes, where each node has exactly one outgoing edge. Concretely, plane $i$ points to plane $f_i$, meaning it “likes” exactly one other plane. Self-loops are explicitly disallowed, so no node points to itself. The task is to determine whether there exists a directed cycle...

CF 948A - Protect Sheep

CF 948A - Protect Sheep Rating: 900 Tags: brute force, dfs and similar, graphs, implementation Solve time: 1m 20s Verified: no Solution Problem Understanding The grid can be viewed as a rectangular graph where each cell is a node connected to its four orthogonal neighbors. Some nodes contain sheep, some contain wolves, and the rest are empty. Wolves are free to move step by step across empty cells, but they...

Codeforces Round 470 (rated, Div. 2, based on VK Cup 2018 Round 1)

Codeforces Round 470 (rated, Div. 2, based on VK Cup 2018 Round 1) Div. 2 | 1 problems | 0/1 verified | Difficulty 900-900 | 1m 20s # Problem Rating Tags Accepted Time ✓ A Protect Sheep 900 brute-force, dfs-and-similar, graphs 15,314 1m 20s

Codeforces Round 469 (Div. 1)

Codeforces Round 469 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1600-3300 | 14m 46s # Problem Rating Tags Accepted Time ✓ A Zebras 1600 greedy 5,655 1m 32s B A Leapfrog in the Array 1700 constructive-algorithms, math 3,833 1m 32s C Data Center Maintenance 1900 dfs-and-similar, graphs 2,252 5m 25s D Curfew 2300 binary-search, brute-force, greedy 881 3m 41s E Binary Cards 2700 brute-force 769...

CF 949C - Data Center Maintenance

CF 949C - Data Center Maintenance Rating: 1900 Tags: dfs and similar, graphs Solve time: 5m 25s Verified: no Solution

Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)

Helvetic Coding Contest 2018 online mirror (teams allowed, unrated) Special | 7 problems | 3/7 verified | Difficulty 1500-3100 | 12m 46s # Problem Rating Tags Accepted Time ✓ A2 Death Stars (medium) 2000 hashing, strings 1,058 1m 31s ✓ A3 Death Stars (hard) 3100 53 59s ✓ B2 Maximum Control (medium) 2200 data-structures, dfs-and-similar, graphs 747 2m 35s C2 Encryption (medium) 2000 dp 1,378 1m 26s E1 Guard Duty...

CF 958B2 - Maximum Control (medium)

CF 958B2 - Maximum Control (medium) Rating: 2200 Tags: data structures, dfs and similar, graphs, greedy, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given a tree with $N$ nodes, meaning every pair of nodes is connected by exactly one simple path. We are allowed to choose $K$ nodes as “active stations”. Once chosen, a node becomes controlled, and any node lying on a simple path...

CF 959E - Mahmoud and Ehab and the xor-MST

CF 959E - Mahmoud and Ehab and the xor-MST Rating: 1900 Tags: bitmasks, dp, graphs, implementation, math Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a complete graph on vertices labeled from 0 to n − 1. Every pair of distinct vertices is connected, and the weight of the edge between u and v is the bitwise XOR of their labels. The task is to compute...

Educational Codeforces Round 42 (Rated for Div. 2)

Educational Codeforces Round 42 (Rated for Div. 2) Div. 2 | 4 problems | 3/4 verified | Difficulty 1300-2800 | 4m 22s # Problem Rating Tags Accepted Time ✓ A Equator 1300 implementation 13,431 1m 14s ✓ C Make a Square 1400 brute-force, implementation, math 8,357 1m 20s ✓ F Simple Cycles Edges 2400 dfs-and-similar, graphs, trees 1,581 1m 16s ✓ G Visible Black Areas 2800 data-structures, dsu, geometry 207...

CF 962F - Simple Cycles Edges

CF 962F - Simple Cycles Edges Rating: 2400 Tags: dfs and similar, graphs, trees Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given an undirected simple graph and asked to identify which edges are “exclusive” to a single simple cycle. In other words, for each edge we want to know whether there exists exactly one cycle in the entire graph that contains this edge, where cycles are...

CF 980F - Cactus to Tree

CF 980F - Cactus to Tree Rating: 2900 Tags: dp, graphs, trees Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a connected undirected graph with a special structure: every vertex can belong to at most one simple cycle. This means the graph looks like a tree where some disjoint cycles have been added, and those cycles never intersect at a vertex. We are allowed, for any...

Codeforces Round 484 (Div. 2)

Codeforces Round 484 (Div. 2) Div. 2 | 3 problems | 3/3 verified | Difficulty 1200-2600 | 3m 50s # Problem Rating Tags Accepted Time ✓ A Row 1200 brute-force, constructive-algorithms 9,711 1m 2s ✓ C Cut 'em all! 1500 dfs-and-similar, dp, graphs 15,845 1m 21s ✓ E Billiard 2600 geometry, number-theory 827 1m 27s ✓

CF 982C - Cut 'em all!

CF 982C - Cut 'em all! Rating: 1500 Tags: dfs and similar, dp, graphs, greedy, trees Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a tree, meaning a connected graph with no cycles, and every edge is available for us to potentially remove. The operation we are allowed to perform is cutting edges so that the graph splits into smaller connected components. After performing some set...

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

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

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

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 ✓

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

Codeforces Round 487 (Div. 2)

Codeforces Round 487 (Div. 2) Div. 2 | 3 problems | 1/3 verified | Difficulty 900-2500 | 5m 51s # Problem Rating Tags Accepted Time ✓ A A Blend of Springtime 900 implementation, strings 11,161 1m 16s ✓ C A Mist of Florescence 1800 constructive-algorithms, graphs 4,034 1m 54s D A Shade of Moonlight 2500 binary-search, geometry, math 536 2m 41s

CF 989C - A Mist of Florescence

CF 989C - A Mist of Florescence Rating: 1800 Tags: constructive algorithms, graphs Solve time: 1m 54s Verified: no Solution Problem Understanding We are asked to construct a rectangular grid and fill it with four letters, each representing a type of flower. The grid should be designed so that when we look at each letter separately, counting connected components using edge adjacency, the number of components for the four letters...

Codeforces Round 490 (Div. 3)

Codeforces Round 490 (Div. 3) Div. 3 | 3 problems | 3/3 verified | Difficulty 800-2000 | 3m 43s # Problem Rating Tags Accepted Time ✓ A Mishka and Contest 800 brute-force, implementation 25,323 1m 20s ✓ B Reversing Encryption 900 implementation 19,432 1m 8s ✓ E Reachability from the Capital 2000 dfs-and-similar, graphs, greedy 7,846 1m 15s ✓

CF 999E - Reachability from the Capital

CF 999E - Reachability from the Capital Rating: 2000 Tags: dfs and similar, graphs, greedy Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a directed graph where cities are nodes and roads are one-way edges. One city is designated as the capital. The goal is to ensure that every city can be reached by following directed roads starting from the capital. If a city is not...

Codeforces Round 494 (Div. 3)

Codeforces Round 494 (Div. 3) Div. 3 | 6 problems | 2/6 verified | Difficulty 800-2200 | 11m 26s # Problem Rating Tags Accepted Time ✓ A Polycarp's Pockets 800 implementation 29,976 1m 15s ✓ B Binary String Constructing 1300 constructive-algorithms 12,222 1m 51s C Intense Heat 1300 brute-force, implementation, math 11,525 1m 30s D Coins and Queries 1600 greedy 8,560 1m 58s E Tree Constructing 2100 constructive-algorithms, graphs 3,029...

CF 1003E - Tree Constructing

CF 1003E - Tree Constructing Rating: 2100 Tags: constructive algorithms, graphs Solve time: 3m 34s Verified: no Solution Problem Understanding We are asked to build a tree with a fixed number of nodes such that two structural constraints hold simultaneously: the longest simple path in the tree has length exactly d , and every vertex is incident to at most k edges. If no such tree can exist, we must...

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

CF 1006E - Military Problem

CF 1006E - Military Problem Rating: 1600 Tags: dfs and similar, graphs, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a rooted tree of officers where each officer has a unique direct superior except the root officer 1. This creates a hierarchy where every node represents an officer and edges point from superior to subordinate. Each query asks us to simulate a very specific traversal...

Educational Codeforces Round 47 (Rated for Div. 2)

Educational Codeforces Round 47 (Rated for Div. 2) Div. 2 | 7 problems | 5/7 verified | Difficulty 800-2400 | 19m 17s # Problem Rating Tags Accepted Time ✓ A Game Shopping 800 implementation 12,310 1m 26s ✓ B Minimum Ternary String 1400 greedy, implementation 10,719 2m 39s C Annoying Present 1700 greedy, math 5,557 3m 45s ✓ D Relatively Prime Graph 1700 brute-force, constructive-algorithms, graphs 6,658 1m 55s E...

CF 1009G - Allowed Letters

CF 1009G - Allowed Letters Rating: 2400 Tags: bitmasks, flows, graph matchings, graphs, greedy Solve time: 3m 35s Verified: yes Solution Problem Understanding We are given a string made only from the first six lowercase letters. We are allowed to rearrange its characters arbitrarily by swapping any positions any number of times, so effectively we can treat it as a multiset of letters with full permutation freedom. On top of...

CF 1009D - Relatively Prime Graph

CF 1009D - Relatively Prime Graph Rating: 1700 Tags: brute force, constructive algorithms, graphs, greedy, math Solve time: 1m 55s Verified: no Solution Problem Understanding We are asked to build a simple undirected graph on vertices numbered from 1 to n. The graph must have exactly m edges, must be connected, and must avoid both self-loops and repeated edges. The extra constraint is that every edge we include must connect...

Codeforces Round 499 (Div. 1)

Codeforces Round 499 (Div. 1) Div. 1 | 6 problems | 4/6 verified | Difficulty 1500-3400 | 15m 26s # Problem Rating Tags Accepted Time ✓ A Fly 1500 binary-search, math 9,003 1m 41s ✓ B Rocket 1800 binary-search, interactive 6,386 2m 23s C Border 1800 number-theory 5,930 4m 4s ✓ D Mars rover 2000 dfs-and-similar, graphs, implementation 2,563 1m 48s ✓ E Store 2700 data-structures 386 2m 29s ✓...

CF 1010F - Tree

CF 1010F - Tree Rating: 3400 Tags: fft, graphs, trees Solve time: 3m 1s Verified: no Solution Problem Understanding We are given a rooted tree where the root is fixed at vertex 1 and every vertex has at most two children. After a process of “pruning”, we keep a connected set of vertices that must still contain the root. This means the remaining vertices always form a rooted subtree: if...

CF 1010D - Mars rover

CF 1010D - Mars rover Rating: 2000 Tags: dfs and similar, graphs, implementation, trees Solve time: 1m 48s Verified: yes Solution Problem Understanding The structure we are given is a rooted tree where every node behaves like a logic component. Leaves are fixed boolean inputs, while internal nodes compute boolean values from their children using standard gates such as AND, OR, XOR, and NOT. The root node produces the final...

CF 1012B - Chemical table

CF 1012B - Chemical table Rating: 1900 Tags: constructive algorithms, dfs and similar, dsu, graphs, matrices Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid where each cell is a distinct chemical element. Some of these cells are already available in the laboratory. From any three elements forming three corners of an axis-aligned rectangle, the scientists can always synthesize the fourth corner....

Codeforces Round 503 (by SIS, Div. 1)

Codeforces Round 503 (by SIS, Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-3200 | 12m 46s # Problem Rating Tags Accepted Time ✓ A Elections 1700 brute-force, greedy 4,852 2m 7s ✓ B The hat 2000 binary-search, interactive 2,112 2m 40s C Sergey's problem 3000 constructive-algorithms, graphs 1,454 2m 39s D Large Triangle 2700 binary-search, geometry, sortings 742 2m 44s ✓ E Raining season 3200...

CF 1019C - Sergey's problem

CF 1019C - Sergey's problem Rating: 3000 Tags: constructive algorithms, graphs Solve time: 2m 39s Verified: no Solution Problem Understanding We are given a directed graph with up to one million vertices and one million edges. The task is to choose a subset of vertices $Q$ with two properties that interact in a non-trivial way. First, no two vertices inside $Q$ are allowed to be connected by a direct edge...

Codeforces Round 503 (by SIS, Div. 2)

Codeforces Round 503 (by SIS, Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 1000-1000 | 4m 30s # Problem Rating Tags Accepted Time ✓ A New Building for SIS 1000 math 9,453 3m ✓ B Badge 1000 brute-force, dfs-and-similar, graphs 25,118 1m 30s ✓

CF 1020B - Badge

CF 1020B - Badge Rating: 1000 Tags: brute force, dfs and similar, graphs Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a directed structure over students where each student points to exactly one other student. This forms a functional graph: every node has outdegree one, so starting from any node and repeatedly following pointers eventually forces us into a cycle. A teacher starts at some student...

CF 1023F - Mobile Phone Network

CF 1023F - Mobile Phone Network Rating: 2600 Tags: dfs and similar, dsu, graphs, trees Solve time: 2m 53s Verified: no Solution Problem Understanding We are given a connected graph with two types of edges. One set is already fixed by a competitor, each with a known cost. The second set is ours: these edges form a forest, and we are allowed to assign any integer weights to them. After...

CF 1027F - Session in BSU

CF 1027F - Session in BSU Rating: 2400 Tags: binary search, dfs and similar, dsu, graph matchings, graphs Solve time: 6m 57s Verified: no Solution Problem Understanding We are given a collection of tasks, each task representing an exam that must be scheduled on exactly one of two possible days. For exam $i$, there are two candidate days $a_i$ and $b_i$, and we must choose one of them. The constraint...

Educational Codeforces Round 49 (Rated for Div. 2)

Educational Codeforces Round 49 (Rated for Div. 2) Div. 2 | 7 problems | 4/7 verified | Difficulty 1000-2600 | 35m 5s # Problem Rating Tags Accepted Time ✓ A Palindromic Twist 1000 implementation, strings 18,799 6m 17s ✓ B Numbers on the Chessboard 1200 implementation, math 8,744 3m 37s C Minimum Value Rectangle 1600 greedy 7,152 6m 46s D Mouse Hunt 1700 dfs-and-similar, graphs 8,366 3m 49s ✓ E...

CF 1027D - Mouse Hunt

CF 1027D - Mouse Hunt Rating: 1700 Tags: dfs and similar, graphs Solve time: 3m 49s Verified: yes Solution Problem Understanding We can think of the dorm as a directed graph where each room has exactly one outgoing edge. From every room i , the mouse deterministically moves to a[i] after one second. Because every node has exactly one outgoing edge, the graph decomposes into chains that eventually enter directed...

CF 1029E - Tree with Small Distances

CF 1029E - Tree with Small Distances Rating: 2100 Tags: dp, graphs, greedy Solve time: 5m 54s Verified: yes Solution Problem Understanding We are given a tree where vertex 1 plays a special role: it is the root of our concern. The structure is initially fixed, but we are allowed to add new edges between any two previously unconnected vertices. The goal is to modify the graph so that every...

Technocup 2019 - Elimination Round 2

Technocup 2019 - Elimination Round 2 Special | 6 problems | 1/6 verified | Difficulty 800-2800 | 1h 4m # Problem Rating Tags Accepted Time ✓ A Golden Plate 800 implementation, math 13,396 6m 26s ✓ B Curiosity Has No Limits 1500 4,064 17m 21s C Cram Time 1600 greedy 5,608 13m 38s D Minimum path 1900 greedy 2,985 6m 46s E Triple Flips 2600 constructive-algorithms 571 8m 34s F...

CF 1031F - Familiar Operations

CF 1031F - Familiar Operations Rating: 2800 Tags: brute force, graphs, math Solve time: 11m 31s Verified: no Solution Stopped thinking

Lyft Level 5 Challenge 2018 - Elimination Round

Lyft Level 5 Challenge 2018 - Elimination Round Special | 6 problems | 3/6 verified | Difficulty 1000-3500 | 50m 45s # Problem Rating Tags Accepted Time ✓ A King Escape 1000 dfs-and-similar, graphs, implementation 16,031 4m 19s ✓ B Square Difference 1100 math, number-theory 11,951 4m 51s ✓ C Permutation Game 1600 brute-force, dp, games 6,216 11m 39s ✓ D Divisors 2000 interactive, math, number-theory 2,611 8m 46s F...

CF 1033A - King Escape

CF 1033A - King Escape Rating: 1000 Tags: dfs and similar, graphs, implementation Solve time: 4m 19s Verified: yes Solution Problem Understanding We are given a square chessboard with coordinates from 1 to n in both directions. A queen is fixed at one cell, and it attacks along rows, columns, and diagonals in the usual chess sense. A king starts at one cell and wants to reach another cell, moving...

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

CF 1038E - Maximum Matching

CF 1038E - Maximum Matching Rating: 2400 Tags: bitmasks, brute force, dfs and similar, dp, graphs Solve time: 4m 42s Verified: yes Solution Problem Understanding Each block can be viewed as a weighted undirected edge between two colors, where each endpoint is one of two possible colors depending on orientation. Choosing an orientation is equivalent to deciding a direction for that edge in a path, because once we fix an...

CF 1039C - Network Safety

CF 1039C - Network Safety Rating: 2200 Tags: dfs and similar, dsu, graphs, math, sortings Solve time: 8m 24s Verified: yes Solution Problem Understanding We are given a network of servers where each server has an integer label (an encryption key) in a fixed bit range. Some pairs of servers are connected, and a connection is considered safe only if the two endpoints currently hold different values. A virus is...

CF 1041E - Tree Reconstruction

CF 1041E - Tree Reconstruction Rating: 1900 Tags: constructive algorithms, data structures, graphs, greedy Solve time: 6m 6s Verified: no Solution Problem Understanding We are given a multiset of information that originally came from a rooted structure, but the structure itself is hidden. There exists a tree on vertices numbered from 1 to n, and each vertex has a unique label equal to its number. For every edge in that...

Bubble Cup 11 - Finals [Online Mirror, Div. 1]

Bubble Cup 11 - Finals [Online Mirror, Div. 1] Div. 1 | 5 problems | 4/5 verified | Difficulty 2200-3400 | 21m 12s # Problem Rating Tags Accepted Time ✓ A Last chance 2500 data-structures, flows, graph-matchings 574 4m 32s C Hyperspace Highways 2300 dfs-and-similar, graphs, trees 827 3m 39s ✓ F Shady Lady 3400 geometry, math 114 3m 49s ✓ G AI robots 2200 data-structures 1,984 2m 33s ✓...

CF 1045A - Last chance

CF 1045A - Last chance Rating: 2500 Tags: data structures, flows, graph matchings, graphs, trees Solve time: 4m 32s Verified: no Solution Problem Understanding We are given a collection of weapons and a line of ships, and we want to assign each destroyed ship to exactly one weapon. Each weapon has a limited way of interacting with ships, and the goal is to maximize how many ships get assigned and...

CF 1045C - Hyperspace Highways

CF 1045C - Hyperspace Highways Rating: 2300 Tags: dfs and similar, graphs, trees Solve time: 3m 39s Verified: yes Solution Problem Understanding We are given a connected undirected graph with up to one hundred thousand vertices and up to half a million edges. Each query asks for the shortest path length between two given vertices, measured in number of edges. A crucial extra constraint changes the structure of the graph....

CF 1559C - Mocha and Hiking

CF 1559C - Mocha and Hiking Rating: 1200 Tags: constructive algorithms, graphs Solve time: 2m 31s Verified: no Solution

CF 1559D2 - Mocha and Diana (Hard Version)

CF 1559D2 - Mocha and Diana (Hard Version) Rating: 2500 Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, greedy, trees, two pointers Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given two different forests built on the same set of vertices from 1 to n. Each forest is already acyclic, but they may have multiple connected components. The task is to add as many new...

CF 1553G - Common Divisor Graph

CF 1553G - Common Divisor Graph Rating: 2700 Tags: brute force, constructive algorithms, dsu, graphs, hashing, math, number theory Solve time: 3m 40s Verified: yes Solution Problem Understanding We are given a fixed set of nodes, each labeled by a distinct integer. Two nodes are connected if their labels share any prime factor. This means the graph is determined entirely by the prime factorizations of the given numbers. For each...

CF 1553E - Permutation Shift

CF 1553E - Permutation Shift Rating: 2100 Tags: brute force, combinatorics, constructive algorithms, dfs and similar, dsu, graphs, math Solve time: 4m 48s Verified: yes Solution Problem Understanding We start from the identity permutation, which is simply the numbers from 1 to n in order. Someone first rotates this array cyclically to the right by an unknown shift k, and then performs at most m arbitrary swaps of elements. After...

CF 1388D - Captain Flint and Treasure

CF 1388D - Captain Flint and Treasure Rating: 2000 Tags: data structures, dfs and similar, graphs, greedy, implementation, trees Solve time: 2m 14s Verified: yes Solution Problem Understanding We are given a directed structure over indices from 1 to n, where each index i has a value a[i] and a pointer b[i]. The pointer either leads to another index or is absent (represented by -1). The crucial operation is that...

CF 1383D - Rearrange

CF 1383D - Rearrange Rating: 2800 Tags: brute force, constructive algorithms, graphs, greedy, sortings Solve time: 5m 10s Verified: no Solution Problem Understanding We are given a complete permutation of numbers from 1 to $n \cdot m$ arranged in an $n \times m$ grid. From this grid we extract two small summaries: the set of row maxima and the set of column maxima. The task is to construct a new...

CF 1383C - String Transformation 2

CF 1383C - String Transformation 2 Rating: 3100 Tags: bitmasks, dp, graphs, trees Solve time: 4m 49s Verified: no Solution Problem Understanding We are given two strings of equal length, built from a small alphabet of 20 letters. We start with string A and want to transform it into string B using a specific operation. One operation works like this: pick a letter x. Look at all positions in A...

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

CF 1369D - TediousLee

CF 1369D - TediousLee Rating: 1900 Tags: dp, graphs, greedy, math, trees Solve time: 2m 30s Verified: no Solution Problem Understanding The structure in this problem is a very specific rooted tree that grows level by level. Starting from a single node, each level expands every vertex depending on how many children it already has. A leaf gets one new child, a node with exactly one child gets two new...

CF 1361C - Johnny and Megan's Necklace

CF 1361C - Johnny and Megan's Necklace Rating: 2500 Tags: binary search, bitmasks, constructive algorithms, dfs and similar, dsu, graphs Solve time: 6m 34s Verified: no Solution Problem Understanding Each input item is a small “edge gadget” consisting of two pearls, and each pearl has an integer color in the range $[0, 2^{20})$. The goal is to take all these $n$ gadgets and connect their endpoints into one single cycle...

CF 1346D - Constructing the Dungeon

CF 1346D - Constructing the Dungeon Rating: 1600 Tags: *special, graphs, greedy Solve time: 2m 56s Verified: yes Solution Problem Understanding We are given an undirected connected graph where vertices represent rooms and edges represent tunnels. Each tunnel already has a fixed value, and we must assign a value to every room. The rule ties rooms and tunnels together tightly: for every edge between two rooms, the edge value must...

CF 1344C - Quantifier Question

CF 1344C - Quantifier Question Rating: 2600 Tags: dfs and similar, dp, graphs, math Solve time: 3m 29s Verified: no Solution Problem Understanding We are given a directed graph on variables $x_1, x_2, \dots, x_n$. Each constraint $x_j < x_k$ behaves like an edge $j \to k$, and a full assignment of real values satisfies the formula only if every edge points from a smaller value to a larger value....

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

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

CF 1335F - Robots on a Grid

CF 1335F - Robots on a Grid Rating: 2200 Tags: data structures, dfs and similar, dsu, graphs, greedy, matrices Solve time: 1m 11s Verified: no Solution Problem Understanding Each cell in the grid behaves like a deterministic state in a directed graph. From every cell, there is exactly one outgoing edge pointing to one of its four neighbors, as dictated by the arrow in that cell. Because of the boundary...

CF 1334D - Minimum Euler Cycle

CF 1334D - Minimum Euler Cycle Rating: 1800 Tags: constructive algorithms, graphs, greedy, implementation Solve time: 4m 3s Verified: no Solution Problem Understanding We are asked to construct a walk in a complete directed graph on vertices labeled from 1 to n, where every ordered pair of distinct vertices forms a directed edge. This means between any two different vertices u and v, both directions u → v and v...

CF 1328D - Carousel

CF 1328D - Carousel Rating: 1800 Tags: constructive algorithms, dp, graphs, greedy, math Solve time: 3m 4s Verified: no Solution Problem Understanding We are given a circular arrangement of positions, each holding an animal type. The positions are connected in a cycle, so after the last position comes the first again. We must assign a color to each position. The constraint is local: whenever two neighboring positions on the cycle...

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

Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics) Div. 1 | 3 problems | 1/3 verified | Difficulty 1300-3500 | 12m 47s # Problem Rating Tags Accepted Time ✓ A Unusual Competitions 1300 greedy 12,886 4m 47s C Instant Noodles 2300 graphs, hashing, math 2,703 2m 42s F Assigning Fares 3500 dp, trees 162 5m 18s ✓

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

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

CF 1310D - Tourism

CF 1310D - Tourism Rating: 2300 Tags: dp, graphs, probabilities Solve time: 14m 40s Verified: no Solution Problem Understanding We are given a complete directed graph of cities where every ordered pair of distinct cities has a travel cost. Starting from city 1, we must perform exactly $k$ moves, and end again at city 1. Each move is just choosing a directed edge and paying its cost. Revisiting cities and...

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

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

CF 1304D - Shortest and Longest LIS

CF 1304D - Shortest and Longest LIS Rating: 1800 Tags: constructive algorithms, graphs, greedy, two pointers Solve time: 2m 52s Verified: no Solution Problem Understanding We are given a pattern of strict comparisons between consecutive positions in a permutation of size n . Each position tells whether the next value must be larger or smaller than the current one. From this constraint, many permutations are possible. The task is not...

CF 1301D - Time to Run

CF 1301D - Time to Run Rating: 2000 Tags: constructive algorithms, graphs, implementation Solve time: 5m 58s Verified: yes Solution Problem Understanding The grid in this problem can be viewed as a directed version of the standard rectangular lattice where every pair of horizontally or vertically adjacent cells is connected by two opposite directed edges. Moving once means traversing exactly one such directed edge, and each traversal has unit cost....

CF 1292D - Chaotic V.

CF 1292D - Chaotic V. Rating: 2700 Tags: dp, graphs, greedy, math, number theory, trees Solve time: 7m 22s Verified: no Solution Problem Understanding The graph in this problem is not given explicitly, but fully determined by the structure of integers. Every positive integer is a node, and each number $x > 1$ has a directed edge to $x / f(x)$, where $f(x)$ is the smallest prime factor of $x$....

Codeforces Round 616 (Div. 2)

Codeforces Round 616 (Div. 2) Div. 2 | 3 problems | 0/3 verified | Difficulty 900-2800 | 15m 2s # Problem Rating Tags Accepted Time ✓ A Even But Not Even 900 greedy, math, strings 20,680 4m 55s B Array Sharpening 1300 greedy, implementation 15,358 5m 13s F Coffee Varieties (easy version) 2800 graphs, interactive 726 4m 54s

CF 1291F - Coffee Varieties (easy version)

CF 1291F - Coffee Varieties (easy version) Rating: 2800 Tags: graphs, interactive Solve time: 4m 54s Verified: no Solution Problem Understanding We are given a hidden sequence of café types, where each café produces exactly one integer “coffee variety”. We do not know the sequence itself, but we can probe cafés one by one. The interaction tool behaves like a sliding-window memory system. Every time we query a café, the...

Codeforces Round 616 (Div. 1)

Codeforces Round 616 (Div. 1) Div. 1 | 5 problems | 1/5 verified | Difficulty 1600-3500 | 19m 56s # Problem Rating Tags Accepted Time ✓ A Mind Control 1600 brute-force, data-structures, implementation 8,899 5m 40s C Prefix Enlightenment 2400 dfs-and-similar, dsu, graphs 2,012 1m 56s ✓ D Coffee Varieties (hard version) 3000 constructive-algorithms, graphs, interactive 948 3m 41s E Cartesian Tree 3300 data-structures 670 4m 7s F Making Shapes...

CF 1290D - Coffee Varieties (hard version)

CF 1290D - Coffee Varieties (hard version) Rating: 3000 Tags: constructive algorithms, graphs, interactive Solve time: 3m 41s Verified: no Solution Problem Understanding We are given a hidden array of length $n$, where each position represents a café and each café produces exactly one type of coffee. The value at position $i$ is the coffee variety label $a_i$, but we never see it directly. Instead, we can query a café...

CF 1286B - Numbers on Tree

CF 1286B - Numbers on Tree Rating: 1800 Tags: constructive algorithms, data structures, dfs and similar, graphs, greedy, trees Solve time: 5m 21s Verified: no Solution Problem Understanding We are given a rooted tree where every node has a hidden integer value. What we do know is the tree structure and, for each node, a number c_i . This number tells us something local to the subtree: among all nodes...

CF 1285E - Delete a Segment

CF 1285E - Delete a Segment Rating: 2300 Tags: brute force, constructive algorithms, data structures, dp, graphs, sortings, trees, two pointers Solve time: 3m 14s Verified: no Solution Problem Understanding We are given several intervals on a number line. Each interval represents a continuous segment of covered points. If multiple intervals overlap or touch, their combined covered region merges into a single continuous piece when we take the union. The...

CF 1284G - Seollal

CF 1284G - Seollal Rating: 3300 Tags: graphs Solve time: 13m 26s Verified: no Solution Problem Understanding The task is to take a small grid with blocked and open cells and construct a special “maze representation” on a refined grid. Each input cell becomes a node in a graph, and adjacency exists between orthogonally neighboring open cells. Some edges between neighbors may be removed by placing walls. The key requirement...

CF 1284F - New Year and Social Network

CF 1284F - New Year and Social Network Rating: 3200 Tags: data structures, graph matchings, graphs, math, trees Solve time: 10m Verified: no Solution Problem Understanding We are given two different spanning trees over the same set of $n$ vertices. One tree, call it $T_1$, represents the main network, and the second tree $T_2$ is a backup structure. Each edge in $T_1$ is a potential failure point. If an edge...

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

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

CF 1282E - The Cake Is a Lie

CF 1282E - The Cake Is a Lie Rating: 2400 Tags: constructive algorithms, data structures, dfs and similar, graphs Solve time: 5m 36s Verified: no Solution Problem Understanding We are given a collection of triangles that once formed a triangulation of a convex polygon with $n$ vertices. Each triangle corresponds to one cut made during a process where we repeatedly remove a boundary triangle from a convex polygon until nothing...

CF 1280C - Jeremy Bearimy

CF 1280C - Jeremy Bearimy Rating: 2000 Tags: dfs and similar, graphs, greedy, trees Solve time: 11m 16s Verified: no Solution Problem Understanding We are given a weighted tree with $2k$ vertices. On these vertices we must place $2k$ people, where the people are grouped into $k$ fixed pairs. After the placement, each pair contributes the distance between the two vertices they occupy, measured along the unique path in the...

Codeforces Round 606 (Div. 1, based on Technocup 2020 Elimination Round 4)

Codeforces Round 606 (Div. 1, based on Technocup 2020 Elimination Round 4) Div. 1 | 4 problems | 2/4 verified | Difficulty 1400-3400 | 21m 23s # Problem Rating Tags Accepted Time ✓ A As Simple as One and Two 1400 dp, greedy 12,947 5m 49s B Two Fairs 1900 combinatorics, dfs-and-similar, dsu 5,668 1m 34s ✓ C Beautiful Rectangle 2300 brute-force, combinatorics, constructive-algorithms 1,788 11m 51s F Asterisk Substrings...

CF 1270G - Subset with Zero Sum

CF 1270G - Subset with Zero Sum Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs, math Solve time: 5m 39s Verified: no Solution Problem Understanding We are given an array of integers where each position i has a value a[i] constrained in a tight interval that depends on its index. The i-th element is never too negative and never too large: it always lies between i − n and...

CF 1255B - Fridge Lockers

CF 1255B - Fridge Lockers Rating: 1100 Tags: graphs, implementation Solve time: 13m 47s Verified: no Solution Problem Understanding We are given a complete system of lockers where each locker belongs to one person and has a weight. We are allowed to install exactly $m$ undirected connections between distinct lockers. Each connection between locker $u$ and $v$ costs $a_u + a_v$. The structural constraint is the key difficulty: a locker...

CF 1253D - Harmonious Graph

CF 1253D - Harmonious Graph Rating: 1700 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, sortings Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given an undirected graph on vertices labeled from 1 to n, and we are allowed to add edges. The goal is to make the graph satisfy a very specific reachability constraint that depends on the natural ordering of vertices. The condition says...

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

CF 1242B - 0-1 MST

CF 1242B - 0-1 MST Rating: 1900 Tags: dfs and similar, dsu, graphs, sortings Solve time: 5m 48s Verified: yes Solution Problem Understanding We are given a complete undirected graph on $n$ vertices. Every pair of vertices is connected, but edges come in only two possible weights: either 0 or 1. Among all $\binom{n}{2}$ edges, exactly $m$ of them have weight 1, and every other edge implicitly has weight 0....

CF 1239F - Swiper, no swiping!

CF 1239F - Swiper, no swiping! Rating: 3400 Tags: graphs, implementation Solve time: 9m 13s Verified: no Solution Problem Understanding We are given multiple connected graphs, each with up to half a million vertices and edges in total across all test cases. For each graph, we are asked to decide whether it is possible to remove a non-empty proper subset of vertices such that, after deleting those vertices and all...

CF 1239D - Catowice City

CF 1239D - Catowice City Rating: 2400 Tags: 2-sat, dfs and similar, graph matchings, graphs Solve time: 5m 40s Verified: no Solution Problem Understanding We are given a system of $n$ people, each of whom owns exactly one cat, forming a natural pairing between person $i$ and cat $i$. Alongside this structure, there is an undirected bipartite relationship between people and cats: each input edge connects a resident $a$ with...

CF 1236F - Alice and the Cactus

CF 1236F - Alice and the Cactus Rating: 3000 Tags: dfs and similar, graphs, math, probabilities Solve time: 5m 7s Verified: no Solution Problem Understanding We are given a connected undirected graph with a special structure: it is a cactus, meaning every edge belongs to at most one simple cycle. On this graph, each vertex independently survives with probability $1/2$, otherwise it is deleted together with all incident edges. After...

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

CF 1220E - Tourism

CF 1220E - Tourism Rating: 2200 Tags: dfs and similar, dp, dsu, graphs, greedy, trees Solve time: 3m 3s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each vertex represents a city and each city has a fixed value. Alex starts from a specific city and walks through the graph by traversing edges, with one restriction: he is not allowed to immediately traverse back along...

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1]

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] Div. 1 | 9 problems | 4/9 verified | Difficulty 1500-3000 | 34m 41s # Problem Rating Tags Accepted Time ✓ A BubbleReactor 2800 dp, graphs 180 3m 35s B Guarding warehouses 3000 data-structures, geometry 95 3m 5s C Jumping Transformers 2600 dp 217 3m 5s D Xor Spanning Tree 2400 divide-and-conquer, fft, graphs 600 5m 2s E Product Tuples...

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

CF 1218D - Xor Spanning Tree

CF 1218D - Xor Spanning Tree Rating: 2400 Tags: divide and conquer, fft, graphs Solve time: 5m 2s Verified: no Solution Problem Understanding We are given an undirected graph where each edge represents a wormhole between two planets and has a repair cost. The goal is not to build a classical spanning tree with minimum sum of weights, but to choose a subset of edges that keeps the graph connected...

CF 1218A - BubbleReactor

CF 1218A - BubbleReactor Rating: 2800 Tags: dp, graphs Solve time: 3m 35s Verified: no Solution Problem Understanding We are given an undirected graph with $N$ vertices and exactly $N$ edges, and no pair of vertices is connected by more than one edge. This structure guarantees that every connected component contains exactly one simple cycle, while all other edges form trees attached to that cycle. In other words, each component...

CF 1217F - Forced Online Queries Problem

CF 1217F - Forced Online Queries Problem Rating: 2600 Tags: data structures, divide and conquer, dsu, graphs, trees Solve time: 5m 11s Verified: no Solution Problem Understanding The graph starts empty, but it is continuously modified by two types of operations. The first operation toggles an edge between two vertices, and the second operation asks whether two vertices are connected in the current graph. The twist is that every query...

CF 1217D - Coloring Edges

CF 1217D - Coloring Edges Rating: 2100 Tags: constructive algorithms, dfs and similar, graphs Solve time: 2m 41s Verified: yes Solution Problem Understanding We are given a directed graph where each edge is fixed in advance, and we must assign a color (an integer label) to every edge. The constraint is not about vertices but about directed cycles: if you look at all edges of a single color, they must...

CF 1214E - Petya and Construction Set

CF 1214E - Petya and Construction Set Rating: 2000 Tags: constructive algorithms, graphs, math, sortings, trees Solve time: 2m 50s Verified: no Solution Problem Understanding We are asked to build a graph on $2n$ labeled vertices using exactly $2n-1$ edges. Since a connected graph with $2n$ vertices and $2n-1$ edges is necessarily a tree, the construction is really about designing a tree on these labeled nodes. The vertices come in...

CF 1213F - Unstable String Sort

CF 1213F - Unstable String Sort Rating: 2100 Tags: data structures, dfs and similar, dsu, graphs, greedy, implementation, strings Solve time: 5m 5s Verified: yes Solution Problem Understanding We are given two permutations of the indices of a string, and both permutations describe an ordering in which the hidden string must appear sorted. In other words, if we take the string and read characters in the order dictated by permutation...

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

CF 1209D - Cow and Snacks

CF 1209D - Cow and Snacks Rating: 1700 Tags: dfs and similar, dsu, graphs Solve time: 2m 49s Verified: yes Solution Problem Understanding We are given a collection of snack types and a group of guests. Each snack type appears exactly once, so there are $n$ distinct items labeled $1$ to $n$. Each guest has two preferred snack types. Guests arrive in some chosen order, and when a guest arrives,...

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

CF 1163E - Magical Permutation

CF 1163E - Magical Permutation Rating: 2400 Tags: bitmasks, brute force, constructive algorithms, data structures, graphs, math Solve time: 4m 34s Verified: yes Solution Problem Understanding We are given a set of integers that represent allowed XOR “moves”. We are asked to build a permutation of all integers from 0 up to some power of two minus one, such that every adjacent pair in the permutation differs by a value...

CF 1103C - Johnny Solving

CF 1103C - Johnny Solving Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs, math Solve time: 4m 21s Verified: yes Solution Problem Understanding We are given a connected undirected simple graph where every vertex has degree at least three. Along with the graph, we are also given an integer $k$. The task is not to compute a single structure, but to decide between two fundamentally different constructions. One option...

CF 1100E - Andrew and Taxi

CF 1100E - Andrew and Taxi Rating: 2200 Tags: binary search, dfs and similar, graphs Solve time: 7m 2s Verified: no Solution Problem Understanding We are given a directed graph representing a city map, where each road has a direction and a cost associated with reversing it. The mayor’s goal is to modify the directions of some roads so that the final directed graph contains no directed cycle in the...

CF 1098C - Construct a tree

CF 1098C - Construct a tree Rating: 2400 Tags: binary search, constructive algorithms, dfs and similar, graphs, greedy, trees Solve time: 5m 19s Verified: yes Solution Problem Understanding We are asked to build a rooted tree on vertices labeled from 1 to n, where vertex 1 is fixed as the root. Each node except the root has exactly one parent, so the structure is fully determined by the parent array....

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

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

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

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

Codeforces Round 518 (Div. 2) [Thanks, Mail.Ru!] Div. 2 | 3 problems | 2/3 verified | Difficulty 1200-1700 | 17m 32s # Problem Rating Tags Accepted Time ✓ A Birthday 1400 math 7,261 4m 29s ✓ B LCM 1200 math, number-theory 13,026 5m 21s ✓ C Colored Rooks 1700 constructive-algorithms, graphs 3,348 7m 42s

CF 1068C - Colored Rooks

CF 1068C - Colored Rooks Rating: 1700 Tags: constructive algorithms, graphs Solve time: 7m 42s Verified: no Solution Problem Understanding We are asked to construct a geometric configuration of colored rooks on a huge grid so that connectivity properties encode a given graph on colors. Each color corresponds to a set of points on a $10^9 \times 10^9$ grid. Each point is a rook. Two rooks are considered adjacent if...

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

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

Mail.Ru Cup 2018 Round 2

Mail.Ru Cup 2018 Round 2 Special | 7 problems | 6/7 verified | Difficulty 900-3500 | 22m 6s # Problem Rating Tags Accepted Time ✓ A Metro 900 graphs 13,441 59s ✓ B Alice and Hairdresser 1300 dsu, implementation 5,541 3m 44s ✓ C Lucky Days 1900 math, number-theory 2,055 2m 17s ✓ D Refactoring 2400 greedy, implementation, strings 649 2m 38s ✓ E Segments on the Line 2500 binary-search,...

CF 1055A - Metro

CF 1055A - Metro Rating: 900 Tags: graphs Solve time: 59s Verified: yes Solution Problem Understanding The metro system can be seen as a line of stations from 1 to n, with two directed ways of movement. One track allows movement from smaller indices to larger ones, while the other allows movement in the opposite direction. Bob starts at station 1 and wants to reach station s. The complication is...

CF 909E - Coprocessor

CF 909E - Coprocessor Rating: 1900 Tags: dfs and similar, dp, graphs, greedy Solve time: 5m 29s Verified: yes Solution Problem Understanding The program consists of tasks that must be executed in an order consistent with a dependency graph. Each task may depend on earlier tasks, forming a directed acyclic graph where execution is only allowed once all prerequisites are completed. Every task has a fixed execution location. Some tasks...

CF 901D - Weighting a Tree

CF 901D - Weighting a Tree Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs Solve time: 2m 17s Verified: no Solution Problem Understanding We are given a connected undirected graph where every edge must eventually receive an integer weight. For each vertex, we are also given a target value, and the requirement is that if you look at all edges incident to a vertex and sum their weights, that...

CF 901C - Bipartite Segments

CF 901C - Bipartite Segments Rating: 2300 Tags: binary search, data structures, dfs and similar, dsu, graphs, two pointers Solve time: 2m 44s Verified: yes Solution Problem Understanding We are given a graph whose vertices are arranged in a fixed line from 1 to n. The edges are arbitrary, but the structure is restricted so that the graph does not contain any cycle of even length when edges are treated...

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

CF 1056G - Take Metro

CF 1056G - Take Metro Rating: 2900 Tags: brute force, data structures, graphs Solve time: 2m 57s Verified: yes Solution Problem Understanding We are given a circular metro line with stations numbered from 1 to n. Moving along the circle is always possible in both directions, so from any station we can go clockwise or counter-clockwise with wrap-around. The line is split into two color regions: stations from 1 to...

CF 1056D - Decorate Apple Tree

CF 1056D - Decorate Apple Tree Rating: 1600 Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, sortings, trees Solve time: 2m 24s Verified: yes Solution Problem Understanding We are given a rooted tree, with node 1 fixed as the root. Only leaf nodes initially receive colors, and all other nodes are uncolored. A leaf, in this problem, is defined as a node whose subtree consists of only itself, which...

CF 1061E - Politics

CF 1061E - Politics Rating: 2600 Tags: flows, graphs Solve time: 6m 52s Verified: yes Solution Problem Understanding We are given two different spanning trees over the same set of cities. Each tree represents how one candidate organizes the country, with a chosen root city acting as their capital. On top of each tree, every city has a requirement: a candidate specifies for certain nodes how many selected cities (ports)...

CF 1062F - Upgrading Cities

CF 1062F - Upgrading Cities Rating: 2900 Tags: dfs and similar, graphs Solve time: 3m 52s Verified: no Solution Problem Understanding We are given a directed acyclic graph of cities connected by one-way roads. From the constraints, the graph has no directed cycles, so it behaves like a partial order: some cities are comparable through reachability, and others are incomparable. A city is called important if it behaves like a...

Codeforces Round 520 (Div. 2)

Codeforces Round 520 (Div. 2) Div. 2 | 6 problems | 4/6 verified | Difficulty 1300-2900 | 22m 46s # Problem Rating Tags Accepted Time ✓ A A Prank 1300 greedy, implementation 9,306 2m 47s ✓ B Math 1500 greedy, math, number-theory 9,890 7m 36s ✓ C Banh-mi 1600 greedy, implementation, math 5,950 3m 30s D Fun with Integers 1800 dfs-and-similar, graphs, implementation 4,170 2m 39s ✓ E Company 2300...

CF 1062D - Fun with Integers

CF 1062D - Fun with Integers Rating: 1800 Tags: dfs and similar, graphs, implementation, math Solve time: 2m 39s Verified: yes Solution Problem Understanding We are given a set of integers from the range of absolute values 2 up to n, and each number also has its negative counterpart available. Think of every integer i in this range as a node in a graph, including both i and -i. A...

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

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

Educational Codeforces Round 52 (Rated for Div. 2)

Educational Codeforces Round 52 (Rated for Div. 2) Div. 2 | 7 problems | 3/7 verified | Difficulty 800-2700 | 26m 32s # Problem Rating Tags Accepted Time ✓ A Vasya and Chocolate 800 implementation, math 15,264 3m 48s ✓ B Vasya and Isolated Vertices 1300 constructive-algorithms, graphs 11,597 5m 51s C Make It Equal 1600 greedy 8,290 2m 44s ✓ D Three Pieces 2200 dfs-and-similar, dp, shortest-paths 1,445 3m...

CF 1065B - Vasya and Isolated Vertices

CF 1065B - Vasya and Isolated Vertices Rating: 1300 Tags: constructive algorithms, graphs Solve time: 5m 51s Verified: no Solution Problem Understanding We are given a simple undirected graph with a fixed number of vertices and edges. The graph has no self-loops and no duplicate edges. The structure is otherwise unrestricted, meaning we are free to imagine any valid configuration that uses exactly $m$ edges among $n$ labeled vertices. A...

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

CF 1082G - Petya and Graph

CF 1082G - Petya and Graph Rating: 2400 Tags: flows, graphs Solve time: 3m 37s Verified: no Solution Problem Understanding We are given a simple undirected graph where each vertex carries a cost and each edge carries a reward. We are allowed to pick any subset of vertices, and then from the edges we may only keep those whose endpoints are both selected. The score of a chosen subgraph is...

Educational Codeforces Round 55 (Rated for Div. 2)

Educational Codeforces Round 55 (Rated for Div. 2) Div. 2 | 7 problems | 4/7 verified | Difficulty 1200-2800 | 31m 12s # Problem Rating Tags Accepted Time ✓ A Vasya and Book 1200 implementation, math 9,273 4m 41s B Vova and Trophies 1600 greedy 8,028 4m 31s ✓ C Multi-Subject Competition 1600 greedy, sortings 6,133 2m 12s ✓ D Maximum Diameter Graph 1800 constructive-algorithms, graphs, implementation 4,089 6m 31s...

CF 1082D - Maximum Diameter Graph

CF 1082D - Maximum Diameter Graph Rating: 1800 Tags: constructive algorithms, graphs, implementation Solve time: 6m 31s Verified: no Solution Problem Understanding We are given a set of vertices, and for each vertex we are told how many edges it is allowed to participate in at most. Our task is to actually construct a simple undirected connected graph that respects these degree limits and, among all such graphs, maximizes the...

Codeforces Round 591 (Div. 1, based on Technocup 2020 Elimination Round 1)

Codeforces Round 591 (Div. 1, based on Technocup 2020 Elimination Round 1) Div. 1 | 1 problems | 0/1 verified | Difficulty 3100-3100 | 3m 41s # Problem Rating Tags Accepted Time ✓ F Football 3100 graphs 327 3m 41s

CF 1240F - Football

CF 1240F - Football Rating: 3100 Tags: graphs Solve time: 3m 41s Verified: no Solution Problem Understanding We are given a set of teams and a list of potential matches between pairs of teams. Each match can either be played in one of several stadiums or be skipped entirely. If a match is played, it contributes one game to both participating teams, and that contribution is tied to the chosen...

Codeforces Round 875 (Div. 1)

Codeforces Round 875 (Div. 1) Div. 1 | 6 problems | 3/6 verified | Difficulty 1400-3500 | 14m 54s # Problem Rating Tags Accepted Time ✓ A Copil Copac Draws Trees 1400 dfs-and-similar, dp, graphs 20,309 2m ✓ B The BOSS Can Count Pairs 2000 brute-force, math 5,850 3m 9s ✓ C Hyperregular Bracket Strings 2400 combinatorics, greedy, hashing 2,184 1m 14s D Mex Tree 2800 brute-force, dp, trees 932...

CF 1830A - Copil Copac Draws Trees

CF 1830A - Copil Copac Draws Trees Rating: 1400 Tags: dfs and similar, dp, graphs, trees Solve time: 2m Verified: yes Solution Problem Understanding We are given a tree described by an ordered list of edges. The edges are not just connectivity information, their order matters because the drawing process scans them sequentially again and again. The process starts with only vertex 1 being considered “drawn”. In each full pass...

CF 1817B - Fish Graph

CF 1817B - Fish Graph Rating: 1900 Tags: brute force, constructive algorithms, dfs and similar, graphs Solve time: 2m 40s Verified: no Solution Problem Understanding We are given an undirected simple graph and asked whether we can select a subset of its edges that forms a very specific structure called a Fish Graph. The target structure consists of two parts. First, there must be a simple cycle. Second, exactly one...

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

CF 1804E - Routing

CF 1804E - Routing Rating: 2400 Tags: bitmasks, brute force, dfs and similar, dp, graphs Solve time: 2m 51s Verified: no Solution Problem Understanding We are given an undirected, connected graph with up to 20 vertices. Each vertex represents a server, and edges represent direct bidirectional communication links. For every server $u$, we must choose exactly one adjacent vertex $a(u)$. Think of this as assigning each node a single outgoing...

CF 1740I - Arranging Crystal Balls

CF 1740I - Arranging Crystal Balls Rating: 3500 Tags: data structures, divide and conquer, dp, geometry, graphs, number theory Solve time: 3m 48s Verified: no Solution Problem Understanding We are given a circular arrangement of $n$ positions, each holding a value modulo $m$. The goal is to transform every value into zero. The only allowed move selects a contiguous block of exactly $k$ consecutive positions on the circle and then...

CF 1726D - Edge Split

CF 1726D - Edge Split Rating: 2000 Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, probabilities, trees Solve time: 3m 56s Verified: no Solution Problem Understanding We are given a connected undirected graph with a small number of extra edges beyond a tree. For each edge, we must decide whether it is colored red or blue. After fixing the coloring, we look at two induced subgraphs: one formed...

CF 1726C - Jatayu's Balanced Bracket Sequence

CF 1726C - Jatayu's Balanced Bracket Sequence Rating: 1300 Tags: data structures, dsu, graphs, greedy Solve time: 7m 30s Verified: no Solution Problem Understanding We are given a balanced bracket string of length $2n$. Each position in this string is treated as a vertex in a graph. Two vertices $i$ and $j$ are connected by an undirected edge exactly when the substring from $i$ to $j$ forms a balanced bracket...

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

CF 1721F - Matching Reduction

CF 1721F - Matching Reduction Rating: 2800 Tags: brute force, constructive algorithms, dfs and similar, flows, graph matchings, graphs, interactive Solve time: 4m 58s Verified: no Solution Problem Understanding We are working with a bipartite graph where the left side has $n_1$ vertices and the right side has $n_2$ vertices. Edges are fixed and each edge connects one left vertex to one right vertex. At any moment, we consider a...

CF 1718E - Impressionism

CF 1718E - Impressionism Rating: 3500 Tags: constructive algorithms, graphs, implementation, math Solve time: 5m 14s Verified: no Solution Problem Understanding We are given two rectangular grids of the same size, and each grid contains colored cells. The only allowed operations are swapping entire rows or swapping entire columns. The goal is to determine whether we can transform the first grid into the second using only these row and column...

CF 1656I - Neighbour Ordering

CF 1656I - Neighbour Ordering Rating: 3500 Tags: constructive algorithms, graphs Solve time: 10m 36s Verified: no Solution Problem Understanding We are given a connected undirected graph, and we are allowed to choose, independently for every vertex, an ordering of its adjacent vertices. This ordering induces a local notion of comparison: at a vertex $v$, if neighbor $a$ appears later than neighbor $b$ in the list of $v$, we say...

CF 1656G - Cycle Palindrome

CF 1656G - Cycle Palindrome Rating: 3200 Tags: constructive algorithms, graphs, math Solve time: 5m 59s Verified: no Solution Problem Understanding We are given an array of integers and we are allowed to reorder its indices using a very restricted type of permutation: a single cycle that visits every position exactly once before returning to the start. In other words, we do not get to choose an arbitrary permutation, only...

CF 1656F - Parametric MST

CF 1656F - Parametric MST Rating: 2600 Tags: binary search, constructive algorithms, graphs, greedy, math, sortings Solve time: 4m 51s Verified: no Solution Problem Understanding We are given an array of integers, and we build a complete graph where every pair of vertices is connected. The weight of an edge between vertices $i$ and $j$ depends on a parameter $t$ and is defined as a linear function in $t$: it...

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

CF 1583E - Moment of Bloom

CF 1583E - Moment of Bloom Rating: 2200 Tags: constructive algorithms, dfs and similar, graph matchings, graphs, greedy, trees Solve time: 6m 39s Verified: no Solution Problem Understanding We are given a connected undirected graph where every edge initially has weight 0. We then receive a sequence of queries, each query specifying two vertices. For each query, we must choose a simple path between its endpoints and add 1 to...

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

CF 1578K - Kingdom of Islands

CF 1578K - Kingdom of Islands Rating: 2800 Tags: brute force, graphs, implementation Solve time: 4m 15s Verified: no Solution Problem Understanding We are given a set of jarls, each belonging to exactly one island. The default rule of conflict is simple: jarls from different islands are in conflict, while jarls from the same island are peaceful. On top of this, there are a few exceptions, at most 20 pairs,...

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

CF 1556H - DIY Tree

CF 1556H - DIY Tree Rating: 3300 Tags: graphs, greedy, math, probabilities Solve time: 4m 54s Verified: no Solution Problem Understanding We are given a complete weighted undirected graph on $n$ vertices, so every pair of vertices is connected and every edge has a known cost. The task is to select exactly $n-1$ edges that form a spanning tree of minimum total weight, but with an additional restriction that only...

CF 1556F - Sports Betting

CF 1556F - Sports Betting Rating: 2500 Tags: bitmasks, combinatorics, dp, graphs, math, probabilities Solve time: 5m 15s Verified: yes Solution Problem Understanding We are given a complete tournament where every pair of teams plays exactly one match. The result of each match is random, but biased: team $i$ beats team $j$ with probability proportional to its strength, specifically $\frac{a_i}{a_i + a_j}$. Each match outcome is independent. From all match...

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

CF 1549B - Gregor and the Pawn Game

CF 1549B - Gregor and the Pawn Game Rating: 800 Tags: dfs and similar, dp, flows, graph matchings, graphs, greedy, implementation Solve time: 7m 50s Verified: no Solution Problem Understanding We are given a square board of size $n \times n$, but only the first and last rows matter. The bottom row contains Gregor’s pawns, and the top row contains enemy pawns. Every column is either empty or occupied independently...

Codeforces Round 736 (Div. 1)

Codeforces Round 736 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1400-3400 | 29m 12s # Problem Rating Tags Accepted Time ✓ A Web of Lies 1400 brute-force, graphs, greedy 17,730 3m 42s B Integers Have Friends 1800 binary-search, data-structures, divide-and-conquer 11,343 2m 20s ✓ C The Three Little Pigs 2500 combinatorics, dp, fft 2,038 5m 48s D1 Gregor and the Odd Cows (Easy) 2300 bitmasks,...

CF 1548E - Gregor and the Two Painters

CF 1548E - Gregor and the Two Painters Rating: 3400 Tags: data structures, divide and conquer, graphs, greedy, math Solve time: 6m 7s Verified: no Solution Problem Understanding The ceiling is split into a grid where each row contributes a fixed amount of paint and each column contributes another fixed amount. This makes every cell’s paint level completely determined by two arrays: one attached to rows and one attached to...

CF 1548A - Web of Lies

CF 1548A - Web of Lies Rating: 1400 Tags: brute force, graphs, greedy Solve time: 3m 42s Verified: no Solution Problem Understanding We are working with a graph whose vertices are fixed nobles numbered from 1 to n, where the label also represents their strength. Edges represent mutual friendships, and these edges change over time through insertions and deletions. The interesting part is a dynamic process defined on the current...

CF 1547G - How Many Paths?

CF 1547G - How Many Paths? Rating: 2100 Tags: dfs and similar, dp, graphs, trees Solve time: 8m 54s Verified: no Solution Problem Understanding We are given a directed graph where we start from node 1 and consider all possible directed walks that end at each vertex. A walk can revisit nodes and edges arbitrarily many times. For every vertex, we are not asked to compute the exact number of...

CF 1545C - AquaMoon and Permutations

CF 1545C - AquaMoon and Permutations Rating: 2800 Tags: 2-sat, brute force, combinatorics, constructive algorithms, graph matchings, graphs Solve time: 4m 36s Verified: no Solution Problem Understanding We are given $2n$ permutations of size $n$. Each row is a rearrangement of numbers $1$ to $n$. We are promised that there exists a hidden structure behind these rows: they originally came from two intertwined Latin squares of size $n$, but then...

CF 1543E - The Final Pursuit

CF 1543E - The Final Pursuit Rating: 2700 Tags: bitmasks, constructive algorithms, divide and conquer, graphs, greedy, math Solve time: 6m Verified: no Solution Problem Understanding The input describes a graph that is guaranteed to be a permuted hypercube. This means the graph has exactly $2^n$ vertices, every vertex has degree exactly $n$, and the structure is isomorphic to the standard $n$-dimensional hypercube, but the vertex labels have been arbitrarily...

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

Codeforces Global Round 15

Codeforces Global Round 15 Global | 9 problems | 4/9 verified | Difficulty 800-3400 | 40m 13s # Problem Rating Tags Accepted Time ✓ A Subsequence Permutation 800 sortings, strings 25,328 6m 22s ✓ B Running for Gold 1500 combinatorics, graphs, greedy 16,929 1m 43s ✓ C Maximize the Intersections 1800 combinatorics, constructive-algorithms, geometry 6,286 7m 19s D Array Differentiation 1800 bitmasks, brute-force, constructive-algorithms 7,886 5m 22s E Colors and...

CF 1533I - Excursions

CF 1533I - Excursions Rating: - Tags: *special, constructive algorithms, dfs and similar, flows, graph matchings, graphs Solve time: 7m 26s Verified: yes Solution Problem Understanding We can view the situation as a two-layer directed routing process between two bipartite sets of nodes. One set corresponds to sights in Saratov, the other to sights in Engels. Each bus route is bidirectional in the sense that it can be used in...

CF 1533G - Biome Map

CF 1533G - Biome Map Rating: - Tags: *special, constructive algorithms, dfs and similar, graphs Solve time: 5m 39s Verified: no Solution Problem Understanding We are given a small grid of biome “types”, where each type is identified by a pair of parameters coming from a fixed $n \times m$ table. Some of these pairs exist and are assigned a unique integer identifier, while others are unavailable. Our task is...

CF 1511D - Min Cost String

CF 1511D - Min Cost String Rating: 1600 Tags: brute force, constructive algorithms, graphs, greedy, strings Solve time: 3m 58s Verified: no Solution Problem Understanding We are asked to construct a string of length n using only the first k lowercase Latin letters. Among all possible such strings, we want one that minimizes a specific cost function. The cost is defined over adjacent pairs inside the string. Every position i...

CF 1499G - Graph Coloring

CF 1499G - Graph Coloring Rating: 3100 Tags: data structures, graphs, interactive Solve time: 5m 52s Verified: no Solution Problem Understanding We start with a bipartite graph whose edges arrive online. Each edge must eventually be assigned one of two labels, red or blue. For any vertex, we compare how many incident edges are red versus blue, and we pay the absolute difference of these two counts. The goal is...

CF 1491G - Switch and Flip

CF 1491G - Switch and Flip Rating: 2800 Tags: constructive algorithms, graphs, math Solve time: 3m 25s Verified: no Solution Problem Understanding We start with a permutation placed on positions from 1 to n. Each position contains a coin with a label, and every coin also has a direction state, initially all facing up. The goal is to transform this arrangement so that every label ends up in its matching...

CF 1411C - Peaceful Rooks

CF 1411C - Peaceful Rooks Rating: 1700 Tags: dfs and similar, dsu, graphs Solve time: 8m 35s Verified: no Solution Problem Understanding We are given a chessboard where no two rooks initially share a row or a column, so every rook sits in a distinct row and a distinct column. A move allows us to pick one rook and slide it any distance in a straight horizontal or vertical line,...

CF 1348F - Phoenix and Memory Rating: 2600 Tags: data structures, dfs and similar, graphs, greedy Model: gpt-5-3-mini Solve time: 3m 38s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e260b-7944-83ec-b0a5-2cf38808ad6a Solution Problem Understanding Each position in the final lineup comes with a constraint: at position i , the person sitting there must have a label from a contiguous range [a_i, b_i] . The labels themselves form a permutation of 1 to n...

CF 1299D - Around the World Rating: 3000 Tags: bitmasks, combinatorics, dfs and similar, dp, graphs, math, trees Model: gpt-5-5 Solve time: 1m 17s Verified: yes (1/1 samples) Solution Problem Understanding We are given an undirected connected graph with weighted edges. The graph has a special structural restriction: any simple cycle that includes vertex 1 can only have length at most 3, meaning vertex 1 is not part of any...

CF 1338E - JYPnation Rating: 3500 Tags: graphs Model: gpt-5-3-mini Solve time: 6m 45s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e15eb-5b44-83ec-8326-84ab80778caa Solution Problem Understanding We are given a directed graph on $n$ cities where every pair of distinct cities has exactly one directed edge between them. This means between any two nodes $i$ and $j$, either $i \to j$ exists or $j \to i$ exists, but never both. The graph is...

CF 1268D - Invertation in Tournament Rating: 3200 Tags: brute force, divide and conquer, graphs, math Model: gpt-5-3-mini Solve time: 3m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d8cdd-8bac-83ec-a73f-1c9a8e0eb4dd Solution Problem Understanding We are given a complete directed graph where every pair of vertices has exactly one directed edge between them. This is a tournament. The structure is fully described by an adjacency matrix, so for each pair we know which...

CF 1278D - Segment Tree Rating: 2100 Tags: data structures, dsu, graphs, trees Model: gpt-5-5 Solve time: 5m 4s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d9e0d-9954-83ec-baf5-8cc431e755d5 Solution Problem Understanding We are given a collection of line segments on a number line. Each segment is defined by two distinct integer endpoints, and no two endpoints coincide anywhere in the input. From these segments we build a graph where each segment is a...

CF 1364D - Ehab's Last Corollary Rating: 2100 Tags: constructive algorithms, dfs and similar, graphs, greedy, implementation, trees Model: gpt-5-3-mini Solve time: 2m 58s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e47c0-f80c-83ec-a0be-6bd3409333b8 Solution Problem Understanding We are given a connected undirected graph. Alongside the graph, we are given a parameter $k$, and we are asked to produce one of two possible outputs depending on what structure we can guarantee from the graph....

CF 1272E - Nearest Opposite Parity Rating: 1900 Tags: dfs and similar, graphs, shortest paths Model: gpt-5-5 Solve time: 2m 33s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d93db-6110-83ec-a15a-c26dceb74345 Solution Problem Understanding We are given a one-dimensional board of length $n$, where each cell $i$ contains a value $a_i$. From position $i$, we can jump deterministically to at most two other positions: $i - a_i$ and $i + a_i$, as long as...

CF 1316D - Nash Matrix Rating: 2000 Tags: constructive algorithms, dfs and similar, graphs, implementation Model: gpt-5-3-mini Solve time: 2m 17s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2de522-2b84-83ec-9041-a685022914d8 Solution Problem Understanding We are given a complete description of what happens on every cell of an $n \times n$ grid, but only in a compressed form. For each starting cell, we are told the final outcome of repeatedly following movement instructions written...

CF 1340D - Nastya and Time Machine Rating: 2600 Tags: constructive algorithms, dfs and similar, graphs, trees Model: gpt-5-3-mini Solve time: 4m 8s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e1967-f7b8-83ec-a5ed-2b526864a552 Solution Problem Understanding We are given a tree of $n$ vertices, with vertex $1$ as the starting and ending location. The traveler begins at vertex $1$ at time $0$. Every edge traversal takes exactly one unit of time, so moving along...

CF 1368G - Shifting Dominoes Rating: 3200 Tags: data structures, geometry, graphs, trees Model: gpt-5-3-mini Solve time: 5m 46s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e4f95-3500-83ec-8e99-f5fd31a6a1fc Solution Problem Understanding We are given a fully covered grid where every cell belongs to exactly one domino, and every domino occupies two orthogonally adjacent cells. So the input is essentially a perfect matching on the grid graph. After this initial tiling is fixed, Bill...

CF 1354E - Graph Coloring Rating: 2100 Tags: dfs and similar, dp, graphs Model: gpt-5-3-mini Solve time: 7m 8s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e30b4-0040-83ec-b7bd-a3c3c9ef7f21 Solution Problem Understanding We are given an undirected graph and asked to assign each vertex one of three labels, 1, 2, or 3. The labels are not arbitrary: every edge forces its endpoints to have labels that differ by exactly one. That means an edge...

CF 1324F - Maximum White Subtree Rating: 1800 Tags: dfs and similar, dp, graphs, trees Model: gpt-5-3-mini Solve time: 2m 38s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2def77-79d8-83ec-88a3-9beb32439d59 Solution Problem Understanding We are given a tree where every vertex is colored either white or black. For each vertex $v$, we want to look at all connected subgraphs of the tree that include $v$, and among them choose one that maximizes the...

CF 1327B - Princesses and Princes Rating: 1200 Tags: brute force, graphs, greedy Model: gpt-5-5 Solve time: 5m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2df92a-38f4-83ec-b77a-1e2eecc301d8 Solution Problem Understanding We are given a process that sequentially assigns each daughter to a prince (represented by a kingdom number). Each daughter has a sorted list of kingdoms she considers acceptable. When processing daughter i , we scan her list from smallest to largest...

CF 1370F1 - The Hidden Pair (Easy Version) Rating: 2400 Tags: binary search, dfs and similar, graphs, interactive, shortest paths, trees Model: gpt-5-5 Solve time: 2m 35s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e5372-8200-83ec-8cd2-b905527f64bf Solution Problem Understanding We are working with a tree where two unknown vertices have been chosen as hidden targets. The only way to gain information is through queries on subsets of nodes. When we query a set,...

CF 1365D - Solve The Maze Rating: 1700 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, implementation, shortest paths Model: gpt-5-3-mini Solve time: 2m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e497a-d7ec-83ec-8d81-7aac5910ae19 Solution Problem Understanding The maze is a small grid where each cell is either a wall, empty space, a good person, or a bad person. All movement is four-directional and blocked by walls. The only exit is the...

CF 1325F - Ehab's Last Theorem Rating: 2500 Tags: constructive algorithms, dfs and similar, graphs, greedy Model: gpt-5-5 Solve time: 6m 18s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2df425-592c-83ec-8ec3-29541239cb9e Solution Problem Understanding We are given a connected undirected simple graph with up to $10^5$ vertices and up to $2 \cdot 10^5$ edges. The task is not to optimize some cost or count something, but to explicitly construct one of two specific...

CF 1366F - Jog Around The Graph Rating: 2700 Tags: binary search, dp, geometry, graphs Model: gpt-5-3-mini Solve time: 2m 30s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e4b1c-15e8-83ec-9c91-18e935817a8a Solution Problem Understanding We are working with a connected undirected graph where each edge has a positive weight. We start at vertex 1 and we are allowed to walk along edges, revisiting vertices and edges as many times as we want. What matters...

CF 1327D - Infinite Path Rating: 2200 Tags: brute force, dfs and similar, graphs, math, number theory Model: gpt-5-3-mini Solve time: 3m 33s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2df9a5-21fc-83ec-95b0-5cb969319ab1 Solution Problem Understanding We are given a permutation that defines a directed graph where every node has exactly one outgoing edge. Each index points to its image under the permutation, and each node also carries a color. Starting from a node,...

CF 1244D - Paint the Tree

CF 1244D - Paint the Tree Rating: 1800 Tags: brute force, constructive algorithms, dp, graphs, implementation, trees Solve time: 2m 52s Verified: yes Solution Problem Understanding We are given a tree where each node must be assigned one of three colors, and each assignment has a cost depending on the chosen color. The structure constraint is not a standard edge constraint but a path constraint: if we take any path...

Codeforces Round 589 (Div. 2)

Codeforces Round 589 (Div. 2) Div. 2 | 6 problems | 4/6 verified | Difficulty 800-2500 | 23m 45s # Problem Rating Tags Accepted Time ✓ A Distinct Digits 800 brute-force, implementation 23,291 4m 3s ✓ B Filling the Grid 1400 implementation, math 11,889 5m 8s C Primes and Multiplication 1700 math, number-theory 9,634 1m 39s ✓ D Complete Tripartite 1900 brute-force, constructive-algorithms, graphs 5,418 5m 56s ✓ E Another...

Technocup 2020 - Elimination Round 3

Technocup 2020 - Elimination Round 3 Special | 9 problems | 5/9 verified | Difficulty 1100-2600 | 36m 16s # Problem Rating Tags Accepted Time ✓ A Math Problem 1100 math 10,264 2m 48s ✓ B Box 1200 constructive-algorithms 10,429 5m 37s C Messy 1700 constructive-algorithms 5,790 5m 39s D1 Optimal Subsequences (Easy Version) 1600 data-structures, greedy 6,829 3m 5s ✓ D2 Optimal Subsequences (Hard Version) 1800 data-structures, greedy 4,726...

CF 1228D - Complete Tripartite

CF 1228D - Complete Tripartite Rating: 1900 Tags: brute force, constructive algorithms, graphs, hashing, implementation Solve time: 5m 56s Verified: yes Solution Problem Understanding We are given an undirected graph with up to 100,000 vertices and up to 300,000 edges. The task is to split all vertices into exactly three non-empty groups so that the structure between every pair of groups is perfectly regular. The rule between any two groups...

Codeforces Round 599 (Div. 1)

Codeforces Round 599 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1500-3400 | 17m 26s # Problem Rating Tags Accepted Time ✓ A Tile Painting 1500 constructive-algorithms, math, number-theory 13,265 6m 35s ✓ B 0-1 MST 1900 dfs-and-similar, dsu, graphs 9,241 5m 48s ✓ C Sum Balance 2400 bitmasks, dfs-and-similar, dp 1,947 1m 43s D Number Discovery 3400 math 234 1m 42s E Planar Perimeter 3200...

CF 1213G - Path Queries

CF 1213G - Path Queries Rating: 1800 Tags: divide and conquer, dsu, graphs, sortings, trees Solve time: 4m 31s Verified: yes Solution Problem Understanding We are given a weighted tree where every edge has a cost, and we are asked multiple questions about how “expensive” paths between pairs of vertices can be. For any two vertices $u$ and $v$, there is exactly one simple path between them because the graph...

CF 1211I - Unusual Graph

CF 1211I - Unusual Graph Rating: 3000 Tags: *special, graphs Solve time: 2m 22s Verified: yes Solution Problem Understanding We are given an undirected graph with up to 500 vertices. The graph is known to come from a very specific hidden labeling process: each vertex originally had a number between 0 and 15, and an edge existed between two vertices if and only if their labels differ in exactly one...

Codeforces Round 534 (Div. 1)

Codeforces Round 534 (Div. 1) Div. 1 | 4 problems | 3/4 verified | Difficulty 1400-3100 | 11m 18s # Problem Rating Tags Accepted Time ✓ A Grid game 1400 constructive-algorithms, implementation 10,596 3m 23s ✓ B Game with modulo 2000 binary-search, constructive-algorithms, interactive 3,528 1m 38s C Johnny Solving 2700 constructive-algorithms, dfs-and-similar, graphs 953 4m 21s ✓ D Professional layer 3100 bitmasks, dp 493 1m 56s ✓

Codeforces Round 580 (Div. 1)

Codeforces Round 580 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1200-3400 | Time: 28m 3s Problem Name Rating Tags Solve Time Verified A Almost Equal 1200 constructive-algorithms, greedy, math 5m 8s ✗ B Shortest Cycle 1900 bitmasks, brute-force, graphs 1m 41s ✓ C Palindromic Paths 2400 implementation, interactive 5m 3s ✗ D Almost All 2700 constructive-algorithms, trees 4m 42s ✗ E Expected Value...

CF 1200F - Graph Traveler

CF 1200F - Graph Traveler Rating: 2300 Tags: brute force, data structures, dfs and similar, dp, graphs, implementation, math, number theory Solve time: 5m 16s Verified: no Solution Problem Understanding We are given a directed graph where each vertex behaves like a deterministic machine with a twist: the outgoing edge is not fixed, but chosen based on a changing integer state $c$. Every time we arrive at a vertex, we...

CF 1198E - Rectangle Painting 2

CF 1198E - Rectangle Painting 2 Rating: 2500 Tags: flows, graph matchings, graphs Solve time: 4m 14s Verified: no Solution Problem Understanding We are given an extremely large $n \times n$ grid, but instead of listing individual black cells, the input describes black regions as up to 50 axis-aligned rectangles. Every cell outside these rectangles is white initially, and inside them is black. The task is to repaint the grid...

CF 1198C - Matching vs Independent Set

CF 1198C - Matching vs Independent Set Rating: 2000 Tags: constructive algorithms, graphs, greedy, sortings Solve time: 6m 44s Verified: no Solution Problem Understanding We are given several undirected graphs, each with exactly $3n$ vertices. For each graph, we must construct one of two specific structures of size $n$: either a matching consisting of $n$ edges, or an independent set consisting of $n$ vertices. If neither structure exists, we must...

CF 1187G - Gang Up

CF 1187G - Gang Up Rating: 2500 Tags: flows, graphs Solve time: 7m 46s Verified: no Solution Problem Understanding We are given a small undirected graph representing a town, with a designated meeting point at node 1. Several people start at specified nodes and all want to reach node 1. Time is discrete, and each person can either wait at their current node or traverse one edge per minute. We...

CF 1186F - Vus the Cossack and a Graph

CF 1186F - Vus the Cossack and a Graph Rating: 2400 Tags: dfs and similar, graphs, greedy, implementation Solve time: 6m 47s Verified: no Solution Problem Understanding We are given an undirected simple graph. Every vertex has some initial degree, and we are allowed to delete edges. After deletions, each vertex must still keep at least half of its original incident edges, rounded up. At the same time, the total...

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

CF 1184E3 - Daleks' Invasion (hard)

CF 1184E3 - Daleks' Invasion (hard) Rating: 2400 Tags: data structures, dsu, graphs, trees Solve time: 5m 41s Verified: no Solution Problem Understanding We are given an undirected connected graph with weighted edges, where each edge represents a corridor between two locations and has an associated energy value. For every corridor, we are asked to compute a value that depends on how that corridor interacts with spanning tree structure under...

CF 1184E1 - Daleks' Invasion (easy)

CF 1184E1 - Daleks' Invasion (easy) Rating: 1900 Tags: graphs, trees Solve time: 3m 19s Verified: no Solution Problem Understanding We are given a connected undirected graph where each edge represents a Time Corridor with an associated energy cost. The Daleks do not necessarily use all corridors. Instead, they always choose a set of corridors that connects all nodes while minimizing total energy cost, which is exactly the definition of...

CF 1178H - Stock Exchange

CF 1178H - Stock Exchange Rating: 3500 Tags: binary search, flows, graphs Solve time: 9m 46s Verified: no Solution Problem Understanding We are given a collection of $2n$ stocks. Each stock $i$ has a price that evolves over time in a very simple deterministic way: at integer time $t$, its price is $a_i \cdot t + b_i$. Time starts at $t = 0$, and prices only change at integer moments....

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

CF 1176D - Recover it!

CF 1176D - Recover it! Rating: 1800 Tags: dfs and similar, graphs, greedy, number theory, sortings Solve time: 9m 59s Verified: no Solution Problem Understanding We are given an unknown array of integers. Each original value is between 2 and 200000. From this hidden array, a second array is produced by expanding every element into two values and then shuffling everything. Our task is to reconstruct any original array that...

CF 1174F - Ehab and the Big Finale

CF 1174F - Ehab and the Big Finale Rating: 2400 Tags: constructive algorithms, divide and conquer, graphs, implementation, interactive, trees Solve time: 11m 51s Verified: no Solution Problem Understanding We are given a tree with nodes numbered from 1 to n, rooted at node 1. Inside this tree, there is a hidden node x. The only way to learn about x is through two types of queries: asking for the...

Codeforces Round 562 (Div. 2)

Codeforces Round 562 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1500 | Time: 3m 38s Problem Name Rating Tags Solve Time Verified A Circle Metro 900 implementation, math 2m 23s ✓ B Pairs 1500 graphs, implementation 1m 15s ✓

CF 1166F - Vicky's Delivery Service

CF 1166F - Vicky's Delivery Service Rating: 2400 Tags: data structures, dsu, graphs, hashing Solve time: 3m 29s Verified: no Solution Problem Understanding The task describes a growing undirected graph where each edge also carries a color. Edges only ever get added, never removed. Interleaved with these updates are connectivity queries, but connectivity is not defined in the usual sense of arbitrary walks. Instead, a valid path must satisfy a...

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

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

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

CF 1263D - Secret Passwords Rating: 1500 Tags: dfs and similar, dsu, graphs Model: gpt-5-3-mini Solve time: 1m 57s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d8071-ffa0-83ec-857d-abcaf5fc2df4 Solution Problem Understanding We are given a collection of strings, where each string represents a password. The system does not treat these passwords as completely independent. Instead, it defines a notion of “equivalence” between passwords: two passwords are equivalent if they share at least one...

CF 1266D - Decreasing Debts Rating: 2000 Tags: constructive algorithms, data structures, graphs, greedy, implementation, math, two pointers Model: gpt-5-3-mini Solve time: 3m 17s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d8730-d1b0-83ec-b40b-a8447d19d422 Solution Problem Understanding We are given a directed weighted graph where each vertex represents a person and each directed edge represents a debt from one person to another. The value on an edge is how much money the source person...

CF 1266H - Red-Blue Graph Rating: 3400 Tags: dp, graphs, math, matrices, meet-in-the-middle Model: gpt-5-3-mini Solve time: 4m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d882b-4204-83ec-8de7-91488c63d3c1 Solution Problem Understanding We are given a directed graph where every vertex except the last one has exactly two outgoing edges, one red and one blue. At any moment, each vertex is in one of two internal states, which decides which of its two edges...

Codeforces Round 529 (Div. 3)

Codeforces Round 529 (Div. 3) Type: Div. 3 | Problems: 6 | Verified: 3/6 | Rating range: 800-1900 | Time: 56m 48s Problem Name Rating Tags Solve Time Verified A Repeating Cipher 800 implementation 22m 53s ✗ B Array Stabilization 900 implementation 1m 24s ✓ C Powers Of Two 1400 bitmasks, greedy 12m 24s ✗ D Circular Dance 1600 implementation 11m 57s ✗ E Almost Regular Bracket Sequence 1900 implementation...

CF 1093D - Beautiful Graph

CF 1093D - Beautiful Graph Rating: 1700 Tags: dfs and similar, graphs Solve time: 3m 33s Verified: yes Solution Problem Understanding We are given an undirected graph and asked to assign each vertex one value from the set {1, 2, 3}. The assignment is valid only if every edge connects two vertices whose values sum to an odd number. The task is to count how many such assignments exist, taken...

CF 1091E - New Year and the Acquaintance Estimation

CF 1091E - New Year and the Acquaintance Estimation Rating: 2400 Tags: binary search, data structures, graphs, greedy, implementation, math, sortings Solve time: 4m 22s Verified: no Solution Problem Understanding We are given a simple undirected graph on $n+1$ vertices, but one vertex is missing from the data. Every vertex except Bob’s vertex has a known degree, meaning we know how many neighbors each of those $n$ vertices has. The...

2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 8/13 | Rating range: 1000-2900 | Time: 40m 49s Problem Name Rating Tags Solve Time Verified A Company Merging 1300 greedy 2m 19s ✓ B LaTeX Expert 1900 - 1m 7s ✗ C New Year Presents 2400 constructive-algorithms, data-structures 3m 14s ✗ D Similar Arrays 1800 constructive-algorithms 2m 13s...

CF 1090H - Linearization

CF 1090H - Linearization Rating: 2900 Tags: graphs Solve time: 2m 42s Verified: no Solution The problem statement section is empty, so I don’t have the actual definition of Codeforces 1090H - Linearization to base the editorial on. Since this is a 2900-rated graph problem, the exact formulation (what “linearization” means, what is being optimized, and the constraints on the graph structure) is essential. Different interpretations lead to completely different...

CF 1090E - Horseback Riding

CF 1090E - Horseback Riding Rating: 2300 Tags: flows, graphs Solve time: 1m 35s Verified: no Solution The problem statement sections are empty, so there isn’t enough information to reconstruct what Codeforces 1090E - Horseback Riding actually asks or which flow/graph construction it uses. Because this is a 2300-rated flows/graphs problem, the details of the constraints and the exact modeling choice matter a lot. Even small differences like whether edges...

CF 1089M - Minegraphed

CF 1089M - Minegraphed Rating: 2400 Tags: constructive algorithms, graphs Solve time: 2m 50s Verified: no Solution Got it - I can write a full Codeforces-style editorial (intuition, key idea, proof, implementation details, complexity, etc.). Please send the problem statement (or link / screenshot text), and if possible also: constraints sample input/output whether you want beginner / intermediate / advanced level explanation Once I have that, I’ll produce a proper...

2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 6/13 | Rating range: 900-3400 | Time: 49m 47s Problem Name Rating Tags Solve Time Verified A Alice the Fan 2200 dp 9m 32s ✗ B Bimatching 3200 graphs 55s ✓ C Cactus Search 2500 interactive 1m 34s ✓ D Distance Sum 3100 graphs 1m 45s ✗ E Easy Chess...

CF 1089H - Harder Satisfiability

CF 1089H - Harder Satisfiability Rating: 3400 Tags: 2-sat, dfs and similar, graphs Solve time: 2m 35s Verified: yes Solution Problem Understanding We are given a logical system built from boolean variables, where constraints are expressed as implications between literals. Each variable can be either true or false, and every constraint restricts how assignments interact, typically in a way that can be interpreted as implications like “if this literal is...

CF 1089D - Distance Sum

CF 1089D - Distance Sum Rating: 3100 Tags: graphs Solve time: 1m 45s Verified: no Solution I can't write a correct editorial for Codeforces 1089D from the information provided. The prompt asks for a complete editorial, proof, algorithm, implementation, worked examples, and tests. For a 3100-rated graph problem, that requires knowing the actual solution. The statement alone is not enough to reliably reconstruct the intended algorithm, especially since the key...

CF 920E - Connected Components?

CF 920E - Connected Components? Rating: 2100 Tags: data structures, dfs and similar, dsu, graphs Solve time: 2m 56s Verified: yes Solution Problem Understanding The graph in this problem is not given in the usual way. Instead of listing edges that exist, the input lists pairs of vertices that are explicitly disconnected. Every pair of vertices that does not appear in this list should be treated as having an edge...

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

CF 919D - Substring

CF 919D - Substring Rating: 1700 Tags: dfs and similar, dp, graphs Solve time: 12m 47s Verified: yes Solution Problem Understanding We are given a directed graph where each vertex carries a lowercase letter. A valid walk follows directed edges from node to node, and we are allowed to revisit nodes and edges as long as we respect direction. For any such walk, we look at the sequence of letters...

CF 917B - MADMAX

CF 917B - MADMAX Rating: 1700 Tags: dfs and similar, dp, games, graphs Solve time: 4m 34s Verified: no Solution Problem Understanding We are given a directed acyclic graph where each edge carries a lowercase letter. Two tokens start on possibly different vertices: one belongs to Max and one to Lucas. They take turns moving their own token along outgoing edges, and the twist is that the letters along the...

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

Educational Codeforces Round 36 (Rated for Div. 2)

Educational Codeforces Round 36 (Rated for Div. 2) Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 900-2400 | Time: 57m 49s Problem Name Rating Tags Solve Time Verified A Garden 900 implementation 11m 44s ✓ B Browser 1300 implementation 5m 31s ✓ C Permute Digits 1700 dp, greedy 3m 31s ✓ D Almost Acyclic Graph 2200 dfs-and-similar, graphs 3m 24s ✓ E Physical Education Lessons 2300...

CF 915F - Imbalance Value of a Tree

CF 915F - Imbalance Value of a Tree Rating: 2400 Tags: data structures, dsu, graphs, trees Solve time: 14m 38s Verified: no Solution Problem Understanding We are given a tree with n vertices, where each vertex carries an integer label. For any pair of vertices x and y , we define the imbalance of the path connecting them as the difference between the maximum and minimum labels along that path....

CF 915D - Almost Acyclic Graph

CF 915D - Almost Acyclic Graph Rating: 2200 Tags: dfs and similar, graphs Solve time: 3m 24s Verified: yes Solution Problem Understanding We are given a directed graph with n vertices and m edges. Each edge has a direction from some vertex u to another vertex v . The task is to determine whether we can remove at most one edge to make the graph acyclic. A directed graph is...

CF 913F - Strongly Connected Tournament

CF 913F - Strongly Connected Tournament Rating: 2800 Tags: dp, graphs, math, probabilities Solve time: 6m 14s Verified: no Solution Problem Understanding We are asked to compute the expected total number of games in a recursively defined chess tournament. There are n players, each with a known probability of beating any lower-numbered player. The tournament works by first having all players compete with each other once, then organizing players into...

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

CF 911F - Tree Destruction

CF 911F - Tree Destruction Rating: 2400 Tags: constructive algorithms, dfs and similar, graphs, greedy, trees Solve time: 14m 49s Verified: no Solution Problem Understanding We are asked to process a tree with n vertices by performing n - 1 operations that each choose two leaves, add the distance between them to a running total, and remove one of the leaves. The goal is to maximize the total sum of...

CF 908F - New Year and Rainbow Roads

CF 908F - New Year and Rainbow Roads Rating: 2400 Tags: graphs, greedy, implementation Solve time: 4m 37s Verified: yes Solution Problem Understanding We are given a sequence of points on the number line, each colored red, green, or blue. The goal is to connect the points with edges such that every point is reachable from every other point, and the total sum of edge lengths is minimized. The catch...

CF 906C - Party

CF 906C - Party Rating: 2400 Tags: bitmasks, brute force, dp, graphs Solve time: 7m 24s Verified: yes Solution Problem Understanding We have a connected friendship graph. Choosing a vertex means that all of its neighbors become pairwise adjacent. In graph theory language, we are allowed to pick a vertex and turn its open neighborhood into a clique. The process continues until the whole graph becomes a complete graph. We...

CF 903G - Yet Another Maxflow Problem

CF 903G - Yet Another Maxflow Problem Rating: 2700 Tags: data structures, flows, graphs Solve time: 2m 13s Verified: no Solution Problem Understanding The graph consists of two directed chains. Vertices $A_1,\dots,A_n$ form one chain and $B_1,\dots,B_n$ form another. Capacities on the $B$-chain are fixed. Capacities on the $A$-chain are updated online. There are also directed edges from some $A_x$ to some $B_y$, and no edges in the reverse direction....

CF 1089B - Bimatching

CF 1089B - Bimatching Rating: 3200 Tags: graphs Solve time: 55s Verified: yes Solution Problem Understanding We are given two sets of vertices, each with n nodes, and m edges that connect vertices from the first set to vertices in the second. Each edge has an associated cost. The task is to select two edges for each vertex in both sets such that every vertex participates in exactly two chosen...

CF 1095F - Make It Connected

CF 1095F - Make It Connected Rating: 1900 Tags: dsu, graphs, greedy Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given n vertices, each with a number a_i written on it, and no edges initially. We can connect any two vertices by paying the sum of their numbers a_x + a_y . Additionally, there are m special offers, each allowing a particular edge to be added at...

CF 1102F - Elongated Matrix

CF 1102F - Elongated Matrix Rating: 2000 Tags: binary search, bitmasks, brute force, dp, graphs Solve time: 1m 6s Verified: yes Solution Problem Understanding We have a rectangular grid of numbers with $n$ rows and $m$ columns. We are allowed to reorder the rows however we like, but the order of numbers within each row is fixed. After picking an order, we traverse the grid column by column from top...

CF 1107F - Vasya and Endless Credits

CF 1107F - Vasya and Endless Credits Rating: 2600 Tags: dp, flows, graph matchings, graphs, sortings Solve time: 1m 57s Verified: no Solution Problem Understanding Vasya starts with zero burles and wants to buy a car. The bank offers n credit deals, each giving him an initial sum a_i immediately and requiring monthly payments of b_i for k_i months. Vasya can take at most one credit per month, but multiple...

CF 1108F - MST Unification

CF 1108F - MST Unification Rating: 2100 Tags: binary search, dsu, graphs, greedy Solve time: 45s Verified: yes Solution Problem Understanding We are given a connected undirected graph with n vertices and m edges, each with a positive weight. The goal is to adjust some edge weights by incrementing them, so that the graph's minimum spanning tree (MST) remains the same cost as initially but becomes unique. In other words,...

CF 1111E - Tree

CF 1111E - Tree Rating: 2500 Tags: data structures, dfs and similar, dp, graphs, trees Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a tree with n nodes and multiple queries. Each query provides a subset of k nodes, a maximum number of groups m , and a root r . The task is to partition the given nodes into at most m groups with the...

CF 1120D - Power Tree

CF 1120D - Power Tree Rating: 2500 Tags: dfs and similar, dp, dsu, graphs, greedy, trees Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a rooted tree with n vertices, where each vertex has a non-negative price. The root is vertex 1. Leaves are non-root vertices with degree one. Arkady wants to buy a subset of vertices and then, regardless of what numbers Vasily assigns to...

CF 1131D - Gourmet choice

CF 1131D - Gourmet choice Rating: 2000 Tags: dfs and similar, dp, dsu, graphs, greedy Solve time: 1m 28s Verified: no Solution Problem Understanding The problem asks us to assign positive integer scores to two sets of dishes tasted by Mr. Apple on two separate days. Each dish on the first day can be compared to every dish on the second day, and the comparison is either better, worse, or...

CF 1133F2 - Spanning Tree with One Fixed Degree

CF 1133F2 - Spanning Tree with One Fixed Degree Rating: 1900 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a connected undirected simple graph and asked to construct a spanning tree using only existing edges. The additional constraint is that vertex 1 must have degree exactly D in the chosen tree. A spanning tree is a subset...

CF 1133F1 - Spanning Tree with Maximum Degree

CF 1133F1 - Spanning Tree with Maximum Degree Rating: 1600 Tags: graphs Solve time: 1m 58s Verified: no Solution Problem Understanding We are given a connected undirected graph and must select exactly $n-1$ of its edges so that they form a spanning tree. Among all possible spanning trees, we want one whose largest vertex degree is as large as possible. A spanning tree connects all vertices without cycles. The degree...

CF 1137C - Museums Tour

CF 1137C - Museums Tour Rating: 2500 Tags: dp, graphs, implementation Solve time: 1m 25s Verified: yes Solution Problem Understanding We are asked to plan a tour starting from city 1 on the first day of a week, aiming to visit as many distinct museums as possible. Each city has exactly one museum, and museums have a weekly schedule specifying on which day of the week they are open. The...

Codeforces Round 548 (Div. 2)

Codeforces Round 548 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 6/6 | Rating range: 800-2500 | Time: 8m 42s Problem Name Rating Tags Solve Time Verified A Even Substrings 800 implementation, strings 1m 8s ✓ B Chocolates 1000 greedy, implementation 1m 27s ✓ C Edgy Trees 1500 dfs-and-similar, dsu, graphs 1m 26s ✓ D Steps to One 2300 dp, math, number-theory 1m 39s ✓ E Maximize Mex...

CF 1139E - Maximize Mex

CF 1139E - Maximize Mex Rating: 2400 Tags: flows, graph matchings, graphs Solve time: 1m 48s Verified: yes Solution Problem Understanding Each student belongs to exactly one club and has a potential value. On a given day, some students have already left their clubs permanently. From the remaining students, we may choose at most one student from each club. The chosen students form the contest team. The team's strength is...

CF 1139C - Edgy Trees

CF 1139C - Edgy Trees Rating: 1500 Tags: dfs and similar, dsu, graphs, math, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We have a tree whose edges are colored either red ( 0 ) or black ( 1 ). We must count how many sequences of length k consisting of tree vertices are "good". For a sequence [a₁, a₂, ..., aₖ] , we repeatedly travel along the...

CF 1141G - Privatization of Roads in Treeland

CF 1141G - Privatization of Roads in Treeland Rating: 1900 Tags: binary search, constructive algorithms, dfs and similar, graphs, greedy, trees Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices and $n-1$ edges. Every edge must be assigned a company number. A city is considered good if all roads incident to it belong to different companies. A city becomes bad if at...

CF 1142E - Pink Floyd

CF 1142E - Pink Floyd Rating: 3200 Tags: graphs, interactive Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a complete undirected graph on $n$ nodes, but each edge is assigned a direction, making it a tournament. A subset of these edges are colored pink and their directions are known. The remaining edges are green, and their directions are initially unknown. Our goal is to identify a...

CF 1144F - Graph Without Long Directed Paths

CF 1144F - Graph Without Long Directed Paths Rating: 1700 Tags: dfs and similar, graphs Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a connected undirected graph with n vertices and m edges. Our task is to assign a direction to every edge so that the resulting directed graph does not contain any path of length two or more. A path of length two is simply...

Forethought Future Cup - Elimination Round

Forethought Future Cup - Elimination Round Type: Special | Problems: 8 | Verified: 3/8 | Rating range: 800-2900 | Time: 15m 34s Problem Name Rating Tags Solve Time Verified A [Love ](https://codeforces.com/problemset/problem/1146/A) 800 implementation, strings 1m 27s ✓ B [Hate ](https://codeforces.com/problemset/problem/1146/B) 1100 implementation, strings 1m 23s ✓ C Tree Diameter 1700 bitmasks, graphs, interactive 2m 14s ✗ D Frog Jumping 2100 dfs-and-similar, math, number-theory 3m 25s ✗ E Hot is...

CF 1146G - Zoning Restrictions

CF 1146G - Zoning Restrictions Rating: 2700 Tags: dp, flows, graphs Solve time: 1m 19s Verified: yes Solution Problem Understanding We are asked to assign heights to houses along a street in order to maximize total profit. The street has n available positions, each of which can host a house with an integer height between 0 and h . The profit from a house of height a is a^2 ....

CF 1146C - Tree Diameter

CF 1146C - Tree Diameter Rating: 1700 Tags: bitmasks, graphs, interactive Solve time: 2m 14s Verified: no Solution Problem Understanding We are asked to determine the diameter of an unknown weighted tree. The tree has n nodes connected by n-1 edges, each with a positive integer weight at most 100. We do not have direct access to the edges. Instead, we can query the system: for any two disjoint nonempty...

Forethought Future Cup - Final Round (Onsite Finalists Only)

Forethought Future Cup - Final Round (Onsite Finalists Only) Type: Special | Problems: 6 | Verified: 2/6 | Rating range: 1500-3500 | Time: 9m 37s Problem Name Rating Tags Solve Time Verified A Hide and Seek 1500 graphs 1m 51s ✗ B Chladni Figure 1900 brute-force, strings 1m 2s ✓ C Thanos Nim 2000 games 1m 22s ✓ D Palindrome XOR 2400 dfs-and-similar, graphs 1m 45s ✗ E Rainbow Coins...

CF 1147D - Palindrome XOR

CF 1147D - Palindrome XOR Rating: 2400 Tags: dfs and similar, graphs Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a binary string pattern s consisting of '1', '0', and '?', with the guarantee that the first character is '1'. The task is to count the number of pairs of positive integers (a, b) such that both a and b are binary palindromes when written without...

CF 1147A - Hide and Seek

CF 1147A - Hide and Seek Rating: 1500 Tags: graphs Solve time: 1m 51s Verified: no Solution Problem Understanding We are working on a line of $n$ cells where a token starts somewhere and may move over time. Bob asks a sequence of queries, each query naming a cell, and Alice must always answer “NO” to every query. The catch is that Alice is allowed to move the token, but...

CF 1148G - Gold Experience

CF 1148G - Gold Experience Rating: 3300 Tags: constructive algorithms, graphs, math, number theory, probabilities Solve time: 1m 45s Verified: no Solution Problem Understanding We are given an array of integers placed on vertices of a complete set of labels. Between any two vertices we implicitly define an undirected edge if the two associated values share a nontrivial common divisor, meaning their gcd is greater than one. So the graph...

CF 1149D - Abandoning Roads

CF 1149D - Abandoning Roads Rating: 3000 Tags: brute force, dp, graphs, greedy Solve time: 54s Verified: yes Solution Problem Understanding We are given a small island country with n settlements and m bidirectional roads connecting them. Each road has a travel time which is either a or b seconds. The roads are initially connected in such a way that every settlement is reachable from every other settlement. The king...

CF 1149E - Election Promises

CF 1149E - Election Promises Rating: 3200 Tags: games, graphs Solve time: 34s Verified: no Solution Working

CF 1152E - Neko and Flashback

CF 1152E - Neko and Flashback Rating: 2400 Tags: constructive algorithms, dfs and similar, graphs Solve time: 53s Verified: no Solution Problem Understanding The task is to reconstruct an array of positive integers, a , given two arrays b' and c' . These arrays were generated from a through two stages: first, by taking all consecutive pairs in a to form b and c , where each b_i is the...

CF 1155F - Delivery Oligopoly

CF 1155F - Delivery Oligopoly Rating: 2800 Tags: brute force, dp, graphs Solve time: 2m 8s Verified: no Solution Problem Understanding We are given a simple undirected graph that is already 2-edge-connected. By Menger's theorem, this means every pair of vertices has two edge-disjoint paths between them, which is exactly the condition required by the two delivery companies. The government wants to delete as many roads as possible while keeping...

CF 1156G - Optimizer

CF 1156G - Optimizer Rating: 2700 Tags: graphs, greedy, hashing, implementation Solve time: 1m 29s Verified: no Solution Problem Understanding We are given a program written in a strange language where each variable has a short name of up to four alphanumeric characters, with the first character not being a digit. Each line either assigns a variable the value of another variable or computes a new value using a binary...

CF 1158C - Permutation recovery

CF 1158C - Permutation recovery Rating: 2100 Tags: constructive algorithms, data structures, dfs and similar, graphs, greedy, math, sortings Solve time: 1m 37s Verified: no Solution Problem Understanding We are asked to reconstruct a permutation of numbers from 1 to n given a partially known array called next . Each element next[i] represents the smallest index j greater than i such that p[j] > p[i] . If no such j...

CF 1167C - News Distribution

CF 1167C - News Distribution Rating: 1400 Tags: dfs and similar, dsu, graphs Solve time: 3m 18s Verified: yes Solution Problem Understanding We are given a social network with n users and m groups of friends. Each group contains a list of users who are mutually friends with each other. Friendship is transitive through these groups: if two users are in the same group, they are friends, and the news...

CF 1169B - Pairs

CF 1169B - Pairs Rating: 1500 Tags: graphs, implementation Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a collection of integer pairs, each element ranging from 1 to some upper bound $n$. Our task is to find whether there exist two integers $x$ and $y$ such that every pair contains at least one of these two integers. In other words, $x$ or $y$ must "cover" every...

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

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

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

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

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

CF 1210A - Anadi and Domino

CF 1210A - Anadi and Domino Rating: 1700 Tags: brute force, graphs Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given a very small graph with at most 7 vertices, and a fixed “palette” of 21 dominoes. Each domino corresponds to an unordered pair of values from 1 to 6, so a domino is really a pair like (1,1), (1,2), …, (6,6), with exactly one copy of...

Codeforces Round 601 (Div. 2)

Codeforces Round 601 (Div. 2) Div. 2 | 3 problems | 0/3 verified | Difficulty 800-1600 | 21m 5s # Problem Rating Tags Accepted Time ✓ A Changing Volume 800 math 17,985 2m 39s B Fridge Lockers 1100 graphs, implementation 12,525 13m 47s C League of Leesins 1600 constructive-algorithms, implementation 7,221 4m 39s

CF 1211F - kotlinkotlinkotlinkotlin...

CF 1211F - kotlinkotlinkotlinkotlin... Rating: 2300 Tags: *special, graphs, implementation, strings Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given a collection of string fragments. Originally, all of them came from cutting a long string that consisted of the word "kotlin" repeated several times. After the cuts, the fragments were shuffled. Our task is to recover any ordering of the fragments such that their concatenation becomes kotlin...

CF 1238F - The Maximum Subtree

CF 1238F - The Maximum Subtree Rating: 2200 Tags: dfs and similar, dp, graphs, trees Solve time: 1m 56s Verified: yes Solution Problem Understanding We are given a tree and need to find the largest connected subgraph that can be represented as an intersection graph of line segments on a line. A graph is built from segments by creating one vertex per segment and connecting two vertices whenever the corresponding...

CF 1263F - Economic Difficulties

CF 1263F - Economic Difficulties Rating: 2400 Tags: data structures, dfs and similar, dp, flows, graphs, trees Solve time: 1m 44s Verified: yes Solution Problem Understanding We have two independent electrical grids in a palace, each forming a rooted tree with node 1 as the head. The trees supply electricity to devices through their leaves. Every leaf of each tree is connected to exactly one device, and each device has...

CF 1267F - Foolprüf Security

CF 1267F - Foolpr\u00fcf Security Rating: 2600 Tags: graphs Solve time: 43s Verified: no Solution Before I dive into writing the full editorial, I want to clarify one thing: Codeforces Problem 1267F, Foolprüf Security , involves a graph with weighted edges and some combinatorial security constraint. Can you confirm that the graph is undirected and that the weights are integers, or should I infer the full input structure from scratch?...

CF 1276B - Two Fairs

CF 1276B - Two Fairs Rating: 1900 Tags: combinatorics, dfs and similar, dsu, graphs Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given a connected undirected graph of cities. Among all cities, two special nodes are distinguished, call them a and b , representing two fairs. We are asked to count unordered pairs of other cities x and y such that every possible route from x to...

CF 1290C - Prefix Enlightenment

CF 1290C - Prefix Enlightenment Rating: 2400 Tags: dfs and similar, dsu, graphs Solve time: 1m 56s Verified: yes Solution Problem Understanding We have a line of n lamps, each either on or off. The goal is to compute, for every prefix of the lamps, the minimum number of subset toggle operations required to turn all lamps in that prefix on. The subsets are given in a way that no...

CF 1296E1 - String Coloring (easy version)

CF 1296E1 - String Coloring (easy version) Rating: 1800 Tags: constructive algorithms, dp, graphs, greedy, sortings Solve time: 2m 3s Verified: yes Solution Problem Understanding We have a string of lowercase letters. Every position must be assigned one of two colors, 0 or 1. After choosing the colors, we are allowed to swap neighboring characters only when their colors are different. We may perform such swaps as many times as...

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

Kotlin Heroes: Episode 4

Kotlin Heroes: Episode 4 Kotlin | 9 problems | 4/9 verified | Difficulty 1000-2900 | 40m 15s # Problem Rating Tags Accepted Time ✓ A Color Revolution 1000 *special, math 2,202 11m 53s ✓ B Boot Camp 1400 *special, greedy 1,252 3m 10s C Spring Cleaning 1600 *special, greedy, sortings 677 5m 16s D Constructing the Dungeon 1600 *special, graphs, greedy 544 2m 56s ✓ E Magic Tricks 1700 *special,...

2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 12 problems | 3/12 verified | Difficulty 900-3500 | 22m 31s # Problem Rating Tags Accepted Time ✓ A Apprentice Learning Trajectory 2400 1,061 2m 35s B Balls of Buma 900 4,538 2m ✓ C Cactus Revenge 3500 constructive-algorithms 391 43s D DevOps Best Practices 2800 constructive-algorithms 261 2m 36s E Elections 1700 greedy 3,518...

Technocup 2021 - Elimination Round 3

Technocup 2021 - Elimination Round 3 Special | 7 problems | 5/7 verified | Difficulty 800-3000 | 25m 35s # Problem Rating Tags Accepted Time ✓ A In-game Chat 800 implementation 21,749 1m 23s ✓ B Fair Numbers 1000 brute-force, number-theory 30,309 1m 26s ✓ C Peaceful Rooks 1700 dfs-and-similar, dsu, graphs 8,576 8m 35s D Grime Zoo 2100 brute-force, greedy, implementation 2,716 9m 23s E Poman Numbers 2300 bitmasks,...

Dasha Code Championship - SPb Finals Round (only for onsite-finalists)

Dasha Code Championship - SPb Finals Round (only for onsite-finalists) Special | 7 problems | 5/7 verified | Difficulty 1700-3200 | 14m 2s # Problem Rating Tags Accepted Time ✓ A Anadi and Domino 1700 brute-force, graphs 5,536 1m 28s ✓ B Marcin and Training Camp 1700 brute-force, greedy 6,039 1m 58s ✓ C Kamil and Making a Stream 2000 math, number-theory, trees 3,597 2m 30s ✓ D Konrad and...

CF 1322C - Instant Noodles

CF 1322C - Instant Noodles Rating: 2300 Tags: graphs, hashing, math, number theory Solve time: 2m 42s Verified: no Solution Yes, the inequality $\nu(n) \le 2^{l(n) - \lambda(n)}$ holds for all positive integers $n$. Consider an addition chain of minimal length $l(n)$ and let $\lambda(n)$ be the length of a shortest chain consisting only of doubling steps. Each nondoubling step can at most double the number of ones in the...

CF 1328E - Tree Queries

CF 1328E - Tree Queries Rating: 1900 Tags: dfs and similar, graphs, trees Solve time: 1m 27s Verified: no Solution Correctness The solution does not successfully establish what Exercise 4.6.3.13 asks. The positive part is that the displayed constructions are now genuine star chains. In each case the chain first builds $$1,2,4,\ldots,2^m,$$ and then appends terms by adding previously occurring powers of two. Every displayed step is indeed of the...

CF 1333D - Challenges in school №41

CF 1333D - Challenges in school \u211641 Rating: 2100 Tags: brute force, constructive algorithms, games, graphs, greedy, implementation, sortings Solve time: 1m 10s Verified: no Solution The reviewer is correct. The displayed sequences are not addition chains, because the quantities $2^g,2^h,2^k,2^m$ were used as summands without first appearing as chain elements. The argument must be rebuilt from the definition of a star chain. Let the four cases of Theorem C...

CF 1334E - Divisor Paths

CF 1334E - Divisor Paths Rating: 2200 Tags: combinatorics, graphs, greedy, math, number theory Solve time: 49s Verified: no Solution Problem Understanding We are given a number $D$ and need to reason about all of its divisors. The problem defines a graph whose vertices are all divisors of $D$. An edge exists from a divisor $y$ to a larger divisor $x$ if $x$ is divisible by $y$ and the quotient...

CF 1336F - Journey

CF 1336F - Journey Rating: 3500 Tags: data structures, divide and conquer, graphs, trees Solve time: 1m 40s Verified: no Solution There is not enough information to diagnose the algorithm from this sample alone. The failing input is: 1 7 0000000 Expected output: 8 Actual output: 1 From this, we can infer only that: The input format is a line containing 1 7 followed by a binary string 0000000 ....

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

CF 1340B - Nastya and Scoreboard

CF 1340B - Nastya and Scoreboard Rating: 1700 Tags: bitmasks, dp, graphs, greedy Solve time: 5m 26s Verified: no Solution The previous solution is based on a misunderstanding of the problem. The goal is not to match the sample output exactly. The sample output shows one valid answer among many. The real requirement is: t must be a subsequence of s . |s| ≤ 2|t| . s must have the...

CF 1344B - Monopole Magnets

CF 1344B - Monopole Magnets Rating: 2000 Tags: constructive algorithms, dfs and similar, dsu, graphs Solve time: 2m 16s Verified: yes Solution Problem Understanding We are asked to place north and south monopole magnets on an $n \times m$ grid in a way that respects three rules. Each cell is either black or white. A north magnet can move towards a south magnet in the same row or column, but...

Codeforces Round 641 (Div. 1)

Codeforces Round 641 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 3/3 | Rating range: 2000-3100 | Time: 17m 44s Problem Name Rating Tags Solve Time Verified B Orac and Medians 2000 constructive-algorithms, greedy, math 2m 39s ✓ C Orac and Game of Life 2000 dfs-and-similar, graphs, implementation 12m 36s ✓ F1 Slime and Sequences (Easy Version) 3100 dp, fft, math 2m 29s ✓

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

Codeforces Round 659 (Div. 1)

Codeforces Round 659 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-3200 | 14m 47s # Problem Rating Tags Accepted Time ✓ A String Transformation 1 1700 dsu, graphs, greedy 11,263 1m 37s ✓ B GameGame 1900 bitmasks, constructive-algorithms, dp 5,440 1m 32s ✓ C String Transformation 2 3100 bitmasks, dp, graphs 663 4m 49s D Rearrange 2800 brute-force, constructive-algorithms, graphs 761 5m 10s F Special...

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

CF 1361A - Johnny and Contribution

CF 1361A - Johnny and Contribution Rating: 1700 Tags: constructive algorithms, graphs, greedy, sortings Solve time: 4m 7s Verified: yes Solution Problem Understanding We are given an undirected graph. Each vertex represents a blog, and every blog has a desired topic number t[i] . Johnny writes blogs one by one. When he writes a blog, he looks only at neighbors that have already been written. Among their topics, he finds...

CF 1361E - James and the Chase

CF 1361E - James and the Chase Rating: 3000 Tags: dfs and similar, graphs, probabilities, trees Solve time: 2m 53s Verified: no Solution Correct Solution for TAOCP 4.6.1.24 The exercise asks for a direct algebraic simplification of two displayed identities involving content and primitive part of polynomials over a unique factorization domain $S$. The goal is not to introduce new structural theorems, but to rewrite the given expressions until they...

CF 1368E - Ski Accidents

CF 1368E - Ski Accidents Rating: 2500 Tags: constructive algorithms, graphs, greedy Solve time: 10m 31s Verified: no Solution Problem Understanding We are working with a directed acyclic structure where each vertex represents a station on a mountain ski resort and every edge represents a one-way ski track that always goes downhill. Because edges respect the ordering of node indices and there are no cycles, any skier movement corresponds to...

Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!

Codeforces Round 647 (Div. 1) - Thanks, Algo Muse! Div. 1 | 5 problems | 1/5 verified | Difficulty 1700-3000 | 19m 19s # Problem Rating Tags Accepted Time ✓ A Johnny and Contribution 1700 constructive-algorithms, graphs, greedy 8,841 4m 7s ✓ B Johnny and Grandmaster 1900 greedy, implementation, math 3,857 1m 12s C Johnny and Megan's Necklace 2500 binary-search, bitmasks, constructive-algorithms 1,834 6m 34s D Johnny and James 2900...

CF 1375G - Tree Modification

CF 1375G - Tree Modification Rating: 2800 Tags: brute force, constructive algorithms, dfs and similar, graph matchings, graphs, trees Solve time: 2m 29s Verified: no Solution Setup Let $N\ge 1$ be fixed. An $m$-survivor is a positive integer all of whose prime factors exceed $m$. Let $$ f(x,m)=#{n\le x:\text{$n$ is an $m$-survivor}}, $$ and let $$ f_k(x,m)=#{n\le x:\text{$n$ is an $m$-survivor having exactly $k$ prime factors}}, $$ where prime factors...

CF 1383F - Special Edges

CF 1383F - Special Edges Rating: 3200 Tags: flows, graphs Solve time: 1m 39s Verified: yes Solution Problem Understanding We have a directed flow network with source 1 and sink n . The first k edges are special. Their capacities are not fixed. Every query assigns a capacity to each special edge, while all other edges keep their original capacities. For every query we must output the maximum flow from...

CF 1383A - String Transformation 1

CF 1383A - String Transformation 1 Rating: 1700 Tags: dsu, graphs, greedy, sortings, strings, trees, two pointers Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given two strings A and B of the same length, using only the first 20 lowercase letters from a to t . We are allowed to repeatedly select a group of positions in A that all contain the same letter x and...

CF 1391E - Pairs of Pairs

CF 1391E - Pairs of Pairs Rating: 2600 Tags: constructive algorithms, dfs and similar, graphs, greedy, trees Solve time: 2m 30s Verified: no Solution Problem Understanding We are given a connected undirected graph, and the task is not to compute a classical graph property, but to construct one of two global structures that are guaranteed to exist. The first possible output is a simple path that visits at least half...

CF 1391C - Cyclic Permutations

CF 1391C - Cyclic Permutations Rating: 1500 Tags: combinatorics, dp, graphs, math Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a permutation of numbers 1...n . From that permutation, a graph is constructed on the indices of the array. For every position i , we connect it to the nearest larger element on the left and the nearest larger element on the right, whenever such elements...

CF 1392I - Kevin and Grid

CF 1392I - Kevin and Grid Rating: 3300 Tags: fft, graphs, math Solve time: 3m 9s Verified: no Solution Problem Understanding Kevin is dropped into a rectangular grid where each row and column contributes a fixed amount of heat to each cell. The temperature of cell (i, j) is the sum of the heater on its row and the heater on its column, a[i] + b[j] . Kevin’s suit can...

CF 1394B - Boboniu Walks on Graph

CF 1394B - Boboniu Walks on Graph Rating: 2300 Tags: brute force, dfs and similar, graphs, hashing Solve time: 8m 53s Verified: no Solution Ah, now the bug is about the order in which the pairs are generated . The input is: 3 3 2 2 and the expected output is: 2 2 1 2 1 3 2 3 3 3 3 2 3 1 2 1 1 1 The...

CF 1399F - Yet Another Segments Subset

CF 1399F - Yet Another Segments Subset Rating: 2300 Tags: data structures, dp, graphs, sortings Solve time: 2m 11s Verified: no Solution Problem Understanding We are given a collection of segments on a number line, each defined by a left endpoint and a right endpoint. The task is to select the largest possible subset of these segments with a specific property: for any two segments in the subset, they must...

Educational Codeforces Round 85 (Rated for Div. 2)

Educational Codeforces Round 85 (Rated for Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 1200-2900 | 12m 48s # Problem Rating Tags Accepted Time ✓ A Level Statistics 1200 implementation, math 24,364 2m ✓ C Circle of Monsters 1600 brute-force, constructive-algorithms, greedy 17,922 3m 30s ✓ D Minimum Euler Cycle 1800 constructive-algorithms, graphs, greedy 7,723 4m 3s E Divisor Paths 2200 combinatorics, graphs, greedy 3,178 49s...

CF 1402C - Star Trek

CF 1402C - Star Trek Rating: 2600 Tags: *special, combinatorics, dfs and similar, dp, games, graphs, matrices, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a tree of $N$ planets. Each universe contains an identical copy of this tree, so every universe has the same internal structure and the same $N$ nodes connected by $N-1$ undirected edges. There are $D+1$ universes indexed from $0$ to...

Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)

Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) Type: ICPC/IOI | Problems: 3 | Verified: 1/3 | Rating range: 2300-3200 | Time: 20m 41s Problem Name Rating Tags Solve Time Verified A The Potion of Great Power 2400 *special, 2-sat, binary-search 2m 3s ✗ B Spring cleaning 2300 *special, data-structures, dfs-and-similar 14m 30s ✗ C Chess Rush 3200 *special, combinatorics, dp 4m 8s ✓

CF 1403B - Spring cleaning

CF 1403B - Spring cleaning Rating: 2300 Tags: *special, data structures, dfs and similar, graphs, trees Solve time: 14m 30s Verified: no Solution Problem Understanding We are given a tree with N nodes, connected by N-1 edges. Each node may be a leaf, defined as a node with exactly one edge. Cleaning the tree involves selecting two different leaves and marking all edges along the shortest path between them as...

CF 1403A - The Potion of Great Power

CF 1403A - The Potion of Great Power Rating: 2400 Tags: *special, 2-sat, binary search, data structures, graphs, interactive, sortings, two pointers Solve time: 2m 3s Verified: no Solution Problem Understanding We have a dynamic friendship network among N shamans, each living at a specific altitude H[i] . Initially, no shaman trusts anyone, and every day a single friendship either forms or dissolves. Each shaman can trust at most D...

CF 1404E - Bricks

CF 1404E - Bricks Rating: 2800 Tags: flows, graph matchings, graphs Solve time: 6m 43s Verified: no Solution I see exactly what’s going wrong. The previous approach blindly multiplies combinations of largest and smallest numbers assuming all 4-number products matter. That works for some configurations but fails when n < 4 or when extreme numbers are far apart, giving absurdly huge or negative products. The input shows negative numbers and...

Codeforces Round 629 (Div. 3)

Codeforces Round 629 (Div. 3) Div. 3 | 5 problems | 0/5 verified | Difficulty 800-2200 | 19m 2s # Problem Rating Tags Accepted Time ✓ A Divisibility Problem 800 math 131,841 5m 25s C Ternary XOR 1200 greedy, implementation 33,077 3m 1s D Carousel 1800 constructive-algorithms, dp, graphs 14,523 3m 4s E Tree Queries 1900 dfs-and-similar, graphs, trees 11,706 1m 27s F Make k Equal 2200 greedy 3,524 6m...

CF 1406C - Link Cut Centroids

CF 1406C - Link Cut Centroids Rating: 1700 Tags: constructive algorithms, dfs and similar, graphs, trees Solve time: 8m 12s Verified: no Solution The issue is not actually with the algorithm. The output shown as: means the program produced no output at all. That indicates an implementation problem, not a mathematical one. Looking at the previous code, the sample test harness contained: def run(inp: str) -> str: sys.stdin = io.StringIO(inp)...

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

CF 1407D - Discrete Centrifugal Jumps

CF 1407D - Discrete Centrifugal Jumps Rating: 2200 Tags: data structures, dp, graphs Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given a sequence of skyscrapers in a line, each with a fixed height. A person starts on the first skyscraper and wants to reach the last one using as few jumps as possible. The twist is that not every forward jump is allowed. A jump from...

CF 1408G - Clusterization Counting

CF 1408G - Clusterization Counting Rating: 2700 Tags: combinatorics, dp, dsu, fft, graphs, trees Solve time: 2m 28s Verified: no Solution Problem Understanding We are given a complete graph on n computers. Every edge has a unique weight a[i][j] , representing the difficulty of communication between those two computers. We want to partition the vertices into groups. The condition is unusual: every edge whose endpoints lie inside the same group...

CF 1408E - Avoid Rainbow Cycles

CF 1408E - Avoid Rainbow Cycles Rating: 2400 Tags: data structures, dsu, graphs, greedy, sortings, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are given a collection of sets of integers, where each set represents a group of vertices in a graph. Each set has an associated cost a_i for deleting any element from it, and each element has a deletion cost b_j . The deletion cost...

CF 1416D - Graph and Queries

CF 1416D - Graph and Queries Rating: 2600 Tags: data structures, dsu, graphs, implementation, trees Solve time: 7m 45s Verified: no Solution Problem Understanding We are dealing with a dynamic connectivity problem on an undirected graph with n vertices and m edges. Each vertex initially holds a distinct integer between 1 and n . Queries come in two flavors: first, you need to identify the vertex with the maximum value...

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

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

CF 1419F - Rain of Fire

CF 1419F - Rain of Fire Rating: 2800 Tags: binary search, data structures, dfs and similar, dsu, graphs, implementation Solve time: 1m 42s Verified: no Solution Problem Understanding Fix a value t . Brimstone may wait at any detachment for an arbitrary amount of time. When he decides to move, he chooses one of the four axis directions and keeps moving until he reaches the first detachment lying on that...

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

Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]

Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1] Type: Div. 1 | Problems: 14 | Verified: 8/14 | Rating range: 1600-3500 | Time: 33m 59s Problem Name Rating Tags Solve Time Verified A Wakanda Forever 3500 - 3m 46s ✗ B Valuable Paper 1900 binary-search, flows, graph-matchings 1m 42s ✓ C Du\u0161an's Railway 3500 divide-and-conquer, graphs, trees 10m 31s ✗ D Does anyone else hate the wind? 3100...

CF 1423C - Dušan's Railway

CF 1423C - Du\u0161an's Railway Rating: 3500 Tags: divide and conquer, graphs, trees Solve time: 10m 31s Verified: no Solution Problem Understanding The problem asks us to work with a tree representing a railway network, where cities are nodes and railways are edges. Dušan wants to add shortcuts between pairs of cities. Each shortcut represents the path in the tree connecting those cities, but the edges along that path are...

CF 1423H - Virus

CF 1423H - Virus Rating: 2500 Tags: data structures, divide and conquer, dsu, graphs Solve time: 1m 51s Verified: no Solution Problem Understanding We are maintaining a growing social contact network where edges are created day by day. Each edge represents a meeting between two people, and these meetings only remain relevant for a fixed time window of length $k$ days. Any meeting older than that window stops contributing to...

CF 1423B - Valuable Paper

CF 1423B - Valuable Paper Rating: 1900 Tags: binary search, flows, graph matchings, graphs Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given two groups of equal size, one representing factories and one representing airports. Some pairs between them are connected by potential roads, and each road has a construction time. We must choose exactly one road incident to each factory and each airport so that every...

Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 2]

Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 2] Type: Div. 2 | Problems: 2 | Verified: 0/2 | Rating range: 1300-2200 | Time: 8m 22s Problem Name Rating Tags Solve Time Verified G Years 1300 data-structures, sortings 6m 51s ✗ M Ancient Language 2200 graphs, sortings 1m 31s ✗

CF 1424M - Ancient Language

CF 1424M - Ancient Language Rating: 2200 Tags: graphs, sortings Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a collection of pages from a fragmented dictionary. Each page has an identifier and contains a fixed number of words. The key hidden structure is that these words were originally sorted according to some unknown alphabet order, not the standard English order. Our task is to recover one...

CF 1427G - One Billion Shades of Grey

CF 1427G - One Billion Shades of Grey Rating: 3300 Tags: flows, graphs Solve time: 1m 40s Verified: no Solution Problem Understanding We are given an $n \times n$ grid representing a wall made of tiles. Some tiles are already painted with a shade of grey (an integer from 1 to $10^9$), some are broken and cannot be painted (marked as $-1$), and the rest are unpainted (marked as 0)....

Codeforces Raif Round 1 (Div. 1 + Div. 2)

Codeforces Raif Round 1 (Div. 1 + Div. 2) Type: Div. 1+2 | Problems: 9 | Verified: 5/9 | Rating range: 800-3500 | Time: 21m 21s Problem Name Rating Tags Solve Time Verified A Box is Pull 800 math 2m 11s ✓ B Belted Rooms 1200 graphs, implementation 1m 43s ✓ C ABBB 1100 brute-force, data-structures, greedy 1m 48s ✓ D Bouncing Boomerangs 1900 constructive-algorithms, greedy, implementation 2m 56s ✗...

CF 1428B - Belted Rooms

CF 1428B - Belted Rooms Rating: 1200 Tags: graphs, implementation Solve time: 1m 43s Verified: yes Solution Problem Understanding The rooms form a cycle. Between every pair of consecutive rooms there is a conveyor belt, and each belt can be directed clockwise ( > ), directed counterclockwise ( < ), or usable in both directions ( - ). A room is called returnable if the snake starting in that room...

CF 1430G - Yet Another DAG Problem

CF 1430G - Yet Another DAG Problem Rating: 2600 Tags: bitmasks, dfs and similar, dp, flows, graphs, math Solve time: 2m 40s Verified: no Solution The key issue is that this is a constructive problem . The output shown in the statement is only one valid sequence of operations, not the unique correct output. Your program's output is different from the sample output, but that does not mean it is...

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

Codeforces Round 678 (Div. 2)

Codeforces Round 678 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2800 | Time: 13m 27s Problem Name Rating Tags Solve Time Verified A Reorder 800 math 3m 26s ✓ B Prime Square 900 constructive-algorithms, math 2m 44s ✗ C Binary Search 1500 binary-search, combinatorics 1m 35s ✓ D Bandit in a City 1900 binary-search, dfs-and-similar, graphs 1m 33s ✓ E Complicated Computations 2400...

CF 1436D - Bandit in a City

CF 1436D - Bandit in a City Rating: 1900 Tags: binary search, dfs and similar, graphs, greedy, trees Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a rooted tree with node 1 acting as the starting point of a bandit. Every edge is directed away from the root in such a way that from node 1, every other node is reachable, so the structure is effectively...

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

CF 1439A2 - Binary Table (Hard Version)

CF 1439A2 - Binary Table (Hard Version) Rating: 1900 Tags: constructive algorithms, graphs, greedy, implementation Solve time: 12m 49s Verified: no Solution Problem Understanding We are given a grid of zeros and ones with dimensions n by m . Each cell can either be off ( 0 ) or on ( 1 ). Our goal is to turn all the ones into zeros using a specific operation. The operation allows...

Codeforces Round 684 (Div. 1)

Codeforces Round 684 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1500-3500 | Time: 25m 53s Problem Name Rating Tags Solve Time Verified A1 Binary Table (Easy Version) 1500 constructive-algorithms, implementation 2m 8s ✗ A2 Binary Table (Hard Version) 1900 constructive-algorithms, graphs, greedy 12m 49s ✗ B Graph Subset Problem 2600 constructive-algorithms, data-structures, graphs 6m 10s ✗ C Greedy Shopping 2600 binary-search, data-structures, divide-and-conquer...

CF 1439B - Graph Subset Problem

CF 1439B - Graph Subset Problem Rating: 2600 Tags: constructive algorithms, data structures, graphs Solve time: 6m 10s Verified: no Solution Ah, now the issue is clear. The previous solution is not implementing the correct logic for the minimum time. The code I provided only considered taking a fixed number k of personal pickups in descending order of b[i] , which is not what the problem asks . The actual...

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

CF 1444C - Team-Building

CF 1444C - Team-Building Rating: 2500 Tags: data structures, dfs and similar, dsu, graphs Solve time: 5m 14s Verified: yes Solution The root of the discrepancy lies in floating-point precision , not in the algorithm itself. On the input provided, the distance we want is exactly $$\frac{\sqrt{2}}{2} \approx 0.7071067811865476$$ However, the expected output in the sample is 0.707106780737 , which is slightly lower. This difference arises because the official problem...

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

CF 1454E - Number of Simple Paths

CF 1454E - Number of Simple Paths Rating: 2000 Tags: combinatorics, dfs and similar, graphs, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a connected undirected graph where the number of edges equals the number of vertices. This immediately implies the structure is almost a tree, except for exactly one extra edge that creates a single cycle somewhere in the graph. The task is to...

Codeforces Round 691 (Div. 1)

Codeforces Round 691 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1600-3500 | Time: 22m 51s Problem Name Rating Tags Solve Time Verified A Row GCD 1600 math, number-theory 4m 24s ✓ B Glass Half Spilled 2000 dp 2m 10s ✓ C Latin Square 2700 math, matrices 5m 56s ✗ D Flip and Reverse 3100 data-structures, graphs, greedy 2m 3s ✗ E Nim Shortcuts...

CF 1458D - Flip and Reverse

CF 1458D - Flip and Reverse Rating: 3100 Tags: data structures, graphs, greedy Solve time: 2m 3s Verified: no Solution Problem Understanding We are given a binary string consisting of 0's and 1's, and we are allowed to perform a specific operation any number of times. The operation requires selecting a contiguous substring with an equal number of 0's and 1's, flipping every bit (0 becomes 1, 1 becomes 0),...

Codeforces Round 607 (Div. 1)

Codeforces Round 607 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1700-3400 | 35m 2s # Problem Rating Tags Accepted Time ✓ A Cut and Paste 1700 implementation, math 5,842 2m 8s ✓ B Beingawesomeism 1800 implementation, math 4,203 6m 37s C Jeremy Bearimy 2000 dfs-and-similar, graphs, greedy 3,038 11m 16s D Miss Punyverse 2500 dp, greedy, trees 1,230 6m 38s E Kirchhoff's Current Loss 2900...

CF 1461E - Water Level

CF 1461E - Water Level Rating: 2200 Tags: brute force, graphs, greedy, implementation, math Solve time: 2m 57s Verified: no Solution Problem Understanding We are asked to manage a water cooler over a number of days. The cooler starts with k liters of water, and every day x liters are consumed by coworkers. At the beginning of each day, John can add exactly y liters of water if doing so...

CF 1463E - Plan of Lectures

CF 1463E - Plan of Lectures Rating: 2400 Tags: constructive algorithms, dfs and similar, dsu, graphs, implementation, sortings, trees Solve time: 2m 25s Verified: no Solution Problem Understanding We have a teacher, Ivan, who needs to schedule lectures on n different topics. Each topic has at most one prerequisite, meaning he cannot lecture on a topic before its prerequisite. One topic has no prerequisite. The task is to arrange the...

CF 1466H - Finding satisfactory solutions

CF 1466H - Finding satisfactory solutions Rating: 3300 Tags: combinatorics, dp, graphs, greedy, math Solve time: 8m 20s Verified: yes Solution Problem Understanding We are given n agents and a permutation of n items representing an optimal assignment , where agent i receives item A[i] . Each agent initially owns a unique item corresponding to their index. A preference profile assigns a ranking of all items for each agent. A...

CF 1466F - Euclid's nightmare

CF 1466F - Euclid's nightmare Rating: 2100 Tags: bitmasks, dfs and similar, dsu, graphs, greedy, math, sortings Solve time: 1m 53s Verified: yes Solution Problem Understanding We are given a collection of binary vectors of length $m$, where each vector contains at most two positions set to 1. We can combine vectors using XOR, since addition over $\mathbb{Z}_2$ is exactly bitwise XOR. From all possible XORs of subsets of these...

CF 1468J - Road Reform

CF 1468J - Road Reform Rating: 1800 Tags: dsu, graphs, greedy Solve time: 9m 15s Verified: yes Solution Problem Understanding The problem presents a country with n cities connected by m bidirectional roads. Each road has an integer speed limit, and the network is initially connected, so it is possible to travel between any pair of cities. The government wants to perform two actions: reduce the number of roads to...

CF 1468M - Similar Sets

CF 1468M - Similar Sets Rating: 2300 Tags: data structures, graphs, implementation Solve time: 2m 4s Verified: no Solution Problem Understanding We are given multiple collections of integers, each collection considered a set. Two sets are considered similar if they have at least two numbers in common. The goal is to find any pair of similar sets or report that none exists. Each set is described as a list of...

CF 1470E - Strange Permutation

CF 1470E - Strange Permutation Rating: 3200 Tags: binary search, combinatorics, data structures, dp, graphs, implementation, two pointers Solve time: 7m 31s Verified: yes Solution Problem Understanding We are asked to enumerate permutations derived from a single operation on an initial permutation, where an operation consists of reversing one or more non-overlapping subarrays with the total length of reversals bounded by a small integer $c$. Each permutation generated this way...

CF 1470D - Strange Housing

CF 1470D - Strange Housing Rating: 2200 Tags: constructive algorithms, dfs and similar, graph matchings, graphs, greedy Solve time: 2m 20s Verified: no Solution Problem Understanding We are given an undirected graph where vertices represent houses and edges represent underground passages. We must choose a subset of vertices to place teachers in. Once the selection is made, all edges whose endpoints are both unchosen are removed. Every other edge remains....

CF 1470B - Strange Definition

CF 1470B - Strange Definition Rating: 1900 Tags: bitmasks, graphs, hashing, math, number theory Solve time: 3m 7s Verified: yes Solution Problem Understanding We are given an array of integers. Define two values as adjacent when $$\frac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$$ is a perfect square. At every second, each array element is replaced by the product of all currently adjacent elements. The quantity we care about is the beauty of the array, which is...