dsu | brain

Practice › Codeforces Solutions › Codeforces Beta Round 81 ›

CF 105D - Entertaining Geodetics

CF 105D - Entertaining Geodetics Rating: 2700 Tags: brute force, dsu, implementation Solve time: 2m 8s Verified: yes Solution Problem Understanding The statement is intentionally wrapped in game terminology, but the underlying process is a sequence of color merges. Each map cell has a panel color. Some cells also contain a symbol, and every symbol has its own color. We start by destroying one specific symbol. Destroyed symbols are processed...

Practice › Codeforces Solutions ›

Codeforces Beta Round 81

Codeforces Beta Round 81 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1700-2700 | Time: 13m 32s Problem Name Rating Tags Solve Time Verified A Transmigration 1700 implementation 3m 6s ✓ B Dark Assembly 1800 brute-force, probabilities 2m 19s ✓ C Item World 2200 brute-force, implementation, sortings 3m 26s ✗ D Entertaining Geodetics 2700 brute-force, dsu, implementation 2m 8s ✓ E Lift and Throw 2500 brute-force 2m...

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 › Codeforces Round 939 (Div. 2) ›

CF 1956F - Nene and the Passing Game

CF 1956F - Nene and the Passing Game Rating: 3000 Tags: constructive algorithms, data structures, dsu, graphs, sortings Solve time: 1m 18s Verified: no Solution Problem Understanding We are given a sequence of basketball players, each with a passing range expressed as an interval $[l_i, r_i]$. The players are numbered from 1 to $n$. Two players $i$ and $j$ can pass the ball between them if the distance between them,...

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

CF 490B - Queue

CF 490B - Queue Rating: 1500 Tags: dsu, implementation Solve time: 11m 48s Verified: no Solution Problem Understanding Each line of input describes one student. For that student we know two IDs: a is the student standing immediately in front of him. b is the student standing immediately behind him. If one of those neighbors does not exist, the value is 0 . The records are given in arbitrary order,...

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

CF 1954E - Chain Reaction

CF 1954E - Chain Reaction Rating: 2200 Tags: binary search, data structures, dsu, greedy, implementation, math, number theory Solve time: 1m 12s Verified: no Solution Problem Understanding We are given a line of monsters, each with some initial health. One operation consists of choosing a single monster as the starting point of a “chain lightning”. That lightning hits the chosen monster and then continues outward to both sides, always staying...

Practice › Codeforces Solutions ›

Codeforces Round 279 (Div. 2)

Codeforces Round 279 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 0/5 | Rating range: 1500-2200 | Time: 44m 5s Problem Name Rating Tags Solve Time Verified B Queue 1500 dsu, implementation 11m 48s ✗ C Hacking Cypher 1700 brute-force, math, number-theory 5m 25s ✗ D Chocolate 1900 brute-force, dfs-and-similar, math 5m 18s ✗ E Restoring Increasing Sequence 2000 binary-search, brute-force, greedy 10m 45s ✗ F Treeland Tour...

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

CF 468B - Two Sets

CF 468B - Two Sets Rating: 2000 Tags: 2-sat, dfs and similar, dsu, graph matchings, greedy Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a set of n distinct integers. Every number must be assigned to one of two groups. If a number x is placed into group A , then its complement with respect to a , namely a - x , must also be...

Practice › Codeforces Solutions ›

Codeforces Round 270

Codeforces Round 270 Type: Special | Problems: 7 | Verified: 5/7 | Rating range: 800-2800 | Time: 12m 18s Problem Name Rating Tags Solve Time Verified A Design Tutorial: Learn from Math 800 math, number-theory 1m 22s ✓ B Design Tutorial: Learn from Life 1300 - 1m 44s ✓ C Design Tutorial: Make It Nondeterministic 1400 greedy 1m 16s ✓ D Design Tutorial: Inverse the Problem 1900 dfs-and-similar, dsu, shortest-paths...

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

CF 461D - Appleman and Complicated Task

CF 461D - Appleman and Complicated Task Rating: 2800 Tags: dsu, math Solve time: 1m 2s Verified: yes Solution Problem Understanding We are given an $n \times n$ grid that is mostly empty, except for a small number of cells that are already fixed as either x or o . Every other cell must be filled with one of these two characters. After filling the grid, we impose a local...

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 ›

