dfs-and-similar

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

CF 2222G - Statistics on Tree

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

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

CF 2227H - Fallen Leaves

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

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

CF 1975E - Chain Queries

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

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

CF 1975D - Paint the Tree

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

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

CF 1949C - Annual Ants' Gathering

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

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

CF 487E - Tourists

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

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

CF 1942D - Learning to Paint

CF 1942D - Learning to Paint Rating: 2100 Tags: binary search, data structures, dfs and similar, dp, greedy, implementation, sortings Solve time: 1m 30s Verified: no Solution Problem Understanding We are asked to help Elsie evaluate her paintings on a 1D canvas of n cells. Each cell can be painted or left empty, and the painting's beauty is determined by a 2D array a . Specifically, for every maximal contiguous...

Practice › Codeforces Solutions › April Fools Day Contest 2024 ›

CF 1952G - Mathematician Takeover

CF 1952G - Mathematician Takeover Rating: - Tags: *special, binary search, dfs and similar, math Solve time: 1m 8s Verified: no Solution Problem Understanding We are given a single real number $x$ between 1 and 100, expressed to exactly three decimal places. The task is to compute a real number result from $x$, with the requirement that the answer's absolute or relative error does not exceed $10^{-4}$. The problem does...

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

CF 486D - Valid Sets

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

Practice › Codeforces Solutions ›

Codeforces Round 282 (Div. 1)

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

Practice › Codeforces Solutions ›

April Fools Day Contest 2024

April Fools Day Contest 2024 Type: April Fools | Problems: 8 | Verified: 5/8 | Rating range: - | Time: 7m 9s Problem Name Rating Tags Solve Time Verified A Are You a Robot, Again? - *special, strings 32s ✓ B Is it stated? - *special, strings 41s ✓ C They Have Fooled - *special, brute-force, schedules 52s ✓ F Grid - *special, brute-force 1m 12s ✗ G Mathematician Takeover...

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

CF 1975F - Set

CF 1975F - Set Rating: 2600 Tags: bitmasks, brute force, combinatorics, dfs and similar, divide and conquer, dp, math Solve time: 5m 17s Verified: no Solution

Practice › Codeforces Solutions ›

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 11 | Verified: 5/11 | Rating range: 1500-3300 | Time: 28m 1s Problem Name Rating Tags Solve Time Verified A Grove 3300 brute-force, dfs-and-similar, dp 2m 41s ✓ B Charming Meals 1500 binary-search, brute-force, greedy 1m 44s ✓ C Annual Ants' Gathering 1900 dfs-and-similar, dp, greedy 4m 48s ✓ D Funny or Scary? 2600 constructive-algorithms...

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

CF 1946F - Nobody is needed

CF 1946F - Nobody is needed Rating: 2500 Tags: 2-sat, data structures, dfs and similar, dp Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a permutation of the numbers from 1 to n. Each query gives us a segment $[l, r]$, and we are asked to count how many strictly increasing index sequences we can choose inside this segment such that every next chosen value is...

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

CF 1943C - Tree Compass

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

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

CF 1976E - Splittable Permutations

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

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

CF 1949A - Grove

CF 1949A - Grove Rating: 3300 Tags: brute force, dfs and similar, dp, geometry, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding Every tree is planted at an integer lattice point. Around that point we place a disk of radius r , representing the root system. Two conditions must hold. The entire disk must stay inside the square lawn. Since the lawn is the square [0,n] × [0,n]...

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

CF 1967D - Long Way to be Non-decreasing

CF 1967D - Long Way to be Non-decreasing Rating: 2800 Tags: binary search, dfs and similar, graphs, implementation, shortest paths, two pointers Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given an array where each position contains a value in the range $1$ to $m$, and a second array that defines a deterministic transformation on values: every value $x$ has a fixed replacement $b_x$. One operation, called...

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

CF 1976F - Remove Bridges

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

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

CF 494D - Birthday

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

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

CF 490F - Treeland Tour

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

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

CF 1950G - Shuffling Songs

CF 1950G - Shuffling Songs Rating: 1900 Tags: bitmasks, dfs and similar, dp, graphs, hashing, implementation, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding Each song has two attributes, a genre and a writer. After removing some songs, we are allowed to reorder the remaining songs arbitrarily. The goal is to arrange them so that every pair of neighboring songs shares at least one attribute: either the same...

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

CF 1955G - GCD on a grid

CF 1955G - GCD on a grid Rating: 1900 Tags: brute force, dfs and similar, dp, implementation, math, number theory Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a rectangular grid of integers. A move starts at the top-left cell and ends at the bottom-right cell, and at each step we can only go either one cell down or one cell right. Every such move sequence...

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

CF 1948C - Arrow Path

CF 1948C - Arrow Path Rating: 1300 Tags: brute force, constructive algorithms, dfs and similar, dp, graphs, shortest paths Solve time: 56s Verified: yes Solution Problem Understanding We have a 2-row grid with $n$ columns, and each cell contains an arrow pointing either left or right. The robot starts at the top-left corner, and each second it first moves to an adjacent cell (up, down, left, right) and then follows...

Practice › Codeforces Solutions ›

Codeforces Round 277 (Div. 2)

Codeforces Round 277 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 800-2200 | Time: 26m 47s Problem Name Rating Tags Solve Time Verified A Calculating Function 800 implementation, math 10m 49s ✗ B OR in Matrix 1300 greedy, hashing, implementation 5m 23s ✗ D Valid Sets 2100 dfs-and-similar, dp, math 5m 18s ✗ E LIS of Sequence 2200 data-structures, dp, greedy 5m 17s ✗

Practice › Codeforces Solutions ›

Educational Codeforces Round 163 (Rated for Div. 2)

Educational Codeforces Round 163 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-3100 | Time: 11m 57s Problem Name Rating Tags Solve Time Verified A Special Characters 800 brute-force, constructive-algorithms 1m 17s ✗ C Arrow Path 1300 brute-force, constructive-algorithms, dfs-and-similar 56s ✓ D Tandem Repeats? 1700 brute-force, strings, two-pointers 2m 48s ✗ E Clique Partition 2100 brute-force, constructive-algorithms, graphs 2m 41s ✗...

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

CF 490D - Chocolate

CF 490D - Chocolate Rating: 1900 Tags: brute force, dfs and similar, math, meet-in-the-middle, number theory Solve time: 5m 18s Verified: no Solution

Practice › Codeforces Solutions › Bayan 2015 Contest Warm Up ›

CF 475E - Strongly Connected City 2

CF 475E - Strongly Connected City 2 Rating: 2700 Tags: dfs and similar Solve time: 2m 26s Verified: yes Solution Problem Understanding We start with a connected undirected graph. Every edge must be assigned a direction. After all directions are chosen, some ordered pairs of vertices $(u,v)$ will satisfy that there is a directed path from $u$ to $v$. The goal is not to make the graph strongly connected. The...

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

CF 463D - Gargari and Permutations

CF 463D - Gargari and Permutations Rating: 1900 Tags: dfs and similar, dp, graphs, implementation Solve time: 58s Verified: yes Solution Problem Understanding We are given k permutations of the numbers from 1 to n . A permutation is simply a rearrangement of these numbers. Our goal is to find the length of the longest sequence of numbers that appears in the same relative order in all k permutations. In...

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

CF 478E - Wavy numbers

CF 478E - Wavy numbers Rating: 2900 Tags: brute force, dfs and similar, meet-in-the-middle, sortings Solve time: 1m 37s Verified: no Solution Problem Understanding We are asked to work with a special class of integers defined purely by their digit structure. A number is called “wavy” if, whenever you look at any digit that is not at the boundary, that digit must sit either strictly above both its neighbors or...

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

CF 455B - A Lot of Games

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

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

CF 453C - Little Pony and Summer Sun Celebration

CF 453C - Little Pony and Summer Sun Celebration Rating: 2200 Tags: constructive algorithms, dfs and similar, graphs Solve time: 2m 13s Verified: no Solution Problem Understanding We are given an undirected graph and, for every vertex, the parity of how many times that vertex must appear in a walk. A walk is represented by a sequence of vertices. Consecutive vertices in the sequence must be connected by an edge....

Practice › Codeforces Solutions › Bayan 2015 Contest Warm Up ›

CF 475B - Strongly Connected City

CF 475B - Strongly Connected City Rating: 1400 Tags: brute force, dfs and similar, graphs, implementation Solve time: 59s Verified: yes Solution Problem Understanding We are asked to determine if a city with a grid of horizontal and vertical streets is "strongly connected" once each street is made one-way. The city can be visualized as a grid of intersections, with n horizontal streets and m vertical streets forming n ×...

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

CF 461B - Appleman and Tree

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

Practice › Codeforces Solutions ›

Codeforces Round 267 (Div. 2)

Codeforces Round 267 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2400 | Time: 6m 31s Problem Name Rating Tags Solve Time Verified A George and Accommodation 800 implementation 1m 1s ✓ B Fedor and New Game 1100 bitmasks, brute-force, constructive-algorithms 1m 19s ✓ C George and Job 1700 dp, implementation 1m 35s ✗ D Fedor and Essay 2400 dfs-and-similar, dp, graphs 1m 26s...

Practice › Codeforces Solutions ›

Codeforces Round 263 (Div. 1)

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

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

CF 468B - Two Sets

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

Practice › Codeforces Solutions ›

Codeforces Round 260 (Div. 1)

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

