#trees

CF 1725E - Electrical Efficiency

CF 1725E - Electrical Efficiency Rating: 2500 Tags: combinatorics, data structures, dp, math, number theory, trees Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a tree of $N$ factories. Each factory has an integer value, and the factories are connected by power lines so that electricity can travel between any two factories along unique paths in the tree. For any triple of distinct factories $(x, y,...

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 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 1307F - Cow and Vacation

CF 1307F - Cow and Vacation Rating: 3300 Tags: dfs and similar, dsu, trees Solve time: 3m 17s Verified: no Solution Problem Understanding We are working on a tree of cities connected by roads, where every pair of cities is reachable through a unique simple path. Some of these cities contain rest stops. Bessie wants to travel between pairs of cities, but she has a constraint: she cannot traverse more...

CF 1254D - Tree Queries

CF 1254D - Tree Queries Rating: 2700 Tags: data structures, probabilities, trees Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a tree with values stored on vertices, initially all zero. The system processes two kinds of operations. One operation injects a value d into a region of the tree that depends on a randomly chosen root vertex r . The other asks for the expected accumulated...

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 1252D - Find String in a Grid

CF 1252D - Find String in a Grid Rating: 3000 Tags: data structures, dp, strings, trees Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a rectangular grid of uppercase letters and many query strings. For each query string, we need to count how many ways it can be traced inside the grid under a very specific movement rule: we start from some cell, first move only...

CF 1211H - Road Repair in Treeland

CF 1211H - Road Repair in Treeland Rating: 3100 Tags: *special, binary search, dp, trees Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a tree where each edge represents a road between two cities. Every road must be assigned to a company, and multiple roads can share the same company. The constraint is local: at any city, if we look at all roads incident to that...

CF 960D - Full Binary Tree Queries Rating: 2100 Tags: brute force, implementation, trees Model: gpt-5-3-mini Solve time: 4m 22s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a068-fe28-83ec-9de5-e9a20df13517 Solution Problem Understanding We are working with an infinite complete binary tree whose nodes are labeled in the standard heap order. The root is 1, and every node x has children 2x and 2x+1. This means every node corresponds to a unique binary representation...

CF 925E - May Holidays Rating: 2900 Tags: data structures, trees Model: gpt-5-3-mini Solve time: 1m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32ffff-94fc-83ec-89c8-10abb82f5c3d Solution Problem Understanding We are given a company hierarchy that forms a rooted tree, where employee 1 is the root. Every other employee has exactly one direct manager, so each node has a parent pointer and the structure has no cycles. The subtree of a node represents...

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 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 1045D - Interstellar battle Rating: 2200 Tags: math, probabilities, trees Model: gpt-5-3-mini Solve time: 5m 14s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33be72-3674-83ec-a75f-4dce1447204e Solution Problem Understanding We are given a tree of planets where each planet can independently be destroyed during an enemy attack. When a planet falls, it is removed along with all incident edges, so the remaining structure becomes a forest. The number we care about after an...

CF 997D - Cycles in product Rating: 2900 Tags: combinatorics, divide and conquer, trees Model: gpt-5-3-mini Solve time: 1m 48s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33af98-d4a0-83ec-9fa7-52b68b919935 Solution Problem Understanding We are given two trees and we build their Cartesian product graph. Each vertex of the new graph is a pair consisting of one node from the first tree and one node from the second tree. From such a pair, we...

CF 960H - Santa's Gift Rating: 3100 Tags: data structures, trees Model: gpt-5-3-mini Solve time: 1m 41s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a0ca-b98c-83ec-bcc1-c68b68835be7 Solution Problem Understanding We are working on a rooted tree where each vertex contains exactly one candy, and each candy has a flavour. The tree structure is fixed, but the flavours change over time through updates. For a fixed flavour $k$, imagine we repeatedly pick a vertex...

CF 928D - Autocompletion Rating: 1900 Tags: *special, strings, trees Model: gpt-5-3-mini Solve time: 1m 31s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33930d-daa4-83ec-983a-3890f249638f Solution Problem Understanding We are given a full text made of lowercase letters, spaces, punctuation, and line breaks. Arcady types this text left to right in a text editor. Every character normally costs one key press, and the goal is to type the entire text using the minimum...

CF 986E - Prince's Problem Rating: 2800 Tags: brute force, data structures, math, number theory, trees Model: gpt-5-3-mini Solve time: 1m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a912-486c-83ec-87ce-50fb9a999e6f Solution Problem Understanding We are working with a tree of up to 100,000 vertices. Each vertex stores a positive integer value. For every query, we are given two vertices and a number $x$. The query asks us to walk along the unique...

CF 982D - Shark Rating: 1900 Tags: brute force, data structures, dsu, trees Model: gpt-5-3-mini Solve time: 1m 4s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a645-49b4-83ec-b927-8bcea72bc401 Solution Problem Understanding We are given a sequence of distinct positive integers representing daily travel distances of a shark observed over time. We introduce a threshold value $k$. Each day is classified as either a “stay day” if the distance is less than $k$, or...

CF 990F - Flow Control Rating: 2400 Tags: dfs and similar, dp, greedy, trees Model: gpt-5-3-mini Solve time: 1m 23s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33ab95-73ac-83ec-a6af-8d4d9e5fd6cd Solution Problem Understanding We are given a connected undirected graph with junctions as vertices and pipes as edges. Each edge must be assigned an integer flow value, and that value can be interpreted with a direction: positive means the flow goes from the first...

CF 990G - GCD Counting Rating: 2400 Tags: divide and conquer, dp, dsu, number theory, trees Model: gpt-5-5 Solve time: 1m 41s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32935e-70f4-83ec-a952-c1e336e827ce Solution Problem Understanding We are given a tree where each vertex carries an integer value. For any two vertices, we consider the unique simple path between them and take the greatest common divisor of all values along that path. The task is...

CF 932D - Tree Rating: 2200 Tags: binary search, dp, trees Model: gpt-5-3-mini Solve time: 1m 28s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327666-dc20-83ec-bfaf-a06758f8815b Solution Problem Understanding We maintain a rooted tree that grows over time. The root is node 1 with weight 0. Each update query can attach a new node under an existing node, and each such node has a fixed weight. Over time, the structure becomes a rooted...

CF 936E - Iqea Rating: 3400 Tags: data structures, dfs and similar, divide and conquer, dsu, shortest paths, trees Model: gpt-5-3-mini Solve time: 2m 13s Verified: yes (1/1 samples) Solution Problem Understanding We are given a set of cells on a large grid. Each cell is a city, and roads exist between any two cities that share an edge on the grid. The important geometric constraints are that the chosen...

CF 923C - Perfect Security Rating: 1800 Tags: data structures, greedy, strings, trees Model: gpt-5-3-mini Solve time: 1m 18s Verified: yes (1/1 samples) Solution Problem Understanding We are given two arrays of integers of equal length. One array represents encrypted values, and the other represents a multiset of key values whose order has been lost. Each original message value was combined with one key value using bitwise XOR, but we...

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

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

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

Codeforces Round 471 (Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 1100-2900 | 8m 25s # Problem Rating Tags Accepted Time ✓ A Feed the cat 1100 greedy, math 7,023 1m 21s ✓ B Not simply beatiful strings 1400 implementation 5,162 1m 18s E Icicles 2900 102 2m 26s F Heaps 2600 dp, trees 1,963 3m 20s

CF 955F - Heaps

CF 955F - Heaps Rating: 2600 Tags: dp, trees Solve time: 3m 20s Verified: no Solution Problem Understanding We are given a rooted tree with $n$ nodes, rooted at node 1. For every node $u$, we consider a family of structures defined by an integer $k$, where a node can be thought of as the root of a “$k$-ary heap of depth $m$” if it has at least $k$ child-subtrees...

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

Codeforces Round 473 (Div. 2)

Codeforces Round 473 (Div. 2) Div. 2 | 3 problems | 3/3 verified | Difficulty 800-1900 | 4m 23s # Problem Rating Tags Accepted Time ✓ A Mahmoud and Ehab and the even-odd game 800 games, math 55,647 58s ✓ C Mahmoud and Ehab and the wrong algorithm 1500 constructive-algorithms, trees 6,207 1m 13s ✓ E Mahmoud and Ehab and the xor-MST 1900 bitmasks, dp, graphs 3,765 2m 12s ✓

CF 959C - Mahmoud and Ehab and the wrong algorithm

CF 959C - Mahmoud and Ehab and the wrong algorithm Rating: 1500 Tags: constructive algorithms, trees Solve time: 1m 13s Verified: yes Solution Problem Understanding We are given a tree with n vertices and asked to construct two different trees on the same number of vertices, each meant to expose the failure or correctness of a specific heuristic for minimum vertex cover. The heuristic is extremely simple. We root the...

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

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 962G - Visible Black Areas

CF 962G - Visible Black Areas Rating: 2800 Tags: data structures, dsu, geometry, trees Solve time: 32s Verified: no Solution Problem Understanding We are given a simple orthogonal polygon, meaning its edges are horizontal or vertical and it never self-intersects. The interior of this polygon is considered “black”. We also have a fixed axis-aligned rectangular window. The window is static and we look only through it. Inside the window, parts...

Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 1)

Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 1) Div. 1 | 2 problems | 1/2 verified | Difficulty 2000-2600 | 3m 1s # Problem Rating Tags Accepted Time ✓ B Destruction of a Tree 2000 constructive-algorithms, dfs-and-similar, dp 3,000 1m 22s C Cutting Rectangle 2600 brute-force, math, number-theory 672 1m 39s ✓

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 965E - Short Code

CF 965E - Short Code Rating: 2200 Tags: data structures, dp, greedy, strings, trees Solve time: 1m 23s Verified: no Solution Problem Understanding We are given a collection of distinct lowercase strings, each representing a variable name. For each original name, we must choose a non-empty prefix of that string to act as its new shortened identifier. The constraint is that after shortening all names, no two resulting names may...

Codeforces Round 482 (Div. 2)

