#dsu

CF 1559D1 - Mocha and Diana (Easy Version)

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

CF 1385G - Columns Swaps

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

CF 1307F - Cow and Vacation

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

CF 1305G - Kuroni and Antihype

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

CF 1253F - Cheap Robot

CF 1253F - Cheap Robot Rating: 2500 Tags: binary search, dsu, graphs, shortest paths, trees Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a weighted undirected graph where a subset of nodes are “centrals”, meaning that whenever a robot arrives there its battery is instantly refilled to full capacity. The robot starts and must finish each query at a central node. Each edge has a weight,...

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

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

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

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

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

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

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

CF 896E - Welcome home, Chtholly Rating: 3100 Tags: data structures, dsu Model: gpt-5-3-mini Solve time: 1m 27s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32b57e-4280-83ec-a22f-8fa1538f3fba Solution Problem Understanding We are maintaining an array of positive integers that changes over time under two types of range operations. Each element represents a remaining “baking time”, and operations either reduce some values or ask how many elements match an exact target value. The first...

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

CF 959B - Mahmoud and Ehab and the message Rating: 1200 Tags: dsu, greedy, implementation Model: gpt-5-3-mini Solve time: 1m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327fbf-b66c-83ec-981d-3b18ee9546df Solution Problem Understanding We are given a vocabulary where each word has a fixed cost of sending, and some words are grouped together because they share the same meaning. Within a group, any word can be replaced by any other word in that...

CF 899E - Segments Removal Rating: 2000 Tags: data structures, dsu, flows, implementation, two pointers Model: gpt-5-5 Solve time: 1m 28s Verified: yes (1/1 samples) Solution Problem Understanding The array starts as a sequence of integers, and it evolves through a very specific greedy deletion rule. At any moment you look at all maximal blocks of consecutive equal values, pick the block with the largest length, and if several blocks...

CF 962G - Visible Black Areas

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

CF 979D - Kuro and GCD and XOR and SUM

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

CF 1009F - Dominant Indices

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

CF 1012E - Cycle sort

CF 1012E - Cycle sort Rating: 3100 Tags: dsu, math Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given an array of integers and allowed to rearrange it using a very specific primitive: we can take any set of indices and rotate the values sitting at those positions cyclically. One operation is exactly one such cycle, and it moves values along a directed loop of chosen positions....

CF 1012B - Chemical table

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

CF 1023F - Mobile Phone Network

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

CF 1027F - Session in BSU

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

CF 1039C - Network Safety

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

CF 1044D - Deduction Queries

CF 1044D - Deduction Queries Rating: 2400 Tags: data structures, dsu Solve time: 7m Verified: no Solution Problem Understanding We are dealing with an extremely large conceptual array indexed from 0 up to $2^{30}-1$, but we never actually store its values. Instead, we receive information about XOR relationships between segments of this array and must answer queries about whether a segment XOR is determined or still ambiguous. Each update gives...

CF 1725I - Imitating the Key Tree

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

CF 1559D2 - Mocha and Diana (Hard Version)

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

CF 1553G - Common Divisor Graph

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

CF 1553E - Permutation Shift

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

CF 1380E - Merging Towers

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

CF 1370D - Odd-Even Subsequence

CF 1370D - Odd-Even Subsequence Rating: 2000 Tags: binary search, dp, dsu, greedy, implementation Solve time: 2m 25s Verified: yes Solution Problem Understanding We are given a sequence of numbers and asked to choose a subsequence of fixed length $k$. Once we pick this subsequence, we alternate its elements into odd and even positions based on their order inside the subsequence, not their original positions in the array. For any...

CF 1361C - Johnny and Megan's Necklace

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

CF 1335F - Robots on a Grid

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

CF 1303F - Number of Components

CF 1303F - Number of Components Rating: 2800 Tags: dsu, implementation Solve time: 3m 15s Verified: no Solution Problem Understanding We are working on a grid that starts completely empty in the sense that every cell contains the same value, zero. Over time, we perform a sequence of updates. Each update picks a single cell and assigns it a value that never decreases over time across queries, since the sequence...

Codeforces Round 616 (Div. 1)

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

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

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

CF 1254E - Send Tree to Charlie

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

CF 1253D - Harmonious Graph

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

CF 1249B1 - Books Exchange (easy version)

CF 1249B1 - Books Exchange (easy version) Rating: 1000 Tags: dsu, math Solve time: 5m 26s Verified: no Solution Problem Understanding Each child starts with exactly one book, and every day all books are passed simultaneously according to a fixed permutation. If a child i gives their book to p[i], then after one day the book moves one step along this directed edge. After two days it moves two steps...

CF 1249B2 - Books Exchange (hard version)

CF 1249B2 - Books Exchange (hard version) Rating: 1300 Tags: dfs and similar, dsu, math Solve time: 4m 6s Verified: no Solution Problem Understanding We are given a system where each child initially holds a unique book, and every day each book is passed to another fixed child according to a permutation. After one day, every book moves once; after two days, it moves again under the same rule, and...

CF 1245D - Shichikuji and Power Grid

CF 1245D - Shichikuji and Power Grid Rating: 1900 Tags: dsu, graphs, greedy, shortest paths, trees Solve time: 3m 18s Verified: no Solution Problem Understanding We are given a set of cities placed on a plane. Each city can be “powered” in one of two ways: either we directly build a power station in it, or we connect it (directly or indirectly through other cities) to a city that already...

CF 1242B - 0-1 MST

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

CF 1236E - Alice and the Unfair Game

CF 1236E - Alice and the Unfair Game Rating: 2500 Tags: binary search, data structures, dp, dsu Solve time: 7m 19s Verified: no Solution Problem Understanding We are given a line of $n$ boxes and a single token hidden in one of them. The game proceeds in $m$ rounds. In each round Alice points to a box index $a_i$, trying to locate the token. After every guess, Marisa is allowed...

CF 1220E - Tourism

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

CF 1217F - Forced Online Queries Problem

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

CF 1213F - Unstable String Sort

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

CF 1209D - Cow and Snacks

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

Mail.Ru Cup 2018 Round 2

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

CF 920F - SUM and REPLACE

CF 920F - SUM and REPLACE Rating: 2000 Tags: brute force, data structures, dsu, number theory Solve time: 3m 26s Verified: yes Solution Problem Understanding We are working with an array of integers where two operations are repeatedly applied over ranges. One operation replaces every value in a segment with its number of positive divisors, and the other asks for the sum of values in a segment after all previous...

Codeforces Round 453 (Div. 2)

Codeforces Round 453 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 1100-1200 | 9m 53s # Problem Rating Tags Accepted Time ✓ A Visiting a Friend 1100 greedy, implementation 10,275 5m 16s ✓ B Coloring a Tree 1200 dfs-and-similar, dsu, greedy 11,948 4m 37s ✓

CF 901C - Bipartite Segments

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

CF 1051G - Distinctification

CF 1051G - Distinctification Rating: 2900 Tags: data structures, dsu, greedy Solve time: 3m 39s Verified: no Solution Problem Understanding We are given a growing sequence of points on the integer line. Each point has a position value and a weight. As we reveal more points one by one, we want to maintain a configuration where all positions are distinct, but we are allowed to move points left or right...

CF 1055B - Alice and Hairdresser

CF 1055B - Alice and Hairdresser Rating: 1300 Tags: dsu, implementation Solve time: 3m 44s Verified: yes Solution Problem Understanding We are maintaining an array of hair lengths on a line of positions, and the system evolves over time as some positions grow. At any moment we can imagine a hypothetical haircut operation: every position whose hair is strictly longer than a fixed threshold $l$ must be reduced down to...

Avito Cool Challenge 2018

Avito Cool Challenge 2018 Special | 8 problems | 5/8 verified | Difficulty 800-3500 | 30m 37s # Problem Rating Tags Accepted Time ✓ A Definite Game 800 constructive-algorithms, math 13,277 6m ✓ B Farewell Party 1500 constructive-algorithms, implementation 4,668 2m 53s ✓ C Colorful Bricks 1500 combinatorics, dp, math 8,557 5m 19s ✓ D Maximum Distance 1800 dsu, graphs, shortest-paths 4,644 2m 31s ✓ E Missing Numbers 1900 binary-search,...

CF 1081D - Maximum Distance

CF 1081D - Maximum Distance Rating: 1800 Tags: dsu, graphs, shortest paths, sortings Solve time: 2m 31s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph where edges have costs, and a subset of vertices is marked as special. Between any two vertices, we define their “distance” in a nonstandard way: instead of summing weights along a path, we consider the maximum edge weight along the...

CF 1740G - Dangerous Laser Power

CF 1740G - Dangerous Laser Power Rating: 3100 Tags: constructive algorithms, dsu, sortings Solve time: 5m 10s Verified: no Solution Problem Understanding We are given an (n \times m) grid where each cell behaves like a directional device that routes a “laser” entering from one side to another side, while possibly increasing its speed. The routing rule depends on a binary configuration we must assign for each cell, and this...

Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022

Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 Div. 1+2 | 7 problems | 1/7 verified | Difficulty 900-3500 | 38m 29s # Problem Rating Tags Accepted Time ✓ A Mainak and Array 900 greedy, math 36,505 4m 32s ✓ B Mainak and Interesting Sequence 1100 bitmasks, constructive-algorithms, math 16,838 4m 46s C Jatayu's Balanced Bracket Sequence 1300 data-structures, dsu, graphs 13,398 7m...

CF 1726D - Edge Split

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

CF 1726C - Jatayu's Balanced Bracket Sequence

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

ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ICPC/IOI | 13 problems | 2/13 verified | Difficulty 1200-3500 | 56m 12s # Problem Rating Tags Accepted Time ✓ A Anti-Tetris 2800 constructive-algorithms, graphs, shortest-paths 422 3m 52s B Building Forest Trails 2800 data-structures, dsu 475 4m 26s ✓ C Cactus Lady and her Cing 3500 13 6m 6s D Dragon Curve 3200 55 2m 10s...

CF 1578L - Labyrinth

CF 1578L - Labyrinth Rating: 2400 Tags: binary search, dsu, greedy Solve time: 3m 48s Verified: no Solution Problem Understanding The labyrinth can be seen as a connected weighted graph where rooms are nodes and passages are undirected edges with capacities. Each room also has a one-time “growth value” that increases Lucy’s width if she chooses to eat that room’s candy. Lucy starts at room 1 with some initial width,...

CF 1578B - Building Forest Trails

CF 1578B - Building Forest Trails Rating: 2800 Tags: data structures, dsu Solve time: 4m 26s Verified: yes Solution Problem Understanding We are given a circular arrangement of villages, labeled from 1 to n in clockwise order. Initially there are no connections between any pair of villages. Over time, we receive events of two types: we either add a straight road between two villages on the circle, or we ask...

CF 1556G - Gates to Another World

CF 1556G - Gates to Another World Rating: 3300 Tags: bitmasks, data structures, dsu, two pointers Solve time: 4m 44s Verified: no Solution Problem Understanding We are working on a graph whose vertices are all integers from $0$ to $2^n - 1$. Each vertex represents an $n$-bit binary string, and there is an undirected edge between two vertices if their binary representations differ in exactly one bit. This is the...

CF 1550F - Jumping Around

CF 1550F - Jumping Around Rating: 2700 Tags: binary search, data structures, divide and conquer, dp, dsu, graphs, shortest paths Solve time: 4m 7s Verified: yes Solution Problem Understanding We are given a sorted set of points on a number line, which we can think of as rocks placed at distinct integer coordinates. A frog starts on one designated rock and can repeatedly jump to other rocks. Each jump has...

CF 1411C - Peaceful Rooks

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

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

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

Codeforces Round 595 (Div. 3)

Codeforces Round 595 (Div. 3) Div. 3 | 9 problems | 5/9 verified | Difficulty 800-2200 | 43m 43s # Problem Rating Tags Accepted Time ✓ A Yet Another Dividing into Teams 800 math 23,707 2m 20s ✓ B1 Books Exchange (easy version) 1000 dsu, math 22,287 5m 26s B2 Books Exchange (hard version) 1300 dfs-and-similar, dsu, math 18,391 4m 6s C1 Good Numbers (easy version) 1300 brute-force, greedy, implementation...

Codeforces Round 597 (Div. 2)

Codeforces Round 597 (Div. 2) Div. 2 | 6 problems | 4/6 verified | Difficulty 1000-2300 | 21m 9s # Problem Rating Tags Accepted Time ✓ A Good ol' Numbers Coloring 1000 math, number-theory 14,891 3m 15s ✓ B Restricted RPS 1200 constructive-algorithms, dp, greedy 14,528 2m 59s ✓ C Constanze's Machine 1400 dp 19,872 2m 6s ✓ D Shichikuji and Power Grid 1900 dsu, graphs, greedy 9,599 3m 18s...

Codeforces Round 599 (Div. 1)

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

CF 1213G - Path Queries

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

CF 1184E3 - Daleks' Invasion (hard)

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

CF 1176E - Cover it!

CF 1176E - Cover it! Rating: 1700 Tags: dfs and similar, dsu, graphs, shortest paths, trees Solve time: 10m 33s Verified: no Solution Problem Understanding We are given an undirected connected graph for each query, and we must select a subset of vertices such that every vertex we do not select has at least one selected neighbor. In other words, every unchosen vertex must be “covered” by an adjacent chosen...

CF 1166F - Vicky's Delivery Service

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

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

Codeforces Round 529 (Div. 3)

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

CF 920E - Connected Components?

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

CF 915F - Imbalance Value of a Tree

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

CF 902B - Coloring a Tree

CF 902B - Coloring a Tree Rating: 1200 Tags: dfs and similar, dsu, greedy Solve time: 4m 37s Verified: yes Solution Problem Understanding We are given a rooted tree with n vertices, where vertex 1 is the root. Each vertex must be colored with a target color specified in the input. Initially, all vertices are color 0. A coloring operation consists of picking any vertex v and a color x...

CF 1095F - Make It Connected

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

CF 1107G - Vasya and Maximum Profit

CF 1107G - Vasya and Maximum Profit Rating: 2400 Tags: binary search, constructive algorithms, data structures, dp, dsu Solve time: 1m 9s Verified: yes Solution Problem Understanding Vasya wants to assemble a contest from a sequence of problems, each with a difficulty and a cost. He gains a fixed reward for including any problem, but he also pays two types of costs: the direct payment to each problem’s author and...

CF 1108F - MST Unification

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

CF 1120D - Power Tree

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

Codeforces Round 542 [Alex Lopashev Thanks-Round] (Div. 2)