Codeforces Round 268 (Div. 1)

Codeforces Round 268 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1500-3100 | Time: 8m 30s Problem Name Rating Tags Solve Time Verified A 24 Game 1500 constructive-algorithms, greedy, math 1m 19s ✓ B Two Sets 2000 2-sat, dfs-and-similar, dsu 2m 32s ✓ C Hack it! 2500 binary-search, constructive-algorithms, math 1m 18s ✓ D Tree 3100 graph-matchings 1m 32s ✗ E Permanent 3100 dp,...

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

CF 452E - Three strings

CF 452E - Three strings Rating: 2400 Tags: data structures, dsu, string suffix structures, strings Solve time: 2m 7s Verified: yes Solution Problem Understanding We have three strings. For every length $l$ from $1$ up to the length of the shortest string, we must count how many triples of positions $$(i_1,i_2,i_3)$$ produce three equal substrings of length $l$, one taken from each string. Another way to view the task is...

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

CF 471E - MUH and Lots and Lots of Segments

CF 471E - MUH and Lots and Lots of Segments Rating: 2700 Tags: data structures, dsu Solve time: 2m 1s Verified: no Solution Problem Understanding We start with a collection of axis-aligned segments. Every segment is either horizontal or vertical, and segments of the same orientation never overlap. We are allowed to delete whole segments or only parts of them. After all deletions, the remaining drawing must satisfy three conditions....

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

Codeforces Round 252 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 1000-2400 | Time: 4m 27s Problem Name Rating Tags Solve Time Verified A Valera and Antique Items 1000 implementation 1m 21s ✓ D Valera and Swaps 2100 constructive-algorithms, dsu, graphs 1m 26s ✗ E Valera and Number 2400 bitmasks, dp, math 1m 40s ✗

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

CF 325E - The Red Button

CF 325E - The Red Button Rating: 2800 Tags: combinatorics, dfs and similar, dsu, graphs, greedy Solve time: 1m 57s Verified: yes Solution Problem Understanding We are asked to construct a walk on a directed functional graph defined by a very specific transition rule. Each state is a node from 0 to n − 1. From a current node i, the next state is not arbitrary: it must be either...

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

CF 212D - Cutting a Fence

CF 212D - Cutting a Fence Rating: 2500 Tags: binary search, data structures, dsu Solve time: 1m 8s Verified: no Solution Problem Understanding We are given a long strip of vertical planks, each with a fixed height. For any contiguous segment of planks of fixed length $k$, Vasya paints a rectangle whose height is determined by the shortest plank inside that segment. So every choice of starting position produces one...

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C1 - Party

CF 177C1 - Party Rating: 1500 Tags: dfs and similar, dsu, graphs Solve time: 3m 2s Verified: yes Solution Problem Understanding The problem asks us to choose the largest possible set of people to invite to a party, subject to two conditions. First, if a person is invited, all their friends must also be invited. Second, no two people in the invited set may dislike each other. Friendships and dislikes...

Practice › Codeforces Solutions ›

Codeforces Round 158 (Div. 2)

Codeforces Round 158 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 0/3 | Rating range: 1400-2100 | Time: 5m 48s Problem Name Rating Tags Solve Time Verified A Adding Digits 1400 implementation, math 1m 21s ✗ C Balls and Boxes 1700 constructive-algorithms, greedy, implementation 1m 20s ✗ D Black and White Tree 2100 constructive-algorithms, dsu, graphs 3m 7s ✗

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

CF 187C - Weak Memory

CF 187C - Weak Memory Rating: 2000 Tags: dfs and similar, dsu Solve time: 2m 12s Verified: yes Solution Problem Understanding We have an undirected graph representing intersections and roads inside the park. Some intersections contain volunteers. PMP starts at intersection s , and the bus station is at intersection t . PMP has weak memory. After talking to a volunteer, he can only remember a path containing at most...

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

CF 160D - Edges in MST

CF 160D - Edges in MST Rating: 2300 Tags: dfs and similar, dsu, graphs, sortings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph with no loops or multiple edges. Each edge has a positive weight. The task is to classify each edge according to whether it belongs to all minimum spanning trees, at least one minimum spanning tree, or no minimum...

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 1