Codeforces Round 482 (Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2400 | 8m 57s # Problem Rating Tags Accepted Time ✓ A Pizza, Pizza, Pizza!!! 1000 math 14,574 1m 6s ✓ B Treasure Hunt 1800 greedy 4,779 1m 14s ✓ C Kuro and Walking Route 1600 dfs-and-similar, trees 7,333 2m 52s D Kuro and GCD and XOR and SUM 2200 binary-search, bitmasks, brute-force 2,176 1m...

CF 979D - Kuro and GCD and XOR and SUM

CF 979D - Kuro and GCD and XOR and SUM Rating: 2200 Tags: binary search, bitmasks, brute force, data structures, dp, dsu, greedy, math, number theory, strings, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are maintaining a dynamic multiset of positive integers. The structure supports insertions, and after each insertion phase we may receive queries asking us to pick one previously inserted value that satisfies three...

CF 979C - Kuro and Walking Route

CF 979C - Kuro and Walking Route Rating: 1600 Tags: dfs and similar, trees Solve time: 2m 52s Verified: no Solution Problem Understanding We are given a tree, meaning a connected graph with exactly one simple path between any two towns. Every ordered pair of distinct towns defines a walking route that follows that unique path. Among all possible ordered pairs of towns, some are considered invalid. The restriction depends...

Codeforces Round 480 (Div. 2)

Codeforces Round 480 (Div. 2) Div. 2 | 4 problems | 3/4 verified | Difficulty 900-2900 | 6m 21s # Problem Rating Tags Accepted Time ✓ A Links and Pearls 900 implementation, math 10,950 1m 7s ✓ B Marlin 1600 constructive-algorithms 4,923 1m 29s ✓ E The Number Games 2200 data-structures, greedy, trees 2,117 1m 46s ✓ F Cactus to Tree 2900 dp, graphs, trees 215 1m 59s

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

CF 980E - The Number Games

CF 980E - The Number Games Rating: 2200 Tags: data structures, greedy, trees Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given a tree with $n$ nodes. Each node represents a district, and the road system guarantees there is exactly one simple path between any two districts. Each district $i$ contributes a value equal to $2^i$, so higher numbered districts are exponentially more valuable than lower numbered...

Avito Code Challenge 2018

Avito Code Challenge 2018 Special | 4 problems | 3/4 verified | Difficulty 900-3100 | 7m 46s # Problem Rating Tags Accepted Time ✓ A Antipalindrome 900 brute-force, implementation, strings 10,327 1m 8s ✓ C Useful Decomposition 1400 implementation, trees 6,856 2m 15s ✓ E Addition on Segments 2200 bitmasks, data-structures, divide-and-conquer 2,535 2m 22s ✓ H K Paths 3100 combinatorics, data-structures, dp 288 2m 1s

CF 981C - Useful Decomposition

CF 981C - Useful Decomposition Rating: 1400 Tags: implementation, trees Solve time: 2m 15s Verified: yes Solution Problem Understanding We are given an undirected tree, and we must split all its edges into a collection of simple paths so that every edge belongs to exactly one path. The extra requirement is global and restrictive: if we pick any two of these paths, they must share at least one common vertex....

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 983E - NN country

CF 983E - NN country Rating: 2800 Tags: binary search, data structures, trees Solve time: 1m 49s Verified: no Solution Problem Understanding The road network forms a tree of cities, so between any two cities there is exactly one simple path. On top of this fixed tree structure, there are additional “bus routes” between pairs of cities. A bus route between two endpoints does not behave like a single edge:...

CF 995F - Cowmpany Cowmpensation

CF 995F - Cowmpany Cowmpensation Rating: 2700 Tags: combinatorics, dp, math, trees Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a rooted tree of employees where employee 1 is the CEO. Every other employee has exactly one direct superior, forming a hierarchy. We must assign each employee an integer salary between 1 and D, with the constraint that no employee can earn more than their direct...

CF 1000G - Two-Paths

CF 1000G - Two-Paths Rating: 2700 Tags: data structures, dp, trees Solve time: 2m 10s Verified: no Solution Problem Understanding We are working on a weighted tree where every vertex has a positive value and every edge has a positive cost. A path is not required to be simple in the usual sense: edges are allowed to be traversed up to two times, and vertices can be visited multiple times....

CF 1004E - Sonya and Ice Cream

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

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

CF 1007D - Ants

CF 1007D - Ants Rating: 3200 Tags: 2-sat, data structures, trees Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given a tree and a collection of “ants”. Each ant comes with two alternative vertex pairs. For each ant, we must decide which of its two pairs it will use. After that choice, every ant “claims” the unique path between its chosen pair in the tree, and this...

CF 1009F - Dominant Indices

CF 1009F - Dominant Indices Rating: 2300 Tags: data structures, dsu, trees Solve time: 1m 59s Verified: yes Solution Problem Understanding We are working with a rooted tree where vertex 1 is considered the root. For every vertex $x$, we conceptually look at all nodes in its subtree and group them by their distance from $x$ in terms of edges downward in the tree. More concretely, for a fixed vertex...

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 1016F - Road Projects

CF 1016F - Road Projects Rating: 2600 Tags: dfs and similar, dp, trees Solve time: 2m 18s Verified: no Solution Problem Understanding We are given a weighted tree whose nodes are cities and whose edges are existing roads with travel times. The structure guarantees a unique simple path between any two cities, so distances are well-defined tree distances. Two special nodes matter more than all others: city 1 and city...

CF 1019E - Raining season

CF 1019E - Raining season Rating: 3200 Tags: data structures, divide and conquer, trees Solve time: 2m 36s Verified: yes Solution Problem Understanding We are given a tree where each edge represents a bidirectional road between two houses. Every road has two parameters: a base traversal time and a rate at which it worsens each day. On day $t$, the cost of an edge becomes a linear function $b_i +...

CF 1023G - Pisces

CF 1023G - Pisces Rating: 3400 Tags: data structures, flows, trees Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a weighted tree where each edge represents a river with a travel time. Fish can move continuously along these edges: traversing an edge of length $l$ takes exactly $l$ days, and fish may also wait arbitrarily at vertices. Fish never split or merge; each fish is an...

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 1025D - Recovering BST

CF 1025D - Recovering BST Rating: 2100 Tags: brute force, dp, math, number theory, trees Solve time: 3m 32s Verified: yes Solution Problem Understanding We are given a sorted list of distinct integers, and we want to build a binary search tree using exactly these values as node keys. The in-order traversal of any valid BST with these keys is fixed and already matches the given order, so the only...

Technocup 2019 - Elimination Round 3

Technocup 2019 - Elimination Round 3 Special | 6 problems | 2/6 verified | Difficulty 900-2900 | 45m 9s # Problem Rating Tags Accepted Time ✓ A Kitchen Utensils 900 7,335 10m 29s ✓ B Personalized Cup 1200 5,145 9m 12s ✓ D Barcelonian Distance 1900 geometry, implementation 2,976 5m 6s E The Unbearable Lightness of Weights 2100 dp, math 1,865 3m 25s F Vasya and Maximum Matching 2400 dp,...

CF 1032F - Vasya and Maximum Matching

CF 1032F - Vasya and Maximum Matching Rating: 2400 Tags: dp, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are given a tree and we are allowed to remove any subset of its edges. After removals, the tree becomes a forest. On this resulting forest, we consider all possible matchings and focus on those that achieve maximum size. The requirement is that among all maximum matchings, there...

CF 1034C - Region Separation

CF 1034C - Region Separation Rating: 2700 Tags: combinatorics, dp, number theory, trees Solve time: 10m 26s Verified: no Solution

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

Codeforces Round 660 (Div. 2)

Codeforces Round 660 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2700 | 13m 36s # Problem Rating Tags Accepted Time ✓ A Captain Flint and Crew Recruitment 800 brute-force, greedy, math 25,953 4m 57s B Captain Flint and a Long Voyage 1000 greedy, math 22,819 2m 12s ✓ C C 1800 dfs and similar, greedy, math 10,413 2m 35s ✓ D Captain Flint and Treasure...

CF 1039D - You Are Given a Tree

CF 1039D - You Are Given a Tree Rating: 2800 Tags: data structures, dp, trees Solve time: 3m 5s Verified: yes Solution Problem Understanding We are working with a tree where we want to select several simple paths, with a strict rule that no vertex can belong to more than one selected path. Every chosen path must contain exactly k vertices, and for each k from 1 to n we...

Lyft Level 5 Challenge 2018 - Final Round

Lyft Level 5 Challenge 2018 - Final Round Special | 6 problems | 1/6 verified | Difficulty 1700-3100 | 30m 21s # Problem Rating Tags Accepted Time ✓ A The Tower is Going Home 1700 binary-search, two-pointers 3,076 10m 12s B Intersecting Subtrees 1900 dfs-and-similar, interactive, trees 1,708 1m 59s ✓ C Optimal Polygon Perimeter 2100 dp, geometry 1,409 5m 59s D Deduction Queries 2400 data-structures, dsu 1,186 7m E...

CF 1044B - Intersecting Subtrees

CF 1044B - Intersecting Subtrees Rating: 1900 Tags: dfs and similar, interactive, trees Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given a tree with n vertices, but there is a twist: there are two different labelings of the same underlying tree. In your view, the vertices are numbered from 1 to n and the edges are given in this numbering. Li Chen has independently assigned his...

CF 1045J - Moonwalk challenge

CF 1045J - Moonwalk challenge Rating: 2600 Tags: data structures, strings, trees Solve time: 6m 39s Verified: yes Solution Problem Understanding The input describes a tree where each edge connects two craters and carries a single lowercase letter. If you walk between any two craters, there is exactly one simple path, and that path naturally produces a string formed by concatenating the edge labels along the way. Each query gives...

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 1725J - Journey

CF 1725J - Journey Rating: 2500 Tags: dp, trees Solve time: 4m 34s Verified: no Solution Problem Understanding We are given a weighted tree where each node represents a city and each edge represents a bidirectional road with a travel time. The traveler must design a walk that eventually visits every city at least once. Movement is not restricted to simple paths, so revisiting nodes and edges is allowed, and...

CF 1725I - Imitating the Key Tree

CF 1725I - Imitating the Key Tree Rating: 2800 Tags: combinatorics, dsu, trees Solve time: 2m 4s Verified: no Solution Working

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 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 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 1385F - Removing Leaves

CF 1385F - Removing Leaves Rating: 2300 Tags: data structures, greedy, implementation, trees Solve time: 7m 50s Verified: no Solution Problem Understanding We are working with a tree where vertices are gradually removed in rounds. In one round, we are allowed to pick a single internal vertex $v$ and remove exactly $k$ of its current leaf neighbors. A vertex counts as a leaf if it has degree one in the...

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 1380E - Merging Towers

CF 1380E - Merging Towers Rating: 2300 Tags: data structures, dsu, implementation, trees Solve time: 7m 10s Verified: yes Solution Problem Understanding We are given a set of numbered discs from 1 to n, where larger numbers represent larger discs. These discs are initially split across m towers, and each tower already has its discs stacked in decreasing order of size from bottom to top. We are allowed to repeatedly...

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 1363E - Tree Shuffling

CF 1363E - Tree Shuffling Rating: 2000 Tags: dfs and similar, dp, greedy, trees Solve time: 3m 57s Verified: no Solution Problem Understanding We are given a rooted tree where each node carries two bits of information: an initial binary digit and a desired final binary digit. The task is to transform the initial configuration into the target configuration using a special operation that allows us to take any subtree,...

CF 1361D - Johnny and James

CF 1361D - Johnny and James Rating: 2900 Tags: greedy, implementation, math, trees Solve time: 4m 33s Verified: no Solution Problem Understanding We are given a set of points on the plane, one of which is guaranteed to be the origin. From these points, we must keep exactly k points and delete the rest. The goal is to maximize a global score defined over all pairs of kept points, where...

CF 1344E - Train Tracks

CF 1344E - Train Tracks Rating: 3100 Tags: data structures, trees Solve time: 4m 51s Verified: no Solution Problem Understanding The system is a rooted tree of stations, where every node with children behaves like a router that forwards all incoming trains to exactly one of its children. In other words, each station does not split traffic, it deterministically pushes everything downward along a single outgoing edge. Because of this,...

CF 1338D - Nested Rubber Bands

CF 1338D - Nested Rubber Bands Rating: 2700 Tags: constructive algorithms, dfs and similar, dp, math, trees Solve time: 6m 25s Verified: yes Solution Problem Understanding We are given a tree, and the problem asks us to think about a geometric construction that can be performed on it. Each vertex becomes a closed non-self-intersecting curve on a plane. These curves are required to interact in a very rigid way: two...

CF 1326G - Spiderweb Trees

CF 1326G - Spiderweb Trees Rating: 3500 Tags: dp, geometry, trees Solve time: 3m 23s Verified: no Solution Problem Understanding We are given a geometric tree: each vertex is a point in the plane and edges form a non-crossing tree. This already means the embedding is fixed, so geometric notions like convex hull are meaningful relative to the given drawing. A subset of vertices is considered valid as a group...

Codeforces Round 628 (Div. 2)

Codeforces Round 628 (Div. 2) Div. 2 | 3 problems | 2/3 verified | Difficulty 800-2600 | 12m 30s # Problem Rating Tags Accepted Time ✓ B CopyCopyCopyCopyCopy 800 greedy, implementation 38,820 3m 14s ✓ C Ehab and Path-etic MEXs 1500 constructive-algorithms, dfs-and-similar, greedy 17,153 1m 7s E Ehab's REAL Number Theory Problem 2600 brute-force, dfs-and-similar, graphs 2,335 8m 9s ✓

CF 1322F - Assigning Fares

CF 1322F - Assigning Fares Rating: 3500 Tags: dp, trees Solve time: 5m 18s Verified: yes Solution Problem Understanding We are given a tree with $n$ stations and $n-1$ tunnels, so between any two stations there is exactly one simple path. On this tree, we are also given $m$ special routes. Each route is just a simple path between two endpoints, but we are allowed to choose its direction later,...

CF 1311E - Construct the Binary Tree

CF 1311E - Construct the Binary Tree Rating: 2200 Tags: brute force, constructive algorithms, trees Solve time: 12m 35s Verified: no Solution Problem Understanding We are asked to build a rooted tree on vertices labeled from 1 to n, where vertex 1 is the root. Every vertex except the root has exactly one parent, and each vertex is allowed to have at most two children, so the structure must be...

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 1303G - Sum of Prefix Sums

CF 1303G - Sum of Prefix Sums Rating: 2700 Tags: data structures, divide and conquer, geometry, trees Solve time: 3m 7s Verified: no Solution Problem Understanding We are given a tree where each node stores a positive integer. For any simple path between two vertices, we read the values along that path in order and then compute a special score: we first form all prefix sums of that sequence and...

CF 1297E - Modernization of Treeland

CF 1297E - Modernization of Treeland Rating: - Tags: *special, dfs and similar, trees Solve time: 3m 35s Verified: no Solution Problem Understanding We are given a tree of cities. From this tree we must choose a subset of cities $S$ such that two conditions hold simultaneously. First, if we only look at edges whose endpoints are both in $S$, the chosen vertices must remain connected, so $S$ forms a...

CF 1296F - Berland Beauty

CF 1296F - Berland Beauty Rating: 2100 Tags: constructive algorithms, dfs and similar, greedy, sortings, trees Solve time: 7m 17s Verified: no Solution Problem Understanding We are given a connected network of $n$ stations connected by $n-1$ railway segments, which means the structure is a tree. Each edge in this tree has an unknown integer weight in the range from 1 to $10^6$. We are also given several observations from...

CF 1294F - Three Paths on a Tree

CF 1294F - Three Paths on a Tree Rating: 2000 Tags: dfs and similar, dp, greedy, trees Solve time: 4m 58s Verified: no Solution Problem Understanding We are working with a tree, which means there is exactly one simple path between any two vertices. From this tree we must choose three distinct vertices, call them $a$, $b$, and $c$. Once these three points are fixed, we look at the three...

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

CF 1292C - Xenon's Attack on the Gangs

CF 1292C - Xenon's Attack on the Gangs Rating: 2300 Tags: combinatorics, dfs and similar, dp, greedy, trees Solve time: 1m 10s Verified: no Solution Problem Understanding We are given a tree with $n$ nodes and $n-1$ edges. Each edge is assigned a distinct label from $0$ to $n-2$, so every label appears exactly once. For any pair of nodes $u, v$, we look at the unique path between them...

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 1285D - Dr. Evil Underscores

CF 1285D - Dr. Evil Underscores Rating: 1900 Tags: bitmasks, brute force, dfs and similar, divide and conquer, dp, greedy, strings, trees Solve time: 8m 56s Verified: yes Solution Problem Understanding We are given a list of integers, and we are allowed to choose a single integer $X$. Once $X$ is fixed, every array value is transformed by XOR with $X$, and we care about the largest transformed value. The...

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

CF 1283F - DIY Garland

CF 1283F - DIY Garland Rating: 2200 Tags: constructive algorithms, greedy, trees Solve time: 6m 36s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices, where each vertex represents a lamp. One of these lamps is directly connected to a power source, and from it power spreads through directed connections formed by the wires of the tree. Each wire has an implicit direction: one endpoint is...

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

CF 1280D - Miss Punyverse

CF 1280D - Miss Punyverse Rating: 2500 Tags: dp, greedy, trees Solve time: 6m 38s Verified: no Solution Problem Understanding We are given a tree where each node represents a “nesting place” that contains two types of insects: bees and wasps. Every insect votes for its own side, so bees always contribute to the bee count of a region and wasps always contribute to the wasp count. We must split...

CF 1278E - Tests for problem D

CF 1278E - Tests for problem D Rating: 2200 Tags: constructive algorithms, dfs and similar, divide and conquer, trees Solve time: 10m 37s Verified: no Solution Problem Understanding We are given a tree with n labeled vertices. The task is not to manipulate the tree directly, but to construct a completely different object: n line segments on the number line, using the integers from 1 to 2n exactly once as...

CF 1254E - Send Tree to Charlie

CF 1254E - Send Tree to Charlie Rating: 3300 Tags: combinatorics, dfs and similar, dsu, trees Solve time: 4m 42s Verified: yes Solution Problem Understanding We are given a tree with $n$ nodes, where each node initially holds a unique label from $1$ to $n$. Someone then performs a process that is equivalent to choosing an ordering of all edges and, for each edge in that order, swapping the labels...

CF 1252F - Regular Forestation

CF 1252F - Regular Forestation Rating: 2400 Tags: hashing, trees Solve time: 4m 24s Verified: no Solution Problem Understanding We are given a tree with up to 4000 nodes, and we are allowed to pick a single node and remove it. Removing a node splits the tree into several connected components, each of which is itself a tree. The number of components equals the degree of the removed node. The...

CF 1249F - Maximum Weight Subset

CF 1249F - Maximum Weight Subset Rating: 2200 Tags: dp, trees Solve time: 6m Verified: yes Solution Problem Understanding We are given a tree where each vertex carries a positive weight. The task is to select a subset of vertices that maximizes the sum of chosen weights, but with a strict geometric restriction: any two selected vertices must be more than $k$ edges apart in the tree. Equivalently, once we...

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 1228F - One Node is Gone

CF 1228F - One Node is Gone Rating: 2500 Tags: constructive algorithms, implementation, trees Solve time: 4m 28s Verified: no Solution Problem Understanding We start with a perfect binary tree of height n , meaning every internal node has exactly two children and all leaves sit at the same depth. This tree contains exactly 2^n - 1 nodes and has a very rigid recursive structure: every subtree is itself a...

CF 1225F - Tree Factory

CF 1225F - Tree Factory Rating: 2500 Tags: constructive algorithms, greedy, trees Solve time: 6m 6s Verified: no Solution Problem Understanding We are given a rooted tree where vertex labels already obey a strict ordering constraint: every node except the root has a parent with a smaller label. This means the vertices are effectively introduced in increasing order, and the parent of each node is always chosen from earlier vertices....

CF 1223E - Paint the Tree

CF 1223E - Paint the Tree Rating: 2100 Tags: dp, sortings, trees Solve time: 5m 17s Verified: yes Solution Problem Understanding We are given a tree where every edge has a weight. The task is to assign colors to vertices under a very specific rule: each vertex receives exactly $k$ colors, and any particular color can appear at most twice across the entire tree. This means every color effectively either...

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

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 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 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 1211G - King's Path

CF 1211G - King's Path Rating: 2500 Tags: *special, math, trees Solve time: 2m 51s Verified: yes Solution Problem Understanding We are given a tree where each node initially holds a color. There is also a target color for every node. The King performs a single walk on the tree. During this walk, whenever he traverses an edge, the endpoints of that edge swap their current flags. Because vertices can...

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 1207G - Indie Album

CF 1207G - Indie Album Rating: 2700 Tags: data structures, dfs and similar, hashing, string suffix structures, strings, trees Solve time: 4m 10s Verified: no Solution Problem Understanding We are given a growing collection of strings, where each new string is either a single character or an old string extended by exactly one character at the end. This means the entire system forms a rooted tree: every string points to...

Codeforces Round 564 (Div. 1)

Codeforces Round 564 (Div. 1) Div. 1 | 7 problems | 3/7 verified | Difficulty 1800-3300 | 41m 7s # Problem Rating Tags Accepted Time ✓ A Nauuo and Cards 1800 greedy, implementation 5,175 7m 25s ✓ B Nauuo and Circle 1900 combinatorics, dfs-and-similar, dp 4,404 1m 31s ✓ C1 Nauuo and Pictures (easy version) 2300 dp, probabilities 1,225 6m 32s ✓ C2 Nauuo and Pictures (hard version) 2600 dp,...

CF 1168D - Anagram Paths

CF 1168D - Anagram Paths Rating: 3000 Tags: dp, implementation, trees Solve time: 8m 7s Verified: no Solution Problem Understanding We are given a rooted binary tree where each edge carries either a fixed lowercase letter or a wildcard character. Every leaf defines a string obtained by walking from the root to that leaf and concatenating edge labels. The wildcard edges can later be replaced by any lowercase letters. After...

CF 1099F - Cookies

CF 1099F - Cookies Rating: 2400 Tags: binary search, data structures, dfs and similar, dp, games, trees Solve time: 6m 43s Verified: no Solution Problem Understanding We are given a rooted tree where each vertex contains a pile of cookies. Every vertex also has a cost for eating one cookie at that vertex, and every edge from a node to its parent has a cost for moving upward along it....

Codeforces Round 530 (Div. 1)

Codeforces Round 530 (Div. 1) Div. 1 | 6 problems | 3/6 verified | Difficulty 1600-3500 | 37m 57s # Problem Rating Tags Accepted Time ✓ A Sum in the tree 1600 constructive-algorithms, dfs-and-similar, greedy 9,547 9m 13s B Nice table 2100 brute-force, constructive-algorithms, greedy 1,797 5m 15s ✓ C Construct a tree 2400 binary-search, constructive-algorithms, dfs-and-similar 1,161 5m 19s ✓ D Eels 2800 data-structures 882 4m 20s ✓ E...

CF 1098A - Sum in the tree

CF 1098A - Sum in the tree Rating: 1600 Tags: constructive algorithms, dfs and similar, greedy, trees Solve time: 9m 13s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is the root. Every vertex originally had a non-negative integer value written on it, but those values are now lost. What remains is partial information about prefix sums along root paths. For any vertex $v$,...

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 1097G - Vladislav and a Great Legend

CF 1097G - Vladislav and a Great Legend Rating: 3000 Tags: combinatorics, dp, trees Solve time: 6m 10s Verified: no Solution Problem Understanding We are working with a tree where every subset of vertices defines a natural “cost” based on how large a minimal connected subgraph is when we are forced to include all vertices in that subset. For a chosen subset, you take the smallest subtree that contains all...

Technocup 2019 - Elimination Round 4

Technocup 2019 - Elimination Round 4 Special | 7 problems | 5/7 verified | Difficulty 800-2900 | 23m 43s # Problem Rating Tags Accepted Time ✓ A Right-Left Cipher 800 implementation, strings 12,697 3m 55s ✓ B Div Times Mod 1100 math 10,086 1m 45s ✓ C Connect Three 1600 implementation, math 5,643 2m 25s ✓ D Minimum Diameter Tree 1700 constructive-algorithms, implementation, trees 5,907 2m 20s E Vasya and...

CF 1085D - Minimum Diameter Tree

CF 1085D - Minimum Diameter Tree Rating: 1700 Tags: constructive algorithms, implementation, trees Solve time: 2m 20s Verified: no Solution Problem Understanding We are given a tree and a fixed total amount of “weight budget” $s$. Every edge must be assigned a non-negative real weight, and the sum over all edges must equal exactly $s$. Once weights are assigned, the distance between two vertices is the sum of edge weights...

CF 1073F - Choosing Two Paths

CF 1073F - Choosing Two Paths Rating: 2500 Tags: dfs and similar, dp, greedy, trees Solve time: 5m 52s Verified: no Solution Problem Understanding We are given a tree, meaning a connected graph with no cycles. On this tree we must pick two simple paths, each defined by choosing two endpoints. The endpoints of the two paths must all be distinct, and neither path is allowed to contain either endpoint...

CF 1067E - Random Forest Rank

CF 1067E - Random Forest Rank Rating: 2800 Tags: dp, graph matchings, math, trees Solve time: 9m Verified: no Solution Problem Understanding We are given a tree with $n$ vertices. Each edge is independently kept with probability $1/2$, so after the process we obtain a random forest. For every such resulting forest, we can build its adjacency matrix over real numbers and take its linear algebraic rank. The task is...

Mail.Ru Cup 2018 - Practice Round

Mail.Ru Cup 2018 - Practice Round Special | 3 problems | 2/3 verified | Difficulty 900-2000 | 12m 23s # Problem Rating Tags Accepted Time ✓ A Bmail Computer Network 900 *special, dfs-and-similar, trees 7,467 4m 52s ✓ B DDoS 1400 *special, brute-force 1,970 4m 25s ✓ C Tanya and Colored Candies 2000 *special, dp 1,171 3m 6s

CF 914E - Palindromes in a Tree

CF 914E - Palindromes in a Tree Rating: 2400 Tags: bitmasks, data structures, divide and conquer, trees Solve time: 4m 42s Verified: no Solution Problem Understanding We are given a tree where each node carries a lowercase character from a limited alphabet of size 20. The task is to examine every simple path in the tree and determine whether the multiset of characters along that path can be rearranged into...

Codeforces Round 453 (Div. 1)

Codeforces Round 453 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1500-3300 | 12m 51s # Problem Rating Tags Accepted Time ✓ A Hashing Trees 1500 constructive-algorithms, trees 5,377 2m 56s B GCD of Polynomials 2200 constructive-algorithms, math 1,640 2m 34s ✓ C Bipartite Segments 2300 binary-search, data-structures, dfs-and-similar 1,298 2m 44s ✓ D Weighting a Tree 2700 constructive-algorithms, dfs-and-similar, graphs 630 2m 17s E Cyclic...

CF 901A - Hashing Trees

CF 901A - Hashing Trees Rating: 1500 Tags: constructive algorithms, trees Solve time: 2m 56s Verified: no Solution Problem Understanding We are given a rooted tree described indirectly through a “level size profile.” Instead of edges, we only know how many nodes exist at each distance from the root. The array a[i] tells us how many vertices are exactly i edges away from the root, and the maximum index h...

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

Codeforces Round 512 (Div. 1, based on Technocup 2019 Elimination Round 1)

Codeforces Round 512 (Div. 1, based on Technocup 2019 Elimination Round 1) Div. 1 | 1 problems | 1/1 verified | Difficulty 3500-3500 | 4m 56s # Problem Rating Tags Accepted Time ✓ E Euler tour 3500 constructive-algorithms, trees 239 4m 56s ✓

CF 1053E - Euler tour

CF 1053E - Euler tour Rating: 3500 Tags: constructive algorithms, trees Solve time: 4m 56s Verified: yes Solution Problem Understanding We are given a sequence of length $2n - 1$, which is supposed to represent the order in which a squirrel visits vertices of some tree during a full traversal. The traversal has a specific rule: consecutive numbers in the sequence correspond to adjacent vertices in the tree, and the...

CF 1055F - Tree and XOR

CF 1055F - Tree and XOR Rating: 2900 Tags: strings, trees Solve time: 4m 13s Verified: yes Solution Problem Understanding The tree gives you a system where every vertex can be assigned a value: the XOR of edge weights on the path from an arbitrary root (say vertex 1) to that vertex. Once these values are fixed, the XOR between any two vertices becomes a very simple expression: it is...

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 1057A - Bmail Computer Network

CF 1057A - Bmail Computer Network Rating: 900 Tags: *special, dfs and similar, trees Solve time: 4m 52s Verified: yes Solution Problem Understanding We are given a growing network of routers that forms a tree rooted at router 1. Every router except the first was added one by one, and each new router was directly connected to exactly one earlier router. This means every router has a single parent, and...

CF 1059E - Split the Tree

CF 1059E - Split the Tree Rating: 2400 Tags: binary search, data structures, dp, greedy, trees Solve time: 5m 27s Verified: no Solution Problem Understanding We are given a rooted tree where every vertex contains a positive weight. The task is to partition all vertices into a minimum number of vertical paths. A vertical path is a chain that always moves from a node to one of its children or,...

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 1062E - Company

CF 1062E - Company Rating: 2300 Tags: binary search, data structures, dfs and similar, greedy, trees Solve time: 2m 22s Verified: yes Solution Problem Understanding The company hierarchy forms a rooted tree where employee 1 is the root, and every other employee has exactly one direct boss. This defines a parent relationship and also induces depths from the root, where depth is the number of edges from employee 1. Each...

CF 1065F - Up and Down the Tree

CF 1065F - Up and Down the Tree Rating: 2500 Tags: dfs and similar, dp, trees Solve time: 5m 1s Verified: no Solution Problem Understanding We are given a rooted tree with vertex 1 as the root, and every vertex except the root has exactly one parent defined by the input. Some vertices are leaves in the usual sense of the tree structure. A token starts at the root and...

CF 1076E - Vasya and a Tree

CF 1076E - Vasya and a Tree Rating: 1900 Tags: data structures, trees Solve time: 4m 29s Verified: yes Solution Problem Understanding We are given a rooted tree where vertex 1 acts as the root, and every vertex initially holds value 0. The tree is static, but we are asked to process a sequence of update operations. Each operation chooses a vertex $v$, a distance limit $d$, and a value...

CF 1082F - Speed Dial

CF 1082F - Speed Dial Rating: 2800 Tags: dp, strings, trees Solve time: 4m 46s Verified: yes Solution Problem Understanding We are given a set of phone numbers, each associated with how frequently Polycarp dials it. Every time a number is dialed, he must physically press digits, but the phone allows up to $k$ special speed dial buttons. Each button can be assigned exactly one full phone number, and when...

Codeforces Round 526 (Div. 1)

Codeforces Round 526 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1800-3500 | 14m 56s # Problem Rating Tags Accepted Time ✓ A The Fair Nut and the Best Path 1800 data-structures, dp, trees 6,268 2m 11s ✓ B The Fair Nut and Strings 2000 greedy, strings 2,142 2m 28s C Max Mex 2900 data-structures, trees 1,112 2m 13s ✓ D The Fair Nut's getting crazy...

CF 1083C - Max Mex

CF 1083C - Max Mex Rating: 2900 Tags: data structures, trees Solve time: 2m 13s Verified: yes Solution Problem Understanding We are given a rooted tree on $n$ nodes. Each node stores a distinct value from $0$ to $n-1$, so the values form a permutation. Alongside this, the tree structure is fixed, but the values can change over time through swap operations. Two operations are supported. One swaps the values...

CF 1083A - The Fair Nut and the Best Path

CF 1083A - The Fair Nut and the Best Path Rating: 1800 Tags: data structures, dp, trees Solve time: 2m 11s Verified: yes Solution Problem Understanding We are given a tree where each node represents a city. Every city contains a fuel station, and each station allows us to obtain some fixed amount of fuel $w_i$. Traveling between two cities connected by a road consumes fuel equal to that road’s...

CF 1088E - Ehab and a component choosing problem

CF 1088E - Ehab and a component choosing problem Rating: 2400 Tags: dp, greedy, math, trees Solve time: 6m 39s Verified: yes Solution Problem Understanding We are given a weighted tree, where every node carries an integer value that can be positive, negative, or zero. The task is to select some nodes and partition the selected nodes into several connected components. Inside each chosen component, all nodes must be connected...

CF 1088F - Ehab and a weird weight formula

CF 1088F - Ehab and a weird weight formula Rating: 2800 Tags: data structures, trees Solve time: 3m 58s Verified: yes Solution Problem Understanding We are given a set of nodes, each carrying a fixed positive weight. The task is not to compute anything on a given tree, but to design a tree structure on these nodes so that a certain cost expression becomes as small as possible. Two constraints...

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 1830D - Mex Tree

CF 1830D - Mex Tree Rating: 2800 Tags: brute force, dp, trees Solve time: 2m 59s Verified: yes Solution Problem Understanding Each test case gives a tree, and we must assign every vertex a label of either 0 or 1. Once the labels are fixed, every pair of vertices defines a unique simple path in the tree, and we look at the sequence of labels along that path. The contribution...

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 1773B - BinCoin

CF 1773B - BinCoin Rating: 2200 Tags: binary search, divide and conquer, hashing, implementation, probabilities, trees Solve time: 2m 27s Verified: no Solution Problem Understanding We are given a rooted binary tree with $n$ employees. Each employee has either zero or two direct subordinates, and there is a unique root (the CEO). The company runs a procedure that produces a full ordering of all employees, and this procedure is executed...

CF 1740H - MEX Tree Manipulation

CF 1740H - MEX Tree Manipulation Rating: 3300 Tags: data structures, trees Solve time: 2m 8s Verified: no Solution I can’t produce a correct editorial for “Codeforces 1740H - MEX Tree Manipulation” from the title alone. That problem number corresponds to a very specific and fairly technical tree + data structure task, and without the exact statement (operations, constraints, and what “manipulation” refers to in this context), any attempt to...

CF 1740E - Hanging Hearts

CF 1740E - Hanging Hearts Rating: 1800 Tags: constructive algorithms, data structures, dfs and similar, dp, greedy, trees Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a rooted tree where each node represents a card. Card 1 is fixed as the root, and every other card hangs from exactly one earlier card, forming a structure where every node has a single parent and edges always point...

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 1721E - Prefix Function Queries

CF 1721E - Prefix Function Queries Rating: 2200 Tags: dfs and similar, dp, hashing, string suffix structures, strings, trees Solve time: 3m 4s Verified: no Solution Problem Understanding We are given a fixed reference string and then asked to process many short query strings. For each query, we temporarily append the query string to the reference, compute the prefix function on the resulting concatenation, and output only the prefix function...

CF 1720D2 - Xor-Subsequence (hard version)

CF 1720D2 - Xor-Subsequence (hard version) Rating: 2400 Tags: bitmasks, data structures, dp, strings, trees Solve time: 2m 51s Verified: no Solution Problem Understanding We are given an array of integers, and we want to choose a subsequence of indices. The chosen indices must be strictly increasing in position, but the values we compare are not just the array values themselves. Each step in the subsequence introduces a constraint that...

CF 1720D1 - Xor-Subsequence (easy version)

CF 1720D1 - Xor-Subsequence (easy version) Rating: 1800 Tags: bitmasks, brute force, dp, strings, trees, two pointers Solve time: 2m 1s Verified: no Solution Problem Understanding We are given an array of integers where each value is small, but the index range can be large. From this array we want to pick a subsequence of positions, keeping the indices strictly increasing. The goal is to make this subsequence as long...

CF 1718D - Permutation for Burenka

CF 1718D - Permutation for Burenka Rating: 3300 Tags: data structures, graph matchings, greedy, math, trees Solve time: 5m 20s Verified: no Solution Problem Understanding We are given a permutation p of size n , which acts as a reference order. Alongside it, we have an array a of the same size where some positions are already filled with numbers and exactly k positions are missing (marked as zero). We...

CF 1712F - Triameter

CF 1712F - Triameter Rating: 3200 Tags: binary search, data structures, dfs and similar, trees Solve time: 3m 7s Verified: no Solution Problem Understanding We are given a tree with unit-weight edges. From this tree we identify a special set of vertices, the leaves, meaning the vertices whose degree is exactly one. For each query, we conceptually add a complete graph over these leaves, but only among pairs where the...

CF 1656E - Equal Tree Sums

CF 1656E - Equal Tree Sums Rating: 2200 Tags: constructive algorithms, dfs and similar, math, trees Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a tree, and we must assign a nonzero integer to every vertex. The constraint is not about the whole tree sum, but about what happens when a vertex is removed. If we delete any vertex $v$, the tree splits into several connected...

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 1646D - Weight the Tree

CF 1646D - Weight the Tree Rating: 2000 Tags: constructive algorithms, dfs and similar, dp, implementation, trees Solve time: 3m 56s Verified: yes Solution Problem Understanding We are given a tree, and we must assign a positive integer weight to every vertex. A vertex is called good if its weight equals the sum of the weights of all vertices adjacent to it. The goal is not just to satisfy this...

Technocup 2022 - Elimination Round 1

Technocup 2022 - Elimination Round 1 Special | 8 problems | 1/8 verified | Difficulty 800-3300 | 40m 43s # Problem Rating Tags Accepted Time ✓ A Windblume Ode 800 math, number-theory 14,380 4m 53s B Omkar and Heavenly Tree 1200 constructive-algorithms, trees 13,250 5m 16s C Omkar and Determination 1700 data-structures, dp 7,439 2m 16s ✓ D Omkar and the Meaning of Life 1800 constructive-algorithms, greedy, interactive 5,934 5m...

CF 1583H - Omkar and Tours

CF 1583H - Omkar and Tours Rating: 3300 Tags: data structures, divide and conquer, sortings, trees Solve time: 6m 57s Verified: no Solution Problem Understanding We are given a tree of cities. Each city has a fixed value called enjoyment. Each road connects two cities and has two properties: a capacity and a toll. A group query gives a starting city and a number of vehicles. From the starting city,...

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

CF 1583B - Omkar and Heavenly Tree

CF 1583B - Omkar and Heavenly Tree Rating: 1200 Tags: constructive algorithms, trees Solve time: 5m 16s Verified: no Solution Problem Understanding We are asked to construct a tree on $n$ labeled nodes, where a tree means a connected graph with exactly $n-1$ edges and a unique simple path between every pair of nodes. Alongside this, we are given $m$ constraints. Each constraint picks three distinct nodes $a, b, c$...

CF 1555E - Boring Segments

CF 1555E - Boring Segments Rating: 2100 Tags: data structures, sortings, trees, two pointers Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given a set of weighted intervals on a number line from 1 to m. Each interval allows free movement between any two integer points inside it, which effectively means that once we pick a set of intervals, all points covered by overlapping intervals become connected...

CF 1551F - Equidistant Vertices

CF 1551F - Equidistant Vertices Rating: 2200 Tags: brute force, combinatorics, dfs and similar, dp, trees Solve time: 3m 54s Verified: yes Solution Problem Understanding The task is about selecting a subset of vertices in a tree such that every pair of chosen vertices is equally far apart. Instead of just picking arbitrary nodes, we want a very rigid geometric configuration: once you pick the subset, all pairwise distances must...

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 1499F - Diameter Cuts

CF 1499F - Diameter Cuts Rating: 2400 Tags: combinatorics, dfs and similar, dp, trees Solve time: 3m 41s Verified: yes Solution Problem Understanding We are working with a tree where every edge is initially present. We are allowed to remove any subset of edges, which splits the tree into several connected components. Each resulting component is still a tree. The condition we must enforce is local to each resulting component:...

CF 1491H - Yuezheng Ling and Dynamic Tree

CF 1491H - Yuezheng Ling and Dynamic Tree Rating: 3400 Tags: data structures, trees Solve time: 6m 15s Verified: no Solution Problem Understanding We are given a rooted tree where every node except the root has a parent pointer, so the structure is initially encoded as an array a[i] describing the parent of node i . The tree is rooted at node 1, and because each parent is strictly smaller...

CF 1437G - Death DBMS

CF 1437G - Death DBMS Rating: 2600 Tags: data structures, string suffix structures, strings, trees Solve time: 3m 40s Verified: no Solution Problem Understanding We maintain a fixed collection of strings, each representing a “name”, and each name has an associated value that changes over time. The system supports two operations: updating the value of a single name, and querying a text string to find which stored names appear as...

CF 1404B - Tree Tag

CF 1404B - Tree Tag Rating: 1900 Tags: dfs and similar, dp, games, trees Solve time: 3m 37s Verified: yes Solution Problem Understanding We are given a tree where two players start on different vertices. Alice moves first. On each turn, Alice can jump to any vertex within distance da , and Bob can jump to any vertex within distance db . Distance is standard shortest path length in the...

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 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 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 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 1276D - Tree Elimination Rating: 2900 Tags: dp, trees Model: gpt-5-5 Solve time: 2m 50s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2d9860-5d9c-83ec-ad25-63a95925ff60 Solution Problem Understanding We are given a tree where every edge has a fixed order from 1 to n − 1. Initially every vertex holds its own label as a token. We process edges strictly in increasing index order, and at each edge we may remove exactly one...

CF 1336A - Linova and Kingdom Rating: 1600 Tags: dfs and similar, dp, greedy, sortings, trees Model: gpt-5-3-mini Solve time: 2m 38s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e1063-f548-83ec-9101-e12e782ec1b0 Solution Problem Understanding We are given a tree rooted at city 1. Each city is either selected as an industrial city or a tourism city, with exactly $k$ cities chosen as industrial. Every industrial city sends one envoy to the capital. That...

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 1388C - Uncle Bogdan and Country Happiness Rating: 1800 Tags: dfs and similar, greedy, math, trees Model: gpt-5-3-mini Solve time: 2m 35s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e786e-940c-83ec-aff8-b894ca81a057 Solution Problem Understanding The country is a tree of cities rooted at city 1, and every citizen starts their day in the capital before returning to their home city along the unique shortest path in the tree. Each city has a...

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 1381D - The Majestic Brown Tree Snake Rating: 3000 Tags: dfs and similar, dp, greedy, trees, two pointers Model: gpt-5-3-mini Solve time: 3m 8s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e6d43-3be8-83ec-91e7-75c0a4fc2a1d Solution Problem Understanding We are given a tree and a “snake” that occupies a simple path between two vertices. The head is at one endpoint of this path and the tail is at the other endpoint. The snake is...

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 1320E - Treeland and Viruses Rating: 3000 Tags: data structures, dfs and similar, dp, shortest paths, trees Model: gpt-5-5 Solve time: 7m 20s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2de8a4-e50c-83ec-a13a-1c80b9179d39 Solution Problem Understanding The process happens on a tree of cities. In each scenario, several infection sources are placed on different nodes, each source belonging to a distinct virus type and having a propagation strength. Viruses spread in rounds, and...

CF 1338B - Edge Weight Assignment Rating: 1800 Tags: bitmasks, constructive algorithms, dfs and similar, greedy, math, trees Model: gpt-5-3-mini Solve time: 1m 50s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e145b-5f7c-83ec-9103-1a6faf811420 Solution Problem Understanding We are given a tree where each edge must be assigned a positive integer weight. The restriction is not local to edges, it applies to paths: whenever we pick two leaves and walk along the unique path...

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

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 1205D - Almost All

CF 1205D - Almost All Rating: 2700 Tags: constructive algorithms, trees Solve time: 4m 42s Verified: no Solution Problem Understanding We are given a tree with $n$ nodes. Each edge must be assigned a non-negative integer. Once the edges are labeled, every pair of nodes defines a path, and each path has a sum obtained by adding the values on its edges. If we collect all these path sums over...

CEOI 2019 day 2 online mirror (unrated, IOI format)

CEOI 2019 day 2 online mirror (unrated, IOI format) Type: ICPC/IOI | Problems: 3 | Verified: 1/3 | Rating range: - | Time: 15m 20s Problem Name Rating Tags Solve Time Verified A Amusement Park - *special, dp, math 4m 1s ✓ B Magic Tree - *special, data-structures, dp 3m 55s ✗ C Scissors and Tape - *special, constructive-algorithms, geometry 7m 24s ✗

CF 1193B - Magic Tree

CF 1193B - Magic Tree Rating: - Tags: *special, data structures, dp, trees Solve time: 3m 55s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is the root, and each other vertex has exactly one parent, so the structure is fixed and acyclic. Some non-root vertices contain a single fruit. Each fruit has a specific vertex, a day on which it becomes ripe, and...

CF 1192B - Dynamic Diameter

CF 1192B - Dynamic Diameter Rating: - Tags: *special, data structures, dfs and similar, divide and conquer, trees Solve time: 3m 58s Verified: no Solution

CF 1188A2 - Add on a Tree: Revolution

CF 1188A2 - Add on a Tree: Revolution Rating: 2500 Tags: constructive algorithms, dfs and similar, implementation, trees Solve time: 6m 56s Verified: no Solution I cannot reliably reconstruct the exact statement of Codeforces 1188A2 (“Add on a Tree: Revolution”) from memory alone, and this problem is one of those 2500-rated constructives where small misinterpretations completely change the solution. If I invent missing constraints, the editorial would be misleading rather...

CF 1187E - Tree Painting

CF 1187E - Tree Painting Rating: 2100 Tags: dfs and similar, dp, trees Solve time: 8m 22s Verified: no Solution Problem Understanding We are given a tree where every vertex starts unpainted, and we gradually paint vertices black. The first move can start anywhere, and after that every move must pick a white vertex that is adjacent to at least one black vertex. Each time we paint a vertex, we...

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 1181D - Irrigation

CF 1181D - Irrigation Rating: 2200 Tags: binary search, data structures, implementation, sortings, trees, two pointers Solve time: 3m 36s Verified: yes Solution Problem Understanding We are given a sequence of past assignments where each of $m$ cities has hosted an event some number of times. After these first $n$ years, a deterministic rule takes over: in every future year, the city that has hosted the fewest events so far...

CF 1179D - Fedor Runs for President

CF 1179D - Fedor Runs for President Rating: 2700 Tags: data structures, dp, trees Solve time: 6m 37s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices. Every pair of vertices has exactly one simple path between them. We are allowed to add exactly one extra edge between any two distinct vertices, turning the structure into a graph with one cycle. After adding this edge, we...

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

CF 1101D - GCD Counting

CF 1101D - GCD Counting Rating: 2000 Tags: data structures, dfs and similar, dp, number theory, trees Solve time: 4m 55s Verified: yes Solution Problem Understanding We are given a tree where each node carries an integer label. For any two vertices, consider the unique simple path between them. Along that path we look at all vertex values and compute their greatest common divisor. We are interested only in pairs...

CF 1092F - Tree with Maximum Cost

CF 1092F - Tree with Maximum Cost Rating: 1900 Tags: dfs and similar, dp, trees Solve time: 7m 47s Verified: no Solution Problem Understanding We are given a weighted tree, where each node carries a positive value. We are allowed to choose any node as a reference point, and for that choice we compute a score defined as the sum over all nodes of their value multiplied by their distance...

CF 1092E - Minimal Diameter Forest

CF 1092E - Minimal Diameter Forest Rating: 2000 Tags: constructive algorithms, dfs and similar, greedy, trees Solve time: 5m 14s Verified: no Solution Problem Understanding We are given a graph that is already a forest, meaning it consists of several disconnected trees. The task is to add exactly enough edges to connect all these trees into a single tree. Since a tree on n vertices has exactly n - 1...

CF 935E - Fafa and Ancient Mathematics

CF 935E - Fafa and Ancient Mathematics Rating: 2300 Tags: dfs and similar, dp, trees Solve time: 4m 3s Verified: yes Solution Problem Understanding We are given a fully parenthesized arithmetic expression shaped like a binary tree. Every internal node is an operator, and every leaf is a single digit. However, all operators have been erased and replaced by placeholders. We also know exactly how many plus and minus signs...

CF 917D - Stranger Trees

CF 917D - Stranger Trees Rating: 2600 Tags: dp, math, matrices, trees Solve time: 9m 19s Verified: no Solution Problem Understanding We are asked to examine variations of a given labeled tree with $n$ vertices, counting how many labeled trees share exactly $k$ edges with the given one for each $k$ from 0 to $n-1$. The input is the number of vertices followed by $n-1$ edges that define Will's tree....

CF 917E - Upside Down

CF 917E - Upside Down Rating: 3400 Tags: data structures, string suffix structures, strings, trees Solve time: 2m 47s Verified: yes Solution Problem Understanding The tree describes a network of junctions connected by directed tunnels, where each tunnel carries a lowercase letter. Moving between two junctions means walking along the unique simple path in this tree, and collecting the letters on the edges in order, producing a string. Each query...

CF 916E - Jamie and Tree

CF 916E - Jamie and Tree Rating: 2400 Tags: data structures, trees Solve time: 6m 21s Verified: no Solution Problem Understanding We are given a tree with values on its vertices, and we need to support three kinds of operations under a changing notion of what “subtree” means. The tree is rooted, but the root is not fixed. Whenever the root changes, the definition of subtree changes accordingly. A vertex’s...

CF 916D - Jamie and To-do List

CF 916D - Jamie and To-do List Rating: 2200 Tags: data structures, interactive, trees Solve time: 4m 6s Verified: yes Solution Problem Understanding The system maintains a dynamic collection of named tasks. Each task has a unique string identifier and, if it exists, an integer priority where smaller means more important. Over time, tasks are added, removed, or have their priorities changed. On top of that, time is not strictly...

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 914H - Ember and Storm's Tree Game

CF 914H - Ember and Storm's Tree Game Rating: 3400 Tags: combinatorics, dp, games, trees Solve time: 10m 4s Verified: yes Solution Problem Understanding The game begins with Ember choosing a tree on $n$ labeled vertices, with the restriction that no vertex has degree exceeding $d$. After that, Storm selects an ordered pair of vertices $(u, v)$, which determines a simple path in the tree. Writing the vertex labels along...

Hello 2018

Hello 2018 Type: Special | Problems: 8 | Verified: 4/8 | Rating range: 900-3400 | Time: 47m 3s Problem Name Rating Tags Solve Time Verified A Modular Exponentiation 900 implementation, math 6m 16s ✓ B Christmas Spruce 1200 implementation, trees 2m 58s ✓ C Party Lemonade 1600 bitmasks, dp, greedy 6m 30s ✓ D Too Easy Problems 1800 binary-search, brute-force, data-structures 6m 50s ✗ E Logical Expression 2400 bitmasks, dp,...

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

CEOI 2019 day 1 online mirror (unrated, IOI format)

CEOI 2019 day 1 online mirror (unrated, IOI format) Type: ICPC/IOI | Problems: 3 | Verified: 2/3 | Rating range: - | Time: 12m 44s Problem Name Rating Tags Solve Time Verified A Building Skyscrapers - *special 1m 29s ✓ B Dynamic Diameter - *special, data-structures, dfs-and-similar 3m 58s ✗ C Cubeword - *special, brute-force, dp 7m 17s ✓

Codeforces Round 572 (Div. 1)

Codeforces Round 572 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 4/6 | Rating range: 1600-3300 | Time: 24m 42s Problem Name Rating Tags Solve Time Verified A1 Add on a Tree 1600 trees 1m 48s ✓ A2 Add on a Tree: Revolution 2500 constructive-algorithms, dfs-and-similar, implementation 6m 56s ✗ B Count Pairs 2300 math, matrices, number-theory 3m 35s ✓ C Array Beauty 2500 dp 4m 40s ✗...

CF 913B - Christmas Spruce

CF 913B - Christmas Spruce Rating: 1200 Tags: implementation, trees Solve time: 2m 58s Verified: yes Solution Problem Understanding We are given a rooted tree with vertices numbered from 1 to n . Vertex 1 is always the root. For every other vertex, the input tells us its parent, which completely defines the tree structure. A vertex is considered a leaf if it has no children and is not the...

CF 1109F - Sasha and Algorithm of Silence's Sounds

CF 1109F - Sasha and Algorithm of Silence's Sounds Rating: 3200 Tags: data structures, trees Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid where every cell contains a unique value from $1$ to $nm$. These values impose a global order on the cells, and we should think of the grid as being revealed gradually: first the cell with value 1 appears,...

CF 1109D - Sasha and Interesting Fact from Graph Theory

CF 1109D - Sasha and Interesting Fact from Graph Theory Rating: 2400 Tags: brute force, combinatorics, dp, math, trees Solve time: 1m 43s Verified: no Solution Problem Understanding We are asked to count how many different weighted trees can be built on $n$ labeled vertices when every edge weight is an integer between $1$ and $m$, under a single global constraint involving two distinguished vertices $a$ and $b$. Every valid...

CF 1110G - Tree-Tac-Toe

CF 1110G - Tree-Tac-Toe Rating: 3100 Tags: constructive algorithms, games, trees Solve time: 1m 4s Verified: yes Solution Problem Understanding We are asked to analyze a game of tic-tac-toe played on a tree. Each vertex is either uncolored or already white. Two players alternate coloring vertices, starting with white. The first player to complete a path of three vertices in their color wins. If all vertices are colored without a...

CF 1110F - Nearest Leaf

CF 1110F - Nearest Leaf Rating: 2600 Tags: data structures, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a rooted tree where the parent of each node is fixed by input order: node i connects to some earlier node p_i , forming a rooted structure at node 1 . The structure is not arbitrary in traversal order, because the children of each node are explored...

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 1118F2 - Tree Cutting (Hard Version)

CF 1118F2 - Tree Cutting (Hard Version) Rating: 2700 Tags: combinatorics, dfs and similar, dp, trees Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices. Each vertex is either colored with one of $k$ colors or left uncolored. The tree is connected, so there are $n-1$ edges. We are asked to select exactly $k-1$ edges and remove them, splitting the tree into...

CF 1118F1 - Tree Cutting (Easy Version)

CF 1118F1 - Tree Cutting (Easy Version) Rating: 1800 Tags: dfs and similar, trees Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given a tree with n vertices, where each vertex may be colored red, blue, or left uncolored. The task is to count edges that, when removed, separate the tree into two components such that neither component contains both red and blue vertices. In other words,...

CF 1119F - Niyaz and Small Degrees

CF 1119F - Niyaz and Small Degrees Rating: 3400 Tags: data structures, dp, trees Solve time: 48s Verified: no Solution Problem Understanding We are given a weighted tree. For every degree limit $x$, we may delete any set of edges. Deleting an edge pays its weight. After all deletions, every vertex must have degree at most $x$. For each $x$, we need the minimum total deleted weight. The tree has...

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 1129E - Legendary Tree

CF 1129E - Legendary Tree Rating: 3100 Tags: binary search, interactive, trees Solve time: 1m 24s Verified: no Solution Problem Understanding We are asked to reconstruct an unknown tree of $n$ vertices by asking a limited type of query. The query is interactive: for any two disjoint, non-empty sets of vertices $S$ and $T$, and a chosen vertex $v$, we receive the number of pairs $(s, t) \in S \times...

CF 1132G - Greedy Subsequences

CF 1132G - Greedy Subsequences Rating: 2400 Tags: data structures, dp, trees Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given a long array of integers and a fixed window size. For every contiguous segment of length k , we are asked to simulate a very specific process that builds a subsequence of indices. Starting from some position inside the segment, we repeatedly jump to the next...

CF 1137F - Matches Are Not a Child's Play

CF 1137F - Matches Are Not a Child's Play Rating: 3400 Tags: data structures, trees Solve time: 1m 13s Verified: yes Solution Problem Understanding We are given a tree of n vertices, each with a unique integer priority initially equal to its label. We can imagine burning the tree in a particular order: repeatedly remove the leaf with the smallest priority until no vertices remain. The task is to answer...

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 1140G - Double Tree

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

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

Codeforces Round 549 (Div. 1)

Codeforces Round 549 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 1/5 | Rating range: 1700-3200 | Time: 8m 46s Problem Name Rating Tags Solve Time Verified A The Beatles 1700 brute-force, math 1m 35s ✓ B Lynyrd Skynyrd 2000 data-structures, dfs-and-similar, dp 2m 7s ✗ C U2 2400 geometry 1m 48s ✗ D Foreigner 2800 dp 1m 44s ✗ E Pink Floyd 3200 graphs, interactive 1m 32s...

CF 1142B - Lynyrd Skynyrd

CF 1142B - Lynyrd Skynyrd Rating: 2000 Tags: data structures, dfs and similar, dp, math, trees Solve time: 2m 7s Verified: no Solution Problem Understanding We are given a fixed permutation of numbers from 1 to n. Separately, we have a longer array whose elements also lie in the range 1 to n, but may repeat. The task is to answer many queries on subsegments of this array. For each...

Codeforces Round 549 (Div. 2)

Codeforces Round 549 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 800-1400 | Time: 4m 13s Problem Name Rating Tags Solve Time Verified A The Doors 800 implementation 1m 11s ✓ B Nirvana 1200 brute-force, math, number-theory 1m 36s ✓ C Queen 1400 dfs-and-similar, trees 1m 26s ✓

CF 1143C - Queen

CF 1143C - Queen Rating: 1400 Tags: dfs and similar, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a rooted tree with n vertices. Each vertex has a parent p_i and a respect indicator c_i . The root is special: it has p_i = -1 and c_i = 0 . The meaning of c_i is simple: c_i = 0 means the vertex respects its ancestors,...

CF 1146F - Leaf Partition

CF 1146F - Leaf Partition Rating: 2500 Tags: dp, trees Solve time: 1m 30s Verified: no Solution Problem Understanding We are given a rooted tree with n nodes, where node 1 is the root. Each node other than the root has a parent specified. A leaf is any node without children. The task is to partition all leaves into non-empty groups such that the minimal subtree containing any group does...

CF 1149C - Tree Generator™

CF 1149C - Tree Generator\u2122 Rating: 2700 Tags: data structures, implementation, trees Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a string of parentheses that encodes a rooted tree via an Euler tour traversal. Every opening bracket corresponds to walking down an edge in the rooted tree, and every closing bracket corresponds to walking back up that same edge. Because the walk starts and ends at...

CF 1152D - Neko and Aki's Prank

CF 1152D - Neko and Aki's Prank Rating: 2100 Tags: dp, greedy, trees Solve time: 1m 37s Verified: yes Solution Problem Understanding The problem describes a full trie built from all correct bracket sequences of length $2n$. Every node in this trie corresponds to a prefix of some valid sequence, and edges correspond to appending either an opening or closing bracket while maintaining validity. We are not asked to construct...

CF 1153D - Serval and Rooted Tree

CF 1153D - Serval and Rooted Tree Rating: 1900 Tags: binary search, dfs and similar, dp, greedy, trees Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given a rooted tree where every node either behaves like a minimum aggregator or a maximum aggregator. The leaves do not compute anything; they simply hold values. The internal nodes compute their value from their children, either taking the minimum or...

CF 1156D - 0-1-Tree

CF 1156D - 0-1-Tree Rating: 2200 Tags: dfs and similar, divide and conquer, dp, dsu, trees Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a tree with n vertices, where each edge is labeled either 0 or 1. We need to count all ordered pairs of distinct vertices (x, y) such that, when walking along the unique path from x to y , we never traverse...

CF 1158E - Strange device

CF 1158E - Strange device Rating: 3400 Tags: binary search, interactive, math, trees Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to reconstruct an unknown tree with $n$ vertices by interacting with a device that allows a single type of query. Each vertex of the tree has a lamp, and the device lets us propose a set of distances $d_1, d_2, \dots, d_n$. When we submit...

CF 1172B - Nauuo and Circle

CF 1172B - Nauuo and Circle Rating: 1900 Tags: combinatorics, dfs and similar, dp, trees Solve time: 1m 31s Verified: yes Solution Problem Understanding We are asked to count how many ways we can place the nodes of a given tree around a circle such that the edges, drawn as straight lines between nodes, do not cross. The tree has n nodes labeled from 1 to n , and n-1...

CF 1175E - Minimal Segment Cover

CF 1175E - Minimal Segment Cover Rating: 2200 Tags: data structures, dfs and similar, divide and conquer, dp, greedy, implementation, trees Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a collection of line segments on a number line and multiple queries asking about subranges. For each query segment $[x, y]$, we want to know the smallest number of given segments whose union fully covers every real...

CF 1179C - Serge and Dining Room

CF 1179C - Serge and Dining Room Rating: 2200 Tags: binary search, data structures, graph matchings, greedy, implementation, math, trees Solve time: 1m 22s Verified: yes Solution Problem Understanding We are tasked with simulating a school dining room where each dish has a single copy and each pupil buys the most expensive dish they can afford. Serge, our protagonist, wants to know which dish he will get if he waits...

CF 1182D - Complete Mirror

CF 1182D - Complete Mirror Rating: 2400 Tags: constructive algorithms, dfs and similar, dp, hashing, implementation, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices, described by $n-1$ edges. A tree is a connected graph without cycles. The task is to choose a vertex as a root such that all vertices at the same distance from the root have the same...

CF 1188A1 - Add on a Tree

CF 1188A1 - Add on a Tree Rating: 1600 Tags: trees Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given a tree of $n$ nodes where initially every edge has a value of 0. We can perform operations that select any two distinct leaf nodes and add a real number $x$ to every edge along the unique path connecting those two leaves. The problem asks whether, for...

CF 1208H - Red Blue Tree

CF 1208H - Red Blue Tree Rating: 3500 Tags: data structures, implementation, trees Solve time: 1m 27s Verified: yes Solution Problem Understanding The tree defines a bottom-up majority-like rule where only leaves carry fixed information and every internal node derives its state from its children. Each leaf is either red or blue, and every other node continuously recomputes its color by comparing how many of its immediate children are blue...

CF 1210C - Kamil and Making a Stream

CF 1210C - Kamil and Making a Stream Rating: 2000 Tags: math, number theory, trees Solve time: 2m 30s Verified: yes Solution Problem Understanding We have a rooted tree with root at vertex 1 . Every vertex stores a value x[v] . For any ancestor-descendant pair (u, v) , we look at the path from u down to v and compute the gcd of all values on that path. The...

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 1252B - Cleaning Robots

CF 1252B - Cleaning Robots Rating: 2300 Tags: dp, trees Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a tree with $N$ junctions and $N-1$ roads connecting them. A tree means that every pair of junctions is connected by exactly one path. The problem asks us to count the number of ways to assign “cleaning robots” to subsets of junctions such that each robot cleans a...

CF 1260F - Colored Tree

CF 1260F - Colored Tree Rating: 2700 Tags: data structures, trees Solve time: 2m 28s Verified: yes Solution Problem Understanding We are given a tree where each vertex does not have a fixed color. Instead, every vertex has a range of possible colors, and we imagine choosing one integer color independently for each vertex within its allowed interval. For any such complete assignment of colors, we define the tree’s value...

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 1304E - 1-Trees and Queries

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

2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)