Practice › Codeforces Solutions ›

Codeforces Round 270

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

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

CF 467D - Fedor and Essay

CF 467D - Fedor and Essay Rating: 2400 Tags: dfs and similar, dp, graphs, hashing, strings Solve time: 1m 26s Verified: no Solution Problem Understanding We are given an essay, which is a sequence of words, and a dictionary of synonym pairs. Each synonym pair allows us to replace one word with another, but only in the direction specified. Fedor wants to modify his essay to minimize the number of...

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472D - Design Tutorial: Inverse the Problem

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

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

CF 455C - Civilization

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

Practice › Codeforces Solutions ›

Codeforces Round 259 (Div. 1)

Codeforces Round 259 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1600-3100 | Time: 8m 34s Problem Name Rating Tags Solve Time Verified A Little Pony and Expected Maximum 1600 probabilities 1m 46s ✓ B Little Pony and Harmony Chest 2000 bitmasks, brute-force, dp 1m 19s ✓ C Little Pony and Summer Sun Celebration 2200 constructive-algorithms, dfs-and-similar, graphs 2m 13s ✗ D Little Pony...

Practice › Codeforces Solutions ›

Codeforces Round 268 (Div. 1)

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

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

CF 463E - Caisa and Tree

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

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

CF 466E - Information Graph

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

Practice › Codeforces Solutions ›

Codeforces Round 264 (Div. 2)

Codeforces Round 264 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2100 | Time: 4m 50s Problem Name Rating Tags Solve Time Verified A Caisa and Sugar 1200 brute-force, implementation 1m ✓ B Caisa and Pylons 1100 brute-force, implementation, math 59s ✓ C Gargari and Bishops 1900 greedy, hashing, implementation 1m 6s ✓ D Gargari and Permutations 1900 dfs-and-similar, dp, graphs 58s ✓ E...

Practice › Codeforces Solutions ›

Bayan 2015 Contest Warm Up

Bayan 2015 Contest Warm Up Type: Special | Problems: 6 | Verified: 4/6 | Rating range: 1100-2900 | Time: 11m 19s Problem Name Rating Tags Solve Time Verified A Bayan Bus 1100 implementation 1m 59s ✓ B Strongly Connected City 1400 brute-force, dfs-and-similar, graphs 59s ✓ C Kamal-ol-molk's Painting 2100 brute-force, constructive-algorithms, greedy 2m 56s ✗ D CGCDSSQ 2000 brute-force, data-structures, math 1m 11s ✓ E Strongly Connected City 2...

Practice › Codeforces Solutions ›

Codeforces Round 190 (Div. 1)

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

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C2 - Party

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

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

CF 246E - Blood Cousins Return

CF 246E - Blood Cousins Return Rating: 2400 Tags: binary search, data structures, dfs and similar, dp, sortings Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a rooted forest describing family relations. Every person has a name and at most one parent. Multiple roots are allowed because some people may have no ancestor at all. For each query (v, k) , we need the number of...

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

CF 164A - Variable, or There and Back Again

CF 164A - Variable, or There and Back Again Rating: 1700 Tags: dfs and similar, graphs Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given a directed graph where every node represents a program state. Each state does one of three things to a variable: 0 means the variable is ignored. 1 means the variable is assigned a new value. 2 means the variable is used. A...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Final

Croc Champ 2012 - Final Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1700-2900 | Time: 10m 12s Problem Name Rating Tags Solve Time Verified A Headquarters 1700 constructive-algorithms, math 1m 52s ✓ B Zoo 1700 brute-force, geometry 1m 27s ✓ C Cyclic Coloring 2200 dfs-and-similar 3m 32s ✓ D T-shirt 2700 dp, greedy, probabilities 1m 15s ✓ E Candy Shop 2900 greedy 2m 6s ✓

Practice › Codeforces Solutions ›

Friday the 13th, Programmers Day

Friday the 13th, Programmers Day Type: Special | Problems: 3 | Verified: 2/3 | Rating range: 1500-2700 | Time: 5m 36s Problem Name Rating Tags Solve Time Verified A Expecting Trouble 1500 *special, probabilities 1m 31s ✓ D Chain Letter 2200 *special, dfs-and-similar, graphs 2m 12s ✓ F Superstitions Inspection 2700 *special 1m 53s ✗

Practice › Codeforces Solutions ›

April Fools Day Contest 2013

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

Practice › Codeforces Solutions ›

VK Cup 2012 Round 3

VK Cup 2012 Round 3 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1700-3100 | Time: 9m 50s Problem Name Rating Tags Solve Time Verified A Variable, or There and Back Again 1700 dfs-and-similar, graphs 1m 51s ✓ B Ancient Berland Hieroglyphs 2000 two-pointers 1m 30s ✓ C Machine Programming 2400 flows, graphs 2m 16s ✓ D Minimum Diameter 3100 binary-search, brute-force 2m 18s ✗ E Polycarpus...

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

CF 172E - BHTML+BCSS

CF 172E - BHTML+BCSS Rating: 2200 Tags: *special, dfs and similar, expression parsing Solve time: 2m 21s Verified: no Solution Problem Understanding We are given a simplified HTML-like document. Every tag is either an opening tag like <a> , a closing tag like </a> , or a self-closing tag like <a/> . The document is guaranteed to be properly nested, so every opening tag has exactly one matching closing tag....

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

CF 321C - Ciel the Commander

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 - Finals (online version) ›

CF 331D1 - Escaping on Beaveractor

CF 331D1 - Escaping on Beaveractor Rating: 2400 Tags: dfs and similar, implementation Solve time: 3m 8s Verified: no Solution Problem Understanding We have a square campus with coordinates from (0, 0) to (b, b) . Inside the square there are several directed segments, called arrows. Every arrow is either horizontal or vertical, and no two arrows intersect or even touch. A Beaveractor starts at some point with an initial...

Practice › Codeforces Solutions ›

Codeforces Round 256 (Div. 2)

Codeforces Round 256 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 800-2200 | Time: 3m 43s Problem Name Rating Tags Solve Time Verified A Rewards 800 implementation 1m 14s ✓ D Multiplication Table 1800 binary-search, brute-force 1m 14s ✓ E Divisors 2200 brute-force, dfs-and-similar, implementation 1m 15s ✗

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

CF 406D - Hill Climbing

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

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

CF 217A - Ice Skating

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

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

CF 190C - STL

CF 190C - STL Rating: 1500 Tags: dfs and similar Solve time: 1m 49s Verified: yes Solution Problem Understanding We are given a sequence of words that originally described a type in a fictional language. The language has only two valid constructions. The simplest type is int . The second type is pair<type,type> , where each side is itself another valid type. The punctuation was removed before the words were...

Practice › Codeforces Solutions ›

ABBYY Cup 3.0

ABBYY Cup 3.0 Type: Special | Problems: 12 | Verified: 6/12 | Rating range: 1100-2400 | Time: 30m 35s Problem Name Rating Tags Solve Time Verified A1 Special Task 1100 greedy 1m 30s ✗ B1 EKG 1500 brute-force, dfs-and-similar 3m 27s ✗ B2 EKG 1600 dfs-and-similar, dp 3m 21s ✗ C1 Tidying Up 2200 flows 1m 56s ✓ C2 Tidying Up 2300 flows, graph-matchings 3m 19s ✓ D2 PE Lesson...

Practice › Codeforces Solutions ›

Codeforces Round 150 (Div. 2)

Codeforces Round 150 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 900-1600 | Time: 4m 21s Problem Name Rating Tags Solve Time Verified A Dividing Orange 900 implementation 3m 13s ✗ B Undoubtedly Lucky Numbers 1600 bitmasks, brute-force, dfs-and-similar 1m 8s ✓

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

CF 225D - Snake

CF 225D - Snake Rating: 2200 Tags: bitmasks, dfs and similar, graphs, implementation Solve time: 58s Verified: yes Solution Problem Understanding We are asked to simulate the movement of a snake on a small grid and determine the minimal number of moves required for the snake to reach an apple. The grid contains walls, empty squares, the snake itself, and one apple. The snake is represented as consecutive numbered segments...

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

CF 237D - T-decomposition

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

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

CF 251E - Tree and Table

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

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 1

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

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

CF 427C - Checkposts

CF 427C - Checkposts Rating: 1700 Tags: dfs and similar, graphs, two pointers Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given a directed graph where each node represents a city junction, and each directed edge represents a one-way road. Each junction has a cost to build a police checkpost. A checkpost at junction i protects all junctions reachable from i and able to return to i...

Practice › Codeforces Solutions ›

Codeforces Round 245 (Div. 1)

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

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

CF 144D - Missile Silos

CF 144D - Missile Silos Rating: 1900 Tags: data structures, dfs and similar, graphs, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph representing cities and roads. City s is the capital. A missile silo may be located either exactly on a city or at some interior point of a road. A position is valid if its shortest-path distance to...

Practice › Codeforces Solutions ›

Codeforces Round 103 (Div. 2)

Codeforces Round 103 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 8m 5s Problem Name Rating Tags Solve Time Verified A Arrival of the General 800 implementation 1m 52s ✓ B Meeting 1300 implementation 1m 15s ✓ C Anagram Search 1500 implementation, strings 1m 23s ✓ D Missile Silos 1900 data-structures, dfs-and-similar, graphs 2m 10s ✓ E Competition 2200 data-structures, greedy...