Codeforces Round 542 [Alex Lopashev Thanks-Round] (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 800-1400 | Time: 4m 41s Problem Name Rating Tags Solve Time Verified A Be Positive 800 implementation 1m 52s ✗ B Two Cakes 1200 greedy 1m 35s ✓ C Connect 1400 brute-force, dfs-and-similar, dsu 1m 14s ✓

CF 1130C - Connect

CF 1130C - Connect Rating: 1400 Tags: brute force, dfs and similar, dsu Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a square grid representing a planet with land and water. Alice starts at one land cell and wants to reach another land cell. She can only walk on land, moving orthogonally between adjacent cells. If a path exists naturally, she can reach her destination at...

CF 1131F - Asya And Kittens

CF 1131F - Asya And Kittens Rating: 1700 Tags: constructive algorithms, dsu Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a set of kittens, each initially in its own cell arranged linearly in a row. Over the course of $n-1$ days, Asya records pairs of kittens who wanted to play together and removes the partition between their cells. Each pair is guaranteed to be in separate...

CF 1131D - Gourmet choice

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

CF 1133F2 - Spanning Tree with One Fixed Degree

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

Codeforces Round 548 (Div. 2)

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

CF 1139C - Edgy Trees

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

CF 1140F - Extending Set of Points

CF 1140F - Extending Set of Points Rating: 2600 Tags: data structures, divide and conquer, dsu Solve time: 1m 23s Verified: yes Solution Problem Understanding We are maintaining a dynamic set of grid points on a large integer lattice. After each insertion or deletion, we are asked to compute not the size of the current set, but the size of its closure under a specific completion rule. The rule says...

CF 1156E - Special Segments of Permutation

CF 1156E - Special Segments of Permutation Rating: 2200 Tags: data structures, divide and conquer, dsu, two pointers Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to n . For every subarray [l, r] , we look at its maximum value. The subarray is called special when the sum of the two endpoint values equals that maximum: $$p_l +...

CF 1156D - 0-1-Tree

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

CF 1167C - News Distribution

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

CF 1209G1 - Into Blocks (easy version)

CF 1209G1 - Into Blocks (easy version) Rating: 2000 Tags: data structures, dsu, greedy, implementation, two pointers Solve time: 1m 44s Verified: yes Solution Problem Understanding We are asked to transform a given sequence of integers into a "nice" sequence. A sequence is nice if all occurrences of the same number appear in contiguous blocks. For example, [3, 3, 1, 1, 2] is nice, but [3, 1, 3] is not...

CF 1276B - Two Fairs

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

CF 1290C - Prefix Enlightenment

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

CF 1292A - NEKO's Maze Game

CF 1292A - NEKO's Maze Game Rating: 1400 Tags: data structures, dsu, implementation Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a 2-row by $n$-column grid representing a maze. The player starts at the top-left cell $(1,1)$ and wants to reach the bottom-right cell $(2,n)$. Movement is allowed only between orthogonally adjacent cells. Initially, all cells are passable ground. The twist is that certain cells can...

Technocup 2021 - Elimination Round 3

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

CF 1332C - K-Complete Word

CF 1332C - K-Complete Word Rating: 1500 Tags: dfs and similar, dsu, greedy, implementation, strings Solve time: 2m 56s Verified: yes Solution Problem Understanding We are given a string s of length n and an integer k such that n is divisible by k . A string is considered k -complete if it is both a palindrome and periodic with period k . Being a palindrome means the string reads...

CF 1344B - Monopole Magnets

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

Codeforces Round 659 (Div. 1)

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

CF 1383A - String Transformation 1

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

CF 1386C - Joker

CF 1386C - Joker Rating: 2800 Tags: *special, bitmasks, data structures, divide and conquer, dsu Solve time: 2m 24s Verified: no Solution Solution Let $N = pq$ where $p \equiv 3 \pmod 8$ and $q \equiv 7 \pmod 8$. We first prove the claimed identity involving the Jacobi symbol. Recall that the Jacobi symbol is multiplicative and satisfies $$\left(\frac{a}{N}\right) = \left(\frac{a}{p}\right) \left(\frac{a}{q}\right)$$ for any integer $a$. We compute $\left(\frac{-1}{N}\right)$ and...

Codeforces Round 639 (Div. 1)

Codeforces Round 639 (Div. 1) Div. 1 | 6 problems | 1/6 verified | Difficulty 1600-3200 | 25m 47s # Problem Rating Tags Accepted Time ✓ A Hilbert's Hotel 1600 math, number-theory, sortings 16,502 5m 20s B Monopole Magnets 2000 constructive-algorithms, dfs-and-similar, dsu 6,353 2m 16s ✓ C Quantifier Question 2600 dfs-and-similar, dp, graphs 1,979 3m 29s D R\u00e9sum\u00e9 Review 2700 binary-search, greedy, math 1,292 3m 49s E Train Tracks...

CF 1400G - Mercenaries

CF 1400G - Mercenaries Rating: 2600 Tags: bitmasks, brute force, combinatorics, dp, dsu, math, two pointers Solve time: 1m 20s Verified: yes Solution Problem Understanding Polycarp wants to select a subset of mercenaries from a pool of n individuals. Each mercenary has two constraints: the minimum and maximum size of the team they are willing to join, given by l_i and r_i . In addition, some pairs of mercenaries dislike...

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

Central-European Olympiad in Informatics, CEOI 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated) Type: ICPC/IOI | Problems: 3 | Verified: 1/3 | Rating range: 1800-2900 | Time: 9m 24s Problem Name Rating Tags Solve Time Verified A Fancy Fence 1800 *special, data-structures, dsu 1m 59s ✗ B Roads 2900 *special, geometry, sortings 5m 59s ✗ C Star Trek 2600 *special, combinatorics, dfs-and-similar 1m 26s ✓

CF 1402A - Fancy Fence

CF 1402A - Fancy Fence Rating: 1800 Tags: *special, data structures, dsu, implementation, math, sortings Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a fence composed of $N$ rectangular sections placed side by side. Each section $i$ has a width $w_i$ and a height $h_i$. Our task is to count all axis-aligned rectangles that can be formed entirely on top of these sections. A rectangle must...

CF 1408G - Clusterization Counting

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

CF 1408E - Avoid Rainbow Cycles

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

CF 1416D - Graph and Queries

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

CF 1419F - Rain of Fire

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

CF 1423H - Virus

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

CF 1434E - A Convex Game

CF 1434E - A Convex Game Rating: 3500 Tags: dsu, games Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given several independent games. Each game consists of a strictly increasing array of integers. Two players alternate moves, and on each move a player selects one element from the array. The chosen indices must form a strictly increasing sequence over time, so once you pick a position, you...

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

Codeforces Round 679 (Div. 1, based on Technocup 2021 Elimination Round 1) Type: Div. 1 | Problems: 1 | Verified: 1/1 | Rating range: 3500-3500 | Time: 1m 8s Problem Name Rating Tags Solve Time Verified E A Convex Game 3500 dsu, games 1m 8s ✓

Codeforces Round 614 (Div. 1)

Codeforces Round 614 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1400-3500 | 17m 14s # Problem Rating Tags Accepted Time ✓ A NEKO's Maze Game 1400 data-structures, dsu, implementation 13,871 1m 55s ✓ C Xenon's Attack on the Gangs 2300 combinatorics, dfs-and-similar, dp 2,252 1m 10s D Chaotic V. 2700 dp, graphs, greedy 971 7m 22s E Rin and The Unknown Flower 3500 constructive-algorithms, greedy,...

Codeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Final)

Codeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Final) Type: Div. 1 | Problems: 6 | Verified: 0/6 | Rating range: 1800-3400 | Time: 14m 47s Problem Name Rating Tags Solve Time Verified A Extreme Subtraction 1800 constructive-algorithms, dp, greedy 1m 35s ✗ B Identify the Operations 1800 combinatorics, data-structures, dsu 1m 55s ✗ C Graph Transpositions 2400 dfs-and-similar, graphs, greedy 6m 37s ✗ D Sum 2800...

CF 1442B - Identify the Operations

CF 1442B - Identify the Operations Rating: 1800 Tags: combinatorics, data structures, dsu, greedy, implementation Solve time: 1m 55s Verified: no Solution Problem Understanding We start with a permutation stored in a line. At each step, we remove one element from the current line and, depending on where we removed it, we are forced to append one of its immediate neighbors (left or right, whichever exists at that moment) into...

CF 1444C - Team-Building

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

CF 1463E - Plan of Lectures

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

CF 1466F - Euclid's nightmare

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

2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)

2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) Type: ICPC/IOI | Problems: 14 | Verified: 8/14 | Rating range: 800-2900 | Time: 44m 52s Problem Name Rating Tags Solve Time Verified A LaIS 2200 data-structures, dp, greedy 4m 33s ✓ B Bakery 2900 data-structures, dsu 2m 17s ✗ C Berpizza 1400 data-structures, implementation 6m 7s ✓ D Firecrackers 1700 binary-search, sortings 3m 41s ✗ E...

CF 1468J - Road Reform

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

CF 1468B - Bakery

CF 1468B - Bakery Rating: 2900 Tags: data structures, dsu Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to compute a measure of stale bread at a bakery over multiple days. Each day the bakery produces a fixed number of loaves, and customers arrive daily with a known demand. Bread is sold in a first-in-last-out fashion: freshly baked loaves are sold first, and older unsold loaves...

CF 1476D - Journey

CF 1476D - Journey Rating: 1700 Tags: dfs and similar, dp, dsu, implementation Solve time: 3m 17s Verified: no Solution Problem Understanding We are given a chain of cities numbered from 0 to $n$, connected linearly by $n$ roads. Each road has a direction, either left (from city $i$ to $i-1$) or right (from $i-1$ to $i$). A traveler wants to start from some city and visit as many distinct...

CF 1482D - Playlist

CF 1482D - Playlist Rating: 1900 Tags: data structures, dsu, implementation, shortest paths Solve time: 2m 10s Verified: no Solution Problem Understanding We are asked to simulate a playlist with songs labeled by genres, where Arkady listens to songs in order, cycling back to the beginning when reaching the end. The rule is that if the genre of the last song Arkady listened to and the genre of the previous...

CF 1494D - Dogeforces

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

CF 1508C - Complete the MST

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

CF 1513D - GCD and MST

CF 1513D - GCD and MST Rating: 2000 Tags: constructive algorithms, dsu, graphs, greedy, number theory, sortings Solve time: 2m 24s Verified: yes Solution Problem Understanding We are asked to compute the minimum spanning tree (MST) of a weighted graph constructed from an array of positive integers. Each array element corresponds to a vertex, and edges exist either between adjacent elements with a fixed weight p or between any pair...

CF 1515F - Phoenix and Earthquake

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

CF 1521D - Nastia Plays with a Tree

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

CF 1534C - Little Alawn's Puzzle

CF 1534C - Little Alawn's Puzzle Rating: 1300 Tags: combinatorics, dp, dsu, graphs, math Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given a 2 by n grid where each row is a permutation of numbers from 1 to n. So every number appears exactly once in each row, and every column contains two distinct values. The only operation allowed is swapping the two values inside any...

CF 1537F - Figure Fixing

CF 1537F - Figure Fixing Rating: 2200 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, math Solve time: 2m 28s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each node has an initial value and a target value. We can pick any edge and add the same integer to both endpoints. The task is to determine whether there exists a sequence of such operations...

CF 1555F - Good Graph

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

CF 1567F - One-Four Overload

CF 1567F - One-Four Overload Rating: 2700 Tags: 2-sat, constructive algorithms, dfs and similar, dsu, graphs, implementation Solve time: 2m 18s Verified: no Solution Problem Understanding We are given a grid of size $n \times m$ where some cells are marked with an X and the rest are unmarked . . The marked cells are never on the boundary of the grid. Our task is to fill every unmarked cell...

CF 1574F - Occurrences

CF 1574F - Occurrences Rating: 2700 Tags: combinatorics, dfs and similar, dp, dsu, fft, graphs Solve time: 2m Verified: no Solution Problem Understanding We are asked to construct a length m array a , where each position can take a value from 1 to k . The twist is that we are given several “pattern arrays” A_i , and these patterns impose constraints on how often they are allowed to...

CF 1575J - Jeopardy of Dropped Balls

CF 1575J - Jeopardy of Dropped Balls Rating: 1500 Tags: binary search, brute force, dsu, implementation Solve time: 56s Verified: yes Solution Problem Understanding We have an n × m grid. Every cell stores one of three directions. A value of 1 means a ball moves one cell to the right. A value of 2 means the ball moves one cell downward. A value of 3 means the ball moves...

Codeforces Round 746 (Div. 2)

Codeforces Round 746 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-2800 | Time: 21m 17s Problem Name Rating Tags Solve Time Verified A Gamer Hemose 800 binary-search, greedy, math 1m 38s ✓ B Hemose Shopping 1200 constructive-algorithms, dsu, math 1m 50s ✓ C Bakry and Partitioning 1700 bitmasks, constructive-algorithms, dfs-and-similar 8m 32s ✓ D Hemose in ICPC ? 2300 binary-search, dfs-and-similar, implementation 1m...

CF 1592B - Hemose Shopping

CF 1592B - Hemose Shopping Rating: 1200 Tags: constructive algorithms, dsu, math, sortings Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given an array of integers and a restriction on swapping elements: we can only swap two elements if their positions differ by at least x . The task is to determine whether it is possible to sort the array in non-decreasing order under this constraint. Each...

CF 1594D - The Number of Imposters

CF 1594D - The Number of Imposters Rating: 1700 Tags: constructive algorithms, dfs and similar, dp, dsu, graphs Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a network of players who make statements about each other. Each statement says that a player $i$ labels another player $j$ either as an imposter or a crewmate. Every player is secretly assigned one of two roles, and the rules...

CF 1609D - Social Network

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

CF 1615D - X(or)-mas Tree

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

CF 1618G - Trader Problem

CF 1618G - Trader Problem Rating: 2200 Tags: data structures, dsu, greedy, sortings Solve time: 1m 41s Verified: no Solution Problem Understanding In this problem, Monocarp has a set of items, each with an integer price, and he can trade these items with another character’s items. Each trade allows him to give away one of his items of price $x$ and take any item from the other character whose price...

CF 1619G - Unusual Minesweeper

CF 1619G - Unusual Minesweeper Rating: 2000 Tags: binary search, dfs and similar, dsu, greedy, sortings Solve time: 3m 19s Verified: no Solution Problem Understanding Each test case gives a set of mines placed on a 2D grid. Every mine has a position and a “natural lifetime”, meaning it will explode automatically after a given number of seconds if nothing triggers it earlier. The key twist is that explosions propagate....

Educational Codeforces Round 119 (Rated for Div. 2)

Educational Codeforces Round 119 (Rated for Div. 2) Type: Div. 2 | Problems: 7 | Verified: 2/7 | Rating range: 800-2800 | Time: 19m 29s Problem Name Rating Tags Solve Time Verified A Equal or Not Equal 800 constructive-algorithms, dsu, implementation 3m 41s ✗ B Triangles on a Rectangle 1000 geometry, greedy, math 1m 16s ✓ C BA-String 1800 brute-force, dp, greedy 8m 11s ✗ D Exact Change 2000 brute-force,...

CF 1620E - Replace the Numbers