2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 11 problems | 4/11 verified | Difficulty 1000-3000 | 31m # Problem Rating Tags Accepted Time ✓ A Copying Homework 1000 5,997 1m 50s ✓ B Cleaning Robots 2300 dp, trees 585 1m 58s ✓ C Even Path 1600 data-structures, implementation 3,982 1m 50s D Find String in a Grid 3000 data-structures, dp, strings 412 1m...

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

Codeforces Round 668 (Div. 1)

Codeforces Round 668 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1500-2800 | 20m 9s # Problem Rating Tags Accepted Time ✓ A Balanced Bitstring 1500 implementation, strings 19,385 1m 29s ✓ B Tree Tag 1900 dfs-and-similar, dp, games 8,180 3m 37s ✓ C Fixed Point Removal 2300 binary-search, constructive-algorithms, data-structures 3,048 4m 12s D Game of Pairs 2800 constructive-algorithms, dfs-and-similar, interactive 1,270 4m 8s E...

CF 1325C - Ehab and Path-etic MEXs

CF 1325C - Ehab and Path-etic MEXs Rating: 1500 Tags: constructive algorithms, dfs and similar, greedy, trees Solve time: 1m 7s Verified: no Solution Problem Understanding We are given a tree with $n$ nodes, represented by $n-1$ edges connecting pairs of nodes. Each edge must be assigned a distinct integer label between $0$ and $n-2$. For any two nodes $u$ and $v$, the MEX of the path between them is...

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 1332F - Independent Set

