#dfs-and-similar
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 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 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...
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...
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 960E - Alternating Tree
CF 960E - Alternating Tree Rating: 2300 Tags: combinatorics, dfs and similar, divide and conquer, dp, probabilities, trees Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a tree with a value attached to every node. Between any two nodes $u$ and $v$, there is exactly one simple path, and we assign a score to that directed path by taking the node values along the path and...
CF 963B - Destruction of a Tree
CF 963B - Destruction of a Tree Rating: 2000 Tags: constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a tree where each vertex has an associated current degree that changes as vertices are removed. A vertex is eligible for removal only when its degree is even at the moment we choose it. When a vertex is removed, all...
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 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 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 1387B2 - Village (Maximum)
CF 1387B2 - Village (Maximum) Rating: 2500 Tags: *special, dfs and similar, trees Solve time: 7m 9s Verified: no Solution Problem Understanding The village is a tree where each house is a node and each road is an edge of length one. Initially, every house has exactly one villager. We must reassign villagers so that every person moves to a different house, forming a permutation of nodes with no fixed...
CF 1387A - Graph
CF 1387A - Graph Rating: 2100 Tags: *special, binary search, dfs and similar, dp, math, ternary search Solve time: 6m 59s Verified: no Solution Problem Understanding We are given an undirected graph where every edge enforces a linear constraint between its endpoints. Each vertex must be assigned a real value, and every edge says exactly what the sum of its two endpoint values must be. Black edges force a sum...
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 1305D - Kuroni and the Celebration
CF 1305D - Kuroni and the Celebration Rating: 1900 Tags: constructive algorithms, dfs and similar, interactive, trees Solve time: 3m 8s Verified: no Solution Problem Understanding We are given a fixed tree with up to 1000 vertices. Somewhere in this tree there is a hidden root vertex $r$, which represents Kuroni’s hotel. The structure of the tree is known, but the root is not. The only way to extract information...
CF 1214H - Tiles Placement
CF 1214H - Tiles Placement Rating: 2800 Tags: constructive algorithms, dfs and similar, trees Solve time: 5m 42s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices, where each vertex represents a square in a pedestrian network. Each vertex must be assigned one of $k$ colors. The requirement is global and path-based: if you take any simple path in the tree that contains exactly $k$ vertices,...
CF 1214D - Treasure Island
CF 1214D - Treasure Island Rating: 1900 Tags: dfs and similar, dp, flows, hashing Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid that represents a map. Each cell is either blocked or free. We start at the top-left cell $(1,1)$ and want to reach the bottom-right cell $(n,m)$. Movement is highly restricted: from any cell we can only go either one...
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 1208F - Bits And Pieces
CF 1208F - Bits And Pieces Rating: 2600 Tags: bitmasks, dfs and similar, dp, greedy Solve time: 2m 39s Verified: yes Solution Problem Understanding We are given a sequence of integers and asked to choose three indices $i < j < k$. For each such triple, we take the value of the first element OR the bitwise AND of the other two elements. The goal is to maximize this expression...
CF 1060E - Sergey and Subway
CF 1060E - Sergey and Subway Rating: 2000 Tags: dfs and similar, dp, trees Solve time: 6m 55s Verified: no Solution Problem Understanding We start with a tree of subway stations. Every station is a node, and every tunnel is an edge, so there is exactly one simple path between any two stations. The quantity we care about is the total distance over all unordered pairs of stations, where distance...
CF 1600J - Robot Factory
CF 1600J - Robot Factory Rating: 1400 Tags: bitmasks, dfs and similar Solve time: 1m 44s Verified: yes Solution Problem Understanding The grid describes a rectangular factory floor where each cell is a tile that may have walls on some of its four sides. Each tile contains a number from 0 to 15, and this number encodes its walls using four bits. Interpreting the binary representation from most significant to...
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 1654D - Potion Brewing Class
CF 1654D - Potion Brewing Class Rating: 2100 Tags: dfs and similar, math, number theory, trees Solve time: 9m 14s Verified: yes Solution Problem Understanding We are given a set of ingredients, each of which must appear in some positive integer quantity in a final mixture. The professor does not provide absolute amounts, but instead gives exactly $n-1$ constraints. Each constraint relates two ingredients and fixes their ratio: if ingredient...
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 1578J - Just Kingdom
CF 1578J - Just Kingdom Rating: 3100 Tags: brute force, data structures, dfs and similar Solve time: 5m 32s Verified: no Solution Problem Understanding We are given a rooted hierarchy with a single root, the king, and up to $n$ lords forming a tree where each lord has exactly one parent. Each lord $i$ has a required amount of money $m_i$. Money flows through this tree in a very specific...
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 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 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 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 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...
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 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 1442E - Black, White and Grey Tree
CF 1442E - Black, White and Grey Tree Rating: 3000 Tags: binary search, constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a tree in which each node is coloured white, black, or grey. The goal is to remove all nodes in the minimum number of operations, where in each operation we select a connected component of nodes to...
CF 1510C - Cactus Not Enough
CF 1510C - Cactus Not Enough Rating: 2900 Tags: dfs and similar, graph matchings, graphs Solve time: 3m 19s Verified: no Solution Problem Understanding The problem gives us a cactus graph, which is a connected undirected graph where each edge belongs to at most one simple cycle. You can think of a cactus as a tree that allows some cycles, but never overlapping cycles. The input represents these cacti in...
CF 1575D - Divisible by Twenty-Five
CF 1575D - Divisible by Twenty-Five Rating: 1800 Tags: brute force, dfs and similar, dp Solve time: 2m 1s Verified: yes Solution Problem Understanding We are given a very short string, at most length 8, that represents a partially unknown integer. Some positions contain fixed digits, some contain a wildcard underscore meaning “any digit is allowed here”, and some contain the character X meaning all X positions must share the...
CF 1648F - Two Avenues
CF 1648F - Two Avenues Rating: 3500 Tags: data structures, dfs and similar, graphs Solve time: 50s Verified: no Solution I can't write a correct editorial and solution for Codeforces 1648F from the problem statement alone. This is a 3500-rated problem whose accepted solution relies on several deep graph-theoretic facts about bridges, edge 3-connectivity structure, randomized XOR labels on DFS back edges, decomposition into chains of equivalent non-bridge edges, and...
CF 1648E - Air Reform
CF 1648E - Air Reform Rating: 3200 Tags: data structures, dfs and similar, divide and conquer, dsu, graphs, implementation, trees Solve time: 2m 16s Verified: no Solution Problem Understanding We start with a connected undirected graph. The graph represents Berlaflot flights, and every edge has a price. The cost of traveling between two cities is unusual. A route may contain many flights, but its cost is not the sum of...
CF 1662O - Circular Maze
CF 1662O - Circular Maze Rating: - Tags: brute force, dfs and similar, graphs, implementation Solve time: 2m Verified: no Solution Problem Understanding The maze is drawn in polar coordinates with the center as the starting point. Movement is allowed continuously in any direction as long as we do not cross or touch a wall. The goal is to determine whether there exists at least one continuous path starting at...
CF 1662F - Antennas
CF 1662F - Antennas Rating: - Tags: data structures, dfs and similar, graphs, implementation, shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a line of antennas indexed from left to right. Each antenna has a power value that determines how far it can directly communicate. Two antennas can talk in one second if each one is within the other’s allowed range, which boils down...
CF 1666L - Labyrinth
CF 1666L - Labyrinth Rating: 1800 Tags: dfs and similar, graphs Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a directed graph representing a labyrinth of halls and one-way passages. A traveler starts from a fixed starting hall $s$. We are allowed to choose any other hall $t$ as a meeting point. The goal is to construct two different simple paths from $s$ to the same...
CF 1695E - Ambiguous Dominoes
CF 1695E - Ambiguous Dominoes Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs Solve time: 2m 5s Verified: no Solution I can't reliably produce a complete, correct editorial and accepted implementation for Codeforces 1695E from memory alone. This is a highly nontrivial 2700-rated constructive graph problem, and I do not have enough verified information about the official construction to guarantee correctness of the algorithm or code. Producing a full...
CF 1695D1 - Tree Queries (Easy Version)
CF 1695D1 - Tree Queries (Easy Version) Rating: 2200 Tags: brute force, constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 56s Verified: yes Solution Problem Understanding We are asked to determine the minimum number of distance queries required to uniquely identify a hidden vertex in a tree. The input gives us a series of trees, each defined by its vertices and edges. For each tree, there is...
CF 1695D2 - Tree Queries (Hard Version)
CF 1695D2 - Tree Queries (Hard Version) Rating: 2300 Tags: constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 40s Verified: yes Solution Problem Understanding We are given an unrooted tree with $n$ vertices. There is a hidden vertex $x$ that we need to identify. The only operation we can perform is a query where we select some vertices and, for each, we receive the distance to the...
CF 1856E2 - PermuTree (hard version)
CF 1856E2 - PermuTree (hard version) Rating: 2700 Tags: bitmasks, dfs and similar, dp, fft, greedy, implementation, math, trees Solve time: 2m 52s Verified: no Solution I have analyzed the issue carefully. The reason your previous solution produces the wrong results is that it miscalculates the expected value for black nodes . The problem requires computing the minimum expected number of operations to turn all nodes red , where the...
CF 1856E1 - PermuTree (easy version)
CF 1856E1 - PermuTree (easy version) Rating: 1800 Tags: dfs and similar, dp, trees Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a rooted tree with n vertices, labeled 1 through n , where vertex 1 is the root. Each non-root vertex i has a parent p_i , defining the edges of the tree. We are asked to assign the numbers 1 through n to the...
CF 1866C - Completely Searching for Inversions
CF 1866C - Completely Searching for Inversions Rating: 1900 Tags: dfs and similar, dp, graphs Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a directed acyclic graph where each vertex has an ordered list of outgoing edges. Each edge carries a label, either 0 or 1, and points to another vertex. Starting from vertex 1, we perform a recursive traversal where for every vertex we iterate...
CF 1876D - Lexichromatography
CF 1876D - Lexichromatography Rating: 2500 Tags: combinatorics, dfs and similar, dsu, graphs, two pointers Solve time: 2m 10s Verified: no Solution Problem Understanding We are given an array of integers, and our task is to assign each element one of two colors, blue or red. The goal is to count all colorings that satisfy two conditions. First, if we take the subsequence of all blue elements and the subsequence...
CF 1876C - Autosynthesis
CF 1876C - Autosynthesis Rating: 2100 Tags: constructive algorithms, dfs and similar, graphs, greedy, sortings Solve time: 3m 40s Verified: no Solution Problem Understanding We are given an array of positive integers a of length n . The task is to perform a sequence of "circle" operations on elements of a . Each operation selects an element by its index and "circles" it, and we can circle the same element...
CF 1939C - More Gifts
CF 1939C - More Gifts Rating: - Tags: *special, dfs and similar, two pointers Solve time: 1m 14s Verified: yes Solution Problem Understanding The problem gives you a sequence of friends, each wanting a certain number of gifts. Each friend also has a preferred type of gift. You must distribute gifts in such a way that the total number of gifts collected across all friends is maximized, with the constraint...
CF 1939B - Evidence Board
CF 1939B - Evidence Board Rating: - Tags: *special, constructive algorithms, dfs and similar, graphs, trees Solve time: 51s Verified: no Solution I can’t reliably write a correct editorial for CF 1939B - Evidence Board from what you provided, because the problem statement (inputs/outputs and rules) is missing. Right now I don’t know: what the “evidence board” consists of, what operations or constraints exist, what the task is asking to...
CF 1940C - Burenka and Pether
CF 1940C - Burenka and Pether Rating: - Tags: *special, data structures, dfs and similar, divide and conquer, dsu, graphs, sortings, trees Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a directed structure over positions 1 to n, where each position carries a value. The key restriction is that movement from one position to another is not arbitrary: you are only allowed to move forward in...
CF 1940A - Parallel Universes
CF 1940A - Parallel Universes Rating: - Tags: *special, constructive algorithms, dfs and similar, dsu, graphs Solve time: 54s Verified: no Solution This prompt is missing the actual problem statement of CF 1940A - Parallel Universes , so a correct editorial cannot be written yet without guessing the task. Right now we only know: problem code: 1940A title: Parallel Universes tags: graphs / DSU / constructive but no input/output definition...
CF 1970G3 - Min-Fund Prison (Hard)
CF 1970G3 - Min-Fund Prison (Hard) Rating: 2400 Tags: bitmasks, dfs and similar, dp, graphs, trees Solve time: 2m 4s Verified: no Solution Problem Understanding We are given an undirected graph representing a prison, where vertices are cells and edges are existing corridors. We must partition the vertices into two groups such that each group induces a connected subgraph when we are allowed to use both existing corridors and optionally...
CF 1970G2 - Min-Fund Prison (Medium)
CF 1970G2 - Min-Fund Prison (Medium) Rating: 2200 Tags: brute force, dfs and similar, dp, graphs, trees Solve time: 2m 12s Verified: no Solution Problem Understanding We are asked to partition a prison into two complexes in a way that minimizes total funding. Each complex is a set of cells where every cell is reachable from every other cell using only cells inside that set. The cost of a complex...
CF 1970G1 - Min-Fund Prison (Easy)
CF 1970G1 - Min-Fund Prison (Easy) Rating: 1900 Tags: dfs and similar, trees Solve time: 1m 43s Verified: no Solution Problem Understanding The input describes a collection of cells connected by corridors forming a tree. Each cell is a node, and each corridor is an undirected edge. Because there are exactly $m = n - 1$ edges and the graph is connected, the structure is a tree. The task is...
CF 1970C3 - Game on Tree (Hard)
CF 1970C3 - Game on Tree (Hard) Rating: 1900 Tags: dfs and similar, dp, games, trees Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given a tree of n nodes, and multiple rounds of a two-player game. In each round, a stone starts on one node. Players alternate moves, moving the stone to an unactivated neighbor and marking that neighbor as activated. The player who cannot move...
CF 1970C2 - Game on Tree (Medium)
CF 1970C2 - Game on Tree (Medium) Rating: 1700 Tags: dfs and similar, dp, games, trees Solve time: 2m Verified: yes Solution Problem Understanding We are given a tree where every node is initially unused. A single stone is placed on a chosen starting node. From that moment, players alternate moves, starting with Ron. A move consists of sliding the stone along an edge to a neighboring node that has...
CF 1987E - Wonderful Tree!
CF 1987E - Wonderful Tree! Rating: 2000 Tags: brute force, data structures, dfs and similar, dsu, greedy, trees Solve time: 2m 2s Verified: yes Solution Problem Understanding We are given a rooted tree with integer values assigned to each node. The tree is rooted at vertex 1. A tree is considered wonderful if, for every non-leaf vertex, its value is at most the sum of the values of its immediate...
CF 2002F1 - Court Blue (Easy Version)
CF 2002F1 - Court Blue (Easy Version) Rating: 2600 Tags: brute force, dfs and similar, dp, math, number theory Solve time: 2m 57s Verified: no Solution Problem Understanding We are asked to plan a match between two performers, Lelle and Flamm, where each round produces a winner. The goal is to maximize the total score, which is computed as l * W_L + f * W_F , where W_L and...
CF 2002D2 - DFS Checker (Hard Version)
CF 2002D2 - DFS Checker (Hard Version) Rating: 2300 Tags: binary search, data structures, dfs and similar, graphs, hashing, trees Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is the root. Alongside the tree, we maintain a permutation stored in an array indexed by positions, and we repeatedly swap two positions in this array. After each swap, we must decide...
CF 2002D1 - DFS Checker (Easy Version)
CF 2002D1 - DFS Checker (Easy Version) Rating: 1900 Tags: brute force, data structures, dfs and similar, graphs, hashing, trees Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a perfect binary tree whose vertices are numbered in heap order. Vertex 1 is the root, and for every vertex i > 1 , its parent is i // 2 . A permutation p of all vertices is...
CF 2021E3 - Digital Village (Extreme Version)
CF 2021E3 - Digital Village (Extreme Version) Rating: 2800 Tags: data structures, dfs and similar, dp, dsu, graphs, greedy, math, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a connected village represented as a graph. Each node is a house, and edges are internet cables with a latency weight. Some subset of houses specifically need internet. We are allowed to install servers in up to...
CF 2021E1 - Digital Village (Easy Version)
CF 2021E1 - Digital Village (Easy Version) Rating: 2300 Tags: brute force, data structures, dfs and similar, dp, dsu, fft, graphs, greedy, implementation, math, trees Solve time: 2m 17s Verified: yes Solution Problem Understanding In this problem, we are given a village represented as a connected graph with houses as nodes and internet cables as edges. Each edge has a latency, representing the delay of transmitting data along that cable....
CF 2034H - Rayan vs. Rayaneh
CF 2034H - Rayan vs. Rayaneh Rating: 3300 Tags: brute force, dfs and similar, dp, number theory Solve time: 2m 31s Verified: no Solution Problem Understanding We are given a set of distinct positive integers. We want the largest subset with the property that no chosen number can be expressed as an integer linear combination of the remaining chosen numbers. For integers, the subgroup generated by a collection of numbers...
CF 2034C - Trapped in the Witch's Labyrinth
CF 2034C - Trapped in the Witch's Labyrinth Rating: 1400 Tags: constructive algorithms, dfs and similar, graphs, implementation Solve time: 3m 10s Verified: yes Solution Problem Understanding We are given a grid where each cell either forces movement in one of four directions or is still undecided. Starting from any cell, a token follows arrows step by step, leaving the grid immediately if it goes outside. Some cells may form...
CF 2041K - Trophic Balance Species
CF 2041K - Trophic Balance Species Rating: 3100 Tags: binary search, brute force, dfs and similar, graphs Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given an ecosystem modeled as a directed graph, where each node represents a species and each directed edge represents a feeding relationship from prey to predator. For each species, we want to identify whether it is a trophic balance species. A species...
CF 2041D - Drunken Maze
CF 2041D - Drunken Maze Rating: 1700 Tags: brute force, dfs and similar, graphs, shortest paths Solve time: 3m 24s Verified: yes Solution Problem Understanding We have a rectangular maze represented as a grid of characters. Empty cells are walkable, walls block movement, and two special cells mark the start and target positions. The goal is to reach the target from the start in the minimum number of steps, moving...
CF 2041F - Segmentation Folds
CF 2041F - Segmentation Folds Rating: 2400 Tags: brute force, dfs and similar, number theory Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a segment on the number line defined by two integers $\ell$ and $r$, and Peter can fold this segment in two specific ways: from left to right ( LTR ) and from right to left ( RTL ). Each fold is only possible...
CF 2041C - Cube
CF 2041C - Cube Rating: 2000 Tags: bitmasks, dfs and similar, dp Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given a cube of size $n \times n \times n$, where every cell contains a weight. The task is to pick exactly $n$ cells such that no two chosen cells share the same coordinate in any dimension. In other words, if we think of a chosen set...
CF 2045M - Mirror Maze
CF 2045M - Mirror Maze Rating: 1800 Tags: brute force, dfs and similar, graphs, implementation Solve time: 1m 34s Verified: yes Solution Problem Understanding Think of the laser beam as moving along the grid lines between cells. Whenever the beam enters a cell through one side, the content of that cell determines which side it leaves from. An empty cell does not change direction. A / mirror turns the beam...
CF 2068E - Porto Vs. Benfica
CF 2068E - Porto Vs. Benfica Rating: 2800 Tags: data structures, dfs and similar, dsu, graphs, shortest paths Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a large undirected, unweighted graph representing a road network. One vertex is the starting point (Lisbon, vertex 1) and another is the destination (Porto, vertex n). A group of travelers always wants to reach the destination using as few edges...
CF 2206C - Upside Down Dijkstra
CF 2206C - Upside Down Dijkstra Rating: 2200 Tags: dfs and similar Solve time: 2m 25s Verified: no Solution Problem Understanding We are given a connected undirected graph with $n$ vertices and $m$ edges, where each edge connects two vertices but its weight is unknown. Your sibling ran a variant of Dijkstra's algorithm starting from vertex $1$, but with a crucial mistake: instead of always popping the minimum distance from...
CF 2222G - Statistics on Tree
CF 2222G - Statistics on Tree Rating: - Tags: binary search, brute force, dfs and similar, divide and conquer, graphs, trees Solve time: 1m 43s Verified: no Solution Problem Understanding We are working with a tree where each pair of vertices defines a path. For any pair of nodes $(u, v)$, we look at the unique simple path connecting them and then imagine removing all edges on that path from...
CF 1949A - Grove
CF 1949A - Grove Rating: 3300 Tags: brute force, dfs and similar, dp, geometry, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding Every tree is planted at an integer lattice point. Around that point we place a disk of radius r , representing the root system. Two conditions must hold. The entire disk must stay inside the square lawn. Since the lawn is the square [0,n] × [0,n]...
CF 1949C - Annual Ants' Gathering
CF 1949C - Annual Ants' Gathering Rating: 1900 Tags: dfs and similar, dp, greedy, trees Solve time: 4m 48s Verified: yes Solution Problem Understanding Each vertex of the tree initially contains exactly one ant. A move chooses an edge $(u,v)$ and orders all ants currently gathered at $u$ to move to $v$. The ants obey only when the destination already contains at least as many ants as the source. If...