tag

#trees

160 pages tagged

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

CF 2217G - Down the Pivot

CF 2217G - Down the Pivot Rating: 2600 Tags: combinatorics, dp, math, trees Solve time: 1m 50s Verified: no Solution Problem Understanding We are working with rooted binary trees where each node carries a binary label, either zero or one. The tree structure is arbitrary as long as every node has at most two children. On top of that structure, we assign labels independently. The only allowed operation is very...

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

CF 2218F - The 67th Tree Problem

CF 2218F - The 67th Tree Problem Rating: 1500 Tags: constructive algorithms, implementation, trees Solve time: 3m 38s Verified: no Solution Problem Understanding We are asked to build a rooted tree with exactly $n = x + y$ vertices. The root is fixed to be vertex $1$. For every vertex, consider the size of its rooted subtree. A vertex is counted in the "even" group if its subtree contains an...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.25 Choosing the Right Tree Algorithm

8.25 Choosing the Right Tree Algorithm This chapter has introduced a wide range of tree algorithms and data structures. At first glance, many of them appear similar. Several support queries. Several support updates. Several flatten trees into arrays. Several decompose trees into smaller structures. The challenge in practice is rarely implementing a tree algorithm. The challenge is choosing the correct one. This final recipe provides a decision framework for selecting...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.8 Binary Lifting

8.8 Binary Lifting Many tree algorithms repeatedly ask the same question: What is the ancestor of this node k levels above? At first glance, the problem seems trivial. Follow the parent pointer k times and stop. Unfortunately, this approach becomes expensive when trees are large or when millions of queries must be processed. Binary Lifting transforms repeated ancestor traversal into a logarithmic-time operation. It is one of the most important...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.20 Tree Isomorphism

8.20 Tree Isomorphism Two trees may look different at first glance yet represent exactly the same structure. Consider: Tree A A / \\n B C / D and: Tree B X / \\n Y Z \\n W The labels differ. The node identifiers differ. The drawing differs. Yet structurally these trees are identical. This raises an important question: How can we determine whether two trees have the same shape? This...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.4 Recursion on Trees

8.4 Recursion on Trees Most tree algorithms are recursive, not because recursion is elegant, but because trees are recursive objects. Every subtree is itself a tree. If you know how to solve a problem for a subtree, you often know how to solve it for the entire structure. This observation is the foundation of nearly every advanced tree algorithm. Tree dynamic programming, Lowest Common Ancestor preprocessing, Heavy-Light Decomposition, Centroid Decomposition,...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.1 Tree Representation

8.1 Tree Representation Trees are usually introduced with drawings: circles connected by lines, one circle at the top, several below it, then more below those. That picture is useful, but an algorithm cannot run on a picture. The first practical question is how to represent the tree in memory. A good representation makes the common operations cheap. If the algorithm needs to visit every child of a node, children should...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.3 Breadth-First Search Traversal

8.3 Breadth-First Search Traversal Breadth-first search (BFS) visits a tree level by level. It starts at the root, visits all nodes at depth 1 , then all nodes at depth 2 , and continues outward until every reachable node has been processed. DFS follows one branch as far as possible before returning. BFS expands evenly across the tree. That difference makes BFS the natural choice when distance from the root...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.9 Euler Tour Technique

8.9 Euler Tour Technique Many tree problems become dramatically easier when you stop thinking of the tree as a tree. At first, this sounds strange. Trees are hierarchical structures, so why abandon that structure? The answer is that many efficient algorithms operate on arrays, not trees. Segment Trees, Fenwick Trees, Sparse Tables, Range Minimum Queries, and many caching techniques all expect linear data. The Euler Tour Technique bridges these two...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.13 Segment Trees

8.13 Segment Trees Many tree algorithms eventually become range-query problems. After applying an Euler Tour, a subtree becomes a contiguous interval. Once that transformation is complete, the original tree often disappears from the solution. What remains is a sequence of values and a collection of interval operations. Examples include: Sum of values in a subtree Maximum value in a subtree Minimum value in a subtree Frequency counts Dynamic updates Range...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.24 Merkle Trees

8.24 Merkle Trees Suppose two computers each store a copy of a large dataset. The datasets contain millions of records. A natural question arises: How can we verify that both copies are identical without comparing every record? A naive solution transfers the entire dataset and performs a complete comparison. For large systems, this is prohibitively expensive. Merkle Trees solve this problem by storing cryptographic hashes in a tree structure. Instead...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.18 Centroid Decomposition

8.18 Centroid Decomposition Many tree algorithms process information from a fixed root. Heavy-Light Decomposition focuses on paths. Euler Tours focus on subtrees. Rerooting Dynamic Programming focuses on changing roots efficiently. Centroid Decomposition takes a different approach entirely. Instead of choosing a root and keeping it forever, it repeatedly divides the tree into smaller balanced pieces. This divide-and-conquer strategy transforms many difficult global tree problems into manageable local problems. Centroid Decomposition...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.23 Expression Trees

8.23 Expression Trees Expression trees represent computations as tree structures. Leaves usually hold operands, and internal nodes hold operators. This representation appears in compilers, interpreters, symbolic algebra systems, query engines, spreadsheet formulas, calculators, and optimization passes. For example, the expression: (3 + 4) * 5 can be represented as: * / \\n + 5 / \\n 3 4 The tree captures the structure of the computation. Parentheses, precedence, and evaluation...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.22 Succinct Trees

8.22 Succinct Trees Most tree representations focus on speed. Examples include: Pointer-based trees Adjacency lists Segment Trees Tries Link-Cut Trees These structures prioritize fast updates and queries, often at the cost of memory. For small trees, this tradeoff is acceptable. For massive datasets, memory becomes a primary concern. Consider: 1 billion nodes Even storing a few pointers per node can require tens of gigabytes of memory. In many applications, the...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.14 Fenwick Trees

8.14 Fenwick Trees Not every range-query problem requires the full power of a Segment Tree. Many practical workloads involve only two operations: Update a single value. Query a prefix sum. Examples include: Running totals Frequency counts Event counters Rankings Histogram maintenance Subtree sums after Euler Tour flattening For these cases, a Fenwick Tree provides an elegant alternative. It uses less memory, requires less code, and often performs better in practice...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.11 Rerooting Dynamic Programming

8.11 Rerooting Dynamic Programming Many tree algorithms compute information relative to a fixed root. Subtree size, subtree sum, height, and many dynamic programming states naturally flow upward from descendants toward the root. However, some problems ask a different question: What would the answer be if every node were the root? At first, this appears expensive. If a tree contains n nodes, recomputing a complete DFS from every possible root leads...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.10 Subtree Queries