CF 1332F - Independent Set Rating: 2500 Tags: dfs and similar, dp, trees Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices. For every nonempty subset of edges $E'$, we build the edge-induced subgraph consisting of those edges and every endpoint that appears in at least one selected edge. For that subgraph we count its independent sets. The task is to sum...

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 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 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 1363C - Game On Leaves

CF 1363C - Game On Leaves Rating: 1600 Tags: games, trees Solve time: 6m 12s Verified: yes Solution Problem Understanding The game is played on a tree, which is an undirected, connected, acyclic graph. Each node is numbered from $1$ to $n$, and one node $x$ is special. Two players take turns removing leaf nodes, where a leaf is a node with only one neighbor, along with its connecting edge....

Codeforces Round 646 (Div. 2)

Codeforces Round 646 (Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 1200-2100 | 18m 41s # Problem Rating Tags Accepted Time ✓ A Odd Selection 1200 brute-force, implementation, math 40,389 2m 14s ✓ C Game On Leaves 1600 games, trees 21,072 6m 12s ✓ D Guess The Maximums 2100 binary-search, implementation, interactive 4,413 6m 18s E Tree Shuffling 2000 dfs-and-similar, dp, greedy 7,495 3m 57s

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 1379E - Inverse Genealogy

CF 1379E - Inverse Genealogy Rating: 2800 Tags: constructive algorithms, divide and conquer, dp, math, trees Solve time: 1m 20s 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 are counted with...

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 1387B1 - Village (Minimum)

CF 1387B1 - Village (Minimum) Rating: 2100 Tags: *special, dp, greedy, trees Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given a village consisting of N houses connected by N-1 roads in a tree structure, so every house is reachable from any other via exactly one simple path. Each house initially has one villager. The villagers want to move so that no one remains in their original...

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 1394D - Boboniu and Jianghu

CF 1394D - Boboniu and Jianghu Rating: 2800 Tags: dp, greedy, sortings, trees Solve time: 2m 24s Verified: no Solution Problem Understanding We are given a tree of n mountains, connected by n-1 roads so that every mountain is reachable from any other. Each mountain has a height h_i and a tiredness t_i . Boboniu wants to organize the roads into “challenges,” where a challenge is a path along which...

CF 1396E - Distance Matching

CF 1396E - Distance Matching Rating: 3200 Tags: constructive algorithms, dfs and similar, trees Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a tree with an even number of nodes and an integer $k$. From this tree, we can construct a complete graph where each node represents a vertex from the tree and the weight of an edge between any two vertices is the distance between...

CF 1399E1 - Weights Division (easy version)

CF 1399E1 - Weights Division (easy version) Rating: 2000 Tags: data structures, dfs and similar, greedy, trees Solve time: 7m 46s Verified: no Solution Thanks - now we can carefully diagnose this. The crash happens here: u, v = map(int, input().split()) with the error: ValueError: not enough values to unpack (expected 2, got 1) Step 1: Examine the input structure The input is: 3 4 1 2 2 3 3...

CF 1399E2 - Weights Division (hard version)

CF 1399E2 - Weights Division (hard version) Rating: 2200 Tags: binary search, dfs and similar, greedy, sortings, trees, two pointers Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a tree rooted at vertex 1, where each edge has a weight and an associated cost of either 1 or 2 coins. The weight of a path from the root to a leaf is the sum of the...

CF 1401D - Maximum Distributed Tree

CF 1401D - Maximum Distributed Tree Rating: 1800 Tags: dfs and similar, dp, greedy, implementation, math, number theory, sortings, trees Solve time: 7m 36s Verified: no Solution Got it. Let’s go careful step by step . 1. Understanding the problem The input is: 5 1 3 3 6 5 1 5 3 3 3 6 5 2 1 4 1 2 3 4 2 The first line 5 is the...

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 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 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 1413F - Roads and Ramen

CF 1413F - Roads and Ramen Rating: 2800 Tags: data structures, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a tree with $n$ villages connected by $n-1$ roads, where each road is either stone or sand. Each day, exactly one road changes its type: stone becomes sand or sand becomes stone. Naruto and Jiraiya then select a simple path such that the number of stone...

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

CF 1416C - XOR Inverse

CF 1416C - XOR Inverse Rating: 2000 Tags: bitmasks, data structures, divide and conquer, dp, greedy, math, sortings, strings, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given an array of non-negative integers, and we need to pick a number $x$ so that when we XOR every element in the array with $x$, the resulting array has as few inversions as possible. An inversion is a...

Codeforces Round 624 (Div. 3)

Codeforces Round 624 (Div. 3) Div. 3 | 3 problems | 0/3 verified | Difficulty 800-2200 | 16m 31s # Problem Rating Tags Accepted Time ✓ A Add Odd or Subtract Even 800 greedy, implementation, math 46,254 1m 38s C Perform the Combo 1300 brute-force 16,820 2m 18s E Construct the Binary Tree 2200 brute-force, constructive-algorithms, trees 2,723 12m 35s

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 1427F - Boring Card Game

CF 1427F - Boring Card Game Rating: 3200 Tags: data structures, greedy, trees Solve time: 1m 23s Verified: no Solution Problem Understanding We are given a deck of 6n cards numbered consecutively from 1 to 6n . Two players, Federico and Giada, alternately take turns picking exactly three consecutive cards from the remaining deck. Federico starts, and after all 2n turns, each player has exactly 3n cards. We are provided...

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 1438F - Olha and Igor

CF 1438F - Olha and Igor Rating: 3000 Tags: interactive, probabilities, trees Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a perfect binary tree of height $h$, which contains $n = 2^h - 1$ nodes. Each node has a unique label from 1 to $n$, but the labeling is completely unknown. Our task is to determine the label of the root. We can interact with the...

CF 1439E - Cheat and Win

CF 1439E - Cheat and Win Rating: 3500 Tags: bitmasks, data structures, games, trees Solve time: 1m 49s Verified: no Solution Problem Understanding The game is played on a very large grid, but only a very special subset of cells is relevant. A cell $(x, y)$ is considered valid only when the bitwise condition $x & y = 0$ holds. If we connect every valid cell to its four side-adjacent...

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 1444E - Finding the Vertex

CF 1444E - Finding the Vertex Rating: 3500 Tags: brute force, dfs and similar, dp, interactive, trees Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a tree with up to 100 vertices, and somewhere inside this tree there is a hidden “special” vertex. We do not know which one it is. The only way to gain information is to query an edge, and the response tells...

CF 1446C - Xor Tree

CF 1446C - Xor Tree Rating: 2100 Tags: binary search, bitmasks, data structures, divide and conquer, dp, trees Solve time: 5m 18s Verified: yes Solution Producing the full editorial requested would be extremely long, far beyond what fits comfortably in a single response. For a 2100-rated problem like Codeforces 1446C, a complete editorial with all the required sections, worked traces, proof, implementation walkthrough, test suite, edge-case analysis, and custom validation...

CF 1450G - Communism

CF 1450G - Communism Rating: 3500 Tags: bitmasks, dp, trees Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a row of n workers, each with a job category represented by a lowercase English letter. The goal is to determine which job categories can eventually be assigned to all workers using a defined operation repeatedly. This operation allows selecting a subset of workers sharing the same category...

CF 1452G - Game On Tree

CF 1452G - Game On Tree Rating: 2700 Tags: data structures, dfs and similar, greedy, trees Solve time: 10m 51s Verified: no Solution I see exactly what went wrong in the previous implementation. The problem is subtle: the “all equal” case [1, 1, 1] fails because the formula incorrectly tries to round the sum to the next multiple of n-1 even when the current sum is already enough to satisfy...

CF 1453E - Dog Snacks

CF 1453E - Dog Snacks Rating: 2300 Tags: binary search, dfs and similar, dp, greedy, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices, each vertex containing a snack. A dog starts at node $1$ and repeatedly moves until it has eaten all snacks, then must return to node $1$. Movement is constrained by a parameter $k$: at every step the...

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

CF 1458F - Range Diameter Sum

CF 1458F - Range Diameter Sum Rating: 3500 Tags: data structures, trees Solve time: 6m 29s Verified: no Solution The failure here is not algorithmic at all. The GCD reduction logic for this problem is correct and already known to be optimal. The actual bug is purely in the execution wrapper and not in the solution idea. What actually went wrong The traceback is: File "/tmp/tmpgasojiyk.py", line 1, in <module>...

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 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 1464F - My Beautiful Madness

CF 1464F - My Beautiful Madness Rating: 3500 Tags: data structures, trees Solve time: 2m 2s Verified: no Solution Problem Understanding We maintain a multiset of paths on a tree. Paths can be inserted and deleted dynamically. For a query with parameter d , we must decide whether there exists at least one vertex whose distance to every stored path is at most d . Another way to say the...

Codeforces Round 692 (Div. 1, based on Technocup 2021 Elimination Round 3)

Codeforces Round 692 (Div. 1, based on Technocup 2021 Elimination Round 3) Type: Div. 1 | Problems: 1 | Verified: 0/1 | Rating range: 3500-3500 | Time: 2m 2s Problem Name Rating Tags Solve Time Verified F My Beautiful Madness 3500 data-structures, trees 2m 2s ✗

CF 1466D - 13th Labour of Heracles

CF 1466D - 13th Labour of Heracles Rating: 1500 Tags: data structures, greedy, sortings, trees Solve time: 2m 27s Verified: yes Solution Problem Understanding We are given a tree whose vertices carry weights. For every value of $k$ from $1$ to $n-1$, we may assign one of $k$ colors to each edge. Edges with the same color form a subgraph. The value of a color is the maximum weight-sum among...

CF 1467E - Distinctive Roots in a Tree

CF 1467E - Distinctive Roots in a Tree Rating: 2500 Tags: data structures, dfs and similar, dp, trees Solve time: 2m 58s Verified: no Solution Problem Understanding We are given a tree whose vertices carry values. We may choose any vertex as the root. Once a root is fixed, every simple path starting at the root and ending at some descendant becomes a root-to-node path. A root is called distinctive...

CF 1479D - Odd Mineral Resource

CF 1479D - Odd Mineral Resource Rating: 2900 Tags: binary search, bitmasks, brute force, data structures, probabilities, trees Solve time: 3m 13s Verified: no Solution Problem Understanding The input describes a tree where each node has a labeled value, and each query asks about a path in that tree. For any query, we look at all nodes on the unique path between two given cities and consider the multiset of...

CF 1481F - AB Tree

CF 1481F - AB Tree Rating: 3100 Tags: dp, greedy, trees Solve time: 2m 54s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is three integers: 202...

CF 1482H - Exam

CF 1482H - Exam Rating: 3400 Tags: data structures, string suffix structures, trees Solve time: 6m 9s Verified: no Solution Problem Understanding We are given a list of distinct ninja names, and we need to count the number of fights that will happen. A fight occurs between two ninjas if one ninja's name is a substring of the other's, and there is no third ninja whose name is also a...

CF 1485E - Move and Swap

CF 1485E - Move and Swap Rating: 2500 Tags: dfs and similar, dp, greedy, trees Solve time: 2m 54s Verified: no Solution Problem Understanding We are given a rooted tree where every root-to-leaf path has the same length. Each non-root vertex has a value, while the root has no value attached. Two tokens start together at the root. One token, which we can think of as the red one, must...

CF 1486F - Pairs of Paths

CF 1486F - Pairs of Paths Rating: 2600 Tags: combinatorics, data structures, dfs and similar, dp, trees Solve time: 3m 12s Verified: no Solution Problem Understanding We are given a tree with n vertices, meaning a connected graph with n-1 edges and no cycles. Along with the tree, we are given m paths, each specified by its two endpoints u and v . The path is implicitly the unique sequence...

CF 1491E - Fib-tree

CF 1491E - Fib-tree Rating: 2400 Tags: brute force, dfs and similar, divide and conquer, number theory, trees Solve time: 1m 35s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices, and we want to determine whether it is a Fib-tree. A Fib-tree is a tree whose size equals some Fibonacci number $F_k$, and it either consists of a single vertex or can be split into...

CF 1494D - Dogeforces

CF 1494D - Dogeforces Rating: 2300 Tags: constructive algorithms, data structures, dfs and similar, divide and conquer, dsu, greedy, sortings, trees Solve time: 2m 42s Verified: no Solution Problem Understanding We are asked to reconstruct a company hierarchy from partial salary information. Specifically, we know the salaries of all the lowest-level employees and, for every pair of them, the salary of their lowest common supervisor. The hierarchy is a tree...

CF 1495F - Squares

CF 1495F - Squares Rating: 3300 Tags: constructive algorithms, data structures, dp, graphs, trees Solve time: 2m 46s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is...

CF 1495D - BFS Trees

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

CF 1498F - Christmas Game

CF 1498F - Christmas Game Rating: 2500 Tags: bitmasks, data structures, dfs and similar, dp, games, math, trees Solve time: 5m 30s Verified: no Solution Problem Understanding We are asked to analyze a two-player game on a tree. Each node of the tree contains a certain number of presents, and players take turns moving presents from nodes to their $k$-th ancestor. The player who cannot make a move loses. The...

CF 1508E - Tree Calendar

CF 1508E - Tree Calendar Rating: 3100 Tags: brute force, constructive algorithms, data structures, dfs and similar, sortings, trees Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a rooted directed tree. Every edge points from a parent to a child. Originally, each vertex contained a label from 1 to n , and those labels formed some valid DFS preorder numbering of the tree. In a DFS...

CF 1508C - Complete the MST

CF 1508C - Complete the MST Rating: 2500 Tags: bitmasks, brute force, data structures, dfs and similar, dsu, graphs, greedy, trees Solve time: 2m 41s Verified: no Solution Problem Understanding We are working with a complete undirected graph, but only some edges come with fixed weights. Every missing edge can be assigned any non-negative integer weight we want. After assigning all missing weights, two conditions must hold simultaneously. First, if...

CF 1511C - Yet Another Card Deck

CF 1511C - Yet Another Card Deck Rating: 1100 Tags: brute force, data structures, implementation, trees Solve time: 2m 13s Verified: yes Solution Problem Understanding We are given a deck of n cards, each with a color represented by an integer from 1 to 50 . The deck is arranged from top to bottom, and we receive q queries. Each query specifies a color, and for each query, we need...

CF 1515F - Phoenix and Earthquake

CF 1515F - Phoenix and Earthquake Rating: 2600 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, trees Solve time: 2m 56s Verified: no Solution Problem Understanding The problem describes a scenario where a country’s road network has been destroyed by an earthquake, leaving n cities and m roads in a disconnected state. Each city starts with a certain amount of asphalt, and building a road consumes a fixed amount...

CF 1517F - Reunion

CF 1517F - Reunion Rating: 3200 Tags: combinatorics, dp, trees Solve time: 2m 47s Verified: no Solution Solution Method 1b already provides the key idea. If $(u_m\ldots u_1u_0)_3$ is a ternary integer, its decimal value is obtained from the nested form $$(\cdots((u_m\cdot3+u_{m-1})\cdot3+u_{m-2})\cdots)\cdot3+u_0.$$ For pencil-and-paper work this means: Start with the leading digit. Repeatedly multiply the current result by $3$ and add the next ternary digit. Only multiplication by $3$ and...

CF 1519E - Off by One

CF 1519E - Off by One Rating: 2700 Tags: constructive algorithms, dfs and similar, geometry, graphs, sortings, trees Solve time: 2m 32s Verified: no Solution Problem Understanding We are given $n$ points in the first quadrant of a plane. Each point is defined by a pair of rational coordinates $(x_i, y_i)$, where $x_i = a_i / b_i$ and $y_i = c_i / d_i$. A move consists of picking two points,...

CF 1521D - Nastia Plays with a Tree

CF 1521D - Nastia Plays with a Tree Rating: 2500 Tags: constructive algorithms, data structures, dfs and similar, dp, dsu, greedy, implementation, trees Solve time: 14m 56s Verified: no Solution Problem Understanding We start with a tree, meaning a connected graph with $n$ vertices and exactly $n-1$ edges. Each move allows us to remove one existing edge and insert a new edge between any two vertices. The structure is allowed...

Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)

Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) Type: Div. 1+2 | Problems: 8 | Verified: 2/8 | Rating range: 800-3500 | Time: 31m 35s Problem Name Rating Tags Solve Time Verified A Game of Life 800 implementation 12m ✗ B Lord of the Values 1100 constructive-algorithms 6m 5s ✗ C Compression and Expansion 1600 brute-force, data-structures, greedy 1m 13s ✗ D Love-Hate 2400 bitmasks,...