CF 1620E - Replace the Numbers Rating: 1900 Tags: constructive algorithms, data structures, dsu, implementation Solve time: 1m 34s Verified: no Solution Problem Understanding We start with an empty sequence and process a stream of operations that either append a value to the end or globally rename every occurrence of one value into another. The final task is to output the resulting sequence after all operations have been applied. The...

CF 1620A - Equal or Not Equal

CF 1620A - Equal or Not Equal Rating: 800 Tags: constructive algorithms, dsu, implementation Solve time: 3m 41s Verified: no Solution Problem Understanding We are given a circular array of positive integers, and for each adjacent pair in the circle, we know whether the numbers are equal or not. The input provides this information as a string s of characters E and N , where E indicates the two neighbors...

CF 1624G - MinOr Tree

CF 1624G - MinOr Tree Rating: 1900 Tags: bitmasks, dfs and similar, dsu, graphs, greedy Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each edge has a positive integer weight. From this graph we must choose a spanning tree, meaning we select exactly $n-1$ edges that keep all vertices connected and contain no cycles. Among all possible spanning trees, we compute...

CF 1628E - Groceries in Meteor Town

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

CF 1633E - Spanning Tree Queries

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

CF 1635E - Cars

CF 1635E - Cars Rating: 2200 Tags: 2-sat, constructive algorithms, dfs and similar, dsu, graphs, greedy, sortings Solve time: 1m 50s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden configuration of points on a line, one for each car, and assign each car a direction, left or right. After reconstruction, the configuration must explain two kinds of pairwise constraints. Each car starts at an integer coordinate,...

Codeforces Round 771 (Div. 2)

Codeforces Round 771 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-3200 | Time: 10m 2s Problem Name Rating Tags Solve Time Verified A Reverse 800 constructive-algorithms, greedy, math 1m 32s ✗ B Odd Swap Sort 1100 data-structures, math, sortings 2m 38s ✗ C Inversion Graph 1300 data-structures, dsu, graphs 1m 11s ✓ D Big Brush 2000 constructive-algorithms, data-structures, greedy 1m 41s ✗ E...

CF 1638C - Inversion Graph

CF 1638C - Inversion Graph Rating: 1300 Tags: data structures, dsu, graphs, math Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a permutation of size $n$, which is an array containing all integers from 1 to $n$ exactly once in some order. From this permutation, we construct an undirected graph on $n$ vertices, where each vertex corresponds to a position in the permutation. An edge exists...

CF 1641C - Anonymity Is Important

CF 1641C - Anonymity Is Important Rating: 2200 Tags: binary search, brute force, data structures, dsu, greedy, sortings Solve time: 2m 2s Verified: yes Solution Problem Understanding We have a line of n people. Every person is either sick or healthy. As information arrives, we receive two kinds of statements. A statement with x = 0 says that nobody in the interval [l, r] is sick. Every person in that...

CF 1648E - Air Reform

CF 1648E - Air Reform Rating: 3200 Tags: data structures, dfs and similar, divide and conquer, dsu, graphs, implementation, trees Solve time: 2m 16s Verified: no Solution Problem Understanding We start with a connected undirected graph. The graph represents Berlaflot flights, and every edge has a price. The cost of traveling between two cities is unusual. A route may contain many flights, but its cost is not the sum of...

CF 1657F - Words on Tree

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

CF 1659E - AND-MEX Walk

CF 1659E - AND-MEX Walk Rating: 2200 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dsu, graphs Solve time: 1m 55s Verified: no Solution Problem Understanding We are given an undirected, connected graph where each edge has a non-negative integer weight less than $2^{30}$. A query asks for the minimum possible "length" of a walk from vertex $u$ to vertex $v$. The "length" of a walk is defined unusually:...

CF 1661E - Narrow Components

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

CF 1670C - Where is the Pizza?

CF 1670C - Where is the Pizza? Rating: 1400 Tags: data structures, dfs and similar, dsu, graphs, implementation, math Solve time: 12m 12s Verified: no Solution Problem Understanding We are given two permutations of size $n$, which are arrays containing each integer from $1$ to $n$ exactly once. From these two permutations, a third array is constructed by choosing for each position either the value from the first permutation or...

CF 1671E - Preorder

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

Codeforces Round 787 (Div. 3)

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

CF 1675E - Replace With the Previous, Minimize

CF 1675E - Replace With the Previous, Minimize Rating: 1500 Tags: dsu, greedy, strings Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a string made of lowercase English letters, and we are allowed to repeatedly perform a global transformation on it. One operation picks a single character, say 'd' , and replaces every occurrence of 'd' in the string with the previous letter in the alphabet,...

CF 1680F - Lenient Vertex Cover

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

CF 1681F - Unique Occurrences

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

CF 1685D1 - Permutation Weight (Easy Version)

CF 1685D1 - Permutation Weight (Easy Version) Rating: 2800 Tags: constructive algorithms, dfs and similar, dsu Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a permutation p of the numbers from 1 to n , and our task is to construct another permutation q of the same numbers that minimizes a specific weight function. The weight of q is calculated as the sum of absolute differences...

CF 1687D - Cute number

CF 1687D - Cute number Rating: 2900 Tags: binary search, brute force, data structures, dsu, implementation, math Solve time: 2m 34s Verified: yes Solution Problem Understanding For every integer, look at the two consecutive perfect squares surrounding it. If $$m^2 \le x < (m+1)^2,$$ then $g(x)=m^2$ and $f(x)=(m+1)^2$. The number is called cute when it is strictly closer to the lower square than to the upper square. A short calculation...

CF 1687C - Sanae and Giant Robot

CF 1687C - Sanae and Giant Robot Rating: 2500 Tags: binary search, brute force, data structures, dsu, greedy, sortings Solve time: 2m 31s Verified: no Solution Correctness The solution addresses the exercise directly. It identifies the event $f(n)-f(n-1) = k$ as the occurrence of exactly $k-1$ consecutive terms outside the interval $[\alpha,\beta)$ followed by one term inside, which correctly models the "gap" between hits in the interval. By invoking the...

CF 1689E - ANDfinity

CF 1689E - ANDfinity Rating: 2500 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dsu, graphs Solve time: 2m 30s Verified: no Solution Problem Understanding We are given an array of non-negative integers. Each array element corresponds to a vertex in a graph. Two vertices are connected by an edge whenever the bitwise AND of their values is positive. The graph is not guaranteed to be connected. We may...

CF 1691E - Number of Groups

CF 1691E - Number of Groups Rating: 2300 Tags: data structures, dfs and similar, dsu, graphs, greedy, sortings Solve time: 3m 12s Verified: yes Solution Problem Understanding We are given a set of segments on the number line, each colored either red or blue. Each segment occupies a continuous interval from l_i to r_i , inclusive. The task is to find groups of segments where two segments are considered connected...

CF 1696F - Tree Recovery

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

Codeforces Round 805 (Div. 3)

Codeforces Round 805 (Div. 3) Type: Div. 3 | Problems: 8 | Verified: 4/8 | Rating range: 800-2000 | Time: 17m 26s Problem Name Rating Tags Solve Time Verified A Round Down the Price 800 constructive-algorithms 1m 54s ✓ B Polycarp Writes a String from Memory 800 greedy 1m 44s ✗ C Train and Queries 1100 data-structures, greedy 2m 37s ✓ D Not a Cheap String 1000 greedy 2m 28s...

CF 1702E - Split Into Two Sets

CF 1702E - Split Into Two Sets Rating: 1600 Tags: dfs and similar, dsu, graphs Solve time: 1m 57s Verified: yes Solution Problem Understanding We are given a collection of dominoes, each domino represented as a pair of integers between 1 and n, and the total number of dominoes n is even. The task is to split these dominoes into two groups so that within each group no number appears...

CF 1706E - Qpwoeirut and Vertices

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

CF 1707C - DFS Trees

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

CF 1709E - XOR Tree

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

CF 1713E - Cross Swapping

CF 1713E - Cross Swapping Rating: 2400 Tags: 2-sat, data structures, dsu, greedy, matrices Solve time: 2m 32s Verified: no Solution Problem Understanding We are given a square matrix of integers, and we are allowed to perform a specific swap operation: for a chosen index k , we swap the k -th row with the k -th column, leaving the diagonal element at (k, k) unchanged. The goal is to...

CF 1725K - Kingdom of Criticism

CF 1725K - Kingdom of Criticism Rating: 2500 Tags: data structures, dsu Solve time: 2m 48s Verified: yes Solution Problem Understanding We are managing a kingdom with a line of buildings, each with an integer height. Residents occasionally issue criticisms targeting all buildings with heights in a specific interval [l, r], where r-l is always odd. The kingdom's construction team must then adjust building heights so no building lies in...

Codeforces Round 824 (Div. 2)

Codeforces Round 824 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2900 | Time: 25m 23s Problem Name Rating Tags Solve Time Verified A Working Week 800 constructive-algorithms, greedy, math 2m 22s ✓ B Tea with Tangerines 900 greedy, math 8m 13s ✗ C Phase Shift 1400 dfs-and-similar, dsu, graphs 1m 18s ✗ D Meta-set 1700 brute-force, combinatorics, data-structures 8m 55s ✓ E House...

CF 1735C - Phase Shift

CF 1735C - Phase Shift Rating: 1400 Tags: dfs and similar, dsu, graphs, greedy, implementation, strings Solve time: 1m 18s Verified: no Solution Producing a complete editorial of the quality requested requires first reconstructing and proving the underlying greedy graph construction used in Codeforces 1735C. I do not want to invent a proof or implementation for a 1400-rated constructive problem without verifying the details, because a subtle mistake in the...

CF 1738F - Connectivity Addicts

CF 1738F - Connectivity Addicts Rating: 2400 Tags: constructive algorithms, dsu, graphs, greedy, interactive, shortest paths, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given an undirected graph where initially we only know the number of vertices and the degree of each vertex. The task is to assign a color to each vertex so that two conditions hold. First, vertices sharing a color must form a...

CF 1738D - Permutation Addicts

CF 1738D - Permutation Addicts Rating: 1900 Tags: constructive algorithms, data structures, dfs and similar, dsu, graphs, trees Solve time: 2m 11s Verified: no Solution Problem Understanding We are given a hidden process that builds an array while scanning a permutation from left to right, but the only thing left after the process is a derived array b . Our task is to reconstruct any valid permutation and threshold that...

CF 1851G - Vlad and the Mountains

CF 1851G - Vlad and the Mountains Rating: 2000 Tags: binary search, data structures, dsu, graphs, implementation, sortings, trees, two pointers Solve time: 2m 2s Verified: no Solution Correctness The solution does answer the correct exercise: it attempts to extend Lemma B from integral $c$ to arbitrary real $c$ with $0\le c<k$, and it proposes an explicit reciprocity formula. However, the proof does not justify the formula it claims. The...

CF 1758E - Tick, Tock

CF 1758E - Tick, Tock Rating: 2500 Tags: combinatorics, dfs and similar, dsu, graphs Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid where each cell either has a clock showing a number between 0 and $h-1$ or is empty. The allowed moves let us pick a row or column and advance all clocks in that row or column by one hour...

CF 1761E - Make It Connected

CF 1761E - Make It Connected Rating: 2400 Tags: binary search, brute force, constructive algorithms, dsu, graphs, greedy, matrices, trees, two pointers Solve time: 11m 43s Verified: no Solution Problem Understanding We are given an undirected graph and a special operation. Choosing a vertex flips all of its incident edges: every neighbor becomes a non-neighbor, and every non-neighbor becomes a neighbor. Viewed another way, choosing vertex u replaces its adjacency...

CF 1763F - Edge Queries

CF 1763F - Edge Queries Rating: 3000 Tags: data structures, dfs and similar, dp, dsu, graphs, trees Solve time: 41s Verified: no Solution

CF 1764F - Doremy's Experimental Tree

CF 1764F - Doremy's Experimental Tree Rating: 2500 Tags: brute force, constructive algorithms, dfs and similar, dsu, sortings, trees Solve time: 3m 10s Verified: no Solution Problem Understanding We are given a mysterious tree with n vertices where each edge has a positive integer weight. For every pair (i, j) with 1 ≤ j ≤ i ≤ n , a “virtual experiment” was done: an edge of weight 1 was...

2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)

2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) Type: ICPC/IOI | Problems: 14 | Verified: 5/14 | Rating range: 800-2900 | Time: 45m 29s Problem Name Rating Tags Solve Time Verified A Access Levels 2400 bitmasks, dsu, flows 2m 29s ✗ B Broken Keyboard 800 greedy 8m 4s ✓ C Card Guessing 2600 combinatorics, dp, probabilities 4m 5s ✓ D Watch the Videos...

CF 1765A - Access Levels

CF 1765A - Access Levels Rating: 2400 Tags: bitmasks, dsu, flows, graph matchings Solve time: 2m 29s Verified: no Solution Problem Understanding Each document is described by which developers should be able to open it. So every column of the input matrix is a subset of developers: those rows where the value is one form the “approved set” for that document. We are allowed to compress this binary matrix into...

CF 1770E - Koxia and Tree

CF 1770E - Koxia and Tree Rating: 2400 Tags: combinatorics, dfs and similar, dp, dsu, math, probabilities, trees Solve time: 2m 4s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices and $k$ butterflies initially located on distinct vertices. Each edge in the tree will be randomly directed, and butterflies can move along edges if the starting vertex has a butterfly and the target vertex is...

CF 1770D - Koxia and Game

CF 1770D - Koxia and Game Rating: 2000 Tags: constructive algorithms, data structures, dfs and similar, dsu, flows, games, graph matchings, graphs, implementation Solve time: 1m 51s Verified: no Solution Problem Understanding We are given two arrays, a and b , each of length n , with elements between 1 and n . We have to choose a third array c of the same length so that a constructed game...

CF 1779D - Boris and His Amazing Haircut

CF 1779D - Boris and His Amazing Haircut Rating: 1700 Tags: constructive algorithms, data structures, dp, dsu, greedy, sortings Solve time: 1m 35s Verified: no Solution Problem Understanding We are asked to transform Boris's current hairstyle into a desired one using a limited set of razors, each of which can cut hair down to a fixed length over any contiguous segment. Conceptually, you can think of the current hairstyle as...

CF 1780G - Delicious Dessert

CF 1780G - Delicious Dessert Rating: 2400 Tags: binary search, dsu, hashing, math, number theory, string suffix structures Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a string s of length n representing Tonio's dessert recipe. A substring of s is called delicious if the number of times it appears in s is divisible by its own length. The task is to count all delicious substrings...

CF 1787D - Game on Axis

CF 1787D - Game on Axis Rating: 1900 Tags: combinatorics, dfs and similar, dsu, graphs, implementation Solve time: 1m 58s Verified: no Solution Problem Understanding We are given an array of integers, each representing a "jump" value on points labeled from $1$ to $n$. Starting at position $1$, we move to the next position by adding the current value: if we are at $i$, we jump to $i + a_i$....