8.10 Subtree Queries Many tree problems ask questions about an entire subtree rather than an individual node. Examples include: What is the sum of all values in this subtree? How many descendants does this node have? What is the maximum value below this node? How many active users belong to this organizational branch? What is the total storage used by a directory and its descendants? A naive solution traverses the...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.19 Link-Cut Trees

8.19 Link-Cut Trees All previous tree algorithms in this chapter assume that the tree structure is fixed. Nodes remain connected in the same way throughout execution. Examples include: Euler Tour Heavy-Light Decomposition Centroid Decomposition Lowest Common Ancestor Binary Lifting These techniques are extremely powerful, but they struggle when the tree itself changes. Suppose we need operations such as: Cut edge (u,v) Link node u to node w Query path(u,v) The...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.21 Tree Serialization

8.21 Tree Serialization A tree in memory is not directly portable. It may contain pointers, slices, maps, parent links, or language-specific objects. To store it in a file, send it over a network, cache it, compare it, or reconstruct it later, you need a serialized representation. Serialization converts a tree into a linear form. Deserialization converts that linear form back into a tree. This recipe shows common tree serialization patterns...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.16 Persistent Trees

8.16 Persistent Trees Most data structures answer questions about the present. A value changes, the old value disappears, and the structure reflects only the latest state. Many real systems, however, need access to the past. Examples include: Version control systems Database snapshots Financial ledgers Historical analytics Time-travel debugging Undo functionality Immutable functional data structures Suppose a value changes: Version 1: [1 2 3 4] Version 2: [1 2 10 4]...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.12 Tries

8.12 Tries Many search problems involve prefixes. Examples include: Autocomplete systems Spell checkers Search suggestions Dictionary lookups URL routing IP routing tables DNA sequence matching A straightforward solution stores strings in a hash table and performs exact lookups. This works well when the entire key is known. However, prefix-based operations are different. Suppose a dictionary contains: apple application apply apt banana Given the prefix: app we want: apple application apply...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.2 Depth-First Search Traversal

8.2 Depth-First Search Traversal Depth-first search (DFS) is the fundamental traversal technique for trees. Nearly every tree algorithm builds upon it. Subtree sizes, heights, diameters, lowest common ancestors, dynamic programming on trees, Heavy-Light Decomposition, Centroid Decomposition, and many other techniques begin with some variation of DFS. The central idea is simple: visit a node, recursively process its children, then return to the parent. Despite its simplicity, DFS exposes the hierarchical...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.15 Lazy Propagation

8.15 Lazy Propagation Segment Trees provide efficient range queries and point updates. However, some workloads involve large range updates. Examples include: Increase all salaries in a department. Add a bonus to every employee in a division. Update all values in a subtree. Mark an entire directory as archived. Apply a discount to every product in a category. A standard Segment Tree handles point updates efficiently, but updating an entire range...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.5 Tree Height

8.5 Tree Height Tree height measures how far a tree extends downward from a node. It is one of the first values you learn to compute on a tree, but it also appears inside more advanced algorithms. Balanced-tree checks, diameter computation, expression-tree evaluation cost, recursion-depth analysis, and many tree dynamic programming problems all depend on height. The main idea is recursive: the height of a node depends on the maximum...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.17 Heavy-Light Decomposition

8.17 Heavy-Light Decomposition Many tree problems ask questions about paths. Examples include: Sum of values along a path Maximum edge weight between two nodes Minimum value between two vertices Path updates Network latency queries Organizational hierarchy analysis A subtree query is relatively easy after an Euler Tour because every subtree becomes a contiguous interval. Path queries are more difficult. Consider: 0 ├── 1 │ ├── 3 │ └── 4 └──...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.6 Tree Diameter

8.6 Tree Diameter The diameter of a tree is the length of the longest path between any two nodes. Unlike height, which measures distance from a chosen root, diameter is a global property of the entire tree. It answers a different question: What is the greatest distance that can exist between any pair of nodes? Diameter appears in network design, distributed systems, phylogenetic trees, transportation networks, game maps, and many...

Programming › Algorithm Cookbook › Chapter 8. Trees ›

8.7 Lowest Common Ancestor

8.7 Lowest Common Ancestor The Lowest Common Ancestor (LCA) of two nodes is the deepest node that is an ancestor of both. It is one of the most important tree queries because many other problems reduce to it. Distance queries, path queries, hierarchy analysis, version-control ancestry, organizational charts, file systems, and network routing all rely on the same underlying operation. Consider the following tree: 0 / \\n 1 2 /...

Programming › Algorithm Cookbook ›

Chapter 8. Trees

Chapter 8. Trees

Programming › Algorithm Cookbook ›

Chapter 7. Binary Search and Ordered Data

Chapter 7. Binary Search and Ordered Data Binary search is one of the most deceptively simple ideas in computer science. Given a sorted array and a target, you repeatedly cut the search space in half by comparing the target with the middle element. Each comparison eliminates half the remaining candidates, so the algorithm terminates in $O(\log n)$ steps. The simplicity is real — the code is short — but the...

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

CF 2227H - Fallen Leaves

CF 2227H - Fallen Leaves Rating: - Tags: dfs and similar, dp, trees Solve time: 2m 56s Verified: no Solution Problem Understanding We are given a tree and a fixed set of vertices consisting of all leaves in the original tree. These leaves are determined once from the initial structure and do not change during the process. We then repeatedly pick two distinct unused leaves, add the length of the...

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

CF 2222G - Statistics on Tree

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

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

CF 2226G - Stop Spot

CF 2226G - Stop Spot Rating: - Tags: implementation, strings, trees Solve time: 2m 32s Verified: no Solution Problem Understanding An array $a$ is fixed, and we append to it a permutation $p$ of ${1,2,\dots,m}$ to form a longer array $b_p$. For each such permutation, we count how many subarrays of $b_p$ with even length are palindromes. This produces a value $i$, and over all permutations we define $f(i)$ as...

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

CF 482E - ELCA

CF 482E - ELCA Rating: 3200 Tags: data structures, trees Solve time: 5m 19s Verified: no Solution

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

CF 1975D - Paint the Tree

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

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

CF 1976E - Splittable Permutations

CF 1976E - Splittable Permutations Rating: 2500 Tags: combinatorics, data structures, dfs and similar, greedy, math, trees Solve time: 5m 16s Verified: no Solution

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

CF 1943C - Tree Compass

CF 1943C - Tree Compass Rating: 2300 Tags: constructive algorithms, dfs and similar, greedy, trees Solve time: 1m 16s Verified: no Solution Problem Understanding We are given a tree and an operation that does not act on a single node, but on a layer of nodes: if we pick a center vertex $v$ and a distance $d$, we recolor every vertex whose shortest-path distance from $v$ is exactly $d$. Each...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951H - Thanos Snap