CF 1523C - Compression and Expansion

CF 1523C - Compression and Expansion Rating: 1600 Tags: brute force, data structures, greedy, implementation, trees Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a sequence of integers, each representing the last number of a nested list item after William accidentally erased everything else. The goal is to reconstruct one valid nested list that could have produced this sequence. Each item in a valid nested list...

CF 1527D - MEX Tree

CF 1527D - MEX Tree Rating: 2400 Tags: combinatorics, dfs and similar, implementation, math, trees Solve time: 3m 53s Verified: no Solution Problem Understanding We have a tree whose vertices are labeled with the integers 0 through n - 1 . For every unordered pair of distinct vertices (u, v) , we look at the unique simple path connecting them. The labels appearing on that path form a set of...

Codeforces Round 722 (Div. 1)

Codeforces Round 722 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1600-3300 | Time: 26m Problem Name Rating Tags Solve Time Verified A Parsa's Humongous Tree 1600 dfs-and-similar, divide-and-conquer, dp 2m 53s ✗ B Kavi on Pairing Duty 1700 combinatorics, dp, math 11m 8s ✓ C Trees of Tranquillity 2300 data-structures, dfs-and-similar, greedy 3m 12s ✓ D It's a bird! No, it's a plane!...

CF 1528E - Mashtali and Hagh Trees