MemSQL start[c]up Round 1 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1500-2800 | Time: 6m 17s Problem Name Rating Tags Solve Time Verified A Square and Rectangles 1500 implementation 4m 20s ✓ E The Red Button 2800 combinatorics, dfs-and-similar, dsu 1m 57s ✓

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

CF 228E - The Road to Berland is Paved With Good Intentions

CF 228E - The Road to Berland is Paved With Good Intentions Rating: 1900 Tags: 2-sat, dfs and similar, dsu, graphs Solve time: 1m 15s Verified: no Solution Problem Understanding We are asked to bring all roads in Berland to an asphalted state using a special operation. Each road connects two cities and has an initial state: asphalted or not. The only operation allowed is to pick a city, and...

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

CF 217A - Ice Skating

CF 217A - Ice Skating Rating: 1200 Tags: brute force, dfs and similar, dsu, graphs Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a set of snow drifts on a 2D grid. Bajtek can move from one snow drift to another by sliding along the rows or columns until he reaches another snow drift, moving strictly in the north, south, east, or west directions. The goal...

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

CF 441D - Valera and Swaps

CF 441D - Valera and Swaps Rating: 2100 Tags: constructive algorithms, dsu, graphs, implementation, math, string suffix structures Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a permutation, which we can think of as a row of numbered positions, where each position contains a distinct value from 1 to n. A swap operation exchanges two positions, and after a sequence of swaps we obtain another permutation....

Practice › Codeforces Solutions ›

ABBYY Cup 2.0 - Easy

ABBYY Cup 2.0 - Easy Type: Special | Problems: 11 | Verified: 10/11 | Rating range: 800-2600 | Time: 24m 43s Problem Name Rating Tags Solve Time Verified A1 Good Matrix Elements 800 implementation 1m 37s ✗ A2 Good Matrix Elements 800 implementation 3m 13s ✓ B1 Rectangular Game 1000 number-theory 1m 36s ✓ B2 Rectangular Game 1200 number-theory 2m 20s ✓ C1 Party 1500 dfs-and-similar, dsu, graphs 3m 2s...

Practice › Codeforces Solutions ›

Codeforces Round 141 (Div. 2)

Codeforces Round 141 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 2/4 | Rating range: 800-2100 | Time: 7m 21s Problem Name Rating Tags Solve Time Verified A Is your horseshoe on the other hoof? 800 implementation 2m 19s ✓ B Two Tables 1400 brute-force, implementation 2m 19s ✓ D Zigzag 2100 data-structures 1m 28s ✗ E The Road to Berland is Paved With Good Intentions 1900 2-sat,...

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

CF 196E - Opening Portals

CF 196E - Opening Portals Rating: 2600 Tags: dsu, graphs, shortest paths Solve time: 2m 19s Verified: yes Solution Problem Understanding We are asked to compute the minimum time needed for a player to open all portals in a country modeled as a graph. The country consists of n cities connected by m bidirectional roads with positive travel times. Some subset of cities, k of them, have portals. Initially, all...

Practice › Codeforces Solutions › April Fools Day Contest 2014 ›

CF 409H - A + B Strikes Back

CF 409H - A + B Strikes Back Rating: 1500 Tags: *special, brute force, constructive algorithms, dsu, implementation Solve time: 33s Verified: no Solution

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

CF 313E - Ilya and Two Numbers

CF 313E - Ilya and Two Numbers Rating: 2300 Tags: constructive algorithms, data structures, dsu, greedy Solve time: 1m 8s Verified: no Solution Problem4 2

Practice › Codeforces Solutions ›

Codeforces Round 186 (Div. 2)

Codeforces Round 186 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 900-2300 | Time: 5m 39s Problem Name Rating Tags Solve Time Verified A Ilya and Bank Account 900 implementation, number-theory 3m 1s ✗ D Ilya and Roads 2100 dp 1m 30s ✓ E Ilya and Two Numbers 2300 constructive-algorithms, data-structures, dsu 1m 8s ✗

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

CF 292D - Connected Components