CF 1788F - XOR, Tree, and Queries

CF 1788F - XOR, Tree, and Queries Rating: 2500 Tags: bitmasks, constructive algorithms, dfs and similar, dsu, graphs, greedy, implementation, trees Solve time: 1m 33s Verified: yes Solution Problem Understanding We have a tree with $n$ vertices and $n-1$ edges. We must assign a non-negative integer weight to every edge. Some constraints are given in the form $(u,v,x)$, meaning that the XOR of all edge weights along the unique path...

CF 1797E - Li Hua and Array

CF 1797E - Li Hua and Array Rating: 2300 Tags: brute force, data structures, dsu, math, number theory, two pointers Solve time: 1m 54s Verified: no Solution Problem Understanding We are given an array of integers and two types of operations. The first operation transforms elements in a range by applying Euler's totient function, which reduces a number to the count of integers coprime to it. The second operation asks,...

CF 1797F - Li Hua and Path

CF 1797F - Li Hua and Path Rating: 3000 Tags: data structures, dfs and similar, divide and conquer, dsu, trees Solve time: 1m 37s Verified: no Solution Problem Understanding We are working with a rooted but otherwise unrooted tree where every vertex carries a unique label from 1 to n, and these labels matter structurally rather than just as identifiers. For any two vertices u and v, consider the unique...

CF 1799E - City Union

CF 1799E - City Union Rating: 2300 Tags: constructive algorithms, dfs and similar, dsu, geometry, greedy, implementation, math Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a rectangular grid of size $n \times m$, where each cell is either filled or empty. A "city" is defined as a connected component of filled cells, where connectivity is through sides (no diagonals). Initially, there are exactly two cities...

CF 1800E2 - Unforgivable Curse (hard version)

CF 1800E2 - Unforgivable Curse (hard version) Rating: 1500 Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, greedy, strings Solve time: 2m 20s Verified: yes Solution Problem Understanding We have two strings of equal length, s and t . Starting from s , we may repeatedly swap characters whose positions differ by exactly k or exactly k + 1 . The question is whether these allowed swaps are...

CF 1800E1 - Unforgivable Curse (easy version)

CF 1800E1 - Unforgivable Curse (easy version) Rating: 1400 Tags: brute force, constructive algorithms, dsu, graphs, greedy, strings Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given two strings of equal length, and we are allowed to transform the first string into the second by swapping characters, but only under a restricted rule: we can swap positions whose indices differ by either 3 or 4. Each swap...

CF 1801E - Gasoline prices

CF 1801E - Gasoline prices Rating: 3000 Tags: data structures, divide and conquer, dsu, hashing, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a country, Berland, structured as a tree of cities rooted at city 1. Each city has a gas station with a price range $[l_i, r_i]$. Every year, the king’s two sons inspect gasoline prices along two paths of equal length. Each inspection...

CF 1804G - Flow Control

CF 1804G - Flow Control Rating: 3500 Tags: data structures, dsu, implementation Solve time: 1m 20s Verified: yes Solution Problem Understanding We are tasked with simulating a network line shared by multiple users, where each user transmits data at a rate that can grow or shrink depending on network congestion. Each user has a start time, end time, and initial data rate. At each millisecond, the total bandwidth consumed by...

CF 1806D - DSU Master

CF 1806D - DSU Master Rating: 2500 Tags: combinatorics, dp, dsu, math Solve time: 2m Verified: no Solution Problem Understanding We are given a binary array that encodes how edges are directed between values, and we are asked to evaluate a rather indirect quantity over all permutations of each prefix length. For a fixed length $k$, we take every permutation of ${1,2,\dots,k}$. Each permutation is processed left to right. During...

CF 1810E - Monsters

CF 1810E - Monsters Rating: 2100 Tags: brute force, data structures, dfs and similar, dsu, graphs, greedy Solve time: 1m 32s Verified: no Solution Problem Understanding We are given an undirected graph where every vertex contains a monster with a numeric requirement. If a monster has value a[i] , you are only allowed to defeat it when you have already defeated at least a[i] other monsters. The process starts by...

CF 1814F - Communication Towers

CF 1814F - Communication Towers Rating: 2700 Tags: brute force, divide and conquer, dsu Solve time: 1m 27s Verified: no Solution Problem Understanding We are dealing with a network of communication towers connected by wires, where each tower can operate only on a continuous range of frequencies. The towers are numbered from 1 to n, and each tower i can operate on frequencies from l_i to r_i inclusive. Two towers...

CF 1824C - LuoTianyi and XOR-Tree

CF 1824C - LuoTianyi and XOR-Tree Rating: 2500 Tags: data structures, dfs and similar, dp, dsu, greedy, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a tree with n vertices, each labeled with a non-negative integer. The root is vertex 1. The goal is to modify as few vertex values as possible so that the XOR of values along every path from the root to...

CF 1825E - LuoTianyi and XOR-Tree

CF 1825E - LuoTianyi and XOR-Tree Rating: 2500 Tags: data structures, dp, dsu, greedy, trees Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given a rooted tree with n vertices, each labeled with a non-negative integer. The root is vertex 1 . We are allowed to change the value of any vertex to any non-negative integer, and our goal is to minimize the number of changes required...

CF 1827B1 - Range Sorting (Easy Version)

CF 1827B1 - Range Sorting (Easy Version) Rating: 2000 Tags: binary search, dp, dsu, greedy, trees, two pointers Solve time: 2m 22s Verified: no Solution Problem Understanding We are asked to compute a “beauty” metric for all subarrays of a given array of distinct integers. The beauty of a subarray is the minimum total time needed to sort it using range-sort operations. Each range-sort is defined by picking a subsegment...

CF 1828D1 - Range Sorting (Easy Version)

CF 1828D1 - Range Sorting (Easy Version) Rating: 2000 Tags: binary search, brute force, data structures, dp, dsu, greedy Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to compute a cumulative measure of "beauty" over all subarrays of a given array of distinct integers. The beauty of a subarray is defined as the minimum total time required to sort it using operations that sort a contiguous...

CF 1829E - The Lakes

CF 1829E - The Lakes Rating: 1100 Tags: dfs and similar, dsu, graphs, implementation Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a two-dimensional grid representing terrain, where each cell contains a non-negative integer indicating the depth of water at that location. A "lake" is defined as a contiguous region of nonzero cells that are connected orthogonally, meaning we can move between them using up, down,...

CF 1833G - Ksyusha and Chinchilla

CF 1833G - Ksyusha and Chinchilla Rating: 1800 Tags: constructive algorithms, dfs and similar, dp, dsu, greedy, implementation, trees Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a tree, and we are allowed to remove edges. After removing some edges, the remaining connected components must each consist of exactly three vertices, and each such component must itself still be a tree. In other words, the final...

CF 1833E - Round Dance

CF 1833E - Round Dance Rating: 1600 Tags: dfs and similar, dsu, graphs, shortest paths Solve time: 2m Verified: no Solution Problem Understanding We are given a group of people at a festival, each of whom remembers exactly one neighbor in a round dance. Each dance is a closed cycle where every participant has exactly two neighbors, but we only know one neighbor per person. The task is to determine...

CF 1844H - Multiple of Three Cycles

CF 1844H - Multiple of Three Cycles Rating: 3400 Tags: combinatorics, data structures, dp, dsu, math Solve time: 1m 39s Verified: no Solution Problem Understanding We are asked to process a sequence of updates on an initially empty array of length $n$. Each update sets a single position in the array to a number, and after all updates, the array becomes a permutation of $1$ through $n$. After each update,...

CF 1844E - Great Grids

CF 1844E - Great Grids Rating: 2400 Tags: 2-sat, constructive algorithms, dfs and similar, dsu, graphs Solve time: 1m 39s Verified: no Solution Problem Understanding We are working with an $n \times m$ grid where every cell must be assigned one of three symbols: $A$, $B$, or $C$. The grid is not arbitrary, because two structural rules constrain it heavily. First, any two cells that share an edge must contain...

CF 1845D - Rating System

CF 1845D - Rating System Rating: 1800 Tags: binary search, brute force, data structures, dp, dsu, greedy, math, two pointers Solve time: 1m 38s Verified: no Solution Problem Understanding We are simulating a rating that starts at zero and is updated after each match by adding an integer delta from an array. Positive values increase the rating, negative values decrease it. There is an extra constraint controlled by a parameter...

CF 1847D - Professor Higashikata

CF 1847D - Professor Higashikata Rating: 1900 Tags: data structures, dsu, greedy, implementation, strings Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a binary string s and a fixed collection of intervals over it. Each interval extracts a substring, and all extracted substrings are concatenated in order to form a new string t(s) . The structure of t(s) is fixed by the intervals, so every position...

CF 1849E - Max to the Right of Min

CF 1849E - Max to the Right of Min Rating: 2300 Tags: binary search, data structures, divide and conquer, dp, dsu, two pointers Solve time: 1m 2s Verified: yes Solution Problem Understanding We are given a permutation of length $n$, which means we have a sequence containing every integer from $1$ to $n$ exactly once. For any contiguous segment of this array, we look at two special positions inside it:...

CF 1850H - The Third Letter

CF 1850H - The Third Letter Rating: 1700 Tags: dfs and similar, dsu, graphs, greedy, implementation Solve time: 1m 7s Verified: yes Solution Problem Understanding Each soldier must be assigned an integer coordinate on a number line, and multiple soldiers are allowed to share the same coordinate. Every constraint connects two soldiers and specifies an exact signed distance between their positions. A constraint of the form (a, b, d) enforces...

CF 2202C1 - Lost Civilization (Easy Version)

CF 2202C1 - Lost Civilization (Easy Version) Rating: 1300 Tags: data structures, dsu, greedy Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to reverse-engineer a process that generates a sequence by repeatedly inserting an incremented copy of an existing element immediately after that element. Formally, we start with an initial sequence of length m and repeatedly insert x_i + 1 after some element x_i until the...

CF 2202C2 - Lost Civilization (Hard Version)

CF 2202C2 - Lost Civilization (Hard Version) Rating: 1700 Tags: data structures, dp, dsu, greedy Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a sequence of integers, and the task revolves around understanding a generative procedure used by an ancient civilization. The procedure starts with a sequence of length m and repeatedly inserts a new element after any existing element, where the new element is one...

CF 2166C - Cyclic Merging

CF 2166C - Cyclic Merging Rating: 1300 Tags: constructive algorithms, data structures, dsu, greedy Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a set of values placed around a circle, and we repeatedly compress this circle until only one value remains. Each move removes two neighboring elements and replaces them with a single element whose value is the larger of the two, and we also pay...

CF 2136E - By the Assignment

CF 2136E - By the Assignment Rating: 2000 Tags: dfs and similar, dsu, graphs Solve time: 1m 46s Verified: no Solution Problem Understanding We are given an undirected connected graph where each vertex carries an integer label. Some labels are fixed, while others are unknown and must be chosen from the range $0$ to $V-1$. For any simple path, we define its value as the XOR of all vertex labels...

CF 2130C - Double Perspective