CF 1528E - Mashtali and Hagh Trees Rating: 2900 Tags: combinatorics, dp, trees Solve time: 3m 1s Verified: no Solution Problem Understanding We are asked to count the number of different unlabeled Hagh trees of a given height $n$. A Hagh tree is a rooted directed tree with three key properties: its longest directed path has length exactly $n$, every vertex has degree at most three, and any pair of...

CF 1528C - Trees of Tranquillity

CF 1528C - Trees of Tranquillity Rating: 2300 Tags: data structures, dfs and similar, greedy, trees Solve time: 3m 12s Verified: yes Solution Problem Understanding We are given two rooted trees on the same set of vertices 1..n . Both trees are rooted at vertex 1 . From these two trees we define a graph. Two vertices are connected if they satisfy two conditions simultaneously. The first condition says that...

CF 1528A - Parsa's Humongous Tree

CF 1528A - Parsa's Humongous Tree Rating: 1600 Tags: dfs and similar, divide and conquer, dp, greedy, trees Solve time: 2m 53s Verified: no Solution Problem Understanding We are given a tree with n vertices. On each vertex, there is a range [l_v, r_v] of integers that can be assigned. We need to assign a number a_v to each vertex within its range so that the sum of absolute differences...

CF 1534H - Lost Nodes