CF 1951H - Thanos Snap Rating: 3200 Tags: binary search, dp, games, greedy, trees Solve time: 1m 17s Verified: no Solution Problem Understanding We are given an array whose length is a power of two, and it initially contains all integers from 1 to $2^k$ exactly once. So the array is just a permutation, but its initial order matters. A game is played on this array. A parameter $t$ is...

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

CF 1976F - Remove Bridges

CF 1976F - Remove Bridges Rating: 2800 Tags: data structures, dfs and similar, dp, greedy, sortings, trees Solve time: 5m 17s Verified: no Solution

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

CF 490F - Treeland Tour

CF 490F - Treeland Tour Rating: 2200 Tags: data structures, dfs and similar, dp, trees Solve time: 10m 49s Verified: no Solution Problem Understanding We are given a tree with n cities, each with a known population. The tree is described by n-1 bidirectional roads connecting the cities. The "Road Accident" band wants to plan a tour along a path in this tree, visiting cities in sequence without repeating, and...

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

CF 487E - Tourists

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

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

CF 1942H - Farmer John's Favorite Intern

CF 1942H - Farmer John's Favorite Intern Rating: 3500 Tags: data structures, dp, flows, trees Solve time: 1m 20s Verified: no Solution Problem Understanding We are asked to maintain a rooted tree where each node starts with zero peaches. Two kinds of operations can happen. In a growth operation at node $x$, we can increase the number of peaches on the parent of $x$ or any node in the subtree...

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

CF 482D - Random Function and Tree

CF 482D - Random Function and Tree Rating: 2700 Tags: combinatorics, dp, trees Solve time: 5m 18s Verified: no Solution

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

CF 1950F - 0, 1, 2, Tree!

CF 1950F - 0, 1, 2, Tree! Rating: 1700 Tags: bitmasks, brute force, greedy, implementation, trees Solve time: 1m Verified: no Solution Problem Understanding We are asked to construct a rooted tree with a specific number of vertices having 0, 1, or 2 children. The input gives three numbers: a vertices with 2 children, b vertices with 1 child, and c vertices that are leaves. The task is to determine...

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

CF 1975E - Chain Queries

CF 1975E - Chain Queries Rating: 2100 Tags: binary search, data structures, dfs and similar, implementation, trees Solve time: 5m 17s Verified: no Solution

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

CF 1949C - Annual Ants' Gathering

CF 1949C - Annual Ants' Gathering Rating: 1900 Tags: dfs and similar, dp, greedy, trees Solve time: 4m 48s Verified: yes Solution Problem Understanding Each vertex of the tree initially contains exactly one ant. A move chooses an edge $(u,v)$ and orders all ants currently gathered at $u$ to move to $v$. The ants obey only when the destination already contains at least as many ants as the source. If...

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

CF 1967C - Fenwick Tree

CF 1967C - Fenwick Tree Rating: 2300 Tags: bitmasks, brute force, combinatorics, data structures, dp, math, trees Solve time: 1m 2s Verified: no Solution Problem Understanding We are asked to reverse a Fenwick Tree construction. A Fenwick Tree is normally defined for an array a of length n such that each element s_k stores the sum of a contiguous subarray of a whose length is the lowest set bit of...

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

CF 486D - Valid Sets

CF 486D - Valid Sets Rating: 2100 Tags: dfs and similar, dp, math, trees Solve time: 5m 18s Verified: no Solution

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

CF 494D - Birthday

CF 494D - Birthday Rating: 2700 Tags: data structures, dfs and similar, dp, trees Solve time: 1m 4s Verified: no Solution Problem Understanding We are given a weighted tree with n vertices rooted at vertex 1 . Each edge has a positive weight. For any vertex v , we define a set S(v) containing all descendants of v (including itself) such that the distance from the root to a vertex...

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

CF 1946C - Tree Cutting

CF 1946C - Tree Cutting Rating: 1600 Tags: binary search, dp, greedy, implementation, trees Solve time: 2m 50s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices, which is a connected graph without cycles. The task is to remove exactly $k$ edges from this tree and determine the largest integer $x$ such that each resulting connected component has at least $x$ vertices. In simpler terms, we...

Practice › Codeforces Solutions ›

Codeforces Round 282 (Div. 1)

Codeforces Round 282 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 1/4 | Rating range: 2000-3200 | Time: 24m 13s Problem Name Rating Tags Solve Time Verified B Obsessive String 2000 dp, strings 10m 58s ✗ C Helping People 2600 dp, probabilities 42s ✓ D Birthday 2700 data-structures, dfs-and-similar, dp 1m 4s ✗ E Sharti 3200 data-structures, games 11m 29s ✗

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

CF 1948G - MST with Matching

CF 1948G - MST with Matching Rating: 3100 Tags: bitmasks, brute force, dsu, graph matchings, trees Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a connected undirected weighted graph with at most 20 vertices. We must choose a spanning tree. The cost of that tree has two parts. The first part is standard, the sum of the chosen edge weights. The second part depends on the...

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

CF 1949F - Dating

CF 1949F - Dating Rating: 2200 Tags: greedy, sortings, trees Solve time: 1m 57s Verified: no Solution Problem Understanding Each user can be viewed as a set of activities. We need to find two users whose sets satisfy three conditions simultaneously: They share at least one activity. The first user has at least one activity that the second user does not have. The second user has at least one activity...

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

CF 1949J - Amanda the Amoeba

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

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

CF 455B - A Lot of Games

CF 455B - A Lot of Games Rating: 1900 Tags: dfs and similar, dp, games, implementation, strings, trees Solve time: 1m 49s Verified: yes Solution Problem Understanding The game can be viewed as moving through a trie built from the given strings. We start at the root, which represents the empty string. On each turn a player chooses one outgoing edge, corresponding to appending a character. The current string must...

Practice › Codeforces Solutions ›

Codeforces Round 260 (Div. 1)

Codeforces Round 260 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2900 | Time: 7m 50s Problem Name Rating Tags Solve Time Verified A Boredom 1500 dp 1m 31s ✓ B A Lot of Games 1900 dfs-and-similar, dp, games 1m 49s ✓ C Civilization 2100 dfs-and-similar, dp, dsu 2m 1s ✓ D Serega and Fun 2700 data-structures 1m 27s ✓ E Function 2900 data-structures...

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

CF 461B - Appleman and Tree

CF 461B - Appleman and Tree Rating: 2000 Tags: dfs and similar, dp, trees Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a tree with n vertices, where some vertices are black and others are white. The tree is rooted implicitly by the way the edges are described: each node i for i > 0 has a parent p[i-1] . We want to choose a subset...

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

CF 466E - Information Graph

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

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472D - Design Tutorial: Inverse the Problem

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

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452B - 4-point polyline