Practice › Codeforces Solutions ›

Codeforces Round 161 (Div. 2)

Codeforces Round 161 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 800-2000 | Time: 5m 38s Problem Name Rating Tags Solve Time Verified A Beautiful Matrix 800 implementation 1m 31s ✗ C Circle of Numbers 2000 brute-force, dfs-and-similar, implementation 1m 10s ✓ D Cycle in Graph 1800 dfs-and-similar, graphs 2m 57s ✗

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

CF 253C - Text Editor

CF 253C - Text Editor Rating: 1600 Tags: data structures, dfs and similar, graphs, greedy, shortest paths Solve time: 53s Verified: yes Solution Problem Understanding We are given a text editor that stores several lines of text. Each line has a known length, and the cursor is allowed to sit not only on characters but also in the gap positions before the first character and after the last character. So...

Practice › Codeforces Solutions ›

Codeforces Round 134 (Div. 1)

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

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

CF 212E - IT Restaurants

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

Practice › Codeforces Solutions ›

Codeforces Round 202 (Div. 1)

Codeforces Round 202 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1600-2800 | Time: 8m 10s Problem Name Rating Tags Solve Time Verified A Mafia 1600 binary-search, math, sortings 4m 1s ✓ D Turtles 2500 dp, matrices 2m 37s ✗ E Pilgrims 2800 dfs-and-similar, dp, trees 1m 32s ✗

Practice › Codeforces Solutions ›

Codeforces Round 181 (Div. 2)

Codeforces Round 181 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1500-2300 | Time: 5m 24s Problem Name Rating Tags Solve Time Verified B Coach 1500 brute-force, dfs-and-similar, graphs 2m 18s ✓ D Painting Square 2300 dp, fft 1m 49s ✗ E Empire Strikes Back 2300 binary-search, math, number-theory 1m 17s ✓

Practice › Codeforces Solutions ›

Codeforces Round 148 (Div. 1)

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

Practice › Codeforces Solutions ›

Codeforces Round 188 (Div. 1)

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

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

CF 291E - Tree-String Problem

CF 291E - Tree-String Problem Rating: 2000 Tags: *special, dfs and similar, hashing, strings Solve time: 1m 51s Verified: yes Solution Problem Understanding We have a rooted tree with root 1 . Every edge from a parent to a child contains a lowercase string. If we walk downward through the tree and read characters along the edges, we obtain a long text embedded into the tree. A position is not...

Practice › Codeforces Solutions ›

Codeforces Round 131 (Div. 1)

Codeforces Round 131 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1700-2700 | Time: 7m 23s Problem Name Rating Tags Solve Time Verified A Game 1700 dfs-and-similar, greedy 52s ✓ B Numbers 1900 combinatorics, dp 54s ✗ C Relay Race 2000 dp 2m 58s ✓ D Stars 2300 constructive-algorithms, geometry 1m 36s ✗ E Two Permutations 2700 data-structures, hashing, strings 1m 3s ✓

Practice › Codeforces Solutions ›

ABBYY Cup 2.0 - Easy

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

Practice › Codeforces Solutions ›

Codeforces Round 119 (Div. 1)

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

Practice › Codeforces Solutions ›

Croc Champ 2013 - Round 1

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

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

CF 165E - Compatible Numbers

CF 165E - Compatible Numbers Rating: 2200 Tags: bitmasks, brute force, dfs and similar, dp Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given an array of integers, and for every element we must find another array element whose bitwise AND with it is zero. Two numbers are compatible exactly when they do not share any bit set to 1 . For example, if we look at...

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

CF 277A - Learning Languages

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316B2 - EKG

CF 316B2 - EKG Rating: 1600 Tags: dfs and similar, dp Solve time: 3m 21s Verified: no Solution Problem Understanding We are asked to reconstruct the possible positions of a specific beaver in a queue based on partial ordering information. Each beaver either knows who should be directly in front of them in the line, or does not know, represented by zero. The beavers are numbered from 1 to n...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Qualification Round

Croc Champ 2012 - Qualification Round Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 800-2200 | Time: 11m 42s Problem Name Rating Tags Solve Time Verified A Phone Code 800 *special, brute-force, implementation 3m ✓ B Pseudorandom Sequence Period 1200 *special, implementation, number-theory 3m 33s ✓ C Bus 1500 *special, implementation, sortings 1m 19s ✓ D Calendar Reform 1500 *special, number-theory 1m 29s ✓ E BHTML+BCSS 2200...

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

CF 213A - Game

CF 213A - Game Rating: 1700 Tags: dfs and similar, greedy Solve time: 52s Verified: yes Solution Problem Understanding We are given a game split into n parts. Each part must be completed on a specific computer, and some parts depend on others, forming a dependency graph without cycles. Rubik can start at any computer and spends exactly one hour to complete a part. Moving between computers has asymmetric costs:...

Practice › Codeforces Solutions ›

Coder-Strike 2014 - Round 1

Coder-Strike 2014 - Round 1 Type: Special | Problems: 4 | Verified: 1/4 | Rating range: 900-2000 | Time: 8m 35s Problem Name Rating Tags Solve Time Verified A Poster 900 greedy, implementation 2m 3s ✗ C Pattern 1200 implementation, strings 2m ✗ D Giving Awards 2000 dfs-and-similar 1m 55s ✓ E E-mail Addresses 1900 implementation 2m 37s ✗

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

CF 217D - Bitonix' Patrol

CF 217D - Bitonix' Patrol Rating: 2900 Tags: bitmasks, brute force, combinatorics, dfs and similar, math Solve time: 3m 51s Verified: no Solution Problem Understanding The orbit contains n stations placed uniformly on a circle. Adjacent stations are exactly m miles apart, so the whole circumference equals n * m . A patrol is valid if Bitonix starts at some station, uses any subset of the fuel tanks in arbitrary...

Practice › Codeforces Solutions ›

Codeforces Round 150 (Div. 1)

Codeforces Round 150 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1600-3000 | Time: 11m 4s Problem Name Rating Tags Solve Time Verified A The Brand New Function 1600 bitmasks 1m 27s ✓ B Hydra 2000 graphs, sortings 3m 20s ✗ C Colorado Potato Beetle 2200 dfs-and-similar, implementation 1m 37s ✗ D Cubes 2700 data-structures, dp, geometry 3m 9s ✓ E Matrix 3000 data-structures...

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

CF 424E - Colored Jenga

CF 424E - Colored Jenga Rating: 2500 Tags: dfs and similar, dp, probabilities Solve time: 6m 29s Verified: no Solution Problem Understanding We are given a vertical stack of levels, each level containing three colored blocks arranged left, middle, right. The tower has a physical constraint: it is only stable if every non-top level has at least one remaining block, and additionally a level is unstable if it is reduced...

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

CF 238C - World Eater Brothers

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

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

CF 187C - Weak Memory

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

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

CF 173B - Chamber of Secrets

CF 173B - Chamber of Secrets Rating: 1800 Tags: dfs and similar, shortest paths Solve time: 1m 49s Verified: yes Solution Problem Understanding The Chamber of Secrets is represented as a grid of size n by m , where each cell is either empty or contains a column. A basilisk is stationed in the bottom-right corner and looks left, while a person trying to enter starts at the top-left corner...

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

CF 300B - Coach

CF 300B - Coach Rating: 1500 Tags: brute force, dfs and similar, graphs Solve time: 2m 18s Verified: yes Solution Problem Understanding We can think of the students as vertices of an undirected graph. Every friendship relation means two students must belong to the same team. Since each team has exactly three students, every connected component of this graph must fit entirely inside one team. The task is to partition...

Practice › Codeforces Solutions › Coder-Strike 2014 - Round 1 ›

CF 412D - Giving Awards

CF 412D - Giving Awards Rating: 2000 Tags: dfs and similar Solve time: 1m 55s Verified: yes Solution Problem Understanding We have a directed graph of debts. An edge a -> b means employee a owes money to employee b . We must arrange all employees in a sequence such that for every pair of consecutive employees (x, y) in the sequence, there is no edge x -> y ....

Practice › Codeforces Solutions ›

Codeforces Round 170 (Div. 1)

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

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

CF 404C - Restore Graph

CF 404C - Restore Graph Rating: 1800 Tags: dfs and similar, graphs, sortings Solve time: 3m 31s Verified: no Solution Problem Understanding We are given a sequence of distances from a single unknown root vertex in an unknown undirected simple graph. Each vertex has a known shortest-path distance to that root, and we are also told that in the original graph every vertex had degree at most k. The task...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Round 1

Croc Champ 2012 - Round 1 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1300-2600 | Time: 10m 55s Problem Name Rating Tags Solve Time Verified A Rock-Paper-Scissors 1300 implementation, math 1m 40s ✓ B Chamber of Secrets 1800 dfs-and-similar, shortest-paths 1m 49s ✓ C Spiral Maximum 1900 brute-force, dp 2m 41s ✗ D Deputies 2500 constructive-algorithms, graphs, greedy 3m 4s ✓ E Camping Groups 2600 data-structures,...

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

CF 348E - Pilgrims

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

Practice › Codeforces Solutions ›

Codeforces Round 107 (Div. 1)

Codeforces Round 107 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1400-3000 | Time: 11m 8s Problem Name Rating Tags Solve Time Verified A Win or Freeze 1400 games, math, number-theory 2m 2s ✗ B Quantity of Strings 1600 combinatorics, dfs-and-similar, graphs 1m 40s ✓ C Smart Cheater 2200 data-structures, math, probabilities 2m 11s ✓ D Mission Impassable 2600 dp, strings 2m 26s ✓...

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