CF 2130C - Double Perspective Rating: 1300 Tags: constructive algorithms, dsu, greedy Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given a set of integer pairs, each representing both a segment on a number line and an edge in a graph. Our goal is to select a subset of these pairs to maximize the difference between the total length of covered integers, called $f(S')$, and the number...

CF 2019F - Max Plus Min Plus Size

CF 2019F - Max Plus Min Plus Size Rating: 2200 Tags: data structures, dp, dsu, greedy, sortings Solve time: 1m 48s Verified: no Solution Problem Understanding We are given an array of positive integers, and we are allowed to mark some of them as "red" under the constraint that no two adjacent elements can both be red. The score is calculated as the sum of three components: the maximum value...

CF 1994D - Funny Game

CF 1994D - Funny Game Rating: 1900 Tags: constructive algorithms, dsu, graphs, greedy, math, number theory, trees Solve time: 1m 36s Verified: no Solution Problem Understanding We are asked to construct a connected graph on $n$ vertices, starting from an empty graph, by performing $n-1$ operations. Each operation is numbered from 1 to $n-1$. For operation $x$, we can choose two vertices $u$ and $v$ such that the absolute difference...

CF 1877F - Lexichromatography

CF 1877F - Lexichromatography Rating: 2500 Tags: combinatorics, dsu Solve time: 3m 17s Verified: no Solution Problem Understanding We are asked to count the number of ways to colour an array of integers either blue or red, subject to two constraints. The first is a lexicographical constraint: if we extract the blue elements as a subsequence and the red elements as another subsequence, the blue sequence must be strictly smaller...

CF 1857G - Counting Graphs

CF 1857G - Counting Graphs Rating: 2000 Tags: combinatorics, divide and conquer, dsu, graphs, greedy, sortings, trees Solve time: 1m 55s Verified: no Solution Problem Understanding We are given a tree on $n$ vertices, where each edge has an integer weight. The task is to count the number of weighted simple graphs such that the given tree is the unique minimum spanning tree (MST), and all edge weights in the...

CF 1859D - Andrey and Escape from Capygrad

CF 1859D - Andrey and Escape from Capygrad Rating: 1800 Tags: binary search, data structures, dp, dsu, greedy, sortings Solve time: 3m 15s Verified: no Solution Problem Understanding We are asked to model escape paths in a one-dimensional world where Andrey can use portals repeatedly. Each portal is a segment [l_i, r_i] from which Andrey can enter and teleport to another contained segment [a_i, b_i] . The goal is to...

CF 1872F - Selling a Menagerie

CF 1872F - Selling a Menagerie Rating: 1800 Tags: dfs and similar, dsu, graphs, implementation, math Solve time: 2m 5s Verified: no Solution Problem Understanding We are given a set of animals, each with a cost and a "fear" relationship: every animal fears exactly one other animal, and no animal fears itself. When selling an animal, the money earned depends on whether the animal it fears has already been sold....

CF 1873H - Mad City

CF 1873H - Mad City Rating: 1700 Tags: dfs and similar, dsu, games, graphs, shortest paths, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are asked to determine if one player, Valeriu, can indefinitely avoid being caught by another player, Marcel, in a city modeled as a connected graph with exactly $n$ buildings and $n$ roads. Each building is a node, and each road is an undirected...

CF 1876D - Lexichromatography

CF 1876D - Lexichromatography Rating: 2500 Tags: combinatorics, dfs and similar, dsu, graphs, two pointers Solve time: 2m 10s Verified: no Solution Problem Understanding We are given an array of integers, and our task is to assign each element one of two colors, blue or red. The goal is to count all colorings that satisfy two conditions. First, if we take the subsequence of all blue elements and the subsequence...

CF 1887D - Split

CF 1887D - Split Rating: 2700 Tags: binary search, data structures, divide and conquer, dsu, math, trees, two pointers Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given an array of distinct integers ranging from 1 to n, and we are asked to answer multiple queries about contiguous subarrays. A subarray is considered "good" if it can be split into two non-empty parts such that all elements...

CF 1895E - Infinite Card Game

CF 1895E - Infinite Card Game Rating: 2300 Tags: binary search, brute force, data structures, dfs and similar, dp, dsu, games, graphs, greedy, sortings, two pointers Solve time: 1m 54s Verified: no Solution Problem Understanding Each test case describes two players who each own a fixed set of cards. Every card has two numbers, an attack and a defence. A card can defeat another card if its attack is strictly...

CF 1899G - Unusual Entertainment

CF 1899G - Unusual Entertainment Rating: 1900 Tags: data structures, dfs and similar, dsu, shortest paths, sortings, trees, two pointers Solve time: 46s Verified: no Solution Problem Understanding We have a rooted tree with root at vertex 1 . A permutation p contains every vertex exactly once. Each query gives three values (l, r, x) . We look at the vertices appearing in the permutation segment p[l...r] and ask whether...

CF 1900E - Transitive Graph

CF 1900E - Transitive Graph Rating: 2100 Tags: dfs and similar, dp, dsu, graphs, implementation Solve time: 1m 55s Verified: yes Solution Problem Understanding The original graph gives directed connections between vertices, and then we repeatedly “complete” it under a transitive rule: whenever there is a path of length two from a vertex $a \to b \to c$, we eventually add a direct edge $a \to c$. After this process...

CF 1909C - Heavy Intervals

CF 1909C - Heavy Intervals Rating: 1400 Tags: constructive algorithms, data structures, dsu, greedy, math, sortings Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a set of $n$ intervals on the number line. Each interval has a left endpoint $l_i$, a right endpoint $r_i$, and a weight per unit length $c_i$. The actual weight of an interval is calculated as $c_i \cdot (r_i - l_i)$. The...

CF 1914G1 - Light Bulbs (Easy Version)

CF 1914G1 - Light Bulbs (Easy Version) Rating: 2100 Tags: brute force, combinatorics, dfs and similar, dp, dsu, graphs, math, trees Solve time: 50s Verified: no Solution Problem Understanding We are given a row of 2n light bulbs, with exactly two bulbs of each color from 1 to n . All bulbs start turned off. We can pick an initial set S of bulbs to turn on. After that, two...

CF 1919D - 01 Tree

CF 1919D - 01 Tree Rating: 2100 Tags: constructive algorithms, data structures, dsu, greedy, sortings, trees Solve time: 46s Verified: no Solution Problem Understanding We are given the distances from the root to the leaves of a binary tree, listed in DFS leaf order. Every internal vertex has exactly two children. One outgoing edge has weight 0 and the other has weight 1 . The actual shape of the tree...

CF 1920F2 - Smooth Sailing (Hard Version)

CF 1920F2 - Smooth Sailing (Hard Version) Rating: 3000 Tags: binary search, data structures, dsu, geometry, graphs, trees Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a rectangular grid where some cells are islands, some are open ocean, and some are underwater volcanoes. Thomas wants to sail in loops that fully encircle the island without stepping onto it. For each ocean or volcano starting cell, we...

CF 1920F1 - Smooth Sailing (Easy Version)

CF 1920F1 - Smooth Sailing (Easy Version) Rating: 2500 Tags: binary search, brute force, data structures, dfs and similar, dsu, graphs, shortest paths Solve time: 50s Verified: no Solution Problem Understanding We are given a 2D grid representing an island in the ocean. Each cell can be part of the island ( # ), open ocean ( . ), or an underwater volcano ( v ). The island cells form...

CF 1920D - Array Repetition

CF 1920D - Array Repetition Rating: 1900 Tags: binary search, brute force, dsu, implementation, math Solve time: 1m 18s Verified: yes Solution Problem Understanding We start with an empty sequence and gradually build a very large array using two kinds of operations. The first operation appends a single value to the end, effectively extending the sequence by one element. The second operation takes the entire current array and concatenates several...

CF 1922D - Berserk Monsters

CF 1922D - Berserk Monsters Rating: 1900 Tags: brute force, data structures, dsu, implementation, math Solve time: 1m 52s Verified: no Solution Problem Understanding We have a row of monsters, each with an attack value a_i and a defense value d_i . Monocarp casts a berserk spell so that monsters attack their immediate neighbors each round. The mechanics are as follows: each alive monster deals damage equal to its attack...

CF 1923E - Count Paths

CF 1923E - Count Paths Rating: 2000 Tags: data structures, dfs and similar, dp, dsu, graphs, trees Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a tree with n nodes, each colored with some integer between 1 and n . The task is to count the number of simple paths of length at least two such that the first and last nodes have the same color,...

CF 1927F - Microcycle

CF 1927F - Microcycle Rating: 1900 Tags: data structures, dfs and similar, dsu, graphs, greedy, implementation, sortings, trees Solve time: 2m 24s Verified: no Solution Problem Understanding We are asked to find a simple cycle in an undirected, weighted graph where the minimal edge in that cycle is as small as possible. The input is a series of graphs: each graph is described by the number of vertices, the number...

CF 1927D - Find the Different Ones!

CF 1927D - Find the Different Ones! Rating: 1300 Tags: binary search, brute force, data structures, dp, dsu, greedy, two pointers Solve time: 2m 21s Verified: no Solution Problem Understanding The problem gives you an array of integers and a series of queries, each specifying a segment of that array. For each query, you are asked to find two positions within the segment such that the values at these positions...

Codeforces Round 1040 (Div. 1)

Codeforces Round 1040 (Div. 1) Div. 1 | 9 problems | 2/9 verified | Difficulty 1300-3500 | 17m 30s # Problem Rating Tags Accepted Time ✓ A Double Perspective 1300 constructive-algorithms, dp, dsu 16,636 1m 22s ✓ B Stay or Mirror 1600 brute-force, data-structures, dp 13,253 1m 38s C1 Interactive RBS (Easy Version) 1900 binary-search, bitmasks, constructive-algorithms 3,856 2m 7s C2 Interactive RBS (Medium Version) 2000 binary-search, bitmasks, constructive-algorithms 2,502...

CF 1930D2 - Sum over all Substrings (Hard Version)

CF 1930D2 - Sum over all Substrings (Hard Version) Rating: 2100 Tags: bitmasks, divide and conquer, dp, dsu, greedy, implementation, strings Solve time: 2m 36s Verified: yes Solution Problem Understanding For every binary pattern $p$, we define $f(p)$ as the minimum number of 1 s in another binary string $q$ of the same length such that every position of $p$ can "justify" its value by looking at some interval of...

CF 1935F - Andrey's Tree

CF 1935F - Andrey's Tree Rating: 2800 Tags: binary search, constructive algorithms, data structures, dfs and similar, dsu, greedy, implementation, trees Solve time: 2m 4s Verified: no Solution Problem Understanding The problem asks us to simulate the removal of each vertex from a given tree and then determine the minimal cost required to reconnect the remaining vertices into a tree. The tree is represented as a standard undirected graph without...

XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)

XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules) Type: ICPC/IOI | Problems: 4 | Verified: 3/4 | Rating range: - | Time: 4m 17s Problem Name Rating Tags Solve Time Verified A Parallel Universes - *special, constructive-algorithms, dfs-and-similar 54s ✗ B Three Arrays - *special, constructive-algorithms, implementation 1m 23s ✓ C Burenka and Pether - *special, data-structures, dfs-and-similar 1m 11s ✓ D Almost...

CF 1940C - Burenka and Pether

CF 1940C - Burenka and Pether Rating: - Tags: *special, data structures, dfs and similar, divide and conquer, dsu, graphs, sortings, trees Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a directed structure over positions 1 to n, where each position carries a value. The key restriction is that movement from one position to another is not arbitrary: you are only allowed to move forward in...

CF 1940A - Parallel Universes

CF 1940A - Parallel Universes Rating: - Tags: *special, constructive algorithms, dfs and similar, dsu, graphs Solve time: 54s Verified: no Solution This prompt is missing the actual problem statement of CF 1940A - Parallel Universes , so a correct editorial cannot be written yet without guessing the task. Right now we only know: problem code: 1940A title: Parallel Universes tags: graphs / DSU / constructive but no input/output definition...

CF 1971G - XOUR

CF 1971G - XOUR Rating: 1700 Tags: data structures, dsu, sortings Solve time: 1m 7s Verified: no Solution Problem Understanding We are given an array of nonnegative integers and a special swap condition: two elements can be swapped if the bitwise XOR of their values is less than 4. The goal is to produce the lexicographically smallest array possible by performing any number of such swaps. The input consists of...

CF 1978F - Large Graph

CF 1978F - Large Graph Rating: 2400 Tags: data structures, dfs and similar, dsu, graphs, number theory, two pointers Solve time: 2m 31s Verified: no Solution Problem Understanding We are given an array of integers and asked to build a square matrix where each row is a cyclic right shift of the previous row. Then, we treat every element of the matrix as a vertex in a graph. Two vertices...

CF 1981E - Turtle and Intersected Segments

CF 1981E - Turtle and Intersected Segments Rating: 2600 Tags: data structures, dsu, graphs, greedy Solve time: 2m 12s Verified: no Solution Problem Understanding We are given a set of segments on the number line. Each segment also carries a value $a_i$. Two segments are considered related if their intervals overlap at least at one point, including touching at endpoints. Whenever two segments overlap, we imagine an edge between them...

CF 1985H1 - Maximize the Largest Component (Easy Version)

CF 1985H1 - Maximize the Largest Component (Easy Version) Rating: 1700 Tags: brute force, data structures, dfs and similar, dsu, graphs, implementation Solve time: 2m 32s Verified: no Solution Problem Understanding We are given a grid consisting of n rows and m columns, where each cell is either empty ('.') or filled ('#'). A connected component of filled cells is a set of '#' tiles where you can move between...

CF 1985H2 - Maximize the Largest Component (Hard Version)

CF 1985H2 - Maximize the Largest Component (Hard Version) Rating: 2200 Tags: data structures, dfs and similar, dp, dsu, implementation Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a grid of size $n \times m$ where each cell is either empty ('.') or filled ('#'). Connected components of '#' are sets of cells that can reach each other by moving up, down, left, or right. Alex...

CF 1987E - Wonderful Tree!

CF 1987E - Wonderful Tree! Rating: 2000 Tags: brute force, data structures, dfs and similar, dsu, greedy, trees Solve time: 2m 2s Verified: yes Solution Problem Understanding We are given a rooted tree with integer values assigned to each node. The tree is rooted at vertex 1. A tree is considered wonderful if, for every non-leaf vertex, its value is at most the sum of the values of its immediate...

CF 2001C - Guess The Tree

CF 2001C - Guess The Tree Rating: 1500 Tags: binary search, brute force, dfs and similar, divide and conquer, dsu, greedy, interactive, trees Solve time: 3m 35s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden tree with n nodes by interacting with a judge that answers specific distance-based queries. Each query "? a b" returns the node x that minimizes the absolute difference in distances from...

CF 2006B - Iris and the Tree

CF 2006B - Iris and the Tree Rating: 1800 Tags: brute force, data structures, dfs and similar, dsu, math, trees Solve time: 1m 34s Verified: no Solution Problem-Type Check This is a Type B (prove) problem. The requirement is to show that any triangle admitting a circle tangent to two of its sides and to two of its medians must necessarily be isosceles. The statement is exact and requires a...

CF 2008D - Sakurako's Hobby

CF 2008D - Sakurako's Hobby Rating: 1100 Tags: dp, dsu, graphs, math Solve time: 2m 4s Verified: no Solution Problem Understanding We are given a permutation of integers from 1 to n, and each number is colored black or white. From any starting integer i, we can repeatedly apply the permutation to jump from i to p_i, then to p_{p_i}, and so on. A number j is considered reachable from...

CF 2018E1 - Complex Segments (Easy Version)

CF 2018E1 - Complex Segments (Easy Version) Rating: 3300 Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a collection of closed segments on a number line, each defined by a left and right endpoint. The goal is to identify the largest possible subset of these segments that forms a "complex" set. A complex set...

CF 2018E2 - Complex Segments (Hard Version)

CF 2018E2 - Complex Segments (Hard Version) Rating: 3400 Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings Solve time: 38s Verified: no Solution Producing a fully correct editorial for Codeforces 2018E2 requires reconstructing a fairly intricate DSU-based optimization and the divide-and-conquer evaluation of all values of $f(m)$. The official editorial only provides a compressed sketch, not enough detail to safely derive a complete accepted implementation line...

CF 2018D - Max Plus Min Plus Size

CF 2018D - Max Plus Min Plus Size Rating: 2200 Tags: data structures, dp, dsu, greedy, implementation, matrices, sortings Solve time: 1m 55s Verified: no Solution Problem Understanding We are given a one-dimensional array of positive integers and the ability to color some elements red. The restriction is that no two consecutive elements can be red. Our goal is to choose a subset of the elements to color red such...

CF 2020D - Connect the Dots

CF 2020D - Connect the Dots Rating: 1800 Tags: brute force, dp, dsu, graphs, math, trees Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given a set of points on a line, initially completely disconnected. Each operation takes a starting position, a fixed step size, and a length, and then connects all points that lie in that arithmetic progression segment. After processing all operations, the goal is...

CF 2021E3 - Digital Village (Extreme Version)

CF 2021E3 - Digital Village (Extreme Version) Rating: 2800 Tags: data structures, dfs and similar, dp, dsu, graphs, greedy, math, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a connected village represented as a graph. Each node is a house, and edges are internet cables with a latency weight. Some subset of houses specifically need internet. We are allowed to install servers in up to...

CF 2021E1 - Digital Village (Easy Version)

CF 2021E1 - Digital Village (Easy Version) Rating: 2300 Tags: brute force, data structures, dfs and similar, dp, dsu, fft, graphs, greedy, implementation, math, trees Solve time: 2m 17s Verified: yes Solution Problem Understanding In this problem, we are given a village represented as a connected graph with houses as nodes and internet cables as edges. Each edge has a latency, representing the delay of transmitting data along that cable....

CF 2021E2 - Digital Village (Hard Version)

CF 2021E2 - Digital Village (Hard Version) Rating: 2500 Tags: data structures, dp, dsu, graphs, math, trees Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a connected undirected graph representing a village, where nodes are houses and edges are internet cables with latencies. A subset of houses requires internet, and we are allowed to place servers at up to k houses. Each house needing internet will...

CF 2022E2 - Billetes MX (Hard Version)

CF 2022E2 - Billetes MX (Hard Version) Rating: 2600 Tags: binary search, combinatorics, data structures, dsu, graphs Solve time: 2m 53s Verified: no Solution Problem Understanding We are asked to count the number of ways to fill an integer grid with certain cells already preassigned so that the grid is "beautiful." A grid is beautiful if, for any rectangle defined by four corners, the XOR of the corner values equals...

CF 2022E1 - Billetes MX (Easy Version)