CF 452B - 4-point polyline Rating: 1800 Tags: brute force, constructive algorithms, geometry, trees Solve time: 2m 2s Verified: yes Solution Problem Understanding We have all lattice points inside and on the boundary of an axis-aligned rectangle whose opposite corners are (0, 0) and (n, m) . The task is to choose four distinct lattice points and connect them in the chosen order. The resulting polyline contains three segments, from...

Practice › Codeforces Solutions ›

Codeforces Round 263 (Div. 1)

Codeforces Round 263 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1200-3000 | Time: 8m 20s Problem Name Rating Tags Solve Time Verified A Appleman and Toastman 1200 greedy, sortings 2m 14s ✓ B Appleman and Tree 2000 dfs-and-similar, dp, trees 1m 26s ✗ C Appleman and a Sheet of Paper 2200 data-structures, implementation 1m 22s ✗ D Appleman and Complicated Task 2800 dsu,...

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

CF 463E - Caisa and Tree

CF 463E - Caisa and Tree Rating: 2100 Tags: brute force, dfs and similar, math, number theory, trees Solve time: 47s Verified: yes Solution Problem Understanding We are given a rooted tree with n nodes, each node assigned a positive integer value. Node 1 is the root. Queries ask either to find the deepest ancestor of a node v whose value shares a non-trivial greatest common divisor with v ,...

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

CF 455C - Civilization

CF 455C - Civilization Rating: 2100 Tags: dfs and similar, dp, dsu, ternary search, trees Solve time: 2m 1s Verified: yes Solution Problem Understanding The graph consists of cities connected by roads. The condition that between any two connected cities there is exactly one simple path means every connected component is a tree. Since the graph may be disconnected, the whole graph is a forest. Two types of operations must...

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

CF 474E - Pillars

CF 474E - Pillars Rating: 2000 Tags: binary search, data structures, dp, sortings, trees Solve time: 2m 1s Verified: yes Solution Problem Understanding We have a sequence of pillars arranged from left to right. Pillar i has height h[i] . A valid jump can only go forward, from a smaller index to a larger index, and the height difference between the two pillars must be at least d . The...

Practice › Codeforces Solutions ›

MemSQL Start[c]UP 2.0 - Round 1

MemSQL Start[c]UP 2.0 - Round 1 Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 1000-2700 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Eevee 1000 brute-force, implementation, strings 1m 6s ✓ B 4-point polyline 1800 brute-force, constructive-algorithms, geometry 2m 2s ✓ C Magic Trick 2100 combinatorics, math, probabilities 1m 44s ✓ E Three strings 2400 data-structures, dsu, string-suffix-structures 2m 7s ✓ F Permutation...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 2 ›

CF 457F - An easy problem about trees

CF 457F - An easy problem about trees Rating: 3200 Tags: dp, games, greedy, trees Solve time: 4m 23s Verified: no Solution I’m sorry, but I can’t reliably produce a correct full editorial and solution for this 3200-rated problem from the information currently available to me. While I can restate the problem and discuss some observations, I do not have enough confidence in the exact game-theoretic DP needed for Codeforces...

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

CF 196C - Paint Tree

CF 196C - Paint Tree Rating: 2200 Tags: constructive algorithms, divide and conquer, geometry, sortings, trees Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to embed a tree onto a set of points on a plane in such a way that tree edges correspond to straight line segments connecting the points. Each vertex of the tree must be mapped to a distinct point, and for any...

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

CF 317C - Balance

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

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

CF 321C - Ciel the Commander

CF 321C - Ciel the Commander Rating: 2100 Tags: constructive algorithms, dfs and similar, divide and conquer, greedy, trees Solve time: 3m 39s Verified: yes Solution Problem Understanding We are given a tree with n cities connected by n-1 roads. Each city must be assigned an officer with a rank from 'A' (highest) to 'Z' (lowest). The constraint is that if two cities share the same officer rank, the path...

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

CF 274B - Zero Tree

CF 274B - Zero Tree Rating: 1800 Tags: dfs and similar, dp, greedy, trees Solve time: 3m 28s Verified: yes Solution Problem Understanding This problem asks whether a matrix returns to its original form after repeatedly applying cyclic row shifts. The matrix has m rows and n columns. Every operation affects all rows simultaneously, but the direction depends on the row index. Rows with even indices, such as 0 ,...

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

CF 429C - Guess the Tree

CF 429C - Guess the Tree Rating: 2300 Tags: bitmasks, constructive algorithms, dp, greedy, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding The problem asks us to reconstruct a rooted tree given constraints on the sizes of the subtrees for each node. You are given an array c of length n , where c[i] represents the total number of nodes in the subtree rooted at node i ....

Practice › Codeforces Solutions ›

Codeforces Round 170 (Div. 1)

Codeforces Round 170 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1400-2800 | Time: 6m 6s Problem Name Rating Tags Solve Time Verified A Learning Languages 1400 dfs-and-similar, dsu 1m 44s ✓ D Google Code Jam 2800 dp, probabilities 2m 17s ✗ E Binary Tree on Plane 2400 flows, trees 2m 5s ✗

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

CF 191C - Fools and Roads

CF 191C - Fools and Roads Rating: 1900 Tags: data structures, dfs and similar, trees Solve time: 1m 55s Verified: yes Solution Problem Understanding The input describes a tree of cities. Since there is exactly one simple path between every pair of cities, the road network forms a connected acyclic graph. Then we are given several pairs of cities. Each pair represents one trip: a fool travels from city a...

Practice › Codeforces Solutions › VK Cup 2012 Round 2 ›

CF 163E - e-Government

CF 163E - e-Government Rating: 2800 Tags: data structures, dfs and similar, dp, strings, trees Solve time: 2m 16s Verified: yes Solution Problem Understanding We have a fixed set of surnames. Each surname can be either active or inactive. Initially every surname is active. The system must process three kinds of operations. A query +i activates the i-th surname. A query -i deactivates the i-th surname. A query ?text asks...

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

CF 294E - Shaass the Great

CF 294E - Shaass the Great Rating: 2300 Tags: dp, trees Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a tree with $n$ cities connected by $n-1$ roads. Each road has a positive length. The tree structure guarantees a unique path between every pair of cities. Shaass wants to remove one existing road and build another road of exactly the same length connecting any two cities,...

Practice › Codeforces Solutions ›

Codeforces Round 121 (Div. 1)

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

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

CF 208E - Blood Cousins

CF 208E - Blood Cousins Rating: 2100 Tags: binary search, data structures, dfs and similar, trees Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a rooted forest representing family relationships, where each node corresponds to a person, and each edge points from a child to their parent. A person may have no parent, in which case they are a root of one of the trees in...

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