CF 150B - Quantity of Strings

CF 150B - Quantity of Strings Rating: 1600 Tags: combinatorics, dfs and similar, graphs, math Solve time: 1m 40s Verified: yes Solution Problem Understanding We want to count strings of length n built from an alphabet of size m , under one strong restriction: every substring of length k must be a palindrome. A substring of length k starting at position i contains characters $$s_i, s_{i+1}, \dots, s_{i+k-1}$$ and being...

Practice › Codeforces Solutions ›

Codeforces Round 141 (Div. 2)

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

Practice › Codeforces Solutions ›

Codeforces Round 147 (Div. 2)

Codeforces Round 147 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 1000-2000 | Time: 9m 35s Problem Name Rating Tags Solve Time Verified A Free Cash 1000 implementation 3m 17s ✓ C Primes on Interval 1600 binary-search, number-theory, two-pointers 4m 4s ✓ D T-decomposition 2000 dfs-and-similar, graphs, greedy 2m 14s ✓

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316B1 - EKG

CF 316B1 - EKG Rating: 1500 Tags: brute force, dfs and similar Solve time: 3m 27s Verified: no Solution Problem Understanding We are given a set of people labeled from 1 to n, and each person may specify exactly one other person who must come immediately after them in a line. If this value is zero, the person does not specify who follows them, meaning their successor is not fixed....

Practice › Codeforces Solutions ›

Codeforces Round 121 (Div. 1)

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

Practice › Codeforces Solutions › April Fools Day Contest 2013 ›

CF 290F - Greedy Petya

CF 290F - Greedy Petya Rating: 2800 Tags: *special, dfs and similar, graphs, greedy Solve time: 1m 19s Verified: yes Solution Problem Understanding The statement is intentionally misleading. We are not asked to solve the Hamiltonian path problem ourselves. Instead, we must reproduce the output of Petya’s supposedly correct program. That changes the task completely. The graph is undirected and may contain repeated edges or self-loops. We receive up to...

Practice › Codeforces Solutions ›

Codeforces Round 149 (Div. 2)

Codeforces Round 149 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2100 | Time: 12m 58s Problem Name Rating Tags Solve Time Verified A Heads or Tails 1100 brute-force, implementation 3m 26s ✓ B Big Segment 1100 implementation, sortings 1m 12s ✓ C King's Path 1800 dfs-and-similar, graphs, hashing 3m 11s ✗ D Dispute 2100 dfs-and-similar, graphs, greedy 1m 37s ✗ E XOR on...

Practice › Codeforces Solutions ›

Codeforces Round 237 (Div. 2)

Codeforces Round 237 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 1000-1900 | Time: 12m 42s Problem Name Rating Tags Solve Time Verified A Valera and X 1000 implementation 4m 55s ✗ B Marathon 1500 implementation, math 2m 40s ✗ C Restore Graph 1800 dfs-and-similar, graphs, sortings 3m 31s ✗ D Minesweeper 1D 1900 dp, implementation 1m 36s ✗

Practice › Codeforces Solutions ›

Codeforces Round 177 (Div. 1)

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

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

CF 191C - Fools and Roads

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

Practice › Codeforces Solutions ›

Codeforces Round 187 (Div. 1)

Codeforces Round 187 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 2/3 | Rating range: 2000-2900 | Time: 6m 22s Problem Name Rating Tags Solve Time Verified B Sereja and Periods 2000 binary-search, dfs-and-similar, strings 1m 23s ✓ D Sereja and Straight Lines 2500 binary-search, data-structures, geometry 1m 45s ✓ E Sereja and Squares 2900 dp 3m 14s ✗

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

CF 448E - Divisors

CF 448E - Divisors Rating: 2200 Tags: brute force, dfs and similar, implementation, number theory Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a single starting integer $X$, and we repeatedly expand it into a sequence. One expansion step replaces every number in the sequence by all of its positive divisors, written in increasing order. After applying this operation $k$ times starting from the one-element sequence...

Practice › Codeforces Solutions ›

Croc Champ 2013 - Qualification Round

Croc Champ 2013 - Qualification Round Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1300-2000 | Time: 3m 17s Problem Name Rating Tags Solve Time Verified B Command Line Arguments 1300 *special, implementation, strings 1m 26s ✓ E Tree-String Problem 2000 *special, dfs-and-similar, hashing 1m 51s ✓

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

CF 258E - Little Elephant and Tree

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

Practice › Codeforces Solutions › Friday the 13th, Programmers Day ›

CF 345D - Chain Letter

CF 345D - Chain Letter Rating: 2200 Tags: *special, dfs and similar, graphs Solve time: 2m 12s Verified: yes Solution Problem Understanding We are asked to simulate the spread of a chain letter through a network of friends. Each person is represented as a node in a graph, and the connections between people-who sends letters to whom-are given as an adjacency matrix of "0" and "1" characters. The graph is...

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

CF 429A - Xor-tree

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

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

CF 445A - DZY Loves Chessboard

CF 445A - DZY Loves Chessboard Rating: 1200 Tags: dfs and similar, implementation Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a chessboard represented as an n by m grid where each cell is either good or bad. A good cell is indicated by a "." and a bad cell by a "-". On every good cell, we must place a chessman that is either white...

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

CF 329B - Biridian Forest

CF 329B - Biridian Forest Rating: 1500 Tags: dfs and similar, shortest paths Solve time: 2m 48s Verified: yes Solution Problem Understanding We are asked to navigate a forest represented as a grid. Each cell can be empty, contain a tree, or contain one or more mikemon breeders. Our goal is to move from our starting position to a designated exit while minimizing the number of battles we are forced...

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

CF 196B - Infinite Maze

CF 196B - Infinite Maze Rating: 2000 Tags: dfs and similar, graphs Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a finite maze of size n × m . Some cells are walls, some are open, and one cell contains the starting position S . The maze is not used only once. Instead, the entire grid is repeated infinitely in every direction, like tiling the plane...

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

CF 246D - Colorful Graph

CF 246D - Colorful Graph Rating: 1600 Tags: brute force, dfs and similar, graphs Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given an undirected graph where each vertex has a color, represented by an integer. The goal is to determine which color has the most diverse set of neighboring colors. Formally, for each color $k$, we look at all vertices of that color and collect the...

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

CF 167E - Wizards and Bets

CF 167E - Wizards and Bets Rating: 2900 Tags: dfs and similar, graphs, math, matrices Solve time: 3m 52s Verified: yes Solution Problem Understanding We are given a directed acyclic graph. Some vertices are sources, meaning no edge enters them. Some vertices are sinks, meaning no edge leaves them. The number of sources and sinks is guaranteed to be equal. A valid configuration consists of vertex-disjoint directed paths such that...

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

CF 350E - Wrong Floyd

CF 350E - Wrong Floyd Rating: 2200 Tags: brute force, constructive algorithms, dfs and similar, graphs Solve time: 2m 18s Verified: no Solution Problem Understanding We are given an undirected, simple, connected graph with a fixed number of vertices and edges. On top of that, a subset of vertices is marked. Someone runs a modified Floyd-Warshall process: instead of iterating all intermediate vertices from 1 to n, they only use...

Practice › Codeforces Solutions ›

Codeforces Round 151 (Div. 2)

Codeforces Round 151 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 900-1600 | Time: 4m 21s Problem Name Rating Tags Solve Time Verified A Buggy Sorting 900 constructive-algorithms, greedy, sortings 1m 8s ✓ C Beauty Pageant 1600 brute-force, constructive-algorithms, greedy 1m 43s ✓ D Colorful Graph 1600 brute-force, dfs-and-similar, graphs 1m 30s ✓

Practice › Codeforces Solutions ›

Codeforces Round 145 (Div. 1, ACM-ICPC Rules)

Codeforces Round 145 (Div. 1, ACM-ICPC Rules) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 2600-2800 | Time: 3m 3s Problem Name Rating Tags Solve Time Verified E Road Repairs 2800 dfs-and-similar, graphs, greedy 1m 58s ✓ F TorCoder 2600 data-structures 1m 5s ✓

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

CF 242C - King's Path

CF 242C - King's Path Rating: 1800 Tags: dfs and similar, graphs, hashing, shortest paths Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a huge implicit grid, up to $10^9 \times 10^9$, but only a small subset of cells are usable. Each usable region is given as a horizontal segment: a row number and a contiguous interval of columns. Taken together, these segments define a sparse...

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

CF 354E - Lucky Number Representation

CF 354E - Lucky Number Representation Rating: 2200 Tags: constructive algorithms, dfs and similar, dp Solve time: 5m 13s Verified: no Solution Problem Understanding The problem asks us to express each of a set of positive integers as a sum of exactly six numbers that only contain the digits 0, 4, or 7. These “lucky” numbers include zero, so numbers like 0, 4, 40, 47, 400, or 7074 are all...

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

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

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

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

CF 314B - Sereja and Periods

CF 314B - Sereja and Periods Rating: 2000 Tags: binary search, dfs and similar, strings Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given two base strings, call them a and c , and two integers b and d . From these, two longer strings are conceptually constructed: the first string is a repeated b times, and the second is c repeated p times for some unknown...

Practice › Codeforces Solutions ›

Codeforces Round 238 (Div. 2)