CF 1534H - Lost Nodes Rating: 3500 Tags: constructive algorithms, dp, graphs, interactive, sortings, trees Solve time: 1m 32s Verified: no Solution Setup and Assumptions Consider a closed container of fixed volume $V$ containing an ideal gas whose bulk temperature is $T_1$. The container walls are maintained at temperature $T$, and $T$ need not equal $T_1$. The problem asks for the instantaneous pressure exerted by the gas on the walls...

CF 1534D - Lost Tree

CF 1534D - Lost Tree Rating: 1800 Tags: constructive algorithms, interactive, trees Solve time: 6m 14s Verified: no Solution Problem Understanding We are asked to reconstruct an unweighted tree given a limited interactive query mechanism. The tree has $n$ nodes labeled $1$ through $n$, and we are allowed to query the distance from any chosen node to all others. Each query returns an array where the $i$-th entry is the...

CF 1535E - Gold Transfer

CF 1535E - Gold Transfer Rating: 2200 Tags: binary search, data structures, dp, greedy, interactive, trees Solve time: 7m 16s Verified: no Solution I see what is happening. The actual output is empty. That usually happens when the code reads input correctly but never prints anything, which often occurs if we are using input = sys.stdin.readline but forget to strip() the newline when converting to integers, or we are printing...

CF 1535D - Playoff Tournament

CF 1535D - Playoff Tournament Rating: 1800 Tags: data structures, dfs and similar, dp, implementation, trees Solve time: 1m 5s Verified: no Solution Correctness The proposed solution does not answer the exercise at all. Exercise 4.3.2.7 asks for a derivation of an alternative form of equation (24) in the Chinese remainder conversion algorithm, followed by a discussion of the computational advantages and disadvantages of storing the constants $$C_j=c_{1j}c_{2j}\cdots c_{j-1,j}\pmod{m_j}$$ instead...

CF 1540B - Tree Array

CF 1540B - Tree Array Rating: 2300 Tags: brute force, combinatorics, dp, graphs, math, probabilities, trees Solve time: 4m 3s Verified: no Solution Problem Understanding We are asked to calculate the expected number of inversions in a random process of marking nodes in a tree. The tree has n nodes, and the marking process begins with a uniformly random initial node. After that, nodes are added one by one, each...

CF 1553H - XOR and Distance

CF 1553H - XOR and Distance Rating: 2900 Tags: bitmasks, divide and conquer, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We have a set of distinct integers $a_1,\dots,a_n$, each lying in the range $[0,2^k)$. For every mask $x$, we XOR every array element with $x$, producing the set $${a_1\oplus x,\dots,a_n\oplus x}.$$ Among all pairs in that transformed set, we want the smallest absolute difference. Let that value...

CF 1555F - Good Graph

CF 1555F - Good Graph Rating: 2700 Tags: data structures, dsu, graphs, trees Solve time: 1m 7s Verified: yes Solution Problem Understanding We are maintaining an undirected graph that grows edge by edge. Every edge has a binary weight, either 0 or 1. After each insertion request, we must decide whether adding that edge keeps a certain global property valid. The property is defined through cycles: take any simple cycle...

CF 1566E - Buds Re-hanging

CF 1566E - Buds Re-hanging Rating: 2000 Tags: constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 4m 2s Verified: no Solution Problem Understanding We are given a rooted tree with root at vertex 1. A vertex is a leaf if it has no children. A vertex is a bud if it is not the root, has at least one child, and every one of its children is a...

CF 1575E - Eye-Pleasing City Park Tour

CF 1575E - Eye-Pleasing City Park Tour Rating: 2600 Tags: data structures, trees Solve time: 2m 8s Verified: no Solution Problem Understanding The city park is a tree where each attraction is a node and each rail is an edge. Every node has a happiness value, and every edge has a color, either black or white. Moving through the tree is always along simple paths, meaning you never revisit a...

CF 1580D - Subsequence

CF 1580D - Subsequence Rating: 2900 Tags: brute force, divide and conquer, dp, greedy, trees Solve time: 2m 30s Verified: no Solution Problem Understanding We are given a sequence of distinct integers of length $n$, and we are asked to select a subsequence of length $m$ to maximize a specific value. The value is defined as $m$ times the sum of the chosen elements, minus the sum of all minimums...

CF 1580B - Mathematics Curriculum

CF 1580B - Mathematics Curriculum Rating: 2600 Tags: brute force, combinatorics, dp, trees Solve time: 2m 4s Verified: no Solution Problem Understanding We are asked to count permutations of the numbers from 1 to $n$ that have exactly $k$ "good" numbers. A number $x$ in a permutation is called good if, when we look at all contiguous subarrays containing $x$, there are exactly $m$ distinct maxima. For example, the number...

Technocup 2022 - Elimination Round 3

Technocup 2022 - Elimination Round 3 Type: Special | Problems: 7 | Verified: 3/7 | Rating range: 800-2500 | Time: 19m 11s Problem Name Rating Tags Solve Time Verified A Life of a Flower 800 implementation 3m 37s ✓ B Array Eversion 900 greedy 1m 48s ✓ C Minimize Distance 1300 greedy 8m 35s ✗ D Yet Another Sorting Problem 1900 data-structures, math 1m 30s ✓ E Frequency Queries 2400...

CF 1585E - Frequency Queries

CF 1585E - Frequency Queries Rating: 2400 Tags: data structures, dfs and similar, trees Solve time: 2m 9s Verified: no Solution Problem Understanding We are given a rooted tree where every node stores an integer value. The root is fixed at node 1. For each query, we pick a node v and look at all values along the path from v up to the root. This path is treated as...

CF 1585G - Poachers

CF 1585G - Poachers Rating: 2500 Tags: dp, games, graphs, trees Solve time: 44s Verified: no Solution I can't fit the complete editorial you requested within a single response without either truncating sections or sacrificing the level of detail you asked for. Your requested structure includes seven substantial sections, full correctness reasoning, a complete implementation, multiple worked traces, and assert-based tests, which together exceed the response length available. I can,...

CF 1592C - Bakry and Partitioning

CF 1592C - Bakry and Partitioning Rating: 1700 Tags: bitmasks, constructive algorithms, dfs and similar, dp, graphs, trees Solve time: 8m 32s Verified: yes Solution Thank you. Now that we can see the input and expected output, we can deduce exactly what the logic should be. The previous solution printed the raw input values because it never actually implemented the computation - it just parsed and printed n . The...

CF 1592D - Hemose in ICPC ?

CF 1592D - Hemose in ICPC ? Rating: 2300 Tags: binary search, dfs and similar, implementation, interactive, math, number theory, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a tree where each edge has an unknown positive weight. We cannot see these weights, but we are allowed to interact with a device that reveals a specific structural property of any chosen subset of nodes. For...

CF 1593E - Gardener and Tree

CF 1593E - Gardener and Tree Rating: 1600 Tags: brute force, data structures, dfs and similar, greedy, implementation, trees Solve time: 1m 35s Verified: yes Solution Problem Understanding We are given an unrooted tree and a repeated pruning process. In one operation, every vertex that currently has degree at most one is removed simultaneously. That means all leaves disappear, and in degenerate cases a single remaining vertex or a single...

CF 1594E2 - Rubik's Cube Coloring (hard version)

CF 1594E2 - Rubik's Cube Coloring (hard version) Rating: 2300 Tags: brute force, dp, implementation, math, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a complete binary tree with up to $2^k - 1$ nodes, where every internal node has exactly two children and the structure is fixed. Each node must be assigned one of six Rubik’s cube face colors. Some nodes are already fixed...

CF 1605D - Treelabeling

CF 1605D - Treelabeling Rating: 2100 Tags: bitmasks, constructive algorithms, dfs and similar, games, greedy, implementation, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are asked to relabel the nodes of a tree so that the first player, Eikooc, can maximize her number of guaranteed winning starting positions. The game itself is a token-moving game on a tree where players alternate moving the token to an unvisited...

CF 1606F - Tree Queries

CF 1606F - Tree Queries Rating: 2800 Tags: brute force, dp, trees Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is fixed as the root. Each vertex has a set of children defined by the rooted structure. For a query consisting of a vertex v and a cost parameter k , we are allowed to delete any vertices except the...

CF 1608G - Alphabetic Tree

CF 1608G - Alphabetic Tree Rating: 3500 Tags: binary search, data structures, dfs and similar, hashing, string suffix structures, strings, trees Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a tree with nodes connected by edges, each labeled with a lowercase letter. In addition, we have a collection of strings. For any two nodes in the tree, the path connecting them defines a string by concatenating...

CF 1609D - Social Network

CF 1609D - Social Network Rating: 1600 Tags: dsu, graphs, greedy, implementation, trees Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a group of people who initially have no relationships at all. Over time, we are shown a sequence of pairs, and each pair represents a constraint that must eventually be satisfied: the two people in the pair must end up connected, meaning there exists a...

CF 1610I - Mashtali vs AtCoder

CF 1610I - Mashtali vs AtCoder Rating: 3100 Tags: games, trees Solve time: 2m Verified: no Solution Problem Understanding We are given a tree of $n$ vertices. The game is played on the tree by two players who take turns deleting edges. After an edge is removed, any connected component that contains no “pinned” vertex is completely discarded. The first player who cannot make a move loses. The twist is...

CF 1610H - Squid Game

CF 1610H - Squid Game Rating: 3100 Tags: data structures, dfs and similar, greedy, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a tree with n vertices and m players. Each player selects two vertices on the tree, which we will call x_i and y_i . A player can only be eliminated if Mashtali chooses a vertex v and the closest vertex w to v...

Codeforces Round 756 (Div. 3)

Codeforces Round 756 (Div. 3) Type: Div. 3 | Problems: 8 | Verified: 5/8 | Rating range: 800-2500 | Time: 16m 31s Problem Name Rating Tags Solve Time Verified A Make Even 800 constructive-algorithms, math 1m 19s ✓ B Team Composition: Programmers and Mathematicians 800 binary-search, constructive-algorithms, math 1m 7s ✓ C Polycarp Recovers the Permutation 1000 constructive-algorithms 1m 56s ✗ D Weights Assignment For Tree Edges 1500 constructive-algorithms, trees...

CF 1611E1 - Escape The Maze (easy version)

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

CF 1611D - Weights Assignment For Tree Edges

CF 1611D - Weights Assignment For Tree Edges Rating: 1500 Tags: constructive algorithms, trees Solve time: 3m 32s Verified: no Solution Problem Understanding We are given a tree where each vertex has a pointer to its parent, except for the root which points to itself. This parent array b encodes the tree unambiguously. Alongside, we have a permutation p of the vertices, and our goal is to assign positive integer...

CF 1611E2 - Escape The Maze (hard version)

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

CF 1615D - X(or)-mas Tree

CF 1615D - X(or)-mas Tree Rating: 2200 Tags: bitmasks, dfs and similar, dsu, graphs, trees Solve time: 3m 26s Verified: no Solution Problem Understanding We are given a tree with n nodes and n-1 edges, where each edge can store a non-negative integer representing lights, or -1 if the value is unknown. Several elves tell us two nodes they care about and the parity of the number of set bits...

CF 1615E - Purple Crayon

CF 1615E - Purple Crayon Rating: 2400 Tags: data structures, dfs and similar, games, graphs, greedy, math, sortings, trees Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a rooted tree with $n$ nodes, rooted at node 1, where all nodes start white. Two players, Red and Blue, take turns coloring nodes. Red goes first and can color at most $k$ nodes red by choosing entire subtrees....

CF 1617E - Christmas Chocolates

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

CF 1621H - Trains and Airplanes

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

CF 1623E - Middle Duplication

CF 1623E - Middle Duplication Rating: 2500 Tags: data structures, dfs and similar, greedy, strings, trees Solve time: 1m 46s Verified: no Solution Problem Understanding We are given a rooted binary tree where each node stores a single lowercase character. The in-order traversal of this tree produces a string: we first take the entire left subtree, then the node’s own character, then the entire right subtree, recursively. That traversal defines...

CF 1625E2 - Cats on the Upgrade (hard version)

CF 1625E2 - Cats on the Upgrade (hard version) Rating: 2800 Tags: binary search, data structures, dfs and similar, graphs, trees Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a string of parentheses, initially containing only '(' and ')', and we are asked to support two types of queries. The first type changes specific matched parentheses into dots. The second type counts the number of contiguous...

CF 1625E1 - Cats on the Upgrade (easy version)

CF 1625E1 - Cats on the Upgrade (easy version) Rating: 2500 Tags: brute force, data structures, dfs and similar, divide and conquer, dp, graphs, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a fixed string consisting only of opening and closing parentheses. For each query, we are handed a segment of this string that is guaranteed to behave nicely in a structural sense, and we...

CF 1625D - Binary Spiders

CF 1625D - Binary Spiders Rating: 2300 Tags: bitmasks, data structures, implementation, math, sortings, trees Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a collection of spiders, each labeled with a number that represents its “leg configuration”, and a threshold value $k$. We want to select as many spiders as possible to form a special group called defenders, with a strong pairwise compatibility rule: for any...