CF 150E - Freezing with Style

CF 150E - Freezing with Style Rating: 3000 Tags: binary search, data structures, divide and conquer, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We are given a tree with n junctions and n - 1 roads. Every road has an integer beauty value. We must choose two junctions so that the path between them contains between l and r edges inclusive. Among all such paths, we want...

Practice › Codeforces Solutions ›

Codeforces Round 190 (Div. 1)

Codeforces Round 190 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 2100-2600 | Time: 5m 17s Problem Name Rating Tags Solve Time Verified C Ciel the Commander 2100 constructive-algorithms, dfs-and-similar, divide-and-conquer 3m 39s ✓ E Ciel and Gondolas 2600 data-structures, divide-and-conquer, dp 1m 38s ✓

Practice › Codeforces Solutions › April Fools Day Contest 2013 ›

CF 290C - WTF?

CF 290C - WTF? Rating: 1700 Tags: *special, graph matchings, implementation, trees Solve time: 1m 31s Verified: yes Solution Problem Understanding The statement is written as a LOLCODE program. The actual task is to understand what this program computes. The input is a sequence of digits between 0 and 9 , one per line. The program repeatedly reads numbers until it encounters 0 . During the process it maintains four...

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

CF 176E - Archaeology

CF 176E - Archaeology Rating: 3100 Tags: data structures, dfs and similar, trees Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a weighted tree. Every node represents a village, and every edge represents a road with a length. Villages can appear and disappear over time through online queries. At any moment, only a subset of villages currently exists. Among all roads in the original tree, people...

Practice › Codeforces Solutions ›

Codeforces Round 177 (Div. 1)

Codeforces Round 177 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 1/2 | Rating range: 1700-2400 | Time: 3m 45s Problem Name Rating Tags Solve Time Verified C Polo the Penguin and XOR operation 1700 implementation, math 1m 39s ✗ D Polo the Penguin and Trees 2400 combinatorics, dfs-and-similar, trees 2m 6s ✓

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

CF 348E - Pilgrims

CF 348E - Pilgrims Rating: 2800 Tags: dfs and similar, dp, trees Solve time: 1m 32s Verified: no Solution Problem Understanding We are

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

CF 237D - T-decomposition

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

Practice › Codeforces Solutions ›

Codeforces Round 245 (Div. 1)

Codeforces Round 245 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1300-3000 | Time: 6m 47s Problem Name Rating Tags Solve Time Verified A Xor-tree 1300 dfs-and-similar, trees 1m 38s ✓ B Working out 1600 dp 57s ✓ C Guess the Tree 2300 bitmasks, constructive-algorithms, dp 1m 26s ✓ D Tricky Function 2200 data-structures, divide-and-conquer, geometry 1m 9s ✓ E Points and Segments 3000...

Practice › Codeforces Solutions › Croc Champ 2013 - Round 2 ›

CF 293E - Close Vertices

CF 293E - Close Vertices Rating: 2700 Tags: data structures, divide and conquer, trees Solve time: 4m 5s Verified: yes Solution Problem Understanding We are given a weighted tree with n vertices. Every edge contributes two different quantities to a path. The first quantity is the path length, meaning the number of edges on the path. The second quantity is the path weight, meaning the sum of edge weights on...

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

CF 152E - Garden

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

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

CF 258E - Little Elephant and Tree

CF 258E - Little Elephant and Tree Rating: 2400 Tags: data structures, dfs and similar, trees Solve time: 2m 57s Verified: no Solution Problem Understanding We are given a rooted tree with n nodes, numbered from 1 to n , with node 1 as the root. Each node has an initially empty list of numbers. There are m operations, where each operation consists of picking two nodes a_i and b_i...

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

CF 406D - Hill Climbing

CF 406D - Hill Climbing Rating: 2200 Tags: dfs and similar, geometry, trees Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a sequence of hills placed along a line. Each hill has a fixed horizontal position and a height, and we imagine it as a vertical segment rising from the ground. From the top of a hill, you can “see” another hill if the straight segment...

Practice › Codeforces Solutions ›

RCC 2014 Warmup (Div. 1)

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

Practice › Codeforces Solutions ›

April Fools Day Contest 2013

April Fools Day Contest 2013 Type: April Fools | Problems: 4 | Verified: 3/4 | Rating range: 1400-2800 | Time: 6m 44s Problem Name Rating Tags Solve Time Verified C WTF? 1700 *special, graph-matchings, implementation 1m 31s ✓ D Orange 1400 *special, implementation 2m 11s ✗ E HQ 2500 *special, constructive-algorithms 1m 43s ✓ F Greedy Petya 2800 *special, dfs-and-similar, graphs 1m 19s ✓

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

CF 403E - Two Rooted Trees

CF 403E - Two Rooted Trees Rating: 2900 Tags: data structures, implementation, trees Solve time: 1m 6s Verified: no Solution

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

CF 414D - Mashmokh and Water Tanks

CF 414D - Mashmokh and Water Tanks Rating: 2300 Tags: binary search, data structures, greedy, trees, two pointers Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a rooted tree where each vertex represents a water tank. Initially all tanks are empty, but we are allowed to place up to $k$ liters of water, each liter placed into a distinct non-root node. After that, the process runs...

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

CF 251E - Tree and Table

CF 251E - Tree and Table Rating: 3000 Tags: dfs and similar, dp, implementation, trees Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a tree with $2n$ nodes, and the goal is to place each node into a 2-row by $n$-column table so that each edge of the tree connects two cells sharing a side. Each node occupies exactly one cell, and each cell contains exactly...

Practice › Codeforces Solutions ›

Codeforces Round 148 (Div. 1)

Codeforces Round 148 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1300-2900 | Time: 16m 8s Problem Name Rating Tags Solve Time Verified A Not Wool Sequences 1300 constructive-algorithms, math 5m 18s ✓ B Boring Partition 1800 constructive-algorithms 3m 56s ✓ C World Eater Brothers 2100 dfs-and-similar, dp, greedy 2m 5s ✓ D Tape Programming 2900 data-structures, implementation 1m 30s ✓ E Meeting Her...

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

CF 260D - Black and White Tree

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

Practice › Codeforces Solutions ›

Codeforces Round 188 (Div. 1)

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

Practice › Codeforces Solutions ›

Codeforces Round 199 (Div. 2)

Codeforces Round 199 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1200-2400 | Time: 16m 31s Problem Name Rating Tags Solve Time Verified A Xenia and Divisors 1200 greedy, implementation 6m 2s ✗ C Cupboard and Balloons 1900 geometry 5m 17s ✓ E Xenia and Tree 2400 data-structures, divide-and-conquer, trees 5m 12s ✓

Practice › Codeforces Solutions ›

Codeforces Round 122 (Div. 1)

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

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