CF 2022E1 - Billetes MX (Easy Version) Rating: 2500 Tags: 2-sat, binary search, combinatorics, constructive algorithms, dfs and similar, dsu, graphs Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a partially specified n × m grid. Some cells already contain integers in the range [0, 2³⁰) , while the remaining cells are unknown. A grid is called beautiful if every axis-aligned rectangle satisfies the XOR condition...

CF 2029D - Cool Graph

CF 2029D - Cool Graph Rating: 1900 Tags: constructive algorithms, data structures, dfs and similar, dsu, graphs, greedy, trees Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a simple undirected graph with $n$ vertices and $m$ edges. The graph can be arbitrary but contains no self-loops or multiple edges. We are allowed to perform a "triangle flip" operation on any three distinct vertices $a$, $b$, $c$....

CF 2031D - Penchick and Desert Rabbit

CF 2031D - Penchick and Desert Rabbit Rating: 1700 Tags: binary search, data structures, dfs and similar, dp, dsu, greedy, implementation, two pointers Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a line of trees, each with a height. A rabbit starts at some position and can move between trees using a very specific rule that depends on both position and height. From a tree at...

CF 2033E - Sakurako, Kosuke, and the Permutation

CF 2033E - Sakurako, Kosuke, and the Permutation Rating: 1400 Tags: brute force, data structures, dfs and similar, dsu, graphs, greedy, math Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a permutation of numbers from 1 to n. We are allowed to repeatedly swap any two positions. After performing some swaps, we want the permutation to satisfy a structural condition on every index i. At each...

CF 2033D - Kousuke's Assignment

CF 2033D - Kousuke's Assignment Rating: 1300 Tags: data structures, dp, dsu, greedy, math Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given an array of integers and need to identify subarrays, or contiguous segments, whose sum is zero. These segments are called beautiful. The task is not just to find all beautiful segments but to maximize the number of them without overlaps. In other words, once...

CF 2127E - Ancient Tree

CF 2127E - Ancient Tree Rating: 2100 Tags: constructive algorithms, data structures, dfs and similar, dsu, greedy, trees Solve time: 2m 24s Verified: no Solution Problem Understanding We are given a rooted tree with weighted vertices, where each vertex either has a fixed color between 1 and k or a missing color represented by 0. The goal is to assign colors to all uncolored vertices to minimize the total weight...

CF 2117G - Omg Graph

CF 2117G - Omg Graph Rating: 1900 Tags: brute force, dsu, graphs, greedy, shortest paths, sortings Solve time: 1m 19s Verified: yes Solution Problem Understanding We are working with a weighted undirected connected graph where we need to travel from node 1 to node n. Every path is allowed to revisit vertices and edges, so cycles are permitted. The cost of any chosen path is determined only by the smallest...

CF 2097B - Baggage Claim

CF 2097B - Baggage Claim Rating: 2300 Tags: combinatorics, dfs and similar, dp, dsu, graphs, implementation, math, trees Solve time: 2m 8s Verified: no Solution Problem Understanding The task is to reconstruct a simple path on a rectangular grid where only the cells with odd indices are known. Specifically, the path alternates between "known" and "unknown" cells, starting and ending with known cells. Each consecutive pair of cells in the...

CF 2060E - Graph Composition

CF 2060E - Graph Composition Rating: 1500 Tags: dfs and similar, dsu, graphs, greedy Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given two undirected graphs on the same set of vertices. One graph, call it the working graph, is the structure we are allowed to modify. The second graph is a fixed reference structure that we must eventually “match” in terms of connectivity. The allowed operation...

CF 2041J - Bottle Arrangement

CF 2041J - Bottle Arrangement Rating: 2700 Tags: data structures, divide and conquer, dp, dsu, greedy Solve time: 2m 2s Verified: no Solution The failure you show is not enough to diagnose the algorithm itself. Let's trace what happened: The input contains 5 test cases : 5 2 2 1 5 2 3 4 5 1 5 2 1 4 2 3 5 4 1 1 5 4 10 4...

CF 2044G2 - Medium Demon Problem (hard version)

CF 2044G2 - Medium Demon Problem (hard version) Rating: 1900 Tags: dfs and similar, dp, dsu, graphs, implementation, trees Solve time: 2m 50s Verified: no Solution The error in your Python solution is a simple syntax mistake: the map(int, input().split()) call for reading b is missing a closing parenthesis. This prevents the code from running at all. Once that is fixed, the solution logic itself can remain the same. Here...

CF 2049F - MEX OR Mania

CF 2049F - MEX OR Mania Rating: 2700 Tags: bitmasks, brute force, data structures, dsu, implementation Solve time: 2m 2s Verified: no Solution Problem Understanding The task asks us to process a sequence of integers and repeatedly answer the following: after each update to an element, what is the length of the longest contiguous subarray for which the MEX minus the bitwise OR of all elements equals exactly one. Here,...

CF 2051G - Snakes

CF 2051G - Snakes Rating: 2100 Tags: bitmasks, dp, dsu, graphs Solve time: 3m 43s Verified: no Solution Problem Understanding We are asked to place a set of snakes on a very long 1-dimensional strip of cells. Each snake initially occupies a single cell, and over a sequence of events it can either grow to the right or shrink from the left. At any point, if two snakes occupy the...

CF 2056E - Nested Segments

CF 2056E - Nested Segments Rating: 2500 Tags: combinatorics, dfs and similar, dp, dsu, math Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a set of integer segments over the range [1, n] . Each segment is a closed interval [l, r] . The initial set of segments, S , is "good", meaning that for any two distinct segments in the set, either they do not...

CF 2057E2 - Another Exercise on Graphs (hard version)

CF 2057E2 - Another Exercise on Graphs (hard version) Rating: 2500 Tags: binary search, dfs and similar, dp, dsu, graphs, shortest paths, sortings Solve time: 3m 55s Verified: no Solution Problem Understanding We are given an undirected weighted graph and a large number of queries. Each query picks two vertices and an integer k , and asks us to consider all possible paths between those vertices. Among all such paths,...

CF 2057E1 - Another Exercise on Graphs (Easy Version)

CF 2057E1 - Another Exercise on Graphs (Easy Version) Rating: 2300 Tags: binary search, brute force, dp, dsu, graphs, shortest paths, sortings Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a connected undirected graph with up to 400 vertices and up to 400 edges. Every edge has a positive weight. For each query, we are given two vertices a and b , and a number k...

CF 2063F2 - Counting Is Not Fun (Hard Version)

CF 2063F2 - Counting Is Not Fun (Hard Version) Rating: 2700 Tags: combinatorics, data structures, dfs and similar, dsu, graphs, implementation, trees Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a hidden balanced bracket sequence of length $2n$. The structure of the sequence is not arbitrary: it can be fully described by a set of $n$ disjoint “matching events”, where each event connects an opening bracket...

CF 2063F1 - Counting Is Not Fun (Easy Version)

CF 2063F1 - Counting Is Not Fun (Easy Version) Rating: 2400 Tags: combinatorics, data structures, dfs and similar, dp, dsu, graphs, hashing, implementation, math, trees Solve time: 1m 55s Verified: no Solution Problem Understanding The problem asks us to count balanced bracket sequences under incremental constraints. We are given a balanced sequence of 2n brackets, but we do not know its content. The sequence can be viewed as a set...

CF 2064E - Mycraft Sand Sort

CF 2064E - Mycraft Sand Sort Rating: 2400 Tags: combinatorics, data structures, dsu, greedy, math, sortings Solve time: 2m Verified: no Solution Problem Understanding After gravity sort, the shape of the sand is completely determined by the permutation. Since $p$ is a permutation of $1 \ldots n$, the final shape is always the same staircase: the first column contains $n$ blocks, the second contains $n-1$, and so on. The interesting...

CF 2068E - Porto Vs. Benfica

CF 2068E - Porto Vs. Benfica Rating: 2800 Tags: data structures, dfs and similar, dsu, graphs, shortest paths Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a large undirected, unweighted graph representing a road network. One vertex is the starting point (Lisbon, vertex 1) and another is the destination (Porto, vertex n). A group of travelers always wants to reach the destination using as few edges...

CF 2069F - Graph Inclusion

CF 2069F - Graph Inclusion Rating: 2800 Tags: data structures, dfs and similar, divide and conquer, dsu, graphs Solve time: 1m 48s Verified: no Solution Problem Understanding We are given two undirected graphs, $A$ and $B$, on the same set of $n$ vertices. Initially, both graphs have no edges. Queries arrive one by one; each query either toggles an edge in $A$ or $B$. After every query, we are asked:...

CF 2081D - MST in Modulo Graph

CF 2081D - MST in Modulo Graph Rating: 2600 Tags: constructive algorithms, dsu, graphs, greedy, math, number theory, sortings, trees Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a complete undirected graph where each vertex carries an integer value. The cost of connecting two vertices is not arbitrary, but is determined purely by their values: when we connect a larger value to a smaller value, the...

CF 2086C - Disappearing Permutation

CF 2086C - Disappearing Permutation Rating: 1300 Tags: dfs and similar, dp, dsu, graphs, greedy, implementation Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a permutation of integers from 1 to n, which means every number in that range appears exactly once in an array of size n. We then perform a sequence of queries, where in each query we replace a specific element of the...

CF 2104G - Modulo 3

CF 2104G - Modulo 3 Rating: 2700 Tags: data structures, divide and conquer, dsu, graphs, trees Solve time: 1m 27s Verified: no Solution Problem Understanding We are given a functional graph, meaning each vertex has exactly one outgoing edge. This forms a combination of cycles and trees pointing into those cycles. Each query modifies a single edge and asks how many distinct colorings exist if we are allowed to color...

CF 2106F - Goblin

CF 2106F - Goblin Rating: 1900 Tags: dfs and similar, dp, dsu, greedy, math Solve time: 2m 41s Verified: no Solution Problem Understanding We are asked to find the largest connected set of zeros in an $n \times n$ grid that is built from a single binary string $s$. Each row of the grid is generated by flipping one character of $s$ at the row's index. In other words, row...

CF 2108C - Neo's Escape

CF 2108C - Neo's Escape Rating: 1500 Tags: binary search, brute force, data structures, dp, dsu, graphs, greedy, implementation Solve time: 1m 33s Verified: no Solution Problem Understanding Neo is faced with a row of buttons, each labeled with a positive integer weight. He wants to press all the buttons such that the sequence of weights of the pressed buttons never increases. Neo himself cannot move, but he can create...

Codeforces Round 1040 (Div. 2)

Codeforces Round 1040 (Div. 2) Type: Div. 2 | Problems: 8 | Verified: 2/8 | Rating range: 800-2600 | Time: 12m 27s Problem Name Rating Tags Solve Time Verified A Submission is All You Need 800 greedy, math 1m 16s ✓ B Pathless 1100 constructive-algorithms 1m 38s ✗ C Double Perspective 1300 constructive-algorithms, dsu, greedy 1m 8s ✓ D Stay or Mirror 1600 data-structures, greedy 1m 46s ✗ E1 Interactive...

CF 2126G2 - Big Wins! (hard version)

CF 2126G2 - Big Wins! (hard version) Rating: 2400 Tags: binary search, data structures, divide and conquer, dsu, trees, two pointers Solve time: 1m 23s Verified: no Solution Problem Understanding We are given an array of integers, each between 1 and $n$, and we need to choose a contiguous subarray that maximizes the difference between its median and its minimum element. The median is defined as the middle element after...

CF 2126G1 - Big Wins! (easy version)

CF 2126G1 - Big Wins! (easy version) Rating: 2200 Tags: binary search, data structures, dp, dsu, two pointers Solve time: 1m 30s Verified: no Solution Problem Understanding We are asked to find, for each array, a contiguous segment whose median minus its minimum is as large as possible. Formally, for a subarray $a[l, r]$, we calculate the median of its elements after sorting, then subtract the smallest element in that...

CF 2129A - Double Perspective

CF 2129A - Double Perspective Rating: 1300 Tags: constructive algorithms, dp, dsu, graphs, greedy, sortings Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a collection of segments on a line, each segment also acting as an edge between two vertices. From this set we must choose some subset of edges. Two different quantities are computed from the chosen subset. The first quantity measures how many unit...

CF 2135C - By the Assignment

CF 2135C - By the Assignment Rating: 2000 Tags: binary search, bitmasks, combinatorics, dfs and similar, dsu, graphs, math Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a connected undirected graph where each vertex may have a weight, but some weights are missing and represented by -1 . The goal is to fill in the missing weights such that the graph becomes balanced . A graph...

CF 2141H - Merging Vertices in a Graph

CF 2141H - Merging Vertices in a Graph Rating: 2700 Tags: *special, dfs and similar, dsu, graphs Solve time: 1m 20s Verified: yes Solution Problem Understanding We start with an undirected simple graph on $n$ vertices. The graph evolves through an operation that removes two existing vertices and replaces them with a new vertex whose neighborhood is exactly the intersection of the neighborhoods of the removed vertices. In other words,...

CF 2155F - Juan's Colorful Tree

CF 2155F - Juan's Colorful Tree Rating: 2800 Tags: data structures, dfs and similar, dsu, graphs, meet-in-the-middle, trees Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a tree with n nodes, where each node contains a set of colors drawn from a palette of size k . Each node's set may be different, and the total number of color assignments across all nodes is s ....

CF 2157E - Adjusting Drones

CF 2157E - Adjusting Drones Rating: 1900 Tags: binary search, brute force, data structures, dp, dsu, greedy, implementation, sortings Solve time: 1m 57s Verified: no Solution Problem Understanding We are managing a fleet of drones, each with an initial energy level. The rule is that no energy level should appear more than k times. If any energy level exceeds this limit, the drones perform a series of balancing operations: each...

CF 2158E - Sink

CF 2158E - Sink Rating: 2600 Tags: data structures, divide and conquer, dsu, graphs, implementation Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a 2D grid of size $n \times m$, where each cell contains a positive integer. We can construct "holes" in cells. A cell is considered a sink either if it has a hole, or if it is adjacent (sharing a side) to another...

CF 2159B - Rectangles

CF 2159B - Rectangles Rating: 2100 Tags: brute force, data structures, dp, dsu, greedy, implementation, two pointers Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given a grid filled with zeros and ones. For every cell in this grid, we want to know the smallest possible “valid rectangle” that covers it, where validity is defined in a very specific way: the rectangle must have ones at all...

CF 2164E - Journey

CF 2164E - Journey Rating: 2300 Tags: data structures, dfs and similar, dsu, graphs, greedy Solve time: 1m 52s Verified: no Solution Problem Understanding We are given an undirected connected graph with vertices and weighted edges. We start at vertex 1 and must traverse the graph such that every edge is marked at least once, returning to the start. We have two modes of movement: walking along an edge at...

CF 2171F - Rae Taylor and Trees (hard version)

CF 2171F - Rae Taylor and Trees (hard version) Rating: 1600 Tags: binary search, constructive algorithms, data structures, dp, dsu, greedy, implementation, trees Solve time: 1m 54s Verified: no Solution Problem Understanding We are asked to construct a tree on $n$ vertices labeled from $1$ to $n$ such that for every edge connecting vertices $u$ and $v$ with $u < v$, the vertex $u$ appears before $v$ in a given...

CF 2171D - Rae Taylor and Trees (easy version)

CF 2171D - Rae Taylor and Trees (easy version) Rating: 1400 Tags: binary search, data structures, dp, dsu, greedy, implementation, trees Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to check whether a tree can be built from a permutation of numbers from 1 to n, subject to a specific ordering constraint. The permutation defines an order of the vertices, and any edge we draw from...

CF 2172J - Sliding Tiles

CF 2172J - Sliding Tiles Rating: 2300 Tags: data structures, divide and conquer, dsu Solve time: 1m 46s Verified: no Solution Problem Understanding We are given an $n \times n$ grid with tiles stacked in columns and vertical bars between adjacent columns. Each column $i$ starts with $a_i$ tiles stacked from the bottom. Each bar between column $i$ and $i+1$ has a height $h_i$, which blocks movement of tiles in...

CF 2176E - Remove at the lowest cost

CF 2176E - Remove at the lowest cost Rating: 2400 Tags: data structures, dfs and similar, dp, dsu, greedy, implementation, trees Solve time: 2m 15s Verified: no Solution Problem Understanding We are given an array of n elements. Each element has a value a_i and a removal cost c_i . The goal is to remove all elements except one, using a series of adjacent removals, paying the minimum total cost....

CF 2184E - Exquisite Array

CF 2184E - Exquisite Array Rating: 1800 Tags: combinatorics, data structures, dsu, sortings Solve time: 2m 4s Verified: no Solution Problem Understanding We are given a permutation of length $n$, which is simply an array of integers from $1$ to $n$ in some order without repeats. The task is to count, for every integer $k$ from $1$ to $n-1$, the number of subarrays of length at least two where every...

CF 2187C - Jerry and Tom

CF 2187C - Jerry and Tom Rating: 2300 Tags: data structures, dfs and similar, dsu, games, graphs, greedy, trees Solve time: 2m 26s Verified: no Solution Problem Understanding We are asked to analyze a two-player game on a directed graph with $n$ vertices. The graph is almost a chain: for every vertex $u$ from 1 to $n-1$, there is an edge $u \to u+1$. On top of this, there are...

CF 2190D - Prufer Vertex

CF 2190D - Prufer Vertex Rating: 2500 Tags: combinatorics, dsu, number theory, probabilities, trees Solve time: 2m 45s Verified: no Solution Problem Understanding We start with a forest. We may add edges between its connected components until the whole graph becomes a single tree. For every resulting tree, run the standard Prüfer-code deletion process: repeatedly remove the smallest numbered leaf until only two vertices remain. One of those vertices is...

CF 2205F - Simons and Reconstructing His Roads

CF 2205F - Simons and Reconstructing His Roads Rating: 2400 Tags: constructive algorithms, data structures, dsu, graphs Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a rectangular grid representing a city, with intersections at coordinates $(i,j)$. Streets only exist between neighboring intersections, either horizontally or vertically. Each street has an integer weight and may or may not be allowed for reconstruction. A reconstruction consists of selecting...

CF 2205E - Simons and Dividing the Rhythm

CF 2205E - Simons and Dividing the Rhythm Rating: 2100 Tags: combinatorics, data structures, dp, dsu, math, string suffix structures, strings Solve time: 2m 21s Verified: no Solution Problem Understanding We are asked to count how many arrays $S$ exist such that, after a single sequence of independent subarray reversals, the resulting array equals a given array $T$. The operation allows splitting the array into consecutive segments that cover the...

CF 2207G - Toothless