Codeforces Round 238 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 900-2300 | Time: 15m 46s Problem Name Rating Tags Solve Time Verified A Gravity Flip 900 greedy, implementation, sortings 6m 21s ✗ B Domino Effect 1100 - 1m 23s ✗ C Unusual Product 1600 implementation, math 1m 27s ✗ E Graph Cutting 2300 dfs-and-similar, graphs 6m 35s ✗

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

CF 274B - Zero Tree

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

Practice › Codeforces Solutions ›

Codeforces Round 120 (Div. 2)

Codeforces Round 120 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 1100-1900 | Time: 6m 10s Problem Name Rating Tags Solve Time Verified A Vasya and the Bus 1100 greedy, math 1m 11s ✓ B Surrounded 1800 geometry 1m 34s ✓ C STL 1500 dfs-and-similar 1m 49s ✓ D Non-Secret Cypher 1900 two-pointers 1m 36s ✓

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

CF 405E - Graph Cutting

CF 405E - Graph Cutting Rating: 2300 Tags: dfs and similar, graphs Solve time: 6m 35s Verified: no Solution Problem Understanding We are given a connected undirected simple graph and we need to break its edge set into groups of three vertices, where each group forms a path of length two. Each such group corresponds to two adjacent edges sharing a middle vertex, so every output line describes a triple...

Practice › Codeforces Solutions ›

ABBYY Cup 3.0 - Finals (online version)

ABBYY Cup 3.0 - Finals (online version) Type: Special | Problems: 7 | Verified: 3/7 | Rating range: 1100-2900 | Time: 27m 55s Problem Name Rating Tags Solve Time Verified B1 Shave Beaver! 1700 implementation 2m 32s ✓ C1 The Great Julya Calendar 1100 dp 4m 55s ✓ C2 The Great Julya Calendar 2400 dp 5m 52s ✗ C3 The Great Julya Calendar 2500 dp 1m 53s ✓ D1 Escaping...

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

CF 254D - Rats

CF 254D - Rats Rating: 2300 Tags: brute force, dfs and similar, graphs, implementation, shortest paths Solve time: 3m 1s Verified: no Solution Problem Understanding The problem presents a rectangular basement of a store as an n × m grid, where some cells are walls, some are empty, and some contain sleeping rats. Vasily has two grenades, and when a grenade explodes in a cell, its blast propagates outward to...

Practice › Codeforces Solutions › Codeforces Round 145 (Div. 1, ACM-ICPC Rules) ›

CF 240E - Road Repairs

CF 240E - Road Repairs Rating: 2800 Tags: dfs and similar, graphs, greedy Solve time: 1m 58s Verified: yes Solution Problem Understanding We have a directed graph of cities and roads. City 1 is the capital. Every road is either already usable or broken. A broken road may be repaired, after which it behaves like a normal directed edge. The government wants every city to become reachable from the capital....

Practice › Codeforces Solutions ›

Codeforces Round 191 (Div. 2)

Codeforces Round 191 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1200-2300 | Time: 7m 2s Problem Name Rating Tags Solve Time Verified A Flipping Game 1200 brute-force, dp, implementation 4m 3s ✓ D Block Tower 1900 constructive-algorithms, dfs-and-similar, graphs 1m 34s ✗ E Axis Walking 2300 bitmasks, combinatorics, constructive-algorithms 1m 25s ✓

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C1 - Party

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316F3 - Suns and Rays

CF 316F3 - Suns and Rays Rating: 2200 Tags: constructive algorithms, dfs and similar, implementation Solve time: 2m Verified: no Solution Problem Understanding The input is a binary image, essentially a grid where each cell is either background or part of a drawn object. Inside this grid, there are multiple disjoint shapes called suns. Each sun is an elliptical blob of foreground pixels, possibly rotated, and from its boundary extend...

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

CF 292D - Connected Components

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

Practice › Codeforces Solutions › VK Cup 2012 Round 2 ›

CF 163E - e-Government

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

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

CF 244B - Undoubtedly Lucky Numbers

CF 244B - Undoubtedly Lucky Numbers Rating: 1600 Tags: bitmasks, brute force, dfs and similar Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given a single positive integer $n$, and we need to count how many integers from 1 up to $n$ have a very specific property: there exists a pair of digits $x$ and $y$ such that every digit in the number’s decimal representation is either...

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

CF 160D - Edges in MST

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

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

CF 176E - Archaeology

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

Practice › Codeforces Solutions ›

Codeforces Round 254 (Div. 2)

Codeforces Round 254 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 1200-1200 | Time: 1m 21s Problem Name Rating Tags Solve Time Verified A DZY Loves Chessboard 1200 dfs-and-similar, implementation 1m 21s ✓

Practice › Codeforces Solutions ›

Codeforces Testing Round 5

Codeforces Testing Round 5 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 900-2000 | Time: 4m 20s Problem Name Rating Tags Solve Time Verified A Subtractions 900 math, number-theory 2m 41s ✓ B Dominoes 2000 dfs-and-similar, graphs 1m 39s ✓

Practice › Codeforces Solutions › Croc Champ 2012 - Final ›

CF 183C - Cyclic Coloring

CF 183C - Cyclic Coloring Rating: 2200 Tags: dfs and similar Solve time: 3m 32s Verified: yes Solution Problem Understanding We have a directed graph where every edge enforces a strict relationship between the colors of its endpoints. If a vertex has color c , then every outgoing neighbor must have color c + 1 , wrapping around modulo k . Another way to write the condition is: $color(v) \equiv...

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

CF 317C - Balance

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

Practice › Codeforces Solutions ›

Codeforces Round 168 (Div. 1)

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

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

CF 325E - The Red Button

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

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 1)

Codeforces Round 124 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1100-2600 | Time: 6m 40s Problem Name Rating Tags Solve Time Verified A Lexicographically Maximum Subsequence 1100 greedy, strings 1m 2s ✓ B Infinite Maze 2000 dfs-and-similar, graphs 1m 39s ✓ C Paint Tree 2200 constructive-algorithms, divide-and-conquer, geometry 1m 40s ✗ E Opening Portals 2600 dsu, graphs, shortest-paths 2m 19s ✓

Practice › Codeforces Solutions ›

Codeforces Round 189 (Div. 2)

Codeforces Round 189 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 0/1 | Rating range: 1500-1500 | Time: 3m 52s Problem Name Rating Tags Solve Time Verified B Ping-Pong (Easy Version) 1500 dfs-and-similar, graphs 3m 52s ✗

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

CF 327D - Block Tower

CF 327D - Block Tower Rating: 1900 Tags: constructive algorithms, dfs and similar, graphs Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a grid where some cells are blocked and the rest are usable land. On each usable cell we may place one building, either a blue tower worth 100 population or a red tower worth 200 population. The restriction is that a red tower is...

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

CF 208E - Blood Cousins

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

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

CF 263C - Circle of Numbers

CF 263C - Circle of Numbers Rating: 2000 Tags: brute force, dfs and similar, implementation Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a hidden cyclic arrangement of the integers from 1 to n placed around a circle. From this arrangement, someone constructed a set of ordered pairs describing connections between values. These connections come from a simple geometric rule: two numbers are connected if they...

Practice › Codeforces Solutions ›

Codeforces Round 238 (Div. 1)

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

Practice › Codeforces Solutions ›

Codeforces Round 192 (Div. 1)

Codeforces Round 192 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1500-3100 | Time: 7m 40s Problem Name Rating Tags Solve Time Verified A Purification 1500 constructive-algorithms, greedy 3m 58s ✗ B Biridian Forest 1500 dfs-and-similar, shortest-paths 2m 48s ✓ E Evil 3100 math 54s ✗

Practice › Codeforces Solutions ›

Codeforces Round 244 (Div. 2)

Codeforces Round 244 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 7m 50s Problem Name Rating Tags Solve Time Verified A Police Recruits 800 implementation 1m 22s ✓ B Prison Transfer 1100 data-structures, implementation 1m 33s ✓ C Checkposts 1700 dfs-and-similar, graphs, two-pointers 1m 34s ✓ D Match & Catch 2200 dp, string-suffix-structures, strings 1m 27s ✓ E Police Patrol 2000...

Practice › Codeforces Solutions ›

Codeforces Round 111 (Div. 2)

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

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

CF 216B - Forming Teams

CF 216B - Forming Teams Rating: 1700 Tags: dfs and similar, implementation Solve time: 1m 27s Verified: yes Solution Problem Understanding We can model the students as an undirected graph. Each student is a vertex, and every pair of enemies creates an edge. We want to split the remaining students into two teams of equal size such that no edge stays inside one team. In graph terms, we need a...

Practice › Codeforces Solutions › Codeforces Testing Round 5 ›

CF 267B - Dominoes

CF 267B - Dominoes Rating: 2000 Tags: dfs and similar, graphs Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a set of domino tiles, each with two numbers on its halves. The task is to arrange all dominoes in a sequence so that the touching halves of adjacent dominoes have the same number. A domino can be flipped, which swaps its two numbers. The output is...

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161D - Distance in Tree

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

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

CF 242D - Dispute

CF 242D - Dispute Rating: 2100 Tags: dfs and similar, graphs, greedy Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a graph of counters, where each counter starts at zero and is connected by undirected wires. Pressing a button on a counter increases its own value by one, and also increases the value of every directly connected neighbor by one. We are allowed to choose a...

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