CF 212E - IT Restaurants

CF 212E - IT Restaurants Rating: 1500 Tags: dfs and similar, dp, trees Solve time: 2m 58s Verified: no Solution Problem Understanding We are asked to place two types of restaurants on a tree-shaped city map in such a way that no two adjacent junctions host different types, each junction hosts at most one restaurant, and each network has at least one restaurant. The goal is to maximize the total...

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

CF 238C - World Eater Brothers

CF 238C - World Eater Brothers Rating: 2100 Tags: dfs and similar, dp, greedy, trees Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given a world of n countries connected by n-1 directed roads. Ignoring the direction of these roads, the countries form a tree. Each brother wants to establish rule in some country and can control every country reachable via directed roads. The problem asks for...

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

CF 342E - Xenia and Tree

CF 342E - Xenia and Tree Rating: 2400 Tags: data structures, divide and conquer, trees Solve time: 5m 12s Verified: yes Solution Problem Understanding We are given a tree of n nodes, rooted conceptually at node 1, which starts painted red. All other nodes are blue. We have to handle two types of queries: first, paint a blue node red; second, for a given node, report the distance to the...

Practice › Codeforces Solutions ›

Codeforces Round 238 (Div. 1)

Codeforces Round 238 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 0/2 | Rating range: 2200-2800 | Time: 6m 36s Problem Name Rating Tags Solve Time Verified D Hill Climbing 2200 dfs-and-similar, geometry, trees 2m 13s ✗ E Hamming Triples 2800 implementation, math, two-pointers 4m 23s ✗

Practice › Codeforces Solutions ›

Codeforces Round 247 (Div. 2)

Codeforces Round 247 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 8m 37s Problem Name Rating Tags Solve Time Verified A Black Square 800 implementation 1m 10s ✓ B Shower Line 1200 brute-force, implementation 1m 52s ✓ C k-Tree 1600 dp, implementation, trees 1m 31s ✓ D Random Task 2100 binary-search, bitmasks, combinatorics 2m 1s ✓ E Chemistry Experiment 2200 binary-search,...

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

CF 277E - Binary Tree on Plane

CF 277E - Binary Tree on Plane Rating: 2400 Tags: flows, trees Solve time: 2m 5s Verified: no Solution Problem Understanding We are given a set of points in the plane, each with distinct coordinates, and we need to construct a rooted binary tree such that each node has at most two children. The arcs, which connect parents to children, must be directed strictly downward in terms of y-coordinates. The...

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

CF 226E - Noble Knight's Path

CF 226E - Noble Knight's Path Rating: 2900 Tags: data structures, trees Solve time: 1m 11s Verified: yes Solution Problem Understanding In this problem, we are asked to simulate a sequence of events in a feudal hierarchy represented as a tree. Each feudal owns a castle, and except for the king, each feudal reports to exactly one superior. The castles are connected by roads along the feudal hierarchy: there is...

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

CF 193A - Cutting Figure

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

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161D - Distance in Tree

CF 161D - Distance in Tree Rating: 1800 Tags: dfs and similar, dp, trees Solve time: 3m 13s Verified: yes Solution Problem Understanding We are given a tree with n vertices, meaning a connected graph with no cycles, and a number k . The task is to count how many pairs of distinct vertices are separated by exactly k edges. Every edge in the tree connects two vertices directly, and...

Practice › Codeforces Solutions ›

Codeforces Round 168 (Div. 1)

Codeforces Round 168 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 1500-1800 | Time: 4m 42s Problem Name Rating Tags Solve Time Verified A k-Multiple Free Set 1500 binary-search, greedy, sortings 1m 14s ✓ B Zero Tree 1800 dfs-and-similar, dp, greedy 3m 28s ✓

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

CF 165D - Beard Graph

CF 165D - Beard Graph Rating: 2100 Tags: data structures, dsu, trees Solve time: 2m 13s Verified: yes Solution Problem Understanding The graph in this problem is almost a simple path. Every vertex has degree at most 2, except possibly one special vertex that may have larger degree. A tree with this shape looks like several chains glued together at one center. Initially every edge is black. Queries can repaint...

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

CF 418D - Big Problems for Organizers

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

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

CF 429A - Xor-tree

CF 429A - Xor-tree Rating: 1300 Tags: dfs and similar, trees Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a rooted tree with n nodes, each node labeled with a 0 or 1. We are also given a target configuration of 0s and 1s for each node. The only operation allowed is to "pick" a node, which flips its value and every second-level descendant down the...

Practice › Codeforces Solutions ›

Codeforces Round 236 (Div. 1)

Codeforces Round 236 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 0/2 | Rating range: 2300-2900 | Time: 1m 57s Problem Name Rating Tags Solve Time Verified D Beautiful Pairs of Numbers 2300 combinatorics, dp 51s ✗ E Two Rooted Trees 2900 data-structures, implementation, trees 1m 6s ✗

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

CF 444E - DZY Loves Planting

CF 444E - DZY Loves Planting Rating: 2700 Tags: binary search, dsu, trees Solve time: 1m 30s Verified: no Solution Problem Understanding We are given a weighted tree where every edge has a cost, and we can think of it as a structure connecting n labeled nodes. Between any two nodes x and y, there is exactly one simple path, and we define a function g(x, y) as the largest...

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

CF 191E - Thwarting Demonstrations

CF 191E - Thwarting Demonstrations Rating: 2200 Tags: binary search, data structures, trees Solve time: 1m 46s Verified: yes Solution Problem Understanding We have an array of soldier reliabilities. Every contiguous subarray represents one possible police group. The general always chooses the strongest unused group first, meaning all subarray sums are sorted in descending order and picked one by one. We need the reliability of the group chosen on day...

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

CF 217E - Alien DNA

CF 217E - Alien DNA Rating: 2800 Tags: data structures, dsu, trees Solve time: 6m 25s Verified: yes Solution Problem Understanding The problem presents a sequence of DNA letters and a series of mutations that sequentially expand the sequence. Each mutation activates a contiguous subsequence, duplicates it, and mangles the copy in a specific way: all letters at even positions come first, followed by all letters at odd positions, then...

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

CF 288D - Polo the Penguin and Trees