CF 2207G - Toothless Rating: 3300 Tags: constructive algorithms, dfs and similar, dsu Solve time: 2m 4s Verified: no Solution Problem Understanding We are given an n × m grid representing sand, initially all white. Some cells are marked as needy ( # ) and must be painted black. Other cells are either special ( x ) or normal ( . ), and each non-needy cell has a value: special...

CF 2207F - Hanabi

CF 2207F - Hanabi Rating: 2900 Tags: binary search, data structures, dp, dsu, flows, graph matchings, graphs, greedy Solve time: 2m 2s Verified: no Solution Problem Understanding The problem gives us a Hanabi-like card game where Zuko holds all cards in a single row, one for each combination of rank and color. Iroh can see the cards, but Zuko cannot. On Iroh's turn, he gives a clue by highlighting either...

CF 2208D1 - Tree Orientation (Easy Version)

CF 2208D1 - Tree Orientation (Easy Version) Rating: 1800 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, matrices, trees Solve time: 3m 24s Verified: no Solution Problem Understanding We are given a binary reachability matrix for a directed graph on $n$ nodes. The matrix tells us, for every ordered pair $(i, j)$, whether node $i$ can reach node $j$ through directed edges. The underlying graph that produced this matrix...

CF 2208D2 - Tree Orientation (Hard Version)

CF 2208D2 - Tree Orientation (Hard Version) Rating: 2200 Tags: dfs and similar, dsu, graphs, greedy, sortings, trees Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a directed reachability matrix of a tree after all its edges have been assigned directions, and we need to reconstruct a tree and its edge directions that produce exactly the same reachability information. Each row of the matrix corresponds to...

CF 2211C2 - Equal Multisets (Hard Version)

CF 2211C2 - Equal Multisets (Hard Version) Rating: 1800 Tags: constructive algorithms, dsu, greedy Solve time: 1m 49s Verified: no Solution Problem Understanding We are given two arrays of length $n$, both indexed from 1 to $n$, and a window size $k$. The first array $a$ is fully fixed, while the second array $b$ is partially unknown because some positions contain $-1$. Our task is to decide whether we can...

Codeforces Round 1077 (Div. 1)

Codeforces Round 1077 (Div. 1) Div. 1 | 8 problems | 0/8 verified | Difficulty 1300-3500 | 15m 1s # Problem Rating Tags Accepted Time ✓ A Restricted Sorting 1300 greedy, sortings 15,850 3m 14s B Shortest Statement Ever 5,276 C Jerry and Tom 2300 data-structures, dfs-and-similar, dsu 1,369 2m 26s D Cool Problem 634 E Doors and Keys 3500 brute-force, data-structures, dp 325 2m 11s F1 Al Fine (Maximizing...

Codeforces Round 279 (Div. 2)

Codeforces Round 279 (Div. 2) Div. 2 | 6 problems | 4/6 verified | Difficulty 800-2200 | 12m 6s # Problem Rating Tags Accepted Time ✓ A Team Olympiad 800 greedy, implementation, sortings 70,942 1m 57s B Queue 1500 dsu, implementation 6,422 2m 47s C Hacking Cypher 1700 brute-force, math, number-theory 9,472 2m 23s ✓ D Chocolate 1900 brute-force, dfs-and-similar, math 2,314 1m 25s ✓ E Restoring Increasing Sequence 2000...

Codeforces Round 248 (Div. 2)

Codeforces Round 248 (Div. 2) Div. 2 | 5 problems | 4/5 verified | Difficulty 1100-2500 | 10m 22s # Problem Rating Tags Accepted Time ✓ A Kitahara Haruki's Gift 1100 brute-force, implementation 17,889 1m 39s ✓ B Kuriyama Mirai's Stones 1200 dp, implementation, sortings 53,791 1m 6s ✓ C Ryouko's Memory Note 1800 implementation, math, sortings 2,619 4m 25s ✓ D Nanami's Digital Board 2000 dsu, implementation 1,317 1m...

Zepto Code Rush 2014

Zepto Code Rush 2014 Special | 6 problems | 3/6 verified | Difficulty 1400-3000 | 16m 9s # Problem Rating Tags Accepted Time ✓ A Feed with Candy 1500 greedy 3,788 1m 36s ✓ B Om Nom and Spiders 1400 implementation, math 3,147 1m 29s ✓ C Dungeons and Candies 1800 dsu, graphs, greedy 2,886 4m 29s ✓ D Pudding Monsters 2800 dp 352 2m 7s E Cardboard Box 2600...

Codeforces Round 250 (Div. 2)

Codeforces Round 250 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 1300-2500 | 7m 13s # Problem Rating Tags Accepted Time ✓ A The Child and Homework 1300 implementation 9,360 1m 7s ✓ B The Child and Set 1500 bitmasks, greedy, implementation 10,447 1m 29s ✓ C The Child and Toy 1400 graphs, greedy, sortings 14,992 1m 52s ✓ D The Child and Zoo 1900 dsu,...

April Fools Day Contest 2014

April Fools Day Contest 2014 April Fools | 9 problems | 6/9 verified | Difficulty 1500-2400 | 39m 30s # Problem Rating Tags Accepted Time ✓ A The Great Game 1700 *special 2,625 4m 21s ✓ B Mysterious Language 1700 *special 1,429 3m 58s ✓ C Magnum Opus 1700 *special 2,137 4m 12s ✓ D Big Data 1700 *special 1,803 4m 2s ✓ E Dome 1800 *special 618 4m 43s...

CF 2222F - Building Tree

CF 2222F - Building Tree Rating: - Tags: data structures, divide and conquer, dsu, graphs, implementation Solve time: 1m 37s Verified: no Solution Problem Understanding We start with a weighted undirected graph on n vertices. The twist is that distance between two nodes is not the usual shortest path sum. Instead, if you take any path and look at the set of edge weights used on that path, the cost...

CF 490B - Queue

CF 490B - Queue Rating: 1500 Tags: dsu, implementation Solve time: 2m 47s Verified: no Solution Problem Understanding Each input line describes one student, but the student's own ID is not given directly. Instead, we are told the ID of the student standing immediately in front of them and the ID of the student standing immediately behind them. Since every student appears exactly once in the queue, these neighbor relationships...

CF 466E - Information Graph

CF 466E - Information Graph Rating: 2100 Tags: dfs and similar, dsu, graphs, trees Solve time: 2m 46s Verified: yes Solution Problem Understanding We have a company hierarchy that is built gradually over time. Initially nobody has a boss. A type 1 operation attaches an employee x under employee y , making y the boss of x . The input guarantees that x currently has no boss, and cycles never...

CF 445B - DZY Loves Chemistry

CF 445B - DZY Loves Chemistry Rating: 1400 Tags: dfs and similar, dsu, greedy Solve time: 1m 49s Verified: yes Solution Problem Understanding The chemicals and reactions form an undirected graph. Each vertex represents a chemical, and an edge between two vertices means those two chemicals react. We start with danger equal to 1. Chemicals are poured one at a time in any order. Whenever the newly added chemical has...

CF 444E - DZY Loves Planting

CF 444E - DZY Loves Planting Rating: 2700 Tags: binary search, dsu, trees Solve time: 5m 47s Verified: no Solution Problem Understanding We are given a tree with n nodes, where each edge has a positive weight. For any two nodes x and y , the function g(x, y) is defined as the maximum weight along the unique path connecting them. A sequence p of length n is then evaluated...

Codeforces Round 1082 (Div. 2)

Codeforces Round 1082 (Div. 2) Type: Div. 2 | Problems: 9 | Verified: 1/9 | Rating range: 800-2800 | Time: 14m 8s Problem Name Rating Tags Solve Time Verified A Parkour Design 800 math 1m 48s ✓ B ABAB Construction 1200 dp, greedy, implementation 2m 8s ✗ C1 Lost Civilization (Easy Version) 1300 data-structures, dsu, greedy 1m 44s ✗ C2 Lost Civilization (Hard Version) 1700 data-structures, dp, dsu 1m 25s...

CF 437D - The Child and Zoo

CF 437D - The Child and Zoo Rating: 1900 Tags: dsu, sortings Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each node represents a zoo area and carries a value describing how many animals live there. For any ordered pair of distinct areas $p$ and $q$, we look at all simple paths connecting them. Along each path, we take the minimum...

CF 436C - Dungeons and Candies

CF 436C - Dungeons and Candies Rating: 1800 Tags: dsu, graphs, greedy, trees Solve time: 4m 29s Verified: yes Solution Problem Understanding We are given k game levels. Each level is an n × m grid of characters. A level can be transmitted in two different ways. The first option is to send the entire grid from scratch. Since every cell must be transmitted, the cost is n * m...

CF 433D - Nanami's Digital Board

CF 433D - Nanami's Digital Board Rating: 2000 Tags: dsu, implementation Solve time: 1m 29s Verified: yes Solution Problem Understanding We have a dynamic binary grid. A cell containing 1 is lit, a cell containing 0 is dark. Two kinds of operations appear. A modification flips one cell. A query asks for the largest all- 1 rectangle whose border contains a given cell (x, y) . The cell does not...

CF 409H - A + B Strikes Back

CF 409H - A + B Strikes Back Rating: 1500 Tags: *special, brute force, constructive algorithms, dsu, implementation Solve time: 4m 14s Verified: yes Solution Problem Understanding The task is to read a single line containing two non-negative integers separated by whitespace and output their arithmetic sum. The input is not structured beyond this simple format, so the entire problem reduces to correctly parsing two numbers from standard input and...

CF 325D - Reclamation

CF 325D - Reclamation Rating: 2900 Tags: dsu Solve time: 1m 30s Verified: no Solution Problem Understanding We are asked to simulate a process of turning cells in a cylindrical grid from sea into land, one by one, while ensuring that a sea path connecting the top row to the bottom row always exists. The grid has r rows and c columns, with horizontal wrap-around connectivity: the leftmost and rightmost...

CF 325E - The Red Button

CF 325E - The Red Button Rating: 2800 Tags: combinatorics, dfs and similar, dsu, graphs, greedy Solve time: 58s Verified: yes Solution Problem Understanding We are asked to find a sequence of node disarmaments for a circular system of size n where node 0 is special. Node 0 must appear twice: first at the start and last at the end. Every other node must appear exactly once. After disarming a...

CF 313E - Ilya and Two Numbers

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

Codeforces Round 170 (Div. 1)

Codeforces Round 170 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1400-2800 | 9m 3s # Problem Rating Tags Accepted Time ✓ A Learning Languages 1400 dfs-and-similar, dsu 21,564 1m 34s ✓ B Set of Points 2300 constructive-algorithms, geometry 847 1m 51s C Game 2400 games, implementation 491 2m 33s D Google Code Jam 2800 dp, probabilities 372 1m 33s E Binary Tree on Plane 2400...

Codeforces Round 134 (Div. 1)

Codeforces Round 134 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1200-2900 | 11m 29s # Problem Rating Tags Accepted Time ✓ A Ice Skating 1200 brute-force, dfs-and-similar, dsu 24,319 1m 27s B Blackboard Fibonacci 2100 brute-force, math 1,093 2m 48s ✓ C Formurosa 2600 divide-and-conquer, dp, expression-parsing 368 2m 29s D Bitonix' Patrol 2900 bitmasks, brute-force, combinatorics 273 1m 37s E Alien DNA 2800 data-structures,...

CF 292D - Connected Components

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

CF 277A - Learning Languages

CF 277A - Learning Languages Rating: 1400 Tags: dfs and similar, dsu Solve time: 1m 34s Verified: yes Solution Problem Understanding We are asked to ensure that every employee at BerCorp can communicate with every other employee, either directly through a shared language or indirectly via a chain of translators. Each employee may initially know zero or more official languages, and we can pay for them to learn additional languages...

CF 217A - Ice Skating

CF 217A - Ice Skating Rating: 1200 Tags: brute force, dfs and similar, dsu, graphs Solve time: 1m 27s Verified: no Solution Problem Understanding We are given a set of snow drifts on a 2D grid with integer coordinates. Bajtek can move only in straight lines along the x or y axis, sliding from one drift until he hits another. In other words, two snow drifts are connected if they...

CF 195E - Building Forest

CF 195E - Building Forest Rating: 2000 Tags: data structures, dsu, graphs Solve time: 1m 21s Verified: yes Solution Problem Understanding We are asked to construct a special kind of directed forest where each vertex has at most one outgoing edge, and each edge carries a weight. Vertices are added one by one. When adding a vertex, we are optionally given a set of pairs consisting of an existing vertex...

CF 260D - Black and White Tree

CF 260D - Black and White Tree Rating: 2100 Tags: constructive algorithms, dsu, graphs, greedy, trees Solve time: 2m 32s Verified: no Solution Error in message stream

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 57s Verified: no Solution Problem Understanding We have a graph with n cities connected by m undirected roads. Each road either has asphalt ( 1 ) or does not ( 0 ). The king can pick a city and the workers will toggle the asphalt status...

CF 217E - Alien DNA

CF 217E - Alien DNA Rating: 2800 Tags: data structures, dsu, trees Solve time: 3m 8s Verified: yes Solution Problem Understanding We start with a DNA string. Each mutation chooses a contiguous segment, keeps that segment in place, and inserts a transformed copy immediately after it. If the chosen segment is x1 x2 x3 x4 x5 x6 then the inserted copy is x2 x4 x6 x1 x3 x5 The mutations...

CF 196E - Opening Portals

CF 196E - Opening Portals Rating: 2600 Tags: dsu, graphs, shortest paths Solve time: 2m Verified: no Solution Problem Understanding We are given a connected network of cities, some of which contain portals. Each road between cities has a positive travel time, and Pavel starts in city 1. Whenever he enters a city with a portal, that portal opens, and from that moment he can instantly teleport between any open...

CF 190E - Counter Attack

CF 190E - Counter Attack Rating: 2100 Tags: data structures, dsu, graphs, hashing, sortings Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a set of cities, but the twist is that the input does not describe the real road system directly. Instead, it describes the complement of it. Every pair of cities that appears as connected in the input actually has no road between them in...

CF 177C2 - Party

CF 177C2 - Party Rating: 1500 Tags: brute force, dfs and similar, dsu, graphs Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a set of people where some pairs are connected by friendship relations and some pairs are in conflict because they dislike each other. Friendship is transitive through chains, so connected components in the friendship graph represent groups that must be treated as inseparable if...

CF 177C1 - Party

CF 177C1 - Party Rating: 1500 Tags: dfs and similar, dsu, graphs Solve time: 1m 13s Verified: yes Solution Problem Understanding We are given a set of people, where some pairs are friends and some pairs dislike each other. Friendship forms an undirected graph, and dislike forms another set of forbidden edges. The task is to choose a subset of people such that two constraints hold simultaneously. First, if a...

Codeforces Beta Round 81

Codeforces Beta Round 81 Beta | 5 problems | 4/5 verified | Difficulty 1700-2700 | 13m 32s # Problem Rating Tags Accepted Time ✓ A Transmigration 1700 implementation 2,022 3m 6s ✓ B Dark Assembly 1800 brute-force, probabilities 906 2m 19s ✓ C Item World 2200 brute-force, implementation, sortings 390 3m 26s D Entertaining Geodetics 2700 brute-force, dsu, implementation 145 2m 8s ✓ E Lift and Throw 2500 brute-force 211...

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

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

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

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

Codeforces Round 268 (Div. 1)

Codeforces Round 268 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1500-3100 | 8m 30s # Problem Rating Tags Accepted Time ✓ A 24 Game 1500 constructive-algorithms, greedy, math 8,398 1m 19s ✓ B Two Sets 2000 2-sat, dfs-and-similar, dsu 5,269 2m 32s ✓ C Hack it! 2500 binary-search, constructive-algorithms, math 2,739 1m 18s ✓ D Tree 3100 graph-matchings 476 1m 32s E Permanent 3100 dp,...

Codeforces Round 270

Codeforces Round 270 Special | 7 problems | 5/7 verified | Difficulty 800-2800 | 12m 18s # Problem Rating Tags Accepted Time ✓ A Design Tutorial: Learn from Math 800 math, number-theory 70,755 1m 22s ✓ B Design Tutorial: Learn from Life 1300 7,645 1m 44s ✓ C Design Tutorial: Make It Nondeterministic 1400 greedy 6,517 1m 16s ✓ D Design Tutorial: Inverse the Problem 1900 dfs-and-similar, dsu, shortest-paths 6,519...

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

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

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

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

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

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

Codeforces Round 252 (Div. 2)

Codeforces Round 252 (Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2400 | 7m 9s # Problem Rating Tags Accepted Time ✓ A Valera and Antique Items 1000 implementation 19,290 1m 21s ✓ B Valera and Fruits 1400 greedy, implementation 7,510 1m 21s ✓ C Valera and Tubes 1500 constructive-algorithms, dfs-and-similar, implementation 11,921 1m 35s D Valera and Swaps 2100 constructive-algorithms, dsu, graphs 1,200 1m 26s...

Codeforces Round 254 (Div. 2)

Codeforces Round 254 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 1200-1400 | 3m 10s # Problem Rating Tags Accepted Time ✓ A DZY Loves Chessboard 1200 dfs-and-similar, implementation 33,654 1m 21s ✓ B DZY Loves Chemistry 1400 dfs-and-similar, dsu, greedy 14,750 1m 49s ✓

VK Cup 2012 Finals, Practice Session

VK Cup 2012 Finals, Practice Session Special | 3 problems | 3/3 verified | Difficulty 1600-2400 | 11m 47s # Problem Rating Tags Accepted Time ✓ A Multicolored Marbles 1600 dp, math 2,845 5m 3s ✓ B Pixels 2100 constructive-algorithms, math 487 1m 41s ✓ C Trails and Glades 2400 constructive-algorithms, dsu, graphs 875 5m 3s ✓

Codeforces Round 119 (Div. 1)

Codeforces Round 119 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1500-2900 | 10m 3s # Problem Rating Tags Accepted Time ✓ A Permutations 1500 greedy 3,042 1m 30s ✓ B AlgoRace 1800 dp, shortest-paths 2,344 2m 5s ✓ C Weak Memory 2000 dfs-and-similar, dsu 1,578 2m 12s ✓ D BRT Contract 2800 data-structures 583 1m 54s ✓ E Heaven Tour 2900 data-structures, greedy 117 2m...

ABBYY Cup 2.0 - Easy

ABBYY Cup 2.0 - Easy Special | 14 problems | 7/14 verified | Difficulty 800-2600 | 22m 32s # Problem Rating Tags Accepted Time ✓ A1 Good Matrix Elements 800 implementation 11,501 1m 37s A2 Good Matrix Elements 800 implementation 8,564 3m 13s ✓ B1 Rectangular Game 1000 number-theory 5,100 4m 29s B2 Rectangular Game 1200 number-theory 3,361 1m 40s ✓ C1 Party 1500 dfs-and-similar, dsu, graphs 2,997 1m 13s...

Codeforces Round 111 (Div. 2)

Codeforces Round 111 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 900-2400 | 8m 5s # Problem Rating Tags Accepted Time ✓ A Twins 900 greedy, sortings 143,576 1m 15s ✓ B Unlucky Ticket 1100 greedy, sortings 15,550 1m 29s ✓ C Find Pair 1700 implementation, math, sortings 3,719 1m 47s ✓ D Edges in MST 2300 dfs-and-similar, dsu, graphs 3,350 1m 21s ✓ E Buses...

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

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

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

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

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

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

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

Codeforces Beta Round 84 (Div. 1 Only)

Codeforces Beta Round 84 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1000-2700 | 11m 6s # Problem Rating Tags Accepted Time ✓ A Lucky Sum of Digits 1000 brute-force, implementation 19,819 2m 22s ✓ B Lucky Probability 1900 brute-force, probabilities 1,780 2m 23s ✓ C Lucky Tree 1900 dp, dsu, trees 4,117 2m 23s ✓ D Lucky Sorting 2000 constructive-algorithms, sortings 894 1m 47s...

Codeforces Beta Round 80 (Div. 1 Only)

Codeforces Beta Round 80 (Div. 1 Only) Div. 1 | 5 problems | 3/5 verified | Difficulty 1100-2900 | 10m 20s # Problem Rating Tags Accepted Time ✓ A Testing Pants for Sadness 1100 greedy, implementation, math 6,572 1m 39s ✓ B Cthulhu 1500 dfs-and-similar, dsu, graphs 10,648 1m 43s ✓ C Russian Roulette 1900 constructive-algorithms, greedy 1,049 2m ✓ D Time to Raid Cowavans 2100 brute-force, data-structures, sortings 2,526...

Codeforces Beta Round 75 (Div. 1 Only)

Codeforces Beta Round 75 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1500-2600 | 12m 45s # Problem Rating Tags Accepted Time ✓ A Newspaper Headline 1500 greedy, strings 3,954 1m 57s ✓ B Queue 1500 binary-search, data-structures 7,733 2m 10s ✓ C Ski Base 2300 combinatorics, dsu, graphs 1,011 3m 29s ✓ D Grocer's Problem 2600 constructive-algorithms, graphs, greedy 297 2m 25s ✓ E...

All-Ukrainian School Olympiad in Informatics

All-Ukrainian School Olympiad in Informatics Special | 6 problems | 4/6 verified | Difficulty 1700-2700 | 9m 50s # Problem Rating Tags Accepted Time ✓ A Gift 2200 dsu, graphs, sortings 2,221 2m 12s ✓ B Mice 2100 greedy, two-pointers 801 1m 53s C Mutation 2700 bitmasks, dp, math 369 2m 6s ✓ D Plus and xor 1700 dp, greedy, math 2,403 1m 46s ✓ E Points 1700 implementation, math...

Codeforces Beta Round 56

Codeforces Beta Round 56 Beta | 5 problems | 4/5 verified | Difficulty 1300-2600 | 11m 17s # Problem Rating Tags Accepted Time ✓ A Where Are My Flakes? 1300 implementation, two-pointers 4,283 1m 40s ✓ B Serial Time! 1400 dfs-and-similar, dsu 5,308 2m 8s C Mushroom Strife 2100 brute-force, dfs-and-similar 654 2m 15s ✓ D Savior 2500 brute-force, dsu, math 547 2m 1s ✓ E Mushroom Gnomes 2600 math,...

Codeforces Beta Round 68

Codeforces Beta Round 68 Beta | 5 problems | 4/5 verified | Difficulty 1000-2800 | 22m 53s # Problem Rating Tags Accepted Time ✓ A Room Leader 1000 implementation 5,865 1m 35s ✓ B Train 1500 dp, games, greedy 1,785 2m 11s ✓ C Chessboard Billiard 2100 dfs-and-similar, dsu, graphs 1,412 1m 36s ✓ D Hanger 2400 data-structures 413 1m 7s ✓ E Shift It! 2800 constructive-algorithms 185 16m 24s

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

School Team Contest 3 (Winter Computer School 2010/11) Special | 10 problems | 7/10 verified | Difficulty 900-2500 | 19m 28s # Problem Rating Tags Accepted Time ✓ A Codecraft III 900 implementation 8,108 1m 14s ✓ B School 2200 dp, dsu 319 2m 6s ✓ C Dancing Lessons 1900 data-structures 1,147 1m 24s ✓ D Event Dates 1900 greedy, meet-in-the-middle, sortings 1,973 1m 35s ✓ E Director 2000 constructive-algorithms,...

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) Beta | 7 problems | 6/7 verified | Difficulty 800-2500 | 10m 14s # Problem Rating Tags Accepted Time ✓ A Ball Game 800 brute-force, implementation 9,933 1m 23s ✓ B T-shirts from Sponsor 1100 implementation 4,135 1m 13s ✓ C Hamsters and Tigers 1600 two-pointers 2,877 1m 18s ✓ D Parking Lot 1800 data-structures,...

Codeforces Beta Round 36

Codeforces Beta Round 36 Beta | 5 problems | 2/5 verified | Difficulty 1300-2600 | 9m 36s # Problem Rating Tags Accepted Time ✓ A Extra-terrestrial Intelligence 1300 implementation 3,547 1m 21s ✓ B Fractal 1600 implementation 2,034 1m 52s ✓ C Bowls 2200 geometry, implementation 380 2m 5s D New Game with a Chess Piece 2300 games 769 1m 43s E Two Paths 2600 constructive-algorithms, dsu, graphs 614 2m...

Codeforces Beta Round 28 (Codeforces format)

Codeforces Beta Round 28 (Codeforces format) Beta | 5 problems | 4/5 verified | Difficulty 1600-2800 | 8m 33s # Problem Rating Tags Accepted Time ✓ A Bender Problem 1600 implementation 970 1m 17s ✓ B pSort 1600 dfs-and-similar, dsu, graphs 5,515 1m 33s ✓ C Bath Queue 2200 combinatorics, dp, probabilities 1,287 1m 44s ✓ D Don't fear, DravDe is kind 2400 binary-search, data-structures, dp 676 1m 40s ✓...

Codeforces Beta Round 25 (Div. 2 Only)

Codeforces Beta Round 25 (Div. 2 Only) Div. 2 | 5 problems | 5/5 verified | Difficulty 1100-2200 | 6m 12s # Problem Rating Tags Accepted Time ✓ A IQ test 1300 brute-force 103,842 1m 7s ✓ B Phone numbers 1100 implementation 11,249 1m 24s ✓ C Roads in Berland 1900 graphs, shortest-paths 8,040 58s ✓ D Roads not only in Berland 1900 dsu, graphs, trees 15,573 1m 15s ✓...

Codeforces Beta Round 17

Codeforces Beta Round 17 Beta | 5 problems | 4/5 verified | Difficulty 1000-2900 | 16m 51s # Problem Rating Tags Accepted Time ✓ A Noldbach problem 1000 brute-force, math, number-theory 21,391 1m 46s ✓ B Hierarchy 1500 dfs-and-similar, dsu, greedy 6,085 1m 34s ✓ C Balance 2500 dp 1,026 6m 37s D Notepad 2400 number-theory 1,327 3m 4s ✓ E Palisection 2900 strings 1,990 3m 50s ✓

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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