CF 243C - Colorado Potato Beetle

CF 243C - Colorado Potato Beetle Rating: 2200 Tags: dfs and similar, implementation Solve time: 1m 37s Verified: no Solution Problem Understanding We are working on an enormous infinite grid of unit square cells, and we can think of each cell as a “bed” in a potato field. We start in the center cell and walk according to a sequence of axis-aligned moves. Every time we move, we do not...

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

CF 263D - Cycle in Graph

CF 263D - Cycle in Graph Rating: 1800 Tags: dfs and similar, graphs Solve time: 2m 57s Verified: no Solution Problem Understanding We are given an undirected graph where every vertex has a very strong local condition: each node is connected to at least $k$ other distinct nodes. From this structure we are asked to extract a simple cycle whose length is not just positive, but at least $k+1$. The...

Practice › Codeforces Solutions ›

Codeforces Round 133 (Div. 2)

Codeforces Round 133 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1200-2000 | Time: 7m 31s Problem Name Rating Tags Solve Time Verified A Tiling with Hexagons 1200 implementation, math 56s ✓ B Forming Teams 1700 dfs-and-similar, implementation 1m 27s ✓ C Hiring Staff 1800 greedy 2m 5s ✗ D Spider's Web 1700 binary-search, sortings, two-pointers 1m 26s ✗ E Martian Luck 2000 math,...

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

CF 320B - Ping-Pong (Easy Version)

CF 320B - Ping-Pong (Easy Version) Rating: 1500 Tags: dfs and similar, graphs Solve time: 3m 52s Verified: no Solution Problem Understanding We are maintaining a growing collection of intervals, each interval identified by its insertion order. Along with building this collection, we also define a directed reachability relation between intervals. From an interval $(a, b)$, you are allowed to move to another interval $(c, d)$ if either endpoint of...

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

CF 288D - Polo the Penguin and Trees

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

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

CF 118E - Bertown roads

CF 118E - Bertown roads Rating: 2000 Tags: dfs and similar, graphs Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a connected undirected graph representing the road network of Bertown, where junctions are nodes and roads are edges. Each road currently allows two-way traffic, but we are tasked with assigning a direction to every road such that the resulting directed graph remains strongly connected. Strong connectivity...

Practice › Codeforces Solutions ›

Codeforces Beta Round 88

Codeforces Beta Round 88 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2900 | Time: 13m 35s Problem Name Rating Tags Solve Time Verified A Elevator 1300 implementation, math 2m 31s ✓ B Very Interesting Game 1800 brute-force, number-theory 2m 31s ✓ C Cycle 2000 dfs-and-similar, graphs 3m ✓ D Not Quick Transformation 2500 divide-and-conquer, math 2m 20s ✓ E Tree or not Tree 2900 data-structures, divide-and-conquer,...

Practice › Codeforces Solutions › Codeforces Beta Round 58 ›

CF 62D - Wormhouse

CF 62D - Wormhouse Rating: 2300 Tags: dfs and similar, graphs Solve time: 2m 15s Verified: no Solution Problem Understanding We are given a connected graph representing rooms in Arnie’s apple house. Each room is a node, corridors between rooms are edges, and the graph has no self-loops or multiple edges between the same pair of rooms. Arnie previously gnawed out a path that starts and ends at the main...

Practice › Codeforces Solutions ›

Codeforces Beta Round 94 (Div. 2 Only)

Codeforces Beta Round 94 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1200 | Time: 3m 59s Problem Name Rating Tags Solve Time Verified A Cookies 900 implementation 1m 44s ✓ B Students and Shoelaces 1200 brute-force, dfs-and-similar, graphs 2m 15s ✓

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

CF 29D - Ant on the Tree

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

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

CF 81E - Pairs

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

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

CF 87D - Beautiful Road

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 83 (Div. 1 Only)

Codeforces Beta Round 83 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1400-2700 | Time: 11m 41s Problem Name Rating Tags Solve Time Verified A Dorm Water Supply 1400 dfs-and-similar, graphs 2m 19s ✓ B Basketball Team 1600 combinatorics, dp, math 2m 22s ✓ C Arrangement 2400 bitmasks, dp 2m 35s ✓ D Crime Management 2400 dp, graphs, matrices 2m 6s ✓ E...

Practice › Codeforces Solutions ›

Codeforces Beta Round 68

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 56

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 27 (Codeforces format, Div. 2)