CF 288D - Polo the Penguin and Trees Rating: 2400 Tags: combinatorics, dfs and similar, trees Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a tree with n nodes labeled from 1 to n . A tree is a connected acyclic graph, so every pair of nodes has a unique simple path between them. The task is to count the number of pairs of paths (a,...

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

CF 431C - k-Tree

CF 431C - k-Tree Rating: 1600 Tags: dp, implementation, trees Solve time: 1m 31s Verified: yes Solution Problem Understanding We are working with a rooted infinite tree where every node always has exactly $k$ outgoing edges to children. Each of those $k$ edges has a fixed weight: the first is 1, the second is 2, and so on up to $k$. From the root, we consider downward paths that move...

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

CF 85C - Petya and Tree

CF 85C - Petya and Tree Rating: 2200 Tags: binary search, dfs and similar, probabilities, sortings, trees Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a valid binary search tree where every internal node has exactly two children. Each node stores a unique key. We are also given several query keys that are guaranteed not to appear in the tree. A normal BST search starts at...

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

CF 75D - Big Maximum Sum

CF 75D - Big Maximum Sum Rating: 2000 Tags: data structures, dp, greedy, implementation, math, trees Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given a set of small arrays and a sequence of indexes indicating how to concatenate them into one larger array. Once the large array is built in this way, the goal is to find the maximum sum of a contiguous subarray. This is...

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

CF 61D - Eternal Victory

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

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

CF 101D - Castle

CF 101D - Castle Rating: 2300 Tags: dp, greedy, probabilities, sortings, trees Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a weighted tree rooted at hall 1, where Gerald starts. The treasure is hidden uniformly at random in one of the other halls. Gerald only discovers the treasure when he first enters the correct hall. The restriction that changes the problem completely is that every corridor...

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

CF 86C - Genetic engineering

CF 86C - Genetic engineering Rating: 2500 Tags: dp, string suffix structures, trees Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given several short DNA fragments over the alphabet {A, C, G, T} . A longer DNA string is considered valid if every position of the string belongs to at least one occurrence of one of the given fragments. The fragments may overlap arbitrarily. One fragment can...

Practice › Codeforces Solutions ›

Codeforces Beta Round 87 (Div. 1 Only)

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 37

Codeforces Beta Round 37 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1000-2600 | Time: 8m 37s Problem Name Rating Tags Solve Time Verified A Towers 1000 sortings 53s ✓ B Computer Game 1800 greedy, implementation 1m 56s ✓ C Old Berland Language 1900 data-structures, greedy, trees 1m 42s ✓ D Lesson Timetable 2300 combinatorics, dp, math 2m 23s ✗ E Trial for Chief 2600 graphs, greedy,...

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

CF 109C - Lucky Tree

CF 109C - Lucky Tree Rating: 1900 Tags: dp, dsu, trees Solve time: 2m 23s Verified: yes Solution Problem Understanding We are given a tree with n vertices where each edge has a positive weight. Some edges are considered "lucky" if their weight consists only of the digits 4 and 7. The task is to count the number of ordered triples of distinct vertices ( i , j , k...

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

CF 123E - Maze

CF 123E - Maze Rating: 2500 Tags: dfs and similar, dp, probabilities, trees Solve time: 2m 39s Verified: no Solution Problem Understanding We are given a tree, and two independent probability distributions over its vertices. One distribution chooses the starting vertex of a DFS, the other chooses the target vertex where the search stops. The DFS behaves randomly: before exploring a node, it shuffles the adjacency list uniformly at random,...

Practice › Codeforces Solutions › Codeforces Beta Round 48 ›

CF 51F - Caterpillar

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

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

CF 6E - Exposition

CF 6E - Exposition Rating: 1900 Tags: binary search, data structures, dsu, trees, two pointers Solve time: 58s Verified: yes Solution Problem Understanding We are given a sequence of books by Berlbury, each with a known height, arranged chronologically. The library wants to organize an exposition by selecting consecutive books such that the difference between the tallest and shortest book in the selection does not exceed a given limit, k...

Practice › Codeforces Solutions › Codeforces Beta Round 64 ›

CF 70E - Information Reform

CF 70E - Information Reform Rating: 2700 Tags: dp, implementation, trees Solve time: 3m 29s Verified: no Solution Problem Understanding We are given a country with cities connected by roads such that the road network forms a tree: there is exactly one simple path between any two cities. Each road has equal length in terms of counting the number of edges. The government wants to establish regional centers in some...

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

CF 61E - Enemy is weak

CF 61E - Enemy is weak Rating: 1900 Tags: data structures, trees Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given an array of distinct integers representing the power of soldiers standing in a line. We need to count how many index triples (i, j, k) satisfy two conditions at the same time: The positions are ordered as i < j < k The values are strictly...

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

CF 98B - Help King

CF 98B - Help King Rating: 2200 Tags: implementation, probabilities, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are asked to simulate a fair random selection of one knight out of n using a coin that can only produce two outcomes. Each coin flip has an equal probability of landing heads or tails. The goal is to find the expected number of flips required to select a...

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

CF 48G - Galaxy Union

CF 48G - Galaxy Union Rating: 2700 Tags: dp, trees, two pointers Solve time: 2m 23s Verified: yes Solution Problem Understanding We are given an undirected weighted graph with exactly n vertices and n edges. Since a connected graph with n vertices and n edges contains exactly one cycle, the graph is a unicyclic graph, a tree with one extra edge. For every planet u , we must compute the...

Practice › Codeforces Solutions ›

Codeforces Beta Round 78 (Div. 1 Only)

Codeforces Beta Round 78 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1700-2700 | Time: 10m 13s Problem Name Rating Tags Solve Time Verified A Help Victoria the Wise 1700 brute-force, implementation 2m 12s ✓ B Help King 2200 implementation, probabilities, trees 1m 17s ✓ C Help Greg the Dwarf 2500 geometry, ternary-search 2m 29s ✓ D Help Monks 2500 constructive-algorithms 1m 50s...

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

CF 22E - Scheme

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

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

CF 76A - Gift

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

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

CF 77C - Beavermuncher-0xFF

CF 77C - Beavermuncher-0xFF Rating: 2100 Tags: dfs and similar, dp, dsu, greedy, trees Solve time: 2m 30s Verified: no Solution Problem Understanding We have a tree where each vertex initially contains some number of beavers. The robot starts at a fixed vertex s . Every time it traverses an edge from u to v , it immediately eats exactly one beaver at v . If v already has zero...

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

CF 97E - Leaders

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

Practice › Codeforces Solutions › Codeforces Beta Round 41 ›

CF 42E - Baldman and the military

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

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

CF 81E - Pairs

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

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

CF 115A - Party

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

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

CF 25D - Roads not only in Berland

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

Practice › Codeforces Solutions › Codeforces Beta Round 37 ›

CF 37C - Old Berland Language

CF 37C - Old Berland Language Rating: 1900 Tags: data structures, greedy, trees Solve time: 1m 42s Verified: yes Solution Problem Understanding We need to construct a binary prefix code. The input gives the lengths of all words in the language. Every word may contain only 0 and 1 , and no word is allowed to be the prefix of another. We must either build such a set of words...

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

CF 29D - Ant on the Tree

CF 29D - Ant on the Tree Rating: 2000 Tags: constructive algorithms, dfs and similar, trees Solve time: 1m 19s Verified: yes Solution Problem Understanding We are asked to construct a path for an ant on a tree. The tree has n vertices, with vertex 1 as the root, and n-1 edges connecting them so the graph is connected. The ant wants to start at the root, traverse every edge...

Practice › Codeforces Solutions ›

Codeforces Beta Round 25 (Div. 2 Only)

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

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

CF 87D - Beautiful Road

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

Practice › Codeforces Solutions › School Regional Team Contest, Saratov, 2011 ›

CF 120F - Spiders

CF 120F - Spiders Rating: 1400 Tags: dp, greedy, trees Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a collection of toy spiders. Each spider is a tree, represented by beads (nodes) connected with strings (edges). A spider with $k$ beads has $k-1$ strings connecting its beads so that all beads are connected and there are no cycles. Petya can glue spiders together by identifying some...

Practice › Codeforces Solutions ›

Codeforces Beta Round 84 (Div. 1 Only)

Codeforces Beta Round 84 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2700 | Time: 11m 6s Problem Name Rating Tags Solve Time Verified A Lucky Sum of Digits 1000 brute-force, implementation 2m 22s ✓ B Lucky Probability 1900 brute-force, probabilities 2m 23s ✓ C Lucky Tree 1900 dp, dsu, trees 2m 23s ✓ D Lucky Sorting 2000 constructive-algorithms, sortings 1m 47s ✓...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117E - Tree or not Tree

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

Practice › Codeforces Solutions ›

All-Ukrainian School Olympiad in Informatics

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

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

CF 14D - Two Paths

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

Wiki › Algorithms › 01. Searching and Sorting ›

4. Tree and Indexed Search

4. Tree and indexed search, 35 index slug name 81 binary-search-tree-search Binary Search Tree Search 82 avl-tree-search AVL Tree Search 83 red-black-tree-search Red Black Tree Search 84 treap-search Treap Search 85 randomized-bst-search Randomized BST Search 86 splay-tree-search Splay Tree Search 87 scapegoat-tree-search Scapegoat Tree Search 88 weight-balanced-tree-search Weight Balanced Tree Search 89 b-tree-search B Tree Search 90 b-plus-tree-search B Plus Tree Search 91 b-star-tree-search B Star Tree Search 92 van-emde-boas-search...

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

BST Search

Binary Search Tree Search Binary Search Tree (BST) search locates a key by following the tree structure and using the ordering invariant: all keys in the left subtree are smaller all keys in the right subtree are larger This property allows you to discard half of the remaining subtree at each step, similar in spirit to binary search on arrays. Problem Given a binary search tree with root node root...

Wiki › Algorithms › 02. Data Structures › 1. Core Data Structures and Operations ›

1.8 Basic Tree Traversals and Operations

1.8 Basic tree traversals and operations, 30 index slug name 1 tree-traversal Tree Traversal 2 dfs Depth First Search 3 bfs Breadth First Search 4 preorder Preorder 5 inorder Inorder 6 postorder Postorder 7 level-order Level Order 8 zigzag-traversal Zigzag Traversal 9 vertical-order Vertical Order 10 boundary-traversal Boundary Traversal 11 tree-height Height 12 tree-size Size 13 tree-diameter Diameter 14 tree-balance Balance 15 tree-lca Lowest Common Ancestor 16 tree-path-sum Path Sum...

Wiki › Algorithms › 02. Data Structures ›

2. Advanced Data Structures and Operations

2. Advanced data structures and operations section name 2.1 Balanced Search Trees 2.2 Range Query Structures 2.3 Fenwick Tree Variants 2.4 Segment Tree Variants 2.5 Disjoint Set Union Variants 2.6 Tries and Prefix Structures 2.7 Order Statistic Structures

Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Finger Search

Finger Search Finger search exploits locality. Instead of searching from the root or beginning, it starts from a known position called a finger and moves toward the target. The cost depends on the distance between the finger and the target, not the total size of the structure. This method appears in ordered data structures such as balanced trees, skip lists, and sorted arrays with auxiliary links. Problem Given an ordered...

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Randomized BST Search

Randomized BST Search Randomized BST search operates on a binary search tree whose shape is maintained by randomized insertion or rotation rules. The key invariant remains identical to a standard BST, while randomization ensures that the expected height stays logarithmic. Search uses only key comparisons. Randomization affects structure, not traversal logic. Problem Given a randomized BST with root root and a target key x , find a node such that...

Wiki › Algorithms › 02. Data Structures › 1. Core Data Structures and Operations ›

1.7 Binary Search Trees

1.7 Binary search trees, 45 index slug name 1 binary-search-tree Binary Search Tree 2 bst-insert BST Insert 3 bst-delete BST Delete 4 bst-search BST Search 5 bst-minimum Minimum 6 bst-maximum Maximum 7 bst-predecessor Predecessor 8 bst-successor Successor 9 bst-height Height 10 bst-depth Depth 11 bst-traversal-inorder Inorder Traversal 12 bst-traversal-preorder Preorder Traversal 13 bst-traversal-postorder Postorder Traversal 14 bst-level-order Level Order 15 bst-iterative-traversal Iterative Traversal 16 bst-recursive-traversal Recursive Traversal 17 bst-balance-check Balance...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Order Statistic Tree Rank

Order Statistic Tree Rank Order Statistic Tree Rank computes how many keys are smaller than a given key. It uses a binary search tree where each node stores the size of its subtree. This operation is the inverse of Order Statistic Tree Select. Select maps a rank to a key. Rank maps a key to its position in sorted order. Problem Given an order statistic tree and a key $x$,...

Wiki › Algorithms › 02. Data Structures › 2. Advanced Data Structures and Operations ›

2.1 Balanced Search Trees

2.1 Balanced search trees, 65 index slug name 1 balanced-search-tree Balanced Search Tree 2 avl-tree AVL Tree 3 avl-insert AVL Insert 4 avl-delete AVL Delete 5 avl-rotation AVL Rotation 6 avl-balance-factor Balance Factor 7 red-black-tree Red Black Tree 8 red-black-insert Red Black Insert 9 red-black-delete Red Black Delete 10 red-black-properties Red Black Properties 11 aa-tree AA Tree 12 aa-tree-skew AA Tree Skew 13 aa-tree-split AA Tree Split 14 treap Treap...

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Order Statistic Tree Select

Order Statistic Tree Select Order Statistic Tree Select finds the element with rank $k$ in a balanced binary search tree. The tree stores one extra field at each node: the size of its subtree. With subtree sizes, selection becomes a guided walk from the root. At each node, compare $k$ with the size of the left subtree. Problem Given a binary search tree node $root$ and an integer $k$, return...