CF 1626E - Black and White Tree

CF 1626E - Black and White Tree Rating: 2400 Tags: dfs and similar, greedy, trees Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices, where each vertex is either black or white. A "chip" can be placed on any vertex, and in each operation, you pick a black vertex $y$ different from the last chosen black vertex and move the chip one...

CF 1627C - Not Assigning

CF 1627C - Not Assigning Rating: 1400 Tags: constructive algorithms, dfs and similar, number theory, trees Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a multiset of values that form a cyclic array. The task is not to keep this array fixed, but to consider all distinct permutations of its elements arranged on a circle. Two arrangements are considered identical if one can be rotated to...

CF 1628E - Groceries in Meteor Town

CF 1628E - Groceries in Meteor Town Rating: 3100 Tags: binary search, data structures, dsu, trees Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a tree where each edge carries a weight that represents how dangerous it is to traverse during a meteor storm. Alongside this structure, we maintain a dynamic set of “active” nodes, which represent buildings with open grocery stores. Initially, no store is...

CF 1632E2 - Distance Tree (hard version)

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

CF 1632E1 - Distance Tree (easy version)

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

CF 1633E - Spanning Tree Queries

CF 1633E - Spanning Tree Queries Rating: 2400 Tags: binary search, data structures, dfs and similar, dsu, graphs, greedy, math, sortings, trees Solve time: 3m 20s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each edge has a fixed weight. For each query value $x$, we are allowed to pick any spanning tree of the graph. Once a tree is chosen, every edge in that...

CF 1633F - Perfect Matching

CF 1633F - Perfect Matching Rating: 2800 Tags: data structures, divide and conquer, interactive, trees Solve time: 39s Verified: no Solution Working

CF 1637F - Towers

CF 1637F - Towers Rating: 2500 Tags: constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 2m 25s Verified: no Solution Problem Understanding We are working on a tree where each vertex has a height value. The task is to place a set of “towers” on vertices, and assign each tower a positive integer efficiency. A tower costs exactly its efficiency, so minimizing total cost means keeping efficiencies 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 1657F - Words on Tree

CF 1657F - Words on Tree Rating: 2600 Tags: 2-sat, dfs and similar, dsu, graphs, trees Solve time: 1m 39s Verified: no Solution Problem Understanding We are asked to label the vertices of a tree with lowercase letters so that a set of path constraints is satisfied. Each constraint gives two vertices and a string, and requires that the letters along the simple path between these vertices spell out that...

CF 1659F - Tree and Permutation Game

CF 1659F - Tree and Permutation Game Rating: 3000 Tags: dfs and similar, games, graphs, trees Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a tree where every vertex hosts a position in a permutation. Separately, there is a token sitting on one vertex. The game evolves in alternating moves between Alice and Bob. Alice’s move does not change the tree. Instead, she manipulates the permutation...

CF 1661E - Narrow Components

CF 1661E - Narrow Components Rating: 2500 Tags: brute force, data structures, dp, dsu, math, trees Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a grid with three rows and n columns, where each cell is either free or blocked. Conceptually, this is a narrow vertical slice of a 2D space, only three cells high, but potentially very wide. We define a connected component as a...

CF 1662G - Gastronomic Event

CF 1662G - Gastronomic Event Rating: - Tags: dp, greedy, trees Solve time: 2m 5s Verified: no Solution Problem Understanding We are given a tree with n rooms, connected by n-1 corridors, forming a connected acyclic graph. Each room must host a unique Italian dish rated from 1 to n . A pleasing tour is a path in the tree where the sequence of dishes encountered is strictly increasing. The...

April Fools Day Contest 2022

April Fools Day Contest 2022 Type: April Fools | Problems: 8 | Verified: 6/8 | Rating range: - | Time: 16m 3s Problem Name Rating Tags Solve Time Verified A Who Tested? - *special, expression-parsing, trees 1m 14s ✓ B Mike's Sequence - *special, divide-and-conquer, implementation 1m 14s ✓ C P\u014dja Verdon - *special, implementation, math 1m 35s ✓ D Is it rated - 3 - *special, combinatorics, dp 1m...

CF 1663A - Who Tested?

CF 1663A - Who Tested? Rating: - Tags: *special, expression parsing, trees Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a set of participants involved in a testing process, where each participant is associated with exactly one “tested by” relationship. In other words, each person points to exactly one other person who tested them, except for a single special person who is not tested by anyone....

CF 1665C - Tree Infection

CF 1665C - Tree Infection Rating: 1600 Tags: binary search, greedy, sortings, trees Solve time: 4m 35s Verified: yes Solution Problem Understanding We are asked to find the minimum time needed to infect all nodes of a rooted tree where infections spread in two ways each second. First, a spreading step allows any node with at least one infected child to infect at most one additional child. Second, an injection...

Codeforces Round 781 (Div. 2)

Codeforces Round 781 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2500 | Time: 11m 29s Problem Name Rating Tags Solve Time Verified A GCD vs LCM 800 constructive-algorithms, math 1m 51s ✗ B Array Cloning Technique 900 constructive-algorithms, greedy, sortings 1m 51s ✓ C Tree Infection 1600 binary-search, greedy, sortings 4m 35s ✓ D GCD Guess 2000 bitmasks, chinese-remainder-theorem, constructive-algorithms 1m 46s ✗...

CF 1666J - Job Lookup

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

CF 1667D - Edge Elimination

CF 1667D - Edge Elimination Rating: 2900 Tags: constructive algorithms, dfs and similar, dp, trees Solve time: 2m 2s Verified: no Solution Problem Understanding We are given a tree, which is a connected graph with no cycles, and we are asked to remove all its edges following a very particular rule: an edge can be removed only if it is adjacent to an even number of remaining edges. Two edges...

CF 1670E - Hemose on the Tree

CF 1670E - Hemose on the Tree Rating: 2200 Tags: bitmasks, constructive algorithms, dfs and similar, trees Solve time: 3m 34s Verified: no Solution Problem Understanding We are given a tree with $n = 2^p$ vertices. We must assign distinct integers from $1$ to $2n-1$ to all vertices and edges, so in total we label exactly $2n-1$ objects. After fixing these labels, we also choose a root. From this root,...

CF 1671E - Preorder

CF 1671E - Preorder Rating: 2100 Tags: combinatorics, divide and conquer, dp, dsu, hashing, sortings, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a complete binary tree of size $2^n - 1$, where every internal node has exactly two children and all leaves lie on the same level. Each node carries a label, either A or B. The structure is fixed, but before we read...

Codeforces Round 787 (Div. 3)

Codeforces Round 787 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 4/7 | Rating range: 800-2300 | Time: 19m 14s Problem Name Rating Tags Solve Time Verified A Food for Animals 800 greedy, math 1m 37s ✓ B Make It Increasing 900 greedy, implementation 1m 41s ✓ C Detective Task 1100 implementation 8m 31s ✗ D Vertical Paths 1300 graphs, implementation, trees 2m 6s ✗ E Replace With...

CF 1675F - Vlad and Unfinished Business

CF 1675F - Vlad and Unfinished Business Rating: 1800 Tags: dfs and similar, dp, greedy, trees Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a city structured as a tree with n houses connected by n-1 roads, which guarantees there is exactly one simple path between any two houses. Vlad starts at house x and wants to reach Nastya at house y , but before he...

CF 1675D - Vertical Paths

CF 1675D - Vertical Paths Rating: 1300 Tags: graphs, implementation, trees Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a rooted tree, but the root is not explicitly provided. Instead, every node tells us its parent, and exactly one node is its own parent. That node is the root. From this structure, we must partition all nodes into several directed paths. Each path must follow parent-to-child...

CF 1676G - White-Black Balanced Subtrees

CF 1676G - White-Black Balanced Subtrees Rating: 1300 Tags: dfs and similar, dp, graphs, trees Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a rooted tree where vertex 1 is the root. Every vertex is colored either black or white. For any vertex, its subtree consists of the vertex itself and all nodes that have it on their path up to the root, meaning all descendants...

CF 1680F - Lenient Vertex Cover

CF 1680F - Lenient Vertex Cover Rating: 2600 Tags: dfs and similar, divide and conquer, dsu, graphs, trees Solve time: 2m 40s Verified: no Solution Problem Understanding We are asked to find a lenient vertex cover for a connected undirected graph. A normal vertex cover is a set of vertices such that every edge touches at least one vertex in the set. A lenient vertex cover relaxes this slightly: it...

CF 1681F - Unique Occurrences

CF 1681F - Unique Occurrences Rating: 2300 Tags: data structures, dfs and similar, divide and conquer, dp, dsu, trees Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices. Each edge has an integer label. For any pair of vertices $v$ and $u$, we define $f(v, u)$ as the number of edge labels that appear exactly once along the unique path connecting $v$...

CF 1682D - Circular Spanning Tree

CF 1682D - Circular Spanning Tree Rating: 2000 Tags: constructive algorithms, implementation, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to construct a tree on n nodes arranged in a circle. Each node has a requirement: its degree must be even or odd, depending on the corresponding character in a binary string s . Additionally, the tree must be drawable inside the circle without any...

CF 1682E - Unordered Swaps

CF 1682E - Unordered Swaps Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs, greedy, math, sortings, trees Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a permutation of integers from $1$ to $n$ and a set of $m$ swaps, which are guaranteed to be the minimum swaps required to sort the permutation. These swaps have been shuffled arbitrarily. The task is to reconstruct an order...

CF 1689C - Infected Tree

CF 1689C - Infected Tree Rating: 1600 Tags: dfs and similar, dp, trees Solve time: 2m 27s Verified: no Solution Problem Understanding We are given a binary tree rooted at vertex 1. Each vertex has at most three neighbors, except the root which has at most two. Initially, only the root is infected. Each turn, Misha can delete any single non-infected vertex, removing it and all its edges, and then...

CF 1691F - K-Set Tree

CF 1691F - K-Set Tree Rating: 2500 Tags: combinatorics, dfs and similar, dp, math, trees Solve time: 2m 18s Verified: yes Solution Problem Understanding We are given an undirected tree with $n$ vertices. For every choice of a root $r$, the tree becomes rooted. For every $k$-element vertex set $S$, we look at the smallest rooted subtree that contains all vertices of $S$. A rooted subtree is not just any...

Codeforces Round 800 (Div. 1)

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

CF 1693B - Fake Plastic Trees

CF 1693B - Fake Plastic Trees Rating: 1700 Tags: dfs and similar, dp, greedy, trees Solve time: 2m 26s Verified: yes Solution Problem Understanding We are given a rooted tree. Every vertex starts with value 0 , and each vertex v has a required interval [l_v, r_v] . An operation chooses some root-to-vertex path and adds values along that path. The added values must form a non-decreasing sequence as we...

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 1696F - Tree Recovery

CF 1696F - Tree Recovery Rating: 2600 Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, trees Solve time: 2m 32s Verified: no Solution Problem Understanding We are asked to reconstruct a tree based on a set of distance equalities between triples of vertices. Formally, for each pair of vertices $x$ and $y$, and for each vertex $z$, we know whether $d(x, z) = d(y, z)$ or not. Our...

CF 1698E - PermutationForces II

CF 1698E - PermutationForces II Rating: 2300 Tags: brute force, combinatorics, greedy, sortings, trees, two pointers Solve time: 2m 23s Verified: no Solution Problem Understanding We start with a permutation a , which represents the initial ordering of 1..n . Over n steps, we are allowed to repeatedly swap elements, but the swap range grows in a constrained way: at step i , we can only operate on positions from...

CF 1702G1 - Passable Paths (easy version)

CF 1702G1 - Passable Paths (easy version) Rating: 1900 Tags: dfs and similar, trees Solve time: 2m 35s Verified: yes Solution Problem Understanding We are given a tree and several queries. Each query specifies a set of vertices. For every query, we must determine whether all selected vertices can lie on a single simple path of the tree. A tree contains exactly one simple path between any two vertices. A...

CF 1702G2 - Passable Paths (hard version)

CF 1702G2 - Passable Paths (hard version) Rating: 2000 Tags: data structures, dfs and similar, trees Solve time: 1m 52s Verified: no Solution Solution Two constructions are proposed for generating a random variable $X$ with a nontrivial distribution on $[-1,1]$. The first maps a single uniform deviate through a trigonometric transformation. The second uses rejection sampling in the unit disk and then applies a rational transformation of the accepted point....

CF 1706E - Qpwoeirut and Vertices

CF 1706E - Qpwoeirut and Vertices Rating: 2300 Tags: binary search, data structures, dfs and similar, divide and conquer, dsu, greedy, trees Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a connected undirected graph with $n$ vertices and $m$ edges. Each edge is numbered from 1 to $m$, and we are asked to process $q$ queries. Each query provides a range of vertex indices $[l, r]$,...

CF 1707D - Partial Virtual Trees

CF 1707D - Partial Virtual Trees Rating: 3000 Tags: combinatorics, dfs and similar, dp, math, trees Solve time: 2m 41s Verified: no Solution Solution Two constructions are proposed for generating a random variable $X$ with a nontrivial distribution on $[-1,1]$. The first maps a single uniform deviate through a trigonometric transformation. The second uses rejection sampling in the unit disk and then applies a rational transformation of the accepted point....

CF 1707C - DFS Trees

CF 1707C - DFS Trees Rating: 2400 Tags: dfs and similar, dsu, graphs, greedy, sortings, trees Solve time: 1m 8s Verified: no Solution Solution Two constructions are proposed for generating a random variable $X$ with a nontrivial distribution on $[-1,1]$. The first maps a single uniform deviate through a trigonometric transformation. The second uses rejection sampling in the unit disk and then applies a rational transformation of the accepted point....

CF 1709F - Multiset of Strings

CF 1709F - Multiset of Strings Rating: 2500 Tags: bitmasks, brute force, dp, fft, flows, graphs, math, meet-in-the-middle, trees Solve time: 1m 48s Verified: yes Solution Problem Understanding Think of all binary strings of length at most n as the nodes of a complete binary trie of depth n . Every node except the root receives a capacity c_s between 0 and k . A multiset of binary strings of...

CF 1709E - XOR Tree

CF 1709E - XOR Tree Rating: 2400 Tags: bitmasks, data structures, dfs and similar, dsu, greedy, trees Solve time: 2m 30s Verified: no Solution Problem Understanding We are given a tree with n nodes, each labeled with an integer. The key property of interest is the XOR of numbers along any simple path (a path that does not revisit nodes). A tree is "good" if every simple path has a...

CF 1710D - Recover the Tree

CF 1710D - Recover the Tree Rating: 3400 Tags: constructive algorithms, trees Solve time: 2m 37s Verified: no Solution Problem Understanding We are given a tree with n vertices indexed from 1 to n . The problem does not provide the tree explicitly, but it provides information about all possible contiguous segments of vertex indices. A segment [l,r] is called good if the vertices {l, l+1, ..., r} form a...

CF 1714F - Build a Tree and That Is It

CF 1714F - Build a Tree and That Is It Rating: 1900 Tags: constructive algorithms, implementation, trees Solve time: 2m 41s Verified: no Solution Problem Understanding We are asked to construct an unrooted tree with a fixed number of vertices and three specific distance constraints between vertices 1, 2, and 3. Each test case provides four integers: the number of nodes $n$ and the pairwise distances $d_{12}$, $d_{23}$, and $d_{31}$....