Codeforces Beta Round 27 (Codeforces format, Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1200-2200 | Time: 6m 38s Problem Name Rating Tags Solve Time Verified A Next Test 1200 implementation, sortings 1m 13s ✓ B Tournament 1300 bitmasks, brute-force, dfs-and-similar 1m 3s ✓ C Unordered Subsequence 1900 constructive-algorithms, greedy 1m 18s ✗ D Ring Road 2 2200 2-sat, dfs-and-similar, dsu 1m 30s ✓...

Practice › Codeforces Solutions ›

Codeforces Beta Round 87 (Div. 1 Only)

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

Practice › Codeforces Solutions › Codeforces Beta Round 41 ›

CF 42E - Baldman and the military

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 22 (Div. 2 Only)

Codeforces Beta Round 22 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 7m 39s Problem Name Rating Tags Solve Time Verified A Second Order Statistics 800 brute-force 1m 21s ✓ B Bargaining Table 1500 brute-force, dp 1m 40s ✓ C System Administrator 1700 graphs 1m 25s ✗ D Segments 1900 greedy, sortings 1m 25s ✓ E Scheme 2300 dfs-and-similar, graphs,...

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

CF 22E - Scheme

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

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

CF 97E - Leaders

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

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

CF 34D - Road Map

CF 34D - Road Map Rating: 1600 Tags: dfs and similar, graphs Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a tree with n cities. Originally, city r1 is considered the capital, and for every other city we know its parent in the rooted tree. The value p[i] means that if we walk from the old capital toward city i , the last city before reaching...

Practice › Codeforces Solutions ›

Codeforces Testing Round 3

Codeforces Testing Round 3 Type: Special | Problems: 3 | Verified: 2/3 | Rating range: 1200-2200 | Time: 5m 24s Problem Name Rating Tags Solve Time Verified A Average Numbers 1200 brute-force, implementation 1m 39s ✓ B Pairs of Numbers 1900 brute-force, dfs-and-similar, math 1m 30s ✓ C Swaps 2200 constructive-algorithms, graphs, greedy 2m 15s ✗

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

CF 131D - Subway

CF 131D - Subway Rating: 1600 Tags: dfs and similar, graphs Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a subway system of n stations connected by exactly n passages, each passage connecting two distinct stations. The system forms a connected graph where each station can reach every other station. By graph theory, a connected graph with n nodes and n edges contains exactly one cycle....

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Round 1

Yandex.Algorithm 2011: Round 1 Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1300-2600 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A Domino 1300 constructive-algorithms, implementation 2m 9s ✓ B Embassy Queue 1800 data-structures, greedy 2m 1s ✓ C Petya and Tree 2200 binary-search, dfs-and-similar, probabilities 2m 4s ✓ D Sum of Medians 2300 binary-search, brute-force, data-structures 1m 18s ✓ E Guard Towers 2600...

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

CF 61D - Eternal Victory

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 14 (Div. 2)

Codeforces Beta Round 14 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-1900 | Time: 7m 42s Problem Name Rating Tags Solve Time Verified A Letter 800 implementation 1m 8s ✓ B Young Photographer 1000 implementation 1m 20s ✓ C Four Segments 1700 brute-force, constructive-algorithms, geometry 1m 48s ✓ D Two Paths 1900 dfs-and-similar, dp, graphs 1m 27s ✓ E Camels 1900 dp 1m...

Practice › Codeforces Solutions ›

Codeforces Beta Round 66

Codeforces Beta Round 66 Type: Beta | Problems: 6 | Verified: 6/6 | Rating range: 1600-2900 | Time: 12m 59s Problem Name Rating Tags Solve Time Verified A The Elder Trolls IV: Oblivon 1600 greedy, math 1m 48s ✓ B Need For Brake 2000 binary-search, greedy, sortings 2m 9s ✓ C LionAge II 1800 dp 1m 27s ✓ D FreeDiv 2200 dfs-and-similar, graphs, greedy 2m 38s ✓ E Morrowindows 2400...

Practice › Codeforces Solutions › Codeforces Beta Round 60 ›

CF 65D - Harry Potter and the Sorting Hat

CF 65D - Harry Potter and the Sorting Hat Rating: 2200 Tags: brute force, dfs and similar, hashing Solve time: 1m 58s Verified: yes Solution Problem Understanding We process students one by one. Each student either has a fixed house, represented by one of the letters G , H , R , S , or has ambiguous ancestry, represented by ? . A fixed student always goes into that house....

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

CF 27D - Ring Road 2

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

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

CF 29C - Mail Stamps

CF 29C - Mail Stamps Rating: 1700 Tags: data structures, dfs and similar, graphs, implementation Solve time: 1m 37s Verified: no Solution Problem Understanding Each stamp describes a direct transfer between two cities. If the envelope contains n stamps, then the letter passed through exactly n + 1 cities in sequence. The route never revisits a city, so the entire journey forms a simple path. The stamps are unordered. We...

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

CF 128A - Statues

CF 128A - Statues Rating: 1500 Tags: dfs and similar Solve time: 2m 10s Verified: yes Solution Problem Understanding We have an 8 × 8 board. Maria starts in the bottom-left corner, Anna stays permanently in the top-right corner, and several statues occupy other cells. The game proceeds in rounds. Maria moves first, then every statue moves one row downward simultaneously. A statue that moves below the board disappears forever....

Practice › Codeforces Solutions ›

Codeforces Beta Round 94 (Div. 1 Only)

Codeforces Beta Round 94 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2900 | Time: 8m 36s Problem Name Rating Tags Solve Time Verified A Statues 1500 dfs-and-similar 2m 10s ✓ B String 2100 brute-force, constructive-algorithms, hashing 1m 21s ✓ C Games with Rectangle 2000 combinatorics, dp 1m 52s ✓ D Numbers 2000 constructive-algorithms, implementation 1m 38s ✓ E Birthday 2900 geometry, math...

Practice › Codeforces Solutions ›

Codeforces Beta Round 31 (Div. 2, Codeforces format)

Codeforces Beta Round 31 (Div. 2, Codeforces format) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1200-2400 | Time: 6m 52s Problem Name Rating Tags Solve Time Verified A Worms Evolution 1200 implementation 1m 46s ✓ B Sysadmin Bob 1500 greedy, implementation, strings 1m 11s ✓ C Schedule 1700 implementation 58s ✓ D Chocolate 2000 dfs-and-similar, implementation 59s ✓ E TV Game 2400 dp 1m 58s...

Practice › Codeforces Solutions › Codeforces Beta Round 56 ›

CF 60B - Serial Time!

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

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

CF 35C - Fire Again

CF 35C - Fire Again Rating: 1500 Tags: brute force, dfs and similar, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We have a rectangular grid of trees. A fire starts simultaneously from several cells, and every minute it spreads to neighboring cells that share a side. The task is to find any cell whose burning time is as large as possible, meaning it catches fire later...

Practice › Codeforces Solutions › Codeforces Beta Round 66 ›

CF 73D - FreeDiv

CF 73D - FreeDiv Rating: 2200 Tags: dfs and similar, graphs, greedy Solve time: 2m 38s Verified: yes Solution Problem Understanding We are given an undirected graph where cities are vertices and roads are edges. Each connected component of the graph is called a province. Vasya may additionally build tunnels between cities, but tunnels have two restrictions. First, every city can participate in at most one tunnel. Second, every province...

Practice › Codeforces Solutions ›

Codeforces Beta Round 57 (Div. 2)

Codeforces Beta Round 57 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2000 | Time: 14m 51s Problem Name Rating Tags Solve Time Verified A Ultra-Fast Mathematician 800 implementation 2m 4s ✓ B Hard Work 1300 strings 6m 35s ✓ C Capture Valerian 2000 math 2m 49s ✓ D Eternal Victory 1800 dfs-and-similar, graphs, greedy 1m 29s ✓ E Enemy is weak 1900 data-structures,...

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

CF 103B - Cthulhu

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

Practice › Codeforces Solutions › Codeforces Beta Round 56 ›

CF 60C - Mushroom Strife

CF 60C - Mushroom Strife Rating: 2100 Tags: brute force, dfs and similar Solve time: 2m 15s Verified: yes Solution Problem Understanding We have an undirected graph where each vertex stores some positive integer, the number of mushrooms on that lawn. For every known edge, we are given two values: the gcd of the two endpoint values and the lcm of the two endpoint values. The original graph may have...

Practice › Codeforces Solutions ›

Codeforces Beta Round 29 (Div. 2, Codeforces format)

Codeforces Beta Round 29 (Div. 2, Codeforces format) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1000-2400 | Time: 6m 47s Problem Name Rating Tags Solve Time Verified A Spit Problem 1000 brute-force 1m 12s ✓ B Traffic Lights 1500 implementation 1m 23s ✓ C Mail Stamps 1700 data-structures, dfs-and-similar, graphs 1m 37s ✗ D Ant on the Tree 2000 constructive-algorithms, dfs-and-similar, trees 1m 19s ✓...

Practice › Codeforces Solutions ›

Codeforces Beta Round 73 (Div. 1 Only)

Codeforces Beta Round 73 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Trains 1500 implementation, math 1m 15s ✓ B Vasya and Types 1800 implementation, strings 1m 56s ✓ C Interesting Game 2000 dp, games, math 1m 9s ✓ D Beautiful Road 2300 dfs-and-similar, dp, dsu 2m 12s ✓ E...

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

CF 85C - Petya and Tree

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 95 (Div. 2)

Codeforces Beta Round 95 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 5/6 | Rating range: 1000-2000 | Time: 10m 6s Problem Name Rating Tags Solve Time Verified A cAPS lOCK 1000 implementation, strings 1m 16s ✓ B Opposites Attract 1200 implementation, math 1m 34s ✓ C The World is a Theatre 1400 combinatorics, math 1m 35s ✓ D Subway 1600 dfs-and-similar, graphs 1m 14s ✓ E Yet...

Practice › Codeforces Solutions ›

Unknown Language Round 3

Unknown Language Round 3 Type: Special | Problems: 10 | Verified: 10/10 | Rating range: 1100-2400 | Time: 23m 31s Problem Name Rating Tags Solve Time Verified A Carpeting the Room 1100 *special, implementation 2m 19s ✓ B Friendly Numbers 1500 *special, implementation 2m 19s ✓ C A+B 1400 *special, implementation 1m 27s ✓ D World of Mouth 1500 *special, strings 2m 18s ✓ E Lamps in a Line 1600...

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

CF 31D - Chocolate

CF 31D - Chocolate Rating: 2000 Tags: dfs and similar, implementation Solve time: 59s Verified: yes Solution Problem Understanding We are given a rectangular chocolate bar with integer width W and height H . Bob breaks the chocolate multiple times along vertical or horizontal lines that go from one edge to the opposite edge of a piece. Each break is specified by two endpoints, and the set of breaks is...

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

CF 77C - Beavermuncher-0xFF

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

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

CF 28B - pSort

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

Practice › Codeforces Solutions › Codeforces Beta Round 48 ›

CF 51F - Caterpillar

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

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

CF 1941D - Rudolf and the Ball Game

CF 1941D - Rudolf and the Ball Game Rating: 1200 Tags: dfs and similar, dp, implementation Solve time: 1m 17s Verified: no Solution Problem Understanding We have a circle of n players, numbered 1 through n clockwise. The ball starts with player x . There are m throws, and each throw has a distance r_i and a remembered direction c_i . The direction could be clockwise ( 0 ), counterclockwise...

Practice › Codeforces Solutions › Codeforces Beta Round 97 (Div. 1) ›

CF 135D - Cycle

CF 135D - Cycle Rating: 2500 Tags: brute force, dfs and similar, implementation Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given a binary grid. Cells containing '1' form usable tiles, while '0' cells are blocked. We want the longest cycle made entirely from '1' cells. The cycle must behave like a simple closed curve on the grid. Every cell on the cycle must touch exactly two...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Qualification 2

Yandex.Algorithm 2011: Qualification 2 Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 1100-2600 | Time: 11m 32s Problem Name Rating Tags Solve Time Verified A Double Cola 1100 implementation, math 1m 30s ✓ B Sets 1700 constructive-algorithms, hashing, implementation 2m 17s ✗ C General Mobilization 2000 data-structures, dfs-and-similar, sortings 2m 42s ✓ D Two out of Three 2000 dp 2m 57s ✓ E Corridor 2600 geometry 2m...

Practice › Codeforces Solutions ›

Codeforces Beta Round 69 (Div. 1 Only)

Codeforces Beta Round 69 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1400-2800 | Time: 11m 16s Problem Name Rating Tags Solve Time Verified A Heroes 1400 brute-force, implementation 1m 49s ✓ B Falling Anvils 1800 math, probabilities 2m 36s ✓ C Beavermuncher-0xFF 2100 dfs-and-similar, dp, dsu 2m 30s ✗ D Domino Carpet 2300 dp, implementation 1m 59s ✗ E Martian Food 2800...

Practice › Codeforces Solutions ›

Codeforces Beta Round 35 (Div. 2)

Codeforces Beta Round 35 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2100 | Time: 7m 52s Problem Name Rating Tags Solve Time Verified A Shell Game 1000 implementation 1m 26s ✓ B Warehouse 1700 implementation 1m 21s ✓ C Fire Again 1500 brute-force, dfs-and-similar, shortest-paths 2m 10s ✓ D Animals 1700 dp, greedy 1m 14s ✓ E Parade 2100 data-structures, sortings 1m 41s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 17

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 80 (Div. 1 Only)

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

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

CF 9E - Interestring graph and Apples

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

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

CF 82C - General Mobilization

CF 82C - General Mobilization Rating: 2000 Tags: data structures, dfs and similar, sortings Solve time: 2m 42s Verified: yes Solution Problem Understanding We have a rooted tree with root at city 1. Every city initially contains exactly one military division. Division i starts in city i and has priority a[i] , where a smaller value means higher priority. Each edge has a capacity. Every day, each non-root city sends...

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

CF 115A - Party

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

Practice › Codeforces Solutions › Codeforces Testing Round 3 ›

CF 134B - Pairs of Numbers

CF 134B - Pairs of Numbers Rating: 1900 Tags: brute force, dfs and similar, math, number theory Solve time: 1m 30s Verified: yes Solution Problem Understanding We are asked to start with the number pair (1,1) and reach a pair where at least one of the numbers equals a given target n . At each step, we can add one number to the other to form a new pair. Concretely,...

Practice › Codeforces Solutions › Codeforces Beta Round 17 ›

CF 17B - Hierarchy

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

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

CF 14D - Two Paths

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

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

CF 129B - Students and Shoelaces

CF 129B - Students and Shoelaces Rating: 1200 Tags: brute force, dfs and similar, graphs, implementation Solve time: 2m 15s Verified: yes Solution Problem Understanding We can model the students and shoelaces as an undirected graph. Each student is a vertex, and every shoelace between two students is an edge. In one round, every student whose degree is exactly 1 gets removed at the same time. When those students leave,...

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

CF 107A - Dorm Water Supply

CF 107A - Dorm Water Supply Rating: 1400 Tags: dfs and similar, graphs Solve time: 2m 19s Verified: yes Solution Problem Understanding The houses and pipes form a directed graph with a very special structure. Every house can have at most one incoming pipe and at most one outgoing pipe. That restriction changes the graph from a general directed graph into a collection of independent chains. A house with outgoing...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117C - Cycle

CF 117C - Cycle Rating: 2000 Tags: dfs and similar, graphs Solve time: 3m Verified: yes Solution Problem Understanding We are given a tournament graph, which is a special type of directed graph where for every pair of distinct vertices, there is exactly one directed edge connecting them. In other words, for any two vertices u and v , either there is an edge from u to v or from...

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

CF 27B - Tournament

CF 27B - Tournament Rating: 1300 Tags: bitmasks, brute force, dfs and similar, greedy Solve time: 1m 3s Verified: yes Solution Problem Understanding We are asked to reconstruct the missing result of a round-robin tournament. There are n participants, and every participant plays against every other participant exactly once. Each match has a clear winner and a loser, and no two participants have the same intrinsic ability: a lower "sleep...

Practice › Codeforces Solutions › Codeforces Beta Round 19 ›

CF 19E - Fairy

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 34 (Div. 2)

Codeforces Beta Round 34 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2000 | Time: 7m 19s Problem Name Rating Tags Solve Time Verified A Reconnaissance 2 800 implementation 1m 18s ✓ B Sale 900 greedy, sortings 1m 19s ✓ C Page Numbers 1300 expression-parsing, implementation, sortings 1m 7s ✓ D Road Map 1600 dfs-and-similar, graphs 1m 29s ✓ E Collisions 2000 brute-force, implementation,...

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

CF 1941G - Rudolf and Subway

CF 1941G - Rudolf and Subway Rating: 2000 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 1m 8s Verified: yes Solution Problem Understanding The problem describes a subway system as an undirected graph where each vertex is a station and each edge represents a direct connection between two stations. Every edge is labeled with a color representing the subway line it belongs to. All edges of the...

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

CF 123E - Maze

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

Practice › Codeforces Solutions › Codeforces Beta Round 53 ›

CF 57A - Square Earth?

CF 57A - Square Earth? Rating: 1300 Tags: dfs and similar, greedy, implementation Solve time: 1m 22s Verified: yes Solution Problem Understanding We are asked to find the shortest distance between two points lying on the perimeter of a square of side length n . The square is aligned with the axes, so its corners are at (0,0), (n,0), (0,n), and (n,n). The two points are guaranteed to lie on...

Practice › Codeforces Solutions ›

Codeforces Beta Round 41

Codeforces Beta Round 41 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1400-2700 | Time: 10m 20s Problem Name Rating Tags Solve Time Verified A Guilty --- to the kitchen! 1400 greedy, implementation 1m 32s ✓ B Game of chess unfinished 1700 implementation 2m 3s ✓ C Safe cracking 2200 brute-force, constructive-algorithms 1m 2s ✓ D Strange town 2300 constructive-algorithms, math 1m 50s ✗ E Baldman and...

Practice › Codeforces Solutions › Unknown Language Round 3 ›

CF 100H - Battleship

CF 100H - Battleship Rating: 2100 Tags: *special, dfs and similar, implementation Solve time: 3m 4s Verified: yes Solution Problem Understanding We are given several 10 × 10 Battleship boards. Each cell is either empty or occupied by part of a ship. The task is to verify whether every occupied cell belongs to a valid fleet configuration. A valid Battleship fleet contains exactly one ship of length 4, two ships...

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

CF 63E - Sweets Game

CF 63E - Sweets Game Rating: 2000 Tags: bitmasks, dfs and similar, dp, games, implementation Solve time: 2m 13s Verified: yes Solution Problem Understanding The board is a fixed hexagon with 19 cells. Some cells contain chocolates, some are empty. Two players alternate moves, and a move consists of choosing a contiguous segment of chocolates that lies on a straight line parallel to one of the three hexagon directions. Every...

Practice › Codeforces Solutions ›

Codeforces Beta Round 53

Codeforces Beta Round 53 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-3000 | Time: 8m 25s Problem Name Rating Tags Solve Time Verified A Square Earth? 1300 dfs-and-similar, greedy, implementation 1m 22s ✓ B Martian Architecture 1600 implementation 1m 37s ✓ C Array 1900 combinatorics, math 1m 21s ✓ D Journey 2500 dp, math 2m 2s ✓ E Chess 3000 math, shortest-paths 2m 3s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 68 ›

CF 74C - Chessboard Billiard

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

Practice › Codeforces Solutions › Codeforces Beta Round 60 ›

CF 65E - Harry Potter and Moving Staircases

CF 65E - Harry Potter and Moving Staircases Rating: 2900 Tags: dfs and similar, implementation Solve time: 2m 47s Verified: no Solution Problem Understanding We are given an undirected multigraph. Floors are vertices, staircases are edges. Harry starts at floor 1 and wants to visit every floor at least once. The graph is dynamic. Between Harry's walks, Ron and Hermione may modify staircases. A modification picks one endpoint of an...

Practice › Codeforces Solutions ›

Codeforces Beta Round 28 (Codeforces format)

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

Practice › Codeforces Solutions ›

Codeforces Round 933 (Div. 3)

Codeforces Round 933 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 6/7 | Rating range: 800-2000 | Time: 12m 58s Problem Name Rating Tags Solve Time Verified A Rudolf and the Ticket 800 brute-force, math 1m 23s ✓ B Rudolf and 121 1000 brute-force, dp, greedy 2m 47s ✓ C Rudolf and the Ugly String 900 dp, greedy, strings 2m 41s ✓ D Rudolf and the Ball Game...

#dfs-and-similar

CF 2222G - Statistics on Tree

CF 2227H - Fallen Leaves

CF 1975E - Chain Queries

CF 1975D - Paint the Tree

CF 1949C - Annual Ants' Gathering

CF 487E - Tourists

CF 1942D - Learning to Paint

CF 1952G - Mathematician Takeover

CF 486D - Valid Sets

Codeforces Round 282 (Div. 1)

April Fools Day Contest 2024

CF 1975F - Set

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

CF 1946F - Nobody is needed

CF 1943C - Tree Compass

CF 1976E - Splittable Permutations

CF 1949A - Grove

CF 1967D - Long Way to be Non-decreasing

CF 1976F - Remove Bridges

CF 494D - Birthday

CF 490F - Treeland Tour

CF 1950G - Shuffling Songs

CF 1955G - GCD on a grid

CF 1948C - Arrow Path

Codeforces Round 277 (Div. 2)

Educational Codeforces Round 163 (Rated for Div. 2)

CF 490D - Chocolate

CF 475E - Strongly Connected City 2

CF 463D - Gargari and Permutations

CF 478E - Wavy numbers

CF 455B - A Lot of Games

CF 453C - Little Pony and Summer Sun Celebration

CF 475B - Strongly Connected City

CF 461B - Appleman and Tree

Codeforces Round 267 (Div. 2)

Codeforces Round 263 (Div. 1)

CF 468B - Two Sets

Codeforces Round 260 (Div. 1)

Codeforces Round 270

CF 467D - Fedor and Essay

CF 472D - Design Tutorial: Inverse the Problem

CF 455C - Civilization

Codeforces Round 259 (Div. 1)

Codeforces Round 268 (Div. 1)

CF 463E - Caisa and Tree

CF 466E - Information Graph

Codeforces Round 264 (Div. 2)

Bayan 2015 Contest Warm Up

Codeforces Round 190 (Div. 1)

CF 177C2 - Party

CF 246E - Blood Cousins Return

CF 164A - Variable, or There and Back Again

Croc Champ 2012 - Final

Friday the 13th, Programmers Day

April Fools Day Contest 2013

VK Cup 2012 Round 3

CF 172E - BHTML+BCSS

CF 321C - Ciel the Commander

CF 331D1 - Escaping on Beaveractor

Codeforces Round 256 (Div. 2)

CF 406D - Hill Climbing

CF 217A - Ice Skating

CF 190C - STL

ABBYY Cup 3.0

Codeforces Round 150 (Div. 2)

CF 225D - Snake

CF 237D - T-decomposition

CF 251E - Tree and Table

MemSQL start[c]up Round 1

CF 427C - Checkposts

Codeforces Round 245 (Div. 1)

CF 144D - Missile Silos

Codeforces Round 103 (Div. 2)

Codeforces Round 161 (Div. 2)

CF 253C - Text Editor

Codeforces Round 134 (Div. 1)

CF 212E - IT Restaurants

Codeforces Round 202 (Div. 1)

Codeforces Round 181 (Div. 2)