CF 292D - Connected Components Rating: 1900 Tags: data structures, dfs and similar, dp, dsu Solve time: 1m 47s Verified: yes Solution Problem Understanding We have an undirected graph representing a computer network. The vertices are computers and the edges are cables. The edges are stored in a fixed order from 1 to m . Each query removes one contiguous segment of edges, from index l to index r ,...

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

Codeforces Round 111 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 900-2400 | Time: 8m 5s Problem Name Rating Tags Solve Time Verified A Twins 900 greedy, sortings 1m 15s ✓ B Unlucky Ticket 1100 greedy, sortings 1m 29s ✓ C Find Pair 1700 implementation, math, sortings 1m 47s ✓ D Edges in MST 2300 dfs-and-similar, dsu, graphs 1m 21s ✓ E Buses and...

Practice › Codeforces Solutions ›

VK Cup 2012 Finals, Practice Session

VK Cup 2012 Finals, Practice Session Type: Special | Problems: 3 | Verified: 3/3 | Rating range: 1600-2400 | Time: 11m 47s Problem Name Rating Tags Solve Time Verified A Multicolored Marbles 1600 dp, math 5m 3s ✓ B Pixels 2100 constructive-algorithms, math 1m 41s ✓ C Trails and Glades 2400 constructive-algorithms, dsu, graphs 5m 3s ✓

Practice › Codeforces Solutions ›

Codeforces Round 119 (Div. 1)

Codeforces Round 119 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1500-2900 | Time: 10m 3s Problem Name Rating Tags Solve Time Verified A Permutations 1500 greedy 1m 30s ✓ B AlgoRace 1800 dp, shortest-paths 2m 5s ✓ C Weak Memory 2000 dfs-and-similar, dsu 2m 12s ✓ D BRT Contract 2800 data-structures 1m 54s ✓ E Heaven Tour 2900 data-structures, greedy 2m 22s ✗

Practice › Codeforces Solutions ›

Codeforces Round 134 (Div. 1)

Codeforces Round 134 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1200-2900 | Time: 12m 51s Problem Name Rating Tags Solve Time Verified A Ice Skating 1200 brute-force, dfs-and-similar, dsu 1m 15s ✓ C Formurosa 2600 divide-and-conquer, dp, expression-parsing 1m 20s ✓ D Bitonix' Patrol 2900 bitmasks, brute-force, combinatorics 3m 51s ✗ E Alien DNA 2800 data-structures, dsu, trees 6m 25s ✓

Practice › Codeforces Solutions ›

April Fools Day Contest 2014

April Fools Day Contest 2014 Type: April Fools | Problems: 6 | Verified: 0/6 | Rating range: 1500-2200 | Time: 15m 44s Problem Name Rating Tags Solve Time Verified A The Great Game 1700 *special 4m 22s ✗ B Mysterious Language 1700 *special 57s ✗ D Big Data 1700 *special 1m 2s ✗ F 000001 1900 *special 6m 57s ✗ G On a plane 2200 *special, geometry 1m 53s ✗...

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 › ABBYY Cup 2.0 - Easy ›

CF 177C2 - Party

CF 177C2 - Party Rating: 1500 Tags: brute force, dfs and similar, dsu, graphs Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a social graph of people. Some pairs are friends, and some pairs dislike each other. Friendship and dislike are both undirected relations. The Beaver wants to invite a set of people satisfying three conditions at the same time. Every invited person must bring all...

Practice › Codeforces Solutions ›

Croc Champ 2013 - Round 1

Croc Champ 2013 - Round 1 Type: Special | Problems: 4 | Verified: 4/4 | Rating range: 1100-2000 | Time: 6m 34s Problem Name Rating Tags Solve Time Verified A SMSC 1100 implementation 1m 18s ✓ C Beautiful IP Addresses 2000 brute-force 1m 33s ✓ D Connected Components 1900 data-structures, dfs-and-similar, dp 1m 47s ✓ E Copying Data 1900 data-structures 1m 56s ✓

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

CF 277A - Learning Languages

CF 277A - Learning Languages Rating: 1400 Tags: dfs and similar, dsu Solve time: 1m 44s Verified: yes Solution Problem Understanding We can think of the company as a graph of employees. Two employees are directly connected if they share at least one language. Communication is allowed through intermediates, so if employee A can talk to B, and B can talk to C, then A and C are effectively connected...

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

CF 195E - Building Forest

CF 195E - Building Forest Rating: 2000 Tags: data structures, dsu, graphs Solve time: 1m 40s Verified: yes Solution Problem Understanding We build a directed weighted forest incrementally. Every vertex has at most one outgoing edge, so if we start from any vertex and repeatedly follow outgoing edges, we eventually reach a root. When vertex i is added, the input gives several pairs (v, x) . For every pair, we...

Practice › Codeforces Solutions › VK Cup 2012 Finals, Practice Session ›

CF 209C - Trails and Glades

CF 209C - Trails and Glades Rating: 2400 Tags: constructive algorithms, dsu, graphs, greedy Solve time: 5m 3s Verified: yes Solution Problem Understanding The park is an undirected multigraph. Glades are vertices, trails are edges. Self-loops are allowed, and multiple edges between the same pair of vertices are also allowed. Vasya wants to start at vertex 1, traverse every edge exactly once, and return to vertex 1. This is exactly...

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

CF 141E - Clearing Up

CF 141E - Clearing Up Rating: 2300 Tags: constructive algorithms, dp, dsu, graphs Solve time: 2m 51s Verified: yes Solution Problem Understanding We are given an undirected graph where every edge already belongs to one of two categories. Roads marked "S" are narrow roads that the Elf clears, and roads marked "M" are wide roads that Santa clears. We must choose a subset of roads satisfying two conditions at the...

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

CF 91C - Ski Base

CF 91C - Ski Base Rating: 2300 Tags: combinatorics, dsu, graphs Solve time: 3m 29s Verified: yes Solution Problem Understanding We are asked to count the number of valid ski bases after each road is added to an initially empty graph. The graph consists of junctions as vertices and roads as edges. A valid ski base is any non-empty set of edges such that each connected component of the set...

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

CF 60B - Serial Time!

CF 60B - Serial Time! Rating: 1400 Tags: dfs and similar, dsu Solve time: 2m 8s Verified: no Solution Problem Understanding We are given a three-dimensional grid representing the inside of a plate. The grid has k layers, each layer has n rows and m columns. Every cell is either empty . or blocked # . Water starts entering from one specific cell on the top layer. From there, it...

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

CF 95E - Lucky Country

CF 95E - Lucky Country Rating: 2500 Tags: dp, dsu, graphs Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given a set of islands connected by bidirectional roads. The islands form regions: each region is a connected component, and islands in different regions have no path between them. A region is called lucky if the number of islands in it is a lucky number - a number...

Practice › Codeforces Solutions ›

Codeforces Beta Round 68

Codeforces Beta Round 68 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1000-2800 | Time: 22m 53s Problem Name Rating Tags Solve Time Verified A Room Leader 1000 implementation 1m 35s ✓ B Train 1500 dp, games, greedy 2m 11s ✓ C Chessboard Billiard 2100 dfs-and-similar, dsu, graphs 1m 36s ✓ D Hanger 2400 data-structures 1m 7s ✓ E Shift It! 2800 constructive-algorithms 16m 24s ✗

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 ›

School Team Contest 3 (Winter Computer School 2010/11)

School Team Contest 3 (Winter Computer School 2010/11) Type: Special | Problems: 10 | Verified: 7/10 | Rating range: 900-2500 | Time: 19m 28s Problem Name Rating Tags Solve Time Verified A Codecraft III 900 implementation 1m 14s ✓ B School 2200 dp, dsu 2m 6s ✓ C Dancing Lessons 1900 data-structures 1m 24s ✓ D Event Dates 1900 greedy, meet-in-the-middle, sortings 1m 35s ✓ E Director 2000 constructive-algorithms, greedy...

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 Personal Contest #2 (Winter Computer School 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules) ›

CF 46F - Hercule Poirot Problem

CF 46F - Hercule Poirot Problem Rating: 2300 Tags: dsu, graphs Solve time: 1m 1s Verified: yes Solution Problem Understanding We are given a house with a certain number of rooms connected by doors, and each door has a unique key. There are several residents in the house, each initially in some room with some keys. We also know the positions and key holdings of every resident at a later...

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 ›

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

CF 13E - Holes

CF 13E - Holes Rating: 2700 Tags: data structures, dsu Solve time: 1m 53s Verified: yes Solution Problem Understanding We have a line of holes indexed from left to right. Every hole contains a jump length. If a ball is dropped into hole i , it immediately moves to i + a[i] . From there it jumps again using the value of the new hole, and this continues until the...

Practice › Codeforces Solutions ›

Codeforces Beta Round 17

Codeforces Beta Round 17 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1000-2900 | Time: 16m 51s Problem Name Rating Tags Solve Time Verified A Noldbach problem 1000 brute-force, math, number-theory 1m 46s ✓ B Hierarchy 1500 dfs-and-similar, dsu, greedy 1m 34s ✓ C Balance 2500 dp 6m 37s ✗ D Notepad 2400 number-theory 3m 4s ✓ E Palisection 2900 strings 3m 50s ✓

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

CF 60D - Savior

CF 60D - Savior Rating: 2500 Tags: brute force, dsu, math Solve time: 2m 1s Verified: yes Solution Problem Understanding Each lawn contains a distinct positive integer. Two lawns are considered connected if their numbers can appear together in some primitive Pythagorean triple. A primitive Pythagorean triple is a triple of pairwise coprime integers satisfying: $x^2+y^2=z^2$ The word "primitive" matters because the numbers must also be pairwise coprime. If lawn...

Practice › Codeforces Solutions › School Team Contest 3 (Winter Computer School 2010/11) ›

CF 45B - School

CF 45B - School Rating: 2200 Tags: dp, dsu Solve time: 2m 6s Verified: yes Solution Problem Understanding Each student points to exactly one other student, the person they call whenever they hear news. This creates a directed functional graph, every node has out-degree exactly one. On day i , one student starts spreading a piece of news with initial strength b[i] . Every time the news is forwarded, its...

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 › Codeforces Beta Round 36 ›

CF 36E - Two Paths

CF 36E - Two Paths Rating: 2600 Tags: constructive algorithms, dsu, graphs, implementation Solve time: 2m 35s Verified: no Solution Problem Understanding Each paper describes an undirected edge between two cities. We are told that all papers came from exactly two travel journals. Inside one journal, the traveler wrote down the sequence of roads they traversed, and a road may appear multiple times because the traveler could reuse it. The...

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

CF 74C - Chessboard Billiard

CF 74C - Chessboard Billiard Rating: 2100 Tags: dfs and similar, dsu, graphs, number theory Solve time: 1m 36s Verified: yes Solution Problem Understanding We have an n × m chessboard. A billiard ball moves diagonally like a bishop, but unlike a bishop it reflects off the borders of the board. When it hits a vertical wall, the horizontal component of the direction flips. When it hits a horizontal wall,...

Practice › Codeforces Solutions ›

School Personal Contest #2 (Winter Computer School 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules)

School Personal Contest #2 (Winter Computer School 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules) Type: Beta | Problems: 7 | Verified: 6/7 | Rating range: 800-2500 | Time: 10m 14s Problem Name Rating Tags Solve Time Verified A Ball Game 800 brute-force, implementation 1m 23s ✓ B T-shirts from Sponsor 1100 implementation 1m 13s ✓ C Hamsters and Tigers 1600 two-pointers 1m 18s ✓ D Parking Lot 1800 data-structures,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 80 (Div. 1 Only)

Codeforces Beta Round 80 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2900 | Time: 10m 20s Problem Name Rating Tags Solve Time Verified A Testing Pants for Sadness 1100 greedy, implementation, math 1m 39s ✓ B Cthulhu 1500 dfs-and-similar, dsu, graphs 1m 43s ✓ C Russian Roulette 1900 constructive-algorithms, greedy 2m ✓ D Time to Raid Cowavans 2100 brute-force, data-structures, sortings 1m...

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

CF 27D - Ring Road 2

CF 27D - Ring Road 2 Rating: 2200 Tags: 2-sat, dfs and similar, dsu, graphs Solve time: 1m 30s Verified: yes Solution Problem Understanding We have a cycle of n cities arranged on a ring. Every pair of consecutive cities is already connected by the outer ring road, and city n is also connected back to city 1 . We are additionally given m new roads. Each new road connects...

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

CF 103B - Cthulhu

CF 103B - Cthulhu Rating: 1500 Tags: dfs and similar, dsu, graphs Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given an undirected graph and need to decide whether it matches a very specific structure. The graph should contain exactly one simple cycle, and every other vertex must belong to a tree attached to some vertex on that cycle. Another way to describe it is that the...

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

CF 19E - Fairy

CF 19E - Fairy Rating: 2900 Tags: dfs and similar, divide and conquer, dsu Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given an undirected graph. Each edge represents a segment drawn between two points. We may erase exactly one edge, and after removing it we want the remaining graph to become bipartite. A graph is bipartite if we can color every vertex using two colors such...

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

CF 85E - Guard Towers

CF 85E - Guard Towers Rating: 2600 Tags: binary search, dsu, geometry, graphs, sortings Solve time: 3m 41s Verified: yes Solution Problem Understanding We have n towers on a 2D plane. Every tower must belong to exactly one of two generals. For each general, the cost he demands is the maximum Manhattan distance between any two towers assigned to him. The king only pays the larger of the two costs....

Practice › Codeforces Solutions ›

Codeforces Beta Round 75 (Div. 1 Only)

Codeforces Beta Round 75 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 12m 45s Problem Name Rating Tags Solve Time Verified A Newspaper Headline 1500 greedy, strings 1m 57s ✓ B Queue 1500 binary-search, data-structures 2m 10s ✓ C Ski Base 2300 combinatorics, dsu, graphs 3m 29s ✓ D Grocer's Problem 2600 constructive-algorithms, graphs, greedy 2m 25s ✓ E Igloo...

Practice › Codeforces Solutions ›

Codeforces Beta Round 56

Codeforces Beta Round 56 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1300-2600 | Time: 11m 17s Problem Name Rating Tags Solve Time Verified A Where Are My Flakes? 1300 implementation, two-pointers 1m 40s ✓ B Serial Time! 1400 dfs-and-similar, dsu 2m 8s ✗ C Mushroom Strife 2100 brute-force, dfs-and-similar 2m 15s ✓ D Savior 2500 brute-force, dsu, math 2m 1s ✓ E Mushroom Gnomes 2600 math,...

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

CF 9E - Interestring graph and Apples

CF 9E - Interestring graph and Apples Rating: 2300 Tags: dfs and similar, dsu, graphs Solve time: 1m 48s Verified: yes Solution Problem Understanding We start with an undirected multigraph. Multiple edges are allowed, and loops are also allowed. We may add new edges, and the goal is to transform the graph into a very specific structure. A graph is called interesting when every vertex belongs to exactly one cycle....

Practice › Codeforces Solutions ›

Codeforces Beta Round 36

Codeforces Beta Round 36 Type: Beta | Problems: 5 | Verified: 2/5 | Rating range: 1300-2600 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Extra-terrestrial Intelligence 1300 implementation 1m 21s ✓ B Fractal 1600 implementation 1m 52s ✓ C Bowls 2200 geometry, implementation 2m 5s ✗ D New Game with a Chess Piece 2300 games 1m 43s ✗ E Two Paths 2600 constructive-algorithms, dsu, graphs 2m...

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

CF 28B - pSort

CF 28B - pSort Rating: 1600 Tags: dfs and similar, dsu, graphs Solve time: 1m 33s Verified: yes Solution Problem Understanding We start with an array where position i initially contains value i . Each position also has a fixed jump distance d[i] . A swap is allowed between positions i and j only if |i - j| = d[i] . The target array is a permutation. We must decide...

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

CF 111C - Petya and Spiders

CF 111C - Petya and Spiders Rating: 2100 Tags: bitmasks, dp, dsu Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given a board of size n by m , with a spider on every cell. Each spider can move to any adjacent cell or stay in place, as long as it stays inside the board. All spiders move simultaneously, and multiple spiders can occupy the same cell...

Practice › Codeforces Solutions › Codeforces Beta Round 17 ›

CF 17B - Hierarchy

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 28 (Codeforces format)

Codeforces Beta Round 28 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1600-2800 | Time: 8m 33s Problem Name Rating Tags Solve Time Verified A Bender Problem 1600 implementation 1m 17s ✓ B pSort 1600 dfs-and-similar, dsu, graphs 1m 33s ✓ C Bath Queue 2200 combinatorics, dp, probabilities 1m 44s ✓ D Don't fear, DravDe is kind 2400 binary-search, data-structures, dp 1m 40s ✓ E...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Parallel Binary Search with DSU

Parallel Binary Search with DSU Parallel binary search with DSU answers many offline connectivity queries over a sequence of edge insertions. It finds the earliest time when each pair of vertices becomes connected. The technique combines two ideas: parallel binary search over answer times disjoint set union for fast connectivity checks It applies when edges are only added. Once two vertices become connected, they remain connected, so the predicate is...

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

2.5 Disjoint Set Union Variants

2.5 Disjoint set union variants, 35 index slug name 1 disjoint-set-union Disjoint Set Union 2 union-find Union Find 3 dsu-make-set Make Set 4 dsu-find Find 5 dsu-union Union 6 path-compression Path Compression 7 union-by-rank Union by Rank 8 union-by-size Union by Size 9 dsu-rollback Rollback DSU 10 dsu-persistent Persistent DSU 11 dsu-parity Parity DSU 12 dsu-weighted Weighted DSU 13 dsu-bipartite-check Bipartite Check 14 dsu-component-size Component Size 15 dsu-component-sum Component Sum...

#dsu

CF 105D - Entertaining Geodetics

Codeforces Beta Round 81

CF 1948G - MST with Matching

CF 1956F - Nene and the Passing Game

CF 490B - Queue

CF 1954E - Chain Reaction

Codeforces Round 279 (Div. 2)

CF 468B - Two Sets

Codeforces Round 270

CF 461D - Appleman and Complicated Task

CF 472D - Design Tutorial: Inverse the Problem

Codeforces Round 268 (Div. 1)

CF 452E - Three strings

CF 466E - Information Graph

CF 471E - MUH and Lots and Lots of Segments

CF 455C - Civilization

Codeforces Round 252 (Div. 2)

CF 325E - The Red Button

CF 212D - Cutting a Fence

CF 177C1 - Party

Codeforces Round 158 (Div. 2)

CF 187C - Weak Memory

CF 444E - DZY Loves Planting

CF 160D - Edges in MST

MemSQL start[c]up Round 1

CF 228E - The Road to Berland is Paved With Good Intentions

CF 217A - Ice Skating

CF 441D - Valera and Swaps

ABBYY Cup 2.0 - Easy

Codeforces Round 141 (Div. 2)

CF 217E - Alien DNA

CF 196E - Opening Portals

CF 409H - A + B Strikes Back

CF 313E - Ilya and Two Numbers

Codeforces Round 186 (Div. 2)

CF 292D - Connected Components

Codeforces Round 170 (Div. 1)

Codeforces Round 111 (Div. 2)

VK Cup 2012 Finals, Practice Session

Codeforces Round 119 (Div. 1)

Codeforces Round 134 (Div. 1)

April Fools Day Contest 2014

CF 165D - Beard Graph

CF 177C2 - Party

Croc Champ 2013 - Round 1

CF 277A - Learning Languages

CF 195E - Building Forest

CF 209C - Trails and Glades

CF 141E - Clearing Up

CF 260D - Black and White Tree

CF 91C - Ski Base

Codeforces Beta Round 84 (Div. 1 Only)

CF 60B - Serial Time!

CF 95E - Lucky Country

Codeforces Beta Round 68

Codeforces Beta Round 25 (Div. 2 Only)

School Team Contest 3 (Winter Computer School 2010/11)

CF 87D - Beautiful Road

CF 46F - Hercule Poirot Problem

CF 109C - Lucky Tree

All-Ukrainian School Olympiad in Informatics

CF 6E - Exposition

CF 13E - Holes

Codeforces Beta Round 17

CF 25D - Roads not only in Berland

CF 81E - Pairs

CF 60D - Savior

CF 45B - School

CF 77C - Beavermuncher-0xFF

CF 36E - Two Paths

CF 97E - Leaders

CF 74C - Chessboard Billiard

School Personal Contest #2 (Winter Computer School 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules)

Codeforces Beta Round 80 (Div. 1 Only)

CF 27D - Ring Road 2

CF 103B - Cthulhu

CF 76A - Gift

CF 19E - Fairy

CF 85E - Guard Towers