constructive-algorithms

Practice › Codeforces Solutions ›

Codeforces Round 1091 (Div. 2) and CodeCraft 26

Codeforces Round 1091 (Div. 2) and CodeCraft 26 Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 1000-2600 | Time: 7m 34s Problem Name Rating Tags Solve Time Verified B Flip the Bit (Easy Version) 1000 greedy, implementation 2m 15s ✗ D Flip the Bit (Hard Version) 1900 greedy, implementation, math 1m 50s ✗ E Definitely Larger 2000 binary-search, constructive-algorithms, data-structures 1m 39s ✗ G Down the...

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

CF 2217E - Definitely Larger

CF 2217E - Definitely Larger Rating: 2000 Tags: binary search, constructive algorithms, data structures, graphs, greedy, sortings Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a fixed permutation p of size n . Alongside it, we must construct another permutation q of the same size. The interaction between p and q defines a dominance relation: an index j is said to dominate an index i if...

Practice › Codeforces Solutions › April Fools Day Contest ›

CF 171A - Mysterious numbers - 1

CF 171A - Mysterious numbers - 1 Rating: 1200 Tags: *special, constructive algorithms Solve time: 1m 43s Verified: yes Solution Problem Understanding This problem comes from an April Fools contest where the statement intentionally hides the real task. We are given two non-negative integers. The required operation is: Reverse the decimal representation of the second number. Add the result to the first number. Output the sum. For example, if the...

Practice › Codeforces Solutions ›

April Fools Day Contest

April Fools Day Contest Type: April Fools | Problems: 8 | Verified: 8/8 | Rating range: 1200-2000 | Time: 13m 15s Problem Name Rating Tags Solve Time Verified A Mysterious numbers - 1 1200 *special, constructive-algorithms 1m 43s ✓ B Star 1300 *special, combinatorics 2m 57s ✓ C A Piece of Cake 2000 *special, implementation 1m 30s ✓ D Broken checker 1300 *special, brute-force 1m 14s ✓ E MYSTERIOUS LANGUAGE...

Practice › Codeforces Solutions ›

Codeforces Round 1090 (Div. 4)

Codeforces Round 1090 (Div. 4) Type: Div. 4 | Problems: 4 | Verified: 1/4 | Rating range: 800-1800 | Time: 10m 7s Problem Name Rating Tags Solve Time Verified A The 67th Integer Problem 800 brute-force, games, implementation 1m 27s ✓ D The 67th OEIS Problem 1100 constructive-algorithms, greedy, math 2m 4s ✗ F The 67th Tree Problem 1500 constructive-algorithms, implementation, trees 3m 38s ✗ G [The 67th Iteration of...

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

CF 2218D - The 67th OEIS Problem

CF 2218D - The 67th OEIS Problem Rating: 1100 Tags: constructive algorithms, greedy, math, number theory Solve time: 2m 4s Verified: no Solution Problem Understanding We are asked to construct sequences of integers of length $n$ such that the greatest common divisor (gcd) of consecutive elements is always distinct. Each test case provides a number $n$, and for each, we must output one valid sequence of length $n$. The output...

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

CF 2218F - The 67th Tree Problem

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

Practice › Codeforces Solutions ›

Codeforces Round 1093 (Div. 1)

Codeforces Round 1093 (Div. 1) Type: Div. 1 | Problems: 1 | Verified: 0/1 | Rating range: - | Time: 3m 30s Problem Name Rating Tags Solve Time Verified A Grid L - brute-force, constructive-algorithms, math 3m 30s ✗

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

CF 2219A - Grid L

CF 2219A - Grid L Rating: - Tags: brute force, constructive algorithms, math, number theory Solve time: 3m 30s Verified: no Solution Problem Understanding An $n \times m$ grid consists of all unit segments that form the lattice. Every cell contributes edges, but neighboring cells share edges, so the total number of unit segments in the whole grid is not $4nm$. We are given two types of pieces. A straight...

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

CF 2222D - Permutation Construction

CF 2222D - Permutation Construction Rating: - Tags: constructive algorithms, data structures, sortings Solve time: 4m 9s Verified: no Solution Problem Understanding We are given an array $a$ of length $n$. We must construct a permutation $p$ of indices $1$ to $n$. For any pair of positions $i<j$, the pair contributes to the score only if it is an inversion in $p$, meaning $p_i>p_j$. Each such inversion contributes the interval...

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

CF 2225E - Covering Points with Circles

CF 2225E - Covering Points with Circles Rating: - Tags: constructive algorithms, geometry, math Solve time: 2m 37s Verified: no Solution Problem Understanding We are given up to $10^4$ integer points on the plane and a fixed radius $r$. We must output the centers of several circles, all having radius $r$, such that the centers have integer coordinates and no two circles overlap in positive area. Touching is allowed, but...

Practice › Codeforces Solutions ›

Educational Codeforces Round 189 (Rated for Div. 2)

Educational Codeforces Round 189 (Rated for Div. 2) Type: Div. 2 | Problems: 5 | Verified: 0/5 | Rating range: - | Time: 14m 18s Problem Name Rating Tags Solve Time Verified B Alternating String - brute-force, greedy 3m 12s ✗ C Red-Black Pairs - dp, greedy 2m 34s ✗ D Exceptional Segments - bitmasks, brute-force, math 3m 1s ✗ E Covering Points with Circles - constructive-algorithms, geometry, math 2m...

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

CF 2227C - Snowfall

CF 2227C - Snowfall Rating: - Tags: constructive algorithms, math Solve time: 4m 24s Verified: no Solution Problem Understanding A subarray product is divisible by $6$ if and only if the product contains at least one factor $2$ and at least one factor $3$. For each number, only its divisibility by $2$ and $3$ matters. The exact value is irrelevant. Every element belongs to one of four groups: $A$: divisible...

Practice › Codeforces Solutions ›

Codeforces Round 1096 (Div. 3)

Codeforces Round 1096 (Div. 3) Type: Div. 3 | Problems: 8 | Verified: 0/8 | Rating range: - | Time: 27m 59s Problem Name Rating Tags Solve Time Verified A Koshary - implementation, math 2m 38s ✗ B Party Monster - greedy 3m 38s ✗ C Snowfall - constructive-algorithms, math 4m 24s ✗ D Palindromex - binary-search, brute-force, constructive-algorithms 3m 24s ✗ E It All Went Sideways - binary-search, data-structures,...

Practice › Codeforces Solutions ›

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

Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2) Type: Div. 1+2 | Problems: 6 | Verified: 0/6 | Rating range: - | Time: 23m 39s Problem Name Rating Tags Solve Time Verified A A Wonderful Contest - brute-force, dp, math 4m 29s ✗ B Artistic Balance Tree - greedy, sortings 3m 53s ✗ C Median Partition - dp, math 2m 36s ✗ D Permutation Construction -...

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

CF 2222E - Seek the Truth

CF 2222E - Seek the Truth Rating: - Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 1m 59s Verified: no Solution Problem Understanding The original problem is interactive, but the version used for judging after the contest is the hacked format. Instead of interacting with a judge, each test case directly gives us the hidden values n , k , and c . The interactive story is useful because...

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

CF 2226D - Reserved Reversals

CF 2226D - Reserved Reversals Rating: - Tags: constructive algorithms, dp, greedy, math Solve time: 2m 22s Verified: no Solution Problem Understanding We are given several test cases, each consisting of an array. The task is to decide whether we can transform each array into a non-decreasing order using a specific operation: we may pick any subarray, compute its minimum and maximum values, and reverse it, but only if the...

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

CF 2227D - Palindromex

CF 2227D - Palindromex Rating: - Tags: binary search, brute force, constructive algorithms, data structures, greedy, implementation, two pointers Solve time: 3m 24s Verified: no Solution Problem Understanding We are given an array of length $2n$. Every value from $0$ to $n-1$ appears exactly twice. The task is to select a contiguous segment of this array that reads the same left-to-right and right-to-left, and among all such segments we want...

Practice › Codeforces Solutions ›

Codeforces Round 276 (Div. 1)

Codeforces Round 276 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 0/4 | Rating range: 1700-2500 | Time: 26m 55s Problem Name Rating Tags Solve Time Verified A Bits 1700 bitmasks, constructive-algorithms 5m 23s ✗ B Maximum Value 2100 binary-search, math, sortings 10m 57s ✗ D Kindergarten 2400 data-structures, dp, greedy 5m 17s ✗ E Sign on Fence 2500 binary-search, constructive-algorithms, data-structures 5m 18s ✗

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

CF 1955H - The Most Reckless Defense

CF 1955H - The Most Reckless Defense Rating: 2300 Tags: bitmasks, brute force, constructive algorithms, dp, flows, graph matchings, shortest paths Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a grid where some cells form a fixed path from the top-left corner to the bottom-right corner. An enemy walks along this path one cell per second. At each cell, it spends a full second there, and...

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

CF 1965E - Connected Cubes

CF 1965E - Connected Cubes Rating: 3100 Tags: constructive algorithms, games Solve time: 1m 10s Verified: no Solution Problem Understanding We are given an $n \times m$ grid sitting at height $z=1$, where each cell already contains a unit cube with a color. You are allowed to stack additional colored cubes at integer coordinates above this base layer, but you are blocked from using any cell on the coordinate planes...

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

CF 1966A - Card Exchange

CF 1966A - Card Exchange Rating: 800 Tags: constructive algorithms, games, greedy Solve time: 1m 12s Verified: no Solution Problem Understanding We are given a multiset of cards, where each card carries an integer label. The only allowed operation takes exactly k cards that all share the same label and removes them, replacing them with k-1 new cards whose labels we are free to choose arbitrarily. The freedom to assign...

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

CF 1954A - Painting the Ribbon

CF 1954A - Painting the Ribbon Rating: 900 Tags: constructive algorithms, greedy, math Solve time: 1m 3s Verified: yes Solution Problem Understanding We are asked to decide whether Alice can paint a ribbon of n parts using m colors such that Bob, who can repaint at most k parts into the same color, cannot make the entire ribbon monochromatic. Alice has full freedom to choose the initial coloring, while Bob...

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

CF 1956C - Nene's Magical Matrix

CF 1956C - Nene's Magical Matrix Rating: 1600 Tags: constructive algorithms, greedy, math Solve time: 57s Verified: yes Solution Problem Understanding We are given a square matrix of size $n \times n$ initially filled with zeroes. Nene can perform two types of operations: either set an entire row to a permutation of $1$ through $n$ or set an entire column to such a permutation. The goal is to maximize the...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951E - No Palindromes

CF 1951E - No Palindromes Rating: 2000 Tags: brute force, constructive algorithms, divide and conquer, greedy, hashing, implementation, math, strings Solve time: 1m 1s Verified: no Solution Problem Understanding We are given a string and we are allowed to cut it into contiguous pieces. The goal is to decide whether we can cut it so that every resulting piece is not a palindrome. If it is possible, we must also...

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

CF 1948A - Special Characters

CF 1948A - Special Characters Rating: 800 Tags: brute force, constructive algorithms Solve time: 1m 17s Verified: no Solution Problem Understanding We are asked to construct a string over uppercase Latin letters such that a specific counting rule is satisfied. A position in the string is called special if the character at that position matches exactly one of its immediate neighbors. Endpoints only have one neighbor, so they can never...

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

CF 1973C - Cat, Fox and Double Maximum

CF 1973C - Cat, Fox and Double Maximum Rating: 1700 Tags: constructive algorithms, greedy, implementation, math, sortings Solve time: 5m 15s Verified: no Solution

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

CF 1944B - Equal XOR

CF 1944B - Equal XOR Rating: 1100 Tags: bitmasks, constructive algorithms Solve time: 1m 19s Verified: no Solution Problem Understanding We are given an array of length $2n$ where every number from $1$ to $n$ appears exactly twice. You can think of it as $n$ paired cards scattered in a line. The first $n$ positions form a left block and the last $n$ positions form a right block. The task...

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

CF 493D - Vasya and Chess

CF 493D - Vasya and Chess Rating: 1700 Tags: constructive algorithms, games, math Solve time: 1m 25s Verified: yes Solution Problem Understanding We have an $n \times n$ board. The white queen starts at the top-left corner $(1,1)$, and the black queen starts at the top-right corner $(1,n)$. Every other square contains a green pawn. A move is mandatory. On each turn, a player must capture some piece with their...

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

CF 1945G - Cook and Porridge

CF 1945G - Cook and Porridge Rating: 2500 Tags: binary search, constructive algorithms, data structures, implementation Solve time: 1m 10s Verified: yes Solution Problem Understanding We are simulating a queue of students where the front of the queue is repeatedly served for a limited number of minutes. Each student, once served, leaves to “process” their porridge for a fixed number of minutes, and then returns to the queue. The return...

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

CF 1974D - Ingenuity-2

CF 1974D - Ingenuity-2 Rating: 1400 Tags: constructive algorithms, greedy, implementation Solve time: 5m 16s Verified: no Solution

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

CF 1956D - Nene and the Mex Operator

CF 1956D - Nene and the Mex Operator Rating: 2000 Tags: bitmasks, brute force, constructive algorithms, divide and conquer, dp, greedy, implementation, math Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a short array of length at most 18. The only allowed move is to pick a contiguous segment, compute the mex of that segment, and overwrite the entire segment with that mex value. This operation...

Practice › Codeforces Solutions ›

Educational Codeforces Round 164 (Rated for Div. 2)

Educational Codeforces Round 164 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 900-3100 | Time: 7m 33s Problem Name Rating Tags Solve Time Verified A Painting the Ribbon 900 constructive-algorithms, greedy, math 1m 3s ✓ B Make It Ugly 1200 implementation, math 1m 15s ✗ C Long Multiplication 1200 greedy, math, number-theory 1m 13s ✗ D Colored Balls 1800 combinatorics, dp, math...

Practice › Codeforces Solutions ›

Codeforces Round 275 (Div. 1)

Codeforces Round 275 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 0/4 | Rating range: 1200-3200 | Time: 23m 24s Problem Name Rating Tags Solve Time Verified A Diverse Permutation 1200 constructive-algorithms, greedy 11m 3s ✗ C Game with Strings 2600 bitmasks, dp, probabilities 1m 44s ✗ D Random Function and Tree 2700 combinatorics, dp, trees 5m 18s ✗ E ELCA 3200 data-structures, trees 5m 19s ✗

Practice › Codeforces Solutions ›

Codeforces Round 940 (Div. 2) and CodeCraft-23

Codeforces Round 940 (Div. 2) and CodeCraft-23 Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 800-1100 | Time: 4m 40s Problem Name Rating Tags Solve Time Verified A Stickogon 800 constructive-algorithms, greedy 43s ✓ B A BIT of a Construction 1100 bitmasks, constructive-algorithms, greedy 3m 57s ✗

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

CF 1942A - Farmer John's Challenge

CF 1942A - Farmer John's Challenge Rating: 800 Tags: constructive algorithms, math Solve time: 1m 37s Verified: no Solution Problem Understanding We need to construct an array of length n such that exactly k of its cyclic shifts are sorted in nondecreasing order. A cyclic shift chooses some position as the new beginning of the array and wraps the remaining elements around. For example, the shifts of [1, 2, 3]...

Practice › Codeforces Solutions ›

Testing Round 11

Testing Round 11 Type: Special | Problems: 3 | Verified: 1/3 | Rating range: 1000-2300 | Time: 17m 39s Problem Name Rating Tags Solve Time Verified A Up the hill 1000 constructive-algorithms, implementation 5m 18s ✗ B New York Hotel 2100 greedy, math 11m 40s ✗ C Deciphering 2300 flows, graph-matchings 41s ✓

Practice › Codeforces Solutions ›

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) Type: Div. 1+2 | Problems: 9 | Verified: 4/9 | Rating range: 800-3500 | Time: 16m 46s Problem Name Rating Tags Solve Time Verified A Farmer John's Challenge 800 constructive-algorithms, math 1m 37s ✗ B Bessie and MEX 1100 constructive-algorithms, math 1m 18s ✗ C1 Bessie's Birthday Cake (Easy Version) 1300 geometry, greedy, math 56s ✓ C2 Bessie's Birthday Cake...

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

CF 1946D - Birthday Gift

CF 1946D - Birthday Gift Rating: 1900 Tags: bitmasks, brute force, constructive algorithms, greedy, implementation Solve time: 1m 7s Verified: no Solution Problem Understanding We are given an array and we are allowed to split it into a sequence of contiguous segments. Each segment is evaluated by taking the bitwise XOR of its elements. Once all segment XORs are computed, we combine those results using bitwise OR, left to right...

Practice › Codeforces Solutions ›

Codeforces Round 941 (Div. 1)

Codeforces Round 941 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 0/6 | Rating range: 1400-3300 | Time: 7m 12s Problem Name Rating Tags Solve Time Verified A Everything Nim 1400 games, greedy, math 1m 24s ✗ B Missing Subsequence Sum 1800 bitmasks, constructive-algorithms, greedy 1m 17s ✗ C Folding Strip 2300 constructive-algorithms, greedy, strings 1m 8s ✗ D Missing Subarray Sum 2900 constructive-algorithms 1m 5s ✗ E...

Practice › Codeforces Solutions › Testing Round 11 ›

CF 491A - Up the hill

CF 491A - Up the hill Rating: 1000 Tags: constructive algorithms, implementation Solve time: 5m 18s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 934 (Div. 2)

Codeforces Round 934 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 800-1100 | Time: 2m 14s Problem Name Rating Tags Solve Time Verified A Destroying Bridges 800 graphs, greedy, math 55s ✓ B Equal XOR 1100 bitmasks, constructive-algorithms 1m 19s ✗

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

CF 1943C - Tree Compass

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

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

CF 484A - Bits

CF 484A - Bits Rating: 1700 Tags: bitmasks, constructive algorithms Solve time: 5m 23s Verified: no Solution

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

CF 1942B - Bessie and MEX

CF 1942B - Bessie and MEX Rating: 1100 Tags: constructive algorithms, math Solve time: 1m 18s Verified: no Solution Problem Understanding We are given an array a of length n , constructed from some unknown permutation p of the integers 0 through n-1 . Each element of a satisfies the relation a[i] = MEX(p[1..i]) - p[i] . The task is to reconstruct any valid permutation p that produces this a...

Practice › Codeforces Solutions › Kotlin Heroes: Episode 10 ›

CF 1958E - Yet Another Permutation Constructive

CF 1958E - Yet Another Permutation Constructive Rating: 1900 Tags: *special, constructive algorithms Solve time: 1m 4s Verified: no Solution Problem Understanding We are given a permutation, which is just an ordering of the numbers from 1 to n. We repeatedly apply a transformation that removes elements which are strictly smaller than at least one of their immediate neighbors. After each round, the remaining elements form a shorter sequence, and...

Practice › Codeforces Solutions › Codeforces Round 940 (Div. 2) and CodeCraft-23 ›

CF 1957A - Stickogon

CF 1957A - Stickogon Rating: 800 Tags: constructive algorithms, greedy Solve time: 43s Verified: yes Solution Problem Understanding We are given a collection of sticks, each with an integer length. The goal is to build as many regular polygons as possible using these sticks, with the restriction that each side of a polygon must be exactly one stick, and no stick can be reused. A regular polygon requires at least...

Practice › Codeforces Solutions ›

Kotlin Heroes: Episode 10

Kotlin Heroes: Episode 10 Type: Kotlin | Problems: 10 | Verified: 7/10 | Rating range: 1100-3200 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A 1-3-5 1100 *special, dp 47s ✓ B Clock in the Pool 1400 *special, math 44s ✓ C Firewood 1500 *special 1m ✓ D Staircase 1600 *special 1m 14s ✗ E Yet Another Permutation Constructive 1900 *special, constructive-algorithms 1m 4s ✗ F Narrow...

Practice › Codeforces Solutions ›

Codeforces Round 941 (Div. 2)

Codeforces Round 941 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 0/2 | Rating range: 800-1100 | Time: 2m 20s Problem Name Rating Tags Solve Time Verified A Card Exchange 800 constructive-algorithms, games, greedy 1m 12s ✗ B Rectangle Filling 1100 constructive-algorithms, implementation 1m 8s ✗

Practice › Codeforces Solutions ›

Codeforces Round 278 (Div. 2)

Codeforces Round 278 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 0/2 | Rating range: 1100-1900 | Time: 21m 45s Problem Name Rating Tags Solve Time Verified A Giga Tower 1100 brute-force 10m 47s ✗ B Candy Boxes 1900 brute-force, constructive-algorithms, math 10m 58s ✗

Practice › Codeforces Solutions ›

Codeforces Global Round 25

Codeforces Global Round 25 Type: Global | Problems: 9 | Verified: 1/9 | Rating range: 900-3200 | Time: 11m 49s Problem Name Rating Tags Solve Time Verified A Dual Trigger 900 constructive-algorithms, greedy, math 51s ✓ B Battle Cows 1200 binary-search, data-structures, greedy 1m 24s ✗ C Ticket Hoarding 1400 greedy, math, sortings 59s ✗ D Buying Jewels 2000 constructive-algorithms, greedy, math 1m 19s ✗ E No Palindromes 2000 brute-force,...

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

CF 1945E - Binary Search

CF 1945E - Binary Search Rating: 1700 Tags: binary search, constructive algorithms, greedy Solve time: 1m 21s Verified: no Solution Problem Understanding We are given a permutation of size $n$, meaning every number from $1$ to $n$ appears exactly once, but in some arbitrary order. Along with it, we are given a target value $x$ that definitely exists somewhere in the array. We are allowed to perform at most two...

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 › European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1949K - Make Triangle

CF 1949K - Make Triangle Rating: 2800 Tags: constructive algorithms, math Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given a multiset of positive integers and three required group sizes. Every number must belong to exactly one of the three groups, and each group must contain exactly the requested number of elements. After splitting the numbers, we look only at the three group sums. If those sums...

Practice › Codeforces Solutions ›

Codeforces Round 278 (Div. 1)

Codeforces Round 278 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 0/4 | Rating range: 1800-3200 | Time: 27m 2s Problem Name Rating Tags Solve Time Verified A Fight the Monster 1800 binary-search, brute-force, implementation 5m 21s ✗ C Prefix Product Sequence 2300 constructive-algorithms, math, number-theory 5m 22s ✗ D Conveyor Belts 2700 data-structures 5m 24s ✗ E Tourists 3200 data-structures, dfs-and-similar, graphs 10m 55s ✗

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951F - Inversion Composition

CF 1951F - Inversion Composition Rating: 2500 Tags: constructive algorithms, data structures, greedy Solve time: 1m 56s Verified: no Solution Problem Understanding We are asked to construct a permutation q of size n such that the sum of inversions of q and the composition q ∘ p equals a given target k . The input permutation p is fixed, and inversions count how many pairs of indices are out of...

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

CF 1965B - Missing Subsequence Sum

CF 1965B - Missing Subsequence Sum Rating: 1800 Tags: bitmasks, constructive algorithms, greedy, number theory Solve time: 1m 17s Verified: no Solution Problem Understanding We are asked to construct an array of non-negative integers such that the sums of all subsequences cover every integer from 1 to $n$, except for a single forbidden sum $k$. Each test case gives the upper bound $n$ and the forbidden sum $k$. The output...

Practice › Codeforces Solutions ›

Codeforces Round 938 (Div. 3)

Codeforces Round 938 (Div. 3) Type: Div. 3 | Problems: 8 | Verified: 5/8 | Rating range: 800-2300 | Time: 7m 51s Problem Name Rating Tags Solve Time Verified A Yogurt Sale 800 math 54s ✓ B Progressive Square 1000 constructive-algorithms, data-structures, implementation 49s ✓ C Inhabitant of the Deep Sea 1300 greedy, implementation, math 1m 10s ✗ D Inaccurate Subsequence Search 1400 data-structures, two-pointers 46s ✓ E Long Inversions...

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

CF 488B - Candy Boxes

CF 488B - Candy Boxes Rating: 1900 Tags: brute force, constructive algorithms, math Solve time: 10m 58s Verified: no Solution Problem Understanding The task is to reconstruct a set of four integers representing candy counts in boxes such that three properties are equal: the arithmetic mean, the median, and the range. We are given some subset of these four numbers (0 to 4) in arbitrary order. The output should confirm...

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

CF 1955B - Progressive Square

CF 1955B - Progressive Square Rating: 1000 Tags: constructive algorithms, data structures, implementation, sortings Solve time: 49s Verified: yes Solution Problem Understanding We are given an $n \times n$ grid that is fully determined by three values: the top-left cell, and two fixed increments that govern movement downwards and rightwards. Moving one step down always adds $c$, and moving one step right always adds $d$. Because of this, every cell...

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

CF 487C - Prefix Product Sequence

CF 487C - Prefix Product Sequence Rating: 2300 Tags: constructive algorithms, math, number theory Solve time: 5m 22s Verified: no Solution

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

CF 1966B - Rectangle Filling

CF 1966B - Rectangle Filling Rating: 1100 Tags: constructive algorithms, implementation Solve time: 1m 8s Verified: no Solution Problem Understanding We are given a grid of size $n \times m$ composed of white and black squares. The task is to determine whether it is possible to make all squares in the grid the same color using a specific operation any number of times. The operation allows selecting two squares of...

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

CF 1965C - Folding Strip

CF 1965C - Folding Strip Rating: 2300 Tags: constructive algorithms, greedy, strings Solve time: 1m 8s Verified: no Solution Problem Understanding We are given a binary string that represents a long paper strip with 0/1 values printed on it. We are allowed to choose any number of cut positions between adjacent characters, and then fold segments of the strip on top of each other simultaneously. After folding, multiple original positions...

Practice › Codeforces Solutions ›

Codeforces Round 939 (Div. 2)

Codeforces Round 939 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-3000 | Time: 7m 40s Problem Name Rating Tags Solve Time Verified A Nene's Game 800 binary-search, brute-force, data-structures 1m 6s ✗ B Nene and the Card Game 800 games, greedy 53s ✓ C Nene's Magical Matrix 1600 constructive-algorithms, greedy, math 57s ✓ D Nene and the Mex Operator 2000 bitmasks, brute-force, constructive-algorithms...

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

CF 1965D - Missing Subarray Sum

CF 1965D - Missing Subarray Sum Rating: 2900 Tags: constructive algorithms Solve time: 1m 5s Verified: no Solution Problem Understanding We are given a multiset that contains almost all subarray sums of an unknown array a , where a has two special properties: every element is strictly positive and the array reads the same forwards and backwards. Exactly one subarray sum is missing from this multiset, and our task is...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951I - Growing Trees

CF 1951I - Growing Trees Rating: 3200 Tags: binary search, constructive algorithms, flows, graphs, greedy Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a connected simple undirected graph with up to 50 vertices and at most 50 edges. Each edge can be used multiple times in a constructed multigraph, and we control how many copies of each edge we create through a non-negative integer array $x$....

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

CF 482A - Diverse Permutation

CF 482A - Diverse Permutation Rating: 1200 Tags: constructive algorithms, greedy Solve time: 11m 3s Verified: no Solution Problem Understanding We are asked to construct a permutation of integers from 1 to n such that the set of absolute differences between consecutive elements contains exactly k distinct values. Concretely, if the permutation is [p1, p2, ..., pn] , then the list [|p1 - p2|, |p2 - p3|, ..., |pn-1 -...

Practice › Codeforces Solutions › Codeforces Round 940 (Div. 2) and CodeCraft-23 ›

CF 1957B - A BIT of a Construction

CF 1957B - A BIT of a Construction Rating: 1100 Tags: bitmasks, constructive algorithms, greedy, implementation Solve time: 3m 57s Verified: no Solution Problem Understanding We are asked to construct a sequence of n non-negative integers that sum to a given value k , while maximizing the number of distinct 1 bits in the binary representation of their bitwise OR. In other words, we are free to distribute k across...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951D - Buying Jewels

CF 1951D - Buying Jewels Rating: 2000 Tags: constructive algorithms, greedy, math Solve time: 1m 19s Verified: no Solution Problem Understanding We are given a buyer who starts with a fixed number of coins. A shop is not fixed in advance; instead, we are allowed to design up to 60 sequential stalls. Each stall has an unlimited supply of jewels, and a fixed integer price per jewel. The buyer behaves...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951A - Dual Trigger

CF 1951A - Dual Trigger Rating: 900 Tags: constructive algorithms, greedy, math Solve time: 51s Verified: yes Solution Problem Understanding We are given a row of lamps, all initially off. We can perform one type of operation any number of times: choose two lamps that are currently off and are not next to each other, and turn them both on simultaneously. Our task is to determine, for multiple test cases,...

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

CF 1956F - Nene and the Passing Game

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

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

CF 484E - Sign on Fence

CF 484E - Sign on Fence Rating: 2500 Tags: binary search, constructive algorithms, data structures Solve time: 5m 18s Verified: no Solution

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

CF 1948E - Clique Partition

CF 1948E - Clique Partition Rating: 2100 Tags: brute force, constructive algorithms, graphs, greedy, implementation Solve time: 2m 41s Verified: no Solution Problem Understanding We are given a problem where we need to assign integers to vertices of an initially empty graph and then construct edges based on a Manhattan-like distance metric. Specifically, for vertices labeled $1$ through $n$, each vertex receives a distinct integer from $1$ to $n$. After...

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 › European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1949D - Funny or Scary?

CF 1949D - Funny or Scary? Rating: 2600 Tags: constructive algorithms Solve time: 1m 10s Verified: no Solution Problem Understanding We are given a set of $n$ game scenarios, each of which must be played exactly once by the player. Between any two different scenarios $i$ and $j$, the game has a transition video that can be either funny (F) or scary (S). This transition is symmetric, meaning the video...

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

CF 459C - Pashmak and Buses

CF 459C - Pashmak and Buses Rating: 1900 Tags: combinatorics, constructive algorithms, math Solve time: 1m 59s Verified: no Solution Problem Understanding We need to assign each student to one of k buses on each of d days. For every student, we can think of their assignment as a sequence of length d . For example, if d = 3 , a student might ride buses (2, 1, 2) over...

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472F - Design Tutorial: Change the Goal

CF 472F - Design Tutorial: Change the Goal Rating: 2700 Tags: constructive algorithms, math, matrices Solve time: 1m 27s Verified: no Solution Problem Understanding We are given two arrays of integers, x and y , each of length n . The array x is the starting state, and y is the desired target state. The only operation allowed is x[i] ^= x[j] , which replaces x[i] with the bitwise XOR...

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 › Bayan 2015 Contest Warm Up ›

CF 475C - Kamal-ol-molk's Painting

CF 475C - Kamal-ol-molk's Painting Rating: 2100 Tags: brute force, constructive algorithms, greedy Solve time: 2m 56s Verified: no Solution Problem Understanding We are given a grid where some cells are marked X . These are the cells that were painted at least once. Originally, a rectangular brush of size h × w was placed somewhere on the grid. After that, the brush was moved several times. Every move was...

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472E - Design Tutorial: Learn from a Game

CF 472E - Design Tutorial: Learn from a Game Rating: 2800 Tags: constructive algorithms, implementation Solve time: 3m 25s Verified: no Solution Problem Understanding We have two boards of the same size. A move starts by choosing one cell and placing a finger on it. After that, the finger walks through adjacent cells. Every time the finger moves from one cell to another, the two orbs in those cells are...

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

CF 468A - 24 Game

CF 468A - 24 Game Rating: 1500 Tags: constructive algorithms, greedy, math Solve time: 1m 19s Verified: yes Solution Problem Understanding The problem gives you the first n positive integers, arranged as a sequence 1 through n . You are allowed to combine any two numbers from this sequence using addition, subtraction, or multiplication, replacing the pair with the result. After repeating this operation n −1 times, only a single...

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

CF 478B - Random Teams

CF 478B - Random Teams Rating: 1300 Tags: combinatorics, constructive algorithms, greedy, math Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given a set of $n$ people who must be partitioned into exactly $m$ non-empty groups. Once the grouping is fixed, every pair of people inside the same group becomes a friendship. A group of size $k$ contributes $\frac{k(k-1)}{2}$ friendships, so the total number of friendships is...

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

CF 467B - Fedor and New Game

CF 467B - Fedor and New Game Rating: 1100 Tags: bitmasks, brute force, constructive algorithms, implementation Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a game with several players, each controlling an army composed of different types of soldiers. Each army is represented as a non-negative integer where the binary representation encodes the presence of soldier types: a bit set to 1 means the army includes...

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

CF 449C - Jzzhu and Apples

CF 449C - Jzzhu and Apples Rating: 2500 Tags: constructive algorithms, number theory Solve time: 1m 44s Verified: no Solution Problem Understanding We have apples numbered from 1 to n . We want to create as many disjoint pairs as possible such that the two numbers in each pair have greatest common divisor greater than 1 . Each apple can appear in at most one pair. The task is not...

Practice › Codeforces Solutions ›

Codeforces Round 273 (Div. 2)

Codeforces Round 273 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1100-2900 | Time: 6m Problem Name Rating Tags Solve Time Verified A Initial Bet 1100 implementation 59s ✓ B Random Teams 1300 combinatorics, constructive-algorithms, greedy 1m 12s ✓ C Table Decorations 1800 greedy 1m 9s ✓ D Red-Green Towers 2000 dp 1m 3s ✓ E Wavy numbers 2900 brute-force, dfs-and-similar, meet-in-the-middle 1m 37s...

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

CF 468C - Hack it!

CF 468C - Hack it! Rating: 2500 Tags: binary search, constructive algorithms, math Solve time: 1m 18s Verified: yes Solution Problem Understanding The task revolves around finding two integers, l and r , such that the sum of all digits from l to r modulo a given number a produces an edge case for a buggy implementation. The function f(x) denotes the sum of the decimal digits of x ....

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 ›

Codeforces Round 261 (Div. 2)

Codeforces Round 261 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1200-1900 | Time: 8m 37s Problem Name Rating Tags Solve Time Verified A Pashmak and Garden 1200 implementation 1m 3s ✓ B Pashmak and Flowers 1300 combinatorics, implementation, sortings 1m 31s ✓ C Pashmak and Buses 1900 combinatorics, constructive-algorithms, math 1m 59s ✗ D Pashmak and Parmida's problem 1800 data-structures, divide-and-conquer, sortings 2m...

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

CF 479B - Towers

CF 479B - Towers Rating: 1400 Tags: brute force, constructive algorithms, greedy, implementation, sortings Solve time: 1m 3s Verified: yes Solution Problem Understanding We are given several stacks of unit cubes, each stack having an initial height. In a single move, we can take exactly one cube from the top of one stack and place it on top of another stack. Over time, this allows us to redistribute cubes between...

Practice › Codeforces Solutions ›

MemSQL Start[c]UP 2.0 - Round 1

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

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

CF 457E - Flow Optimality

CF 457E - Flow Optimality Rating: 3000 Tags: constructive algorithms, flows, math Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a network of nodes connected by links, where each link can carry data in one direction at a time. Each link has a cost proportional to the square of the bandwidth multiplied by a given weight. Some links already have assigned bandwidths, representing the intern’s proposed...

Practice › Codeforces Solutions ›

Codeforces Round 257 (Div. 1)

Codeforces Round 257 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1700-2900 | Time: 9m 38s Problem Name Rating Tags Solve Time Verified A Jzzhu and Chocolate 1700 greedy, math 2m 1s ✓ B Jzzhu and Cities 2000 graphs, greedy, shortest-paths 1m 26s ✓ C Jzzhu and Apples 2500 constructive-algorithms, number-theory 1m 44s ✗ D Jzzhu and Numbers 2400 bitmasks, combinatorics, dp 1m 54s...

Practice › Codeforces Solutions ›

Codeforces Round 274 (Div. 2)

Codeforces Round 274 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1000-1900 | Time: 19m 33s Problem Name Rating Tags Solve Time Verified A Expression 1000 brute-force, math 5m 21s ✗ B Towers 1400 brute-force, constructive-algorithms, greedy 1m 3s ✓ C Exams 1400 greedy, sortings 10m 58s ✗ D Long Jumps 1700 binary-search, greedy, implementation 1m 9s ✓ E Riding in a Lift 1900...

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

CF 460D - Little Victor and Set

CF 460D - Little Victor and Set Rating: 2300 Tags: brute force, constructive algorithms, math Solve time: 1m 21s Verified: no Solution Problem Understanding Victor wants to build a set of integers within a specified range such that the XOR of all its elements is minimized. The set can contain up to k elements, all distinct, and every element must lie between l and r inclusive. The input consists of...

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

CF 476D - Dreamoon and Sets

CF 476D - Dreamoon and Sets Rating: 1900 Tags: constructive algorithms, greedy, math Solve time: 2m 8s Verified: yes Solution Problem Understanding The task is to construct n sets of four distinct positive integers, where each set has a certain "rank" k . The rank condition requires that the greatest common divisor (GCD) of any two numbers within the set equals exactly k . We are allowed to use integers...

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 › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452B - 4-point polyline

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

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

CF 432E - Square Tiling

CF 432E - Square Tiling Rating: 2300 Tags: constructive algorithms, greedy Solve time: 2m 40s Verified: yes Solution Problem Understanding We are asked to color an $n \times m$ grid such that every contiguous region of the same color forms a square. Each square can be of any size, as long as it is a perfect square in shape and does not overlap another square of the same color. The...

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 ›

Codeforces Round 158 (Div. 2)

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

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

CF 148C - Terse princess

CF 148C - Terse princess Rating: 1700 Tags: constructive algorithms, greedy Solve time: 2m 14s Verified: no Solution Problem Understanding We need to construct an array of groom fortunes so that the princess reacts in exactly the required way. For every groom after the first one, two special situations are possible. If the current fortune is larger than every previous fortune, the princess says Oh... . If the current fortune...

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

CF 198D - Cube Snake

CF 198D - Cube Snake Rating: 2700 Tags: constructive algorithms Solve time: 2m 13s Verified: no Solution Problem Understanding We must fill an $n \times n \times n$ cube with the integers from $1$ to $n^3$. Consecutive numbers must always occupy cubes that share a face, so the numbering forms a Hamiltonian path through the 3D grid. The second requirement is the unusual one. For every cube size $i$ from...

Practice › Codeforces Solutions ›

Codeforces Round 105 (Div. 2)

Codeforces Round 105 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-1900 | Time: 9m 21s Problem Name Rating Tags Solve Time Verified A Insomnia cure 800 constructive-algorithms, implementation, math 1m 34s ✗ B Escape 1500 implementation, math 1m 12s ✓ C Terse princess 1700 constructive-algorithms, greedy 2m 14s ✗ D Bag of mice 1800 dp, games, math 1m 55s ✓ E Porcelain 1900...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Round 2

Croc Champ 2012 - Round 2 Type: Special | Problems: 4 | Verified: 4/4 | Rating range: 1200-3100 | Time: 6m 33s Problem Name Rating Tags Solve Time Verified A Trading Business 1200 greedy, sortings 1m 11s ✓ B Word Cut 1700 dp 1m 42s ✓ C Playing with Superglue 2000 combinatorics, constructive-algorithms 1m 28s ✓ E Archaeology 3100 data-structures, dfs-and-similar, trees 2m 12s ✓

Practice › Codeforces Solutions › Codeforces Round 116 (Div. 2, ACM-ICPC Rules) ›

CF 180F - Mathematical Analysis Rocks!

CF 180F - Mathematical Analysis Rocks! Rating: 1200 Tags: constructive algorithms, implementation, math Solve time: 1m 28s Verified: yes Solution Problem Understanding Every student points to exactly one best friend, and every student is pointed to by exactly one other student. That means the friendship relation forms a permutation p . On day 1, notebook i stays with student i . On every following day, notebooks move according to p...

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 › VK Cup 2012 Finals, Practice Session ›

CF 209C - Trails and Glades

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

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

CF 443A - Anton and Letters

CF 443A - Anton and Letters Rating: 800 Tags: constructive algorithms, implementation Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a single formatted string that represents a set of lowercase English letters. The set is written in a very specific textual form: it starts with an opening brace, ends with a closing brace, and inside the braces letters are listed separated by comma and space. The...

Practice › Codeforces Solutions ›

Codeforces Round 165 (Div. 1)

Codeforces Round 165 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 2/4 | Rating range: 1700-3100 | Time: 7m 2s Problem Name Rating Tags Solve Time Verified B Greenhouse Effect 1700 dp 1m 21s ✓ C Flawed Flow 2100 constructive-algorithms, flows, graphs 2m ✓ D Maximum Waterfall 2600 data-structures, dp, graphs 1m 43s ✗ E String Theory 3100 geometry, math, strings 1m 58s ✗

Practice › Codeforces Solutions ›

Codeforces Round 166 (Div. 2)

Codeforces Round 166 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 3/4 | Rating range: 1300-2200 | Time: 7m 9s Problem Name Rating Tags Solve Time Verified B Prime Matrix 1300 binary-search, brute-force, math 1m 46s ✓ C Secret 1500 constructive-algorithms, implementation 1m 31s ✗ D Good Substrings 1800 data-structures, strings 1m 42s ✓ E Three Horses 2200 constructive-algorithms, math, number-theory 2m 10s ✓

Practice › Codeforces Solutions ›

VK Cup 2012 Finals, Practice Session

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

Practice › Codeforces Solutions ›

RCC 2014 Warmup (Div. 2)

RCC 2014 Warmup (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1400-2400 | Time: 7m 19s Problem Name Rating Tags Solve Time Verified A Elimination 1500 dp, implementation, math 1m 39s ✓ B Crash 1400 implementation 1m 29s ✓ C Football 1400 constructive-algorithms, graphs, implementation 1m 49s ✓ D Cunning Gena 1900 bitmasks, dp, greedy 34s ✗ E Square Table 2400 constructive-algorithms, math, probabilities...

Practice › Codeforces Solutions ›

Codeforces Round 174 (Div. 1)

Codeforces Round 174 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 2/3 | Rating range: 1600-2400 | Time: 5m 38s Problem Name Rating Tags Solve Time Verified A Cows and Sequence 1600 constructive-algorithms, data-structures, implementation 1m 35s ✓ C Coin Troubles 2100 dp 2m 22s ✗ D Cows and Cool Sequences 2400 dp, math, number-theory 1m 41s ✓

Practice › Codeforces Solutions ›

April Fools Day Contest 2014

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

Practice › Codeforces Solutions ›

Codeforces Round 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 102 (Div. 1) ›

CF 142B - Help General

CF 142B - Help General Rating: 1800 Tags: constructive algorithms, greedy, implementation Solve time: 1m 38s Verified: yes Solution Problem Understanding We have an n × m chessboard-like grid, and we want to place as many soldiers as possible. Two soldiers conflict if the squared Euclidean distance between their cells is exactly 5 . The only integer pairs whose squared distance equals 5 are (1, 2) and (2, 1) up...

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 ›

Codeforces Round 182 (Div. 1)

Codeforces Round 182 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1800-2800 | Time: 17m 11s Problem Name Rating Tags Solve Time Verified A Yaroslav and Sequence 1800 constructive-algorithms 1m 30s ✓ B Yaroslav and Time 2100 binary-search, graphs, shortest-paths 2m 10s ✓ C Yaroslav and Algorithm 2500 constructive-algorithms 6m 58s ✓ D Yaroslav and Divisors 2200 data-structures 2m 55s ✓ E Yaroslav and...

Practice › Codeforces Solutions ›

Codeforces Round 127 (Div. 1)

Codeforces Round 127 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1700-2600 | Time: 7m 7s Problem Name Rating Tags Solve Time Verified A Clear Symmetry 1700 constructive-algorithms, dp, math 1m 9s ✓ B Guess That Car! 1800 math, ternary-search 1m ✓ C Fragile Bridges 2000 dp 1m 40s ✓ D Brand New Problem 2600 bitmasks, brute-force, dp 1m 39s ✓ E Thoroughly Bureaucratic...

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

CF 331E1 - Deja Vu

CF 331E1 - Deja Vu Rating: 2900 Tags: constructive algorithms, graphs, implementation Solve time: 6m 28s Verified: no Solution Problem Understanding We are given a directed graph of shops and streets. Every directed edge has an attached sequence of shop numbers called a vision. Whenever Neo traverses that edge, he sees exactly that sequence. Suppose Neo walks through a path $$p_0 \to p_1 \to p_2 \to \dots \to p_k$$ The...

Practice › Codeforces Solutions ›

Codeforces Round 164 (Div. 2)

Codeforces Round 164 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 3/4 | Rating range: 800-2300 | Time: 7m 8s Problem Name Rating Tags Solve Time Verified A Games 800 brute-force 1m 29s ✓ C Beautiful Sets of Points 1500 constructive-algorithms, implementation 1m 33s ✗ D Wall Bars 2300 dp 2m 21s ✓ E Playlist 2100 math, probabilities, sortings 1m 45s ✓

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

CF 271C - Secret

CF 271C - Secret Rating: 1500 Tags: constructive algorithms, implementation Solve time: 1m 31s Verified: no Solution Problem Understanding We are asked to distribute a collection of n words among k Keepers in such a way that every Keeper receives a subset of words satisfying three conditions. First, no two Keepers can share a word. Second, every word must be assigned to some Keeper. Third, the numbers of words assigned...

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

CF 266B - Queue at the School

CF 266B - Queue at the School Rating: 800 Tags: constructive algorithms, graph matchings, implementation, shortest paths Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a queue made of boys and girls, represented as a string containing only B and G . Every second, each adjacent pair "BG" swaps positions and becomes "GB" . The swaps happen simultaneously. That detail matters a lot. If a boy...

Practice › Codeforces Solutions › Coder-Strike 2014 - Finals (online edition, Div. 2) ›

CF 421A - Pasha and Hamsters

CF 421A - Pasha and Hamsters Rating: 800 Tags: constructive algorithms, implementation Solve time: 1m Verified: yes Solution Problem Understanding We are given a line of apples numbered from 1 to n. Each apple can be given to exactly one of two hamsters, Arthur or Alexander. The only restriction is that Arthur must receive only apples he likes, and Alexander must receive only apples he likes. Some apples may be...

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

CF 286E - Ladies' Shop

CF 286E - Ladies' Shop Rating: 2800 Tags: constructive algorithms, fft, math Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a collection of “bag capacities” $a_1 < a_2 < \dots < a_n$, each capacity describing a special requirement: the bag can exactly accommodate some multiset of item weights whose sum is exactly that capacity, but it is forbidden to use a configuration whose total weight is...

Practice › Codeforces Solutions ›

Codeforces Round 134 (Div. 2)

Codeforces Round 134 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 0/2 | Rating range: 1100-1100 | Time: 4m 13s Problem Name Rating Tags Solve Time Verified A Mountain Scenery 1100 brute-force, constructive-algorithms, implementation 2m 49s ✗ B Airport 1100 implementation 1m 24s ✗

Practice › Codeforces Solutions ›

Codeforces Round 180 (Div. 1)

Codeforces Round 180 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 2/3 | Rating range: 1600-3000 | Time: 4m 3s Problem Name Rating Tags Solve Time Verified A Parity Game 1700 constructive-algorithms 1m 14s ✓ B Fish Weight 1600 constructive-algorithms, greedy 1m 2s ✓ E Mystic Carvings 3000 data-structures 1m 47s ✗

Practice › Codeforces Solutions ›

VK Cup 2012 Round 1

VK Cup 2012 Round 1 Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1300-2500 | Time: 11m 9s Problem Name Rating Tags Solve Time Verified A Dress'em in Vests! 1300 binary-search, brute-force, greedy 1m 15s ✓ B Discounts 1700 constructive-algorithms, greedy, sortings 2m 13s ✓ C Abracadabra 2400 divide-and-conquer 2m 37s ✓ D Distance in Tree 1800 dfs-and-similar, dp, trees 3m 13s ✓ E Polycarpus the Safecracker...

Practice › Codeforces Solutions ›

Codeforces Round 125 (Div. 2)

Codeforces Round 125 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 900-1900 | Time: 3m 12s Problem Name Rating Tags Solve Time Verified A Hexadecimal's theorem 900 brute-force, constructive-algorithms, implementation 1m 37s ✓ B Special Olympics 1900 geometry 1m 35s ✗

Practice › Codeforces Solutions ›

Codeforces Round 160 (Div. 1)

Codeforces Round 160 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 3/3 | Rating range: 1400-2800 | Time: 6m 1s Problem Name Rating Tags Solve Time Verified A Maxim and Discounts 1400 greedy, sortings 3m 10s ✓ C Maxim and Matrix 2000 constructive-algorithms, dp, math 1m 11s ✓ E Maxim and Calculator 2800 brute-force, dp, two-pointers 1m 40s ✓

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

CF 173D - Deputies

CF 173D - Deputies Rating: 2500 Tags: constructive algorithms, graphs, greedy, implementation Solve time: 3m 4s Verified: yes Solution Problem Understanding We are asked to assign k deputies to n cities, with the condition that each deputy manages exactly three cities. The cities are placed on two sides of a river, and some pairs of cities are connected by bridges that span the river. No deputy may manage two cities...

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

CF 234H - Merging Two Decks

CF 234H - Merging Two Decks Rating: 2000 Tags: constructive algorithms, greedy Solve time: 2m 57s Verified: no Solution Problem Understanding We are given two stacks of cards, each card either face up or face down. The goal is to merge the decks into a single stack in a way that preserves the relative order of cards within each original deck, and then perform a series of operations to turn...

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

CF 260D - Black and White Tree

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

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

CF 264A - Escape from Stones

CF 264A - Escape from Stones Rating: 1200 Tags: constructive algorithms, data structures, implementation, two pointers Solve time: 1m 5s Verified: yes Solution Problem Understanding We start with a segment representing Liss’s current safe region, initially the interval from 0 to 1. Stones fall one after another, and each stone always lands exactly at the midpoint of Liss’s current interval. After each impact, Liss reacts by discarding either the left...

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

CF 303A - Lucky Permutation Triple

CF 303A - Lucky Permutation Triple Rating: 1300 Tags: constructive algorithms, implementation, math Solve time: 2m 15s Verified: no Solution Problem Understanding We are asked to construct three permutations $a$, $b$, and $c$ of length $n$ such that for every index $i$ the sum of $a[i]$ and $b[i]$ modulo $n$ equals $c[i]$ modulo $n$. Each permutation contains exactly the numbers from 0 to $n-1$ once, and the output must either...

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

CF 321C - Ciel the Commander

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

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

CF 261C - Maxim and Matrix

CF 261C - Maxim and Matrix Rating: 2000 Tags: constructive algorithms, dp, math Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a very large range of possible values for a parameter m, and for each such value a deterministic procedure produces a matrix filled using bitwise XOR rules. The matrix has size (m + 1) by (m + 1), and the filling follows a fixed recursive...

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

CF 232A - Cycles

CF 232A - Cycles Rating: 1600 Tags: binary search, constructive algorithms, graphs, greedy Solve time: 3m 45s Verified: yes Solution Problem Understanding We need to construct an undirected graph that contains exactly k triangles. A triangle means three different vertices where every pair is connected by an edge. The graph may contain any number of other structures, but the total number of triangles must be exactly k . We are...

Practice › Codeforces Solutions ›

Codeforces Round 144 (Div. 1)

Codeforces Round 144 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 2/4 | Rating range: 1600-2900 | Time: 17m 15s Problem Name Rating Tags Solve Time Verified A Cycles 1600 binary-search, constructive-algorithms, graphs 3m 45s ✓ B Table 1900 bitmasks, combinatorics, dp 8m 46s ✗ C Doe Graphs 2600 constructive-algorithms, divide-and-conquer, dp 2m 23s ✓ D Fence 2900 binary-search, data-structures, string-suffix-structures 2m 21s ✗

Practice › Codeforces Solutions › April Fools Day Contest 2013 ›

CF 290E - HQ

CF 290E - HQ Rating: 2500 Tags: *special, constructive algorithms Solve time: 1m 43s Verified: yes Solution Problem Understanding The original HQ9+ language has several commands with special behavior. This problem asks about a reduced version called HQ..., and the destroyed statement leaves only enough clues to reconstruct the intended task. We are given a single string representing a program. We must determine whether this program produces output. In the...

Practice › Codeforces Solutions ›

MemSQL start[c]up Round 2 - online version

MemSQL start[c]up Round 2 - online version Type: Special | Problems: 3 | Verified: 1/3 | Rating range: 1900-2800 | Time: 8m 55s Problem Name Rating Tags Solve Time Verified B Palindrome 1900 constructive-algorithms, dp 2m 24s ✗ D Rectangles and Square 2400 brute-force, dp 3m 41s ✓ E Counting Skyscrapers 2800 dp, math, probabilities 2m 50s ✗

Practice › Codeforces Solutions ›

Codeforces Round 203 (Div. 2)

Codeforces Round 203 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 1/4 | Rating range: 1200-2200 | Time: 17m 31s Problem Name Rating Tags Solve Time Verified A TL 1200 brute-force, greedy, implementation 6m 57s ✗ B Resort 1500 graphs 4m 28s ✗ C Bombs 1600 greedy, implementation, sortings 3m 48s ✓ E Wrong Floyd 2200 brute-force, constructive-algorithms, dfs-and-similar 2m 18s ✗

Practice › Codeforces Solutions › Croc Champ 2012 - Final ›

CF 183A - Headquarters

CF 183A - Headquarters Rating: 1700 Tags: constructive algorithms, math Solve time: 1m 52s Verified: yes Solution Problem Understanding The car started somewhere on the infinite 2D grid and eventually reached the ice-cream stall at (0, 0) . We know the number of moves and the order of the GPS records, but each record only tells us a set of possible directions for that step. For example, "UR" means the...

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

CF 141E - Clearing Up

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

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

CF 141C - Queue

CF 141C - Queue Rating: 1800 Tags: constructive algorithms, greedy, sortings Solve time: 2m 24s Verified: no Solution Problem Understanding Each person remembers a single number, how many taller people stood before them in the queue. We no longer know either the original order or the actual heights. The task is to reconstruct any valid queue order together with heights that satisfy every person's remembered value. Suppose a person has...

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

CF 271E - Three Horses

CF 271E - Three Horses Rating: 2200 Tags: constructive algorithms, math, number theory Solve time: 2m 10s Verified: yes Solution Problem Understanding We start with exactly one card (x, y) where 1 ≤ x < y ≤ m . Three operations are available. The gray horse increases both numbers by one: (a, b) → (a + 1, b + 1) . The white horse works only when both numbers are...

Practice › Codeforces Solutions ›

Codeforces Round 192 (Div. 2)

Codeforces Round 192 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 0/1 | Rating range: 1300-1300 | Time: 1m 46s Problem Name Rating Tags Solve Time Verified B Road Construction 1300 constructive-algorithms, graphs 1m 46s ✗

Practice › Codeforces Solutions ›

Codeforces Round 246 (Div. 2)

Codeforces Round 246 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-2300 | Time: 4m 1s Problem Name Rating Tags Solve Time Verified A Choosing Teams 800 greedy, implementation, sortings 1m 21s ✓ E Square Tiling 2300 constructive-algorithms, greedy 2m 40s ✓

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 ›

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 ›

CROC-MBTU 2012, Elimination Round (ACM-ICPC)

CROC-MBTU 2012, Elimination Round (ACM-ICPC) Type: ICPC/IOI | Problems: 8 | Verified: 8/8 | Rating range: 800-2200 | Time: 18m 42s Problem Name Rating Tags Solve Time Verified A System Administrator 800 implementation 3m 27s ✓ B Internet Address 1100 implementation, strings 1m 53s ✓ C Game with Coins 1700 greedy 1m 37s ✓ D Restoring Table 1500 constructive-algorithms, greedy 3m 10s ✓ E Mishap in Club 1400 greedy, implementation...

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

CF 268C - Beautiful Sets of Points

CF 268C - Beautiful Sets of Points Rating: 1500 Tags: constructive algorithms, implementation Solve time: 1m 33s Verified: no Solution Problem Understanding We are asked to construct a set of points on a 2D integer grid with coordinates between 0 and n along the x-axis and 0 and m along the y-axis, excluding the origin (0,0). The set must satisfy the property that the Euclidean distance between any two points...

Practice › Codeforces Solutions ›

Codeforces Round 104 (Div. 1)

Codeforces Round 104 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1200-2900 | Time: 10m 29s Problem Name Rating Tags Solve Time Verified A Lucky Conversion 1200 greedy, implementation 2m 2s ✓ B Lucky Number 2 1800 constructive-algorithms 2m 22s ✓ C Lucky Subsequence 2100 combinatorics, dp, math 2m 5s ✓ D Lucky Pair 2900 combinatorics, data-structures, implementation 1m 48s ✗ E Lucky Queries...

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

CF 283A - Cows and Sequence

CF 283A - Cows and Sequence Rating: 1600 Tags: constructive algorithms, data structures, implementation Solve time: 1m 35s Verified: yes Solution Problem Understanding We maintain a dynamic sequence of integers. Initially the sequence contains only one value, 0 . Each operation changes the sequence in one of three ways. We may add some value x to the first a elements, append a new number to the end, or remove the...

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 › Codeforces Round 104 (Div. 1) ›

CF 145B - Lucky Number 2

CF 145B - Lucky Number 2 Rating: 1800 Tags: constructive algorithms Solve time: 2m 22s Verified: yes Solution Problem Understanding We need to construct the lexicographically smallest lucky number consisting only of digits 4 and 7 such that four substring counts match given values. The values mean: a1 is the number of digit 4 a2 is the number of digit 7 a3 is the number of substring "47" a4 is...

Practice › Codeforces Solutions ›

Codeforces Round 131 (Div. 2)

Codeforces Round 131 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1600 | Time: 3m 45s Problem Name Rating Tags Solve Time Verified A System of Equations 800 brute-force 56s ✓ B Hometask 1600 brute-force, constructive-algorithms, greedy 2m 49s ✓

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

CF 214B - Hometask

CF 214B - Hometask Rating: 1600 Tags: brute force, constructive algorithms, greedy, math Solve time: 2m 49s Verified: yes Solution Problem Understanding We are given a multiset of digits and asked to construct the largest integer from some or all of them such that the resulting number is divisible by 2, 3, and 5 simultaneously. Because a number divisible by 2, 3, and 5 is divisible by 30, the task...

Practice › Codeforces Solutions ›

Codeforces Round 186 (Div. 2)

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

Practice › Codeforces Solutions ›

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) Type: ICPC/IOI | Problems: 4 | Verified: 3/4 | Rating range: 1900-2900 | Time: 7m 47s Problem Name Rating Tags Solve Time Verified D Numbers 2900 - 2m 21s ✗ E Flights 2600 graphs, shortest-paths 1m 54s ✓ F Race 2300 brute-force, implementation 2m 26s ✓ G Challenging Balloons 1900 constructive-algorithms 1m 6s ✓

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

CF 311A - The Closest Pair

CF 311A - The Closest Pair Rating: 1300 Tags: constructive algorithms, implementation Solve time: 3m 3s Verified: yes Solution Problem Understanding We are given a set of points in a 2D plane, and we want to measure how quickly a specific closest-pair algorithm behaves on a worst-case input. The algorithm itself is a straightforward double loop over points sorted by x-coordinate, but it includes a pruning condition: once the horizontal...

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

CF 218A - Mountain Scenery

CF 218A - Mountain Scenery Rating: 1100 Tags: brute force, constructive algorithms, implementation Solve time: 2m 49s Verified: no Solution Problem Understanding We are given a polyline representing mountain peaks. The polyline has 2*n + 1 vertices, with even-indexed vertices (2, 4, 6, ..., 2*n) representing peaks. In the initial picture, each peak is strictly higher than its neighbors, i.e., for every even i , y[i-1] < y[i] > y[i+1]...

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

CF 232C - Doe Graphs

CF 232C - Doe Graphs Rating: 2600 Tags: constructive algorithms, divide and conquer, dp, graphs, shortest paths Solve time: 2m 23s Verified: yes Solution Problem Understanding The graph family is built recursively. D(0) is a single vertex. D(1) is a single edge. For every larger order, D(n) is formed by taking a copy of D(n-1) and a shifted copy of D(n-2) , then connecting them with two extra edges. The...

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

CF 301C - Yaroslav and Algorithm

CF 301C - Yaroslav and Algorithm Rating: 2500 Tags: constructive algorithms Solve time: 6m 58s Verified: yes Solution Problem Understanding We must construct a small string rewriting program. The program consists of ordered commands. Each command searches for a substring and replaces its first occurrence with another string. Some commands continue execution after replacement, while others terminate immediately. The task is not to increment every integer in general. We only...

Practice › Codeforces Solutions › Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) ›

CF 241G - Challenging Balloons

CF 241G - Challenging Balloons Rating: 1900 Tags: constructive algorithms Solve time: 1m 6s Verified: yes Solution Problem Understanding We have a row of balloons placed at increasing positions on a line. Each balloon has a pressure endurance, which limits how large its radius can grow. We inflate balloons sequentially from left to right. Each balloon expands until either it reaches its maximum radius, dictated by its pressure endurance, or...

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

CF 209B - Pixels

CF 209B - Pixels Rating: 2100 Tags: constructive algorithms, math Solve time: 1m 41s Verified: yes Solution Problem Understanding We start with three piles of pixels, one red, one green, and one blue. A fight can only happen between two different colors. When that happens, one pixel survives and immediately changes into the third color. For example, if a red and a green pixel fight, the survivor becomes blue. A...

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 › Codeforces Round 148 (Div. 1) ›

CF 238A - Not Wool Sequences

CF 238A - Not Wool Sequences Rating: 1300 Tags: constructive algorithms, math Solve time: 5m 18s Verified: yes Solution Problem Understanding We work with arrays of length n , where every element is an integer from 0 to 2^m - 1 . A sequence is called "wool" if there exists some contiguous subarray whose xor is 0 . We are asked to count how many sequences are not wool, meaning...

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

CF 417C - Football

CF 417C - Football Rating: 1400 Tags: constructive algorithms, graphs, implementation Solve time: 1m 49s Verified: yes Solution Problem Understanding We are asked to construct a complete record of matches between n teams, where every match has a winner and a loser, and no pair of teams plays more than once. The final condition we must satisfy is global: for every ordered pair of distinct teams (i, j) , team...

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 › Testing Round 6 ›

CF 306D - Polygon

CF 306D - Polygon Rating: 2300 Tags: constructive algorithms, geometry Solve time: 2m 9s Verified: no Solution Problem Understanding We need to construct a convex polygon with exactly n vertices such that every interior angle is equal, but every side length is different. A polygon where all angles are equal is called equiangular. For a convex equiangular polygon, the direction of each edge is fixed. If we walk around the...

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

CF 246C - Beauty Pageant

CF 246C - Beauty Pageant Rating: 1600 Tags: brute force, constructive algorithms, greedy Solve time: 1m 43s Verified: yes Solution Problem Understanding We are asked to select soldiers from a battalion to participate in a beauty pageant over several days. Each soldier has a unique beauty value. On each day, we must send a group of soldiers whose combined beauty is unique compared to the other days. The detachment for...

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

CF 327E - Axis Walking

CF 327E - Axis Walking Rating: 2300 Tags: bitmasks, combinatorics, constructive algorithms, dp, meet-in-the-middle Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a multiset of positive segment lengths. Any permutation of these lengths defines a walk along the number line starting from 0, where we cumulatively add each chosen segment. After each segment, we “pause” at the current position, and these pause positions are exactly the...

Practice › Codeforces Solutions › MemSQL start[c]up Round 2 - online version ›

CF 335B - Palindrome

CF 335B - Palindrome Rating: 1900 Tags: constructive algorithms, dp Solve time: 2m 24s Verified: no Solution Problem Understanding We are given a lowercase string and asked to extract a palindromic subsequence from it. A subsequence keeps the original order of characters but may skip positions. The output requirement has a twist. If the string contains any palindromic subsequence of length at least 100, we only need to print one...

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

CF 329A - Purification

CF 329A - Purification Rating: 1500 Tags: constructive algorithms, greedy Solve time: 3m 58s Verified: no Solution Problem Understanding We are given an $n \times n$ grid where every cell is initially unclean. Some cells are marked as forbidden for casting a spell. When we cast a purification spell on a cell $(r, c)$, we clean every cell in row $r$ and every cell in column $c$. However, the chosen...

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

CF 231B - Magic, Wizardry and Wonders

CF 231B - Magic, Wizardry and Wonders Rating: 1500 Tags: constructive algorithms, greedy Solve time: 1m 38s Verified: yes Solution LeetCode 2659 - Make Array Empty Problem Understanding We are given an array of distinct integers. At every operation, we inspect the first element of the current array. If that first element is currently the smallest remaining value in the array, we remove it. Otherwise, we rotate it by moving...

Practice › Codeforces Solutions ›

Testing Round 7

Testing Round 7 Type: Special | Problems: 1 | Verified: 1/1 | Rating range: 1600-1600 | Time: 3m 39s Problem Name Rating Tags Solve Time Verified A Black-and-White Cube 1600 combinatorics, constructive-algorithms 3m 39s ✓

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

CF 193A - Cutting Figure

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

Practice › Codeforces Solutions › CROC-MBTU 2012, Elimination Round (ACM-ICPC) ›

CF 245D - Restoring Table

CF 245D - Restoring Table Rating: 1500 Tags: constructive algorithms, greedy Solve time: 3m 10s Verified: yes Solution Problem Understanding We are given a square table that was originally generated from a hidden array of non-negative integers. Each off-diagonal entry is the bitwise AND of the corresponding pair of hidden values, while diagonal entries are artificially replaced by -1. The task is to reconstruct any valid hidden array that could...

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 › RCC 2014 Warmup (Div. 2) ›

CF 417E - Square Table

CF 417E - Square Table Rating: 2400 Tags: constructive algorithms, math, probabilities Solve time: 1m 48s Verified: yes Solution Problem Understanding We are asked to fill an $n \times m$ grid with positive integers not exceeding $10^8$. The constraint is not about individual cells but about structure: for every row and every column, if we square all numbers in that line and sum them, the result must itself be a...

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

CF 220B - Little Elephant and Array

CF 220B - Little Elephant and Array Rating: 1800 Tags: constructive algorithms, data structures Solve time: 1m 7s Verified: yes Solution Problem Understanding We are given an array of positive integers and multiple queries, each specifying a contiguous subarray. For each query, we are asked to count how many numbers appear in the subarray exactly as many times as their own value. For instance, if a number 3 appears exactly...

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

CF 197A - Plate Game

CF 197A - Plate Game Rating: 1600 Tags: constructive algorithms, games, math Solve time: 1m 22s Verified: yes Solution Problem Understanding We have a rectangular table with dimensions a × b and an unlimited supply of identical circular plates with radius r . Two players alternate placing plates on the table. Every plate must lie completely inside the rectangle, and plates may touch but cannot overlap. The game ends when...

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

CF 441D - Valera and Swaps

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

Practice › Codeforces Solutions ›

Codeforces Round 252 (Div. 2)

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

Practice › Codeforces Solutions ›

Codeforces Round 136 (Div. 1)

Codeforces Round 136 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1300-2500 | Time: 8m 14s Problem Name Rating Tags Solve Time Verified A Little Elephant and Problem 1300 implementation, sortings 2m 48s ✓ B Little Elephant and Array 1800 constructive-algorithms, data-structures 1m 7s ✓ C Little Elephant and Shifts 2100 data-structures 1m 54s ✓ D Little Elephant and Triangle 2500 geometry, math 2m...

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

CF 301A - Yaroslav and Sequence

CF 301A - Yaroslav and Sequence Rating: 1800 Tags: constructive algorithms Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given an array of length (2·n - 1). Yaroslav can perform an operation any number of times where he selects exactly n elements and multiplies each by -1. Our task is to determine the maximum sum achievable by applying this operation optimally. The input consists of a single...

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

CF 148A - Insomnia cure

CF 148A - Insomnia cure Rating: 800 Tags: constructive algorithms, implementation, math Solve time: 1m 34s Verified: no Solution Problem Understanding The problem asks us to figure out how many dragons get affected by a princess who has a unique way of defending herself. She targets every k -th, l -th, m -th, and n -th dragon with different actions. The total number of dragons is d . The input...

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 › Codeforces Round 140 (Div. 1) ›

CF 226D - The table

CF 226D - The table Rating: 2100 Tags: constructive algorithms, greedy Solve time: 2m 58s Verified: no Solution Problem Understanding We are given a rectangular table of integers with $n$ rows and $m$ columns. Each cell contains a number that could be positive, negative, or zero. Harry can perform two types of operations: flip the sign of all numbers in a row or flip the sign of all numbers in...

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

Codeforces Round 184 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1600-2300 | Time: 7m 58s Problem Name Rating Tags Solve Time Verified A Strange Addition 1600 brute-force, constructive-algorithms, implementation 1m 22s ✓ B Continued Fractions 1700 brute-force, implementation, math 1m 25s ✓ C Ivan and Powers of Two 1600 greedy, implementation 1m 48s ✓ D Olya and Graph 2200 combinatorics, math 1m 36s...

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

CF 424D - Biathlon Track

CF 424D - Biathlon Track Rating: 2300 Tags: binary search, brute force, constructive algorithms, data structures, dp Solve time: 1m 21s Verified: no Solution Problem Understanding We are given a rectangular grid where each cell has a height. A biathlon track must be the boundary of a sub-rectangle, and athletes run clockwise along this boundary. Every move is between adjacent cells on the perimeter, so the total cost depends entirely...

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 › VK Cup 2012 Round 1 ›

CF 161B - Discounts

CF 161B - Discounts Rating: 1700 Tags: constructive algorithms, greedy, sortings Solve time: 2m 13s Verified: yes Solution Problem Understanding We have a collection of items sold in a supermarket. Every item has a price and a type. Type 1 means the item is a stool, type 2 means it is a pencil. Polycarpus owns exactly k shopping carts, and every cart must contain at least one item. The store...

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

CF 234G - Practice

CF 234G - Practice Rating: 1600 Tags: constructive algorithms, divide and conquer, implementation Solve time: 2m 54s Verified: no Solution Problem Understanding We are given a team of n football players, each with a unique number from 1 to n . The coach wants to organize practice games so that every pair of players has faced each other on opposing teams at least once. Each practice splits all players into...

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

CF 238B - Boring Partition

CF 238B - Boring Partition Rating: 1800 Tags: constructive algorithms Solve time: 3m 56s Verified: yes Solution Problem Understanding We are given an array of integers and a value h . Every pair of elements contributes a value depending on whether the two elements are placed into the same group or different groups. If two numbers a[i] and a[j] belong to the same subsequence, their pair value is: $$a[i] +...

Practice › Codeforces Solutions ›

Codeforces Round 163 (Div. 2)

Codeforces Round 163 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 2/4 | Rating range: 800-2500 | Time: 8m 10s Problem Name Rating Tags Solve Time Verified B Queue at the School 800 constructive-algorithms, graph-matchings, implementation 1m 21s ✓ C Below the Diagonal 2100 constructive-algorithms, greedy, math 2m 17s ✗ D BerDonalds 2400 graphs, math, shortest-paths 2m 9s ✗ E More Queries to Array... 2500 data-structures, math 2m...

Practice › Codeforces Solutions ›

Codeforces Round 176 (Div. 1)

Codeforces Round 176 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 2200-2800 | Time: 2m 31s Problem Name Rating Tags Solve Time Verified B Shifting 2200 implementation 1m 1s ✓ E Ladies' Shop 2800 constructive-algorithms, fft, math 1m 30s ✓

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

CF 213D - Stars

CF 213D - Stars Rating: 2300 Tags: constructive algorithms, geometry Solve time: 1m 36s Verified: no Solution Problem Understanding We must construct n pentagram-shaped stars in the plane. Each star comes from a regular pentagon with side length 10 , and the painted segments are exactly its five diagonals. The output is not just geometry. We also need a valid drawing order. Rubik starts with the pen touching the paper,...

Practice › Codeforces Solutions ›

Codeforces Round 125 (Div. 1)

Codeforces Round 125 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1700-2700 | Time: 6m 48s Problem Name Rating Tags Solve Time Verified A About Bacteria 1700 implementation, math 1m 28s ✓ D Cube Snake 2700 constructive-algorithms 2m 13s ✗ E Gripping Story 2400 binary-search, data-structures, sortings 3m 7s ✗

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

CF 430A - Points and Segments (easy)

CF 430A - Points and Segments (easy) Rating: 1600 Tags: constructive algorithms, sortings Solve time: 1m 34s Verified: no Solution Problem Understanding We are asked to color a set of points on a number line using two colors, red and blue, so that for each given segment, the number of red and blue points inside that segment differ by at most one. In other words, every segment should be nearly...

Practice › Codeforces Solutions ›

Codeforces Round 245 (Div. 2)

Codeforces Round 245 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 1400-1600 | Time: 3m 20s Problem Name Rating Tags Solve Time Verified A Points and Segments (easy) 1600 constructive-algorithms, sortings 1m 34s ✗ B Balls Game 1400 brute-force, two-pointers 1m 46s ✓

Practice › Codeforces Solutions ›

Codeforces Round 102 (Div. 1)

Codeforces Round 102 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1600-3000 | Time: 13m 21s Problem Name Rating Tags Solve Time Verified A Help Farmer 1600 brute-force, math 1m 53s ✓ B Help General 1800 constructive-algorithms, greedy, implementation 1m 38s ✓ C Help Caretaker 2300 brute-force, dp 1m 30s ✓ D Help Shrek and Donkey 2 2600 games 2m 34s ✓ E Help...

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

CF 176C - Playing with Superglue

CF 176C - Playing with Superglue Rating: 2000 Tags: combinatorics, constructive algorithms Solve time: 1m 28s Verified: yes Solution Problem Understanding We have a rectangular grid and two chips placed on different cells. The first player moves first. On every turn, the first player chooses one chip that is still movable and shifts it by one square in one of the four cardinal directions. After that, the second player chooses...

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

CF 266C - Below the Diagonal

CF 266C - Below the Diagonal Rating: 2100 Tags: constructive algorithms, greedy, math Solve time: 2m 17s Verified: no Solution Problem Understanding We are given an $n \times n$ binary matrix with exactly $n-1$ ones. We may swap any two rows or any two columns. The goal is to rearrange the matrix so that every one ends up strictly below the main diagonal. In other words, if a one is...

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

CF 260C - Balls and Boxes

CF 260C - Balls and Boxes Rating: 1700 Tags: constructive algorithms, greedy, implementation Solve time: 1m 20s Verified: no Solution Problem Understanding We are given the final state of a row of boxes after a very specific operation was applied exactly once in reverse history. Originally, each box contained some number of balls. One box was chosen, emptied completely, and its balls were redistributed one by one starting from the...

Practice › Codeforces Solutions ›

Codeforces Round 253 (Div. 2)

Codeforces Round 253 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 800-800 | Time: 1m 19s Problem Name Rating Tags Solve Time Verified A Anton and Letters 800 constructive-algorithms, implementation 1m 19s ✓

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

CF 305A - Strange Addition

CF 305A - Strange Addition Rating: 1600 Tags: brute force, constructive algorithms, implementation Solve time: 1m 22s Verified: yes Solution Problem Understanding We are asked to select the largest possible subset of integers from a given set such that any two numbers in the subset can be summed by Vasya. Vasya’s summing rule is unusual: for each decimal place, at least one of the two numbers must have a zero...

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

CF 414A - Mashmokh and Numbers

CF 414A - Mashmokh and Numbers Rating: 1500 Tags: constructive algorithms, number theory Solve time: 2m 6s Verified: no Solution Problem Understanding Mashmokh wants to pick a sequence of n distinct integers so that his boss, Bimokh, gains exactly k points in a game. The game proceeds in pairs: Bimokh repeatedly removes the first two integers from the current sequence, scoring the greatest common divisor of these two numbers as...

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

CF 297B - Fish Weight

CF 297B - Fish Weight Rating: 1600 Tags: constructive algorithms, greedy Solve time: 1m 2s Verified: yes Solution Problem Understanding We are given two people, Alice and Bob, each of whom has caught a collection of fish. Every fish belongs to one of k species, and species numbers are ordered so that species with a larger index are guaranteed to be at least as heavy as those with a smaller...

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

CF 272E - Dima and Horses

CF 272E - Dima and Horses Rating: 2200 Tags: combinatorics, constructive algorithms, graphs Solve time: 2m 32s Verified: no Solution Problem Understanding We are given an undirected graph where each vertex represents a horse and each edge represents mutual enmity. We must color every vertex with one of two colors, corresponding to the two parties, such that every horse has at most one enemy inside its own party. Rephrased in...

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

CF 246A - Buggy Sorting

CF 246A - Buggy Sorting Rating: 900 Tags: constructive algorithms, greedy, sortings Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given only a single integer $n$, and we must construct an array of length $n$ that either breaks a very specific sorting procedure or prove that no such array exists. The procedure itself is a double loop that repeatedly scans adjacent pairs in a prefix-like manner and...

Practice › Codeforces Solutions ›

Codeforces Round 143 (Div. 2)

Codeforces Round 143 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 800-1600 | Time: 5m 32s Problem Name Rating Tags Solve Time Verified A Team 800 brute-force, greedy 56s ✓ B Magic, Wizardry and Wonders 1500 constructive-algorithms, greedy 1m 38s ✓ C To Add or Not to Add 1600 binary-search, sortings, two-pointers 2m 58s ✓

Practice › Codeforces Solutions ›

Coder-Strike 2014 - Finals (online edition, Div. 2)

Coder-Strike 2014 - Finals (online edition, Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1900 | Time: 2m 37s Problem Name Rating Tags Solve Time Verified A Pasha and Hamsters 800 constructive-algorithms, implementation 1m ✓ D Bug in Code 1900 binary-search, data-structures, sortings 1m 37s ✓

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

Codeforces Round 183 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-3000 | Time: 15m 59s Problem Name Rating Tags Solve Time Verified A Lucky Permutation Triple 1300 constructive-algorithms, implementation, math 2m 15s ✗ B Rectangle Puzzle II 1700 implementation, math 3m 45s ✓ C Minimum Modular 2400 brute-force, graphs, math 4m 56s ✓ D Rotatable Number 2600 math, number-theory 1m 56s ✓ E...

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

CF 429C - Guess the Tree

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

Practice › Codeforces Solutions ›

Codeforces Round 240 (Div. 1)

Codeforces Round 240 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 2/5 | Rating range: 1400-3200 | Time: 8m 52s Problem Name Rating Tags Solve Time Verified A Mashmokh and Numbers 1500 constructive-algorithms, number-theory 2m 6s ✗ B Mashmokh and ACM 1400 combinatorics, dp, number-theory 1m 21s ✓ C Mashmokh and Reverse Operation 2100 combinatorics, divide-and-conquer 1m 40s ✓ D Mashmokh and Water Tanks 2300 binary-search, data-structures, greedy...

Practice › Codeforces Solutions ›

Codeforces Round 101 (Div. 2)

Codeforces Round 101 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 10m 27s Problem Name Rating Tags Solve Time Verified A Amusing Joke 800 implementation, sortings, strings 1m 31s ✓ B Hopscotch 1400 geometry, math 1m 26s ✓ C Queue 1800 constructive-algorithms, greedy, sortings 2m 24s ✗ D Take-off Ramps 2300 graphs, shortest-paths 2m 15s ✓ E Clearing Up 2300 constructive-algorithms,...

Practice › Codeforces Solutions ›

Codeforces Round 167 (Div. 2)

Codeforces Round 167 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1400-2200 | Time: 5m 30s Problem Name Rating Tags Solve Time Verified B Dima and Sequence 1400 implementation, math 1m 30s ✓ C Dima and Staircase 1500 data-structures, implementation 1m 28s ✓ E Dima and Horses 2200 combinatorics, constructive-algorithms, graphs 2m 32s ✗

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

CF 317E - Princess and Her Shadow

CF 317E - Princess and Her Shadow Rating: 3100 Tags: constructive algorithms, shortest paths Solve time: 1m 46s Verified: yes Solution Problem Understanding We are asked to simulate a chase on a two-dimensional grid between Princess Vlada and her playful Shadow. The grid is infinite but sparse trees are present, which act as obstacles. Both the Princess and Shadow start at distinct integer coordinates. Each turn, the Princess can move...

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 2)

Codeforces Round 124 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1400-1600 | Time: 2m 55s Problem Name Rating Tags Solve Time Verified A Plate Game 1600 constructive-algorithms, games, math 1m 22s ✓ B Limit 1400 math 1m 33s ✓

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

CF 313E - Ilya and Two Numbers

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

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

CF 196C - Paint Tree

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

Practice › Codeforces Solutions ›

Codeforces Round 155 (Div. 2)

Codeforces Round 155 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1200-2300 | Time: 37m 47s Problem Name Rating Tags Solve Time Verified A Cards with Numbers 1200 constructive-algorithms, sortings 2m 30s ✗ B Jury Size 1500 brute-force, implementation 14m 52s ✓ C Anagram 1800 greedy, strings 14m 52s ✓ D Rats 2300 brute-force, dfs-and-similar, graphs 3m 1s ✗ E Dormitory 2100 dp, implementation...

Practice › Codeforces Solutions ›

Codeforces Round 162 (Div. 1)

Codeforces Round 162 (Div. 1) Type: Div. 1 | Problems: 1 | Verified: 1/1 | Rating range: 1200-1200 | Time: 1m 5s Problem Name Rating Tags Solve Time Verified A Escape from Stones 1200 constructive-algorithms, data-structures, implementation 1m 5s ✓

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

CF 193C - Hamming Distance

CF 193C - Hamming Distance Rating: 2400 Tags: constructive algorithms, greedy, math, matrices Solve time: 2m 31s Verified: no Solution Problem Understanding We are given the six pairwise Hamming distances between four unknown binary strings. Every string contains only 'a' and 'b' , and all four strings must have the same length. The task is not to recover the original strings. We only need to construct any four strings whose...

Practice › Codeforces Solutions › Testing Round 7 ›

CF 323A - Black-and-White Cube

CF 323A - Black-and-White Cube Rating: 1600 Tags: combinatorics, constructive algorithms Solve time: 3m 39s Verified: yes Solution Problem Understanding We are working with a 3D grid of size $k \times k \times k$, where every cell is a unit cube in a larger cube. Each unit cube has up to six face-adjacent neighbors in the 3D grid. The task is to assign each unit cube one of two colors,...

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

CF 269C - Flawed Flow

CF 269C - Flawed Flow Rating: 2100 Tags: constructive algorithms, flows, graphs, greedy Solve time: 2m Verified: yes Solution Problem Understanding We are given an undirected graph where every edge already has a flow amount attached to it. The graph is supposed to represent a valid maximum flow from vertex 1 to vertex n , but the directions of the edges were lost. Our task is to recover directions for...

Practice › Codeforces Solutions ›

Codeforces Round 185 (Div. 1)

Codeforces Round 185 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1300-2500 | Time: 7m 26s Problem Name Rating Tags Solve Time Verified A The Closest Pair 1300 constructive-algorithms, implementation 3m 3s ✓ B Cats Transport 2400 data-structures, dp 56s ✓ C Fetch the Treasure 2500 brute-force, data-structures, graphs 1m 7s ✓ E Biologist 2300 flows 2m 20s ✗

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

CF 254A - Cards with Numbers

CF 254A - Cards with Numbers Rating: 1200 Tags: constructive algorithms, sortings Solve time: 2m 30s Verified: no Solution Problem Understanding We have 2n cards laid out in a sequence. Every card has an integer written on it, and each card also has an index from 1 to 2n . The task is to divide all cards into exactly n pairs such that both cards inside every pair contain the...

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

CF 199A - Hexadecimal's theorem

CF 199A - Hexadecimal's theorem Rating: 900 Tags: brute force, constructive algorithms, implementation, number theory Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a single integer n , and the statement guarantees that n itself is a Fibonacci number. The task is to represent n as the sum of three Fibonacci numbers. The three values are allowed to repeat, and zero is also a valid Fibonacci...

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

CF 201A - Clear Symmetry

CF 201A - Clear Symmetry Rating: 1700 Tags: constructive algorithms, dp, math Solve time: 1m 9s Verified: yes Solution Problem Understanding We are asked to construct a square matrix of size n × n , filled with zeros and ones, that satisfies two properties: it must be clear, meaning that no two ones are adjacent horizontally or vertically, and it must be symmetrical along both the horizontal and vertical axes....

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

CF 330B - Road Construction

CF 330B - Road Construction Rating: 1300 Tags: constructive algorithms, graphs Solve time: 1m 46s Verified: no Solution Problem Understanding We are working with a set of cities and we are allowed to build undirected roads between some pairs of them, except for a set of forbidden pairs that are explicitly given. The goal is to choose a set of roads so that every city can reach every other city...

Practice › Codeforces Solutions ›

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

Codeforces Round 145 (Div. 2, ACM-ICPC Rules) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1000-2000 | Time: 9m 42s Problem Name Rating Tags Solve Time Verified B Reading 1000 sortings 1m 19s ✓ C Weather 1300 dp, implementation 1m 27s ✓ F Fence 1800 dp 1m 5s ✗ G Practice 1600 constructive-algorithms, divide-and-conquer, implementation 2m 54s ✗ H Merging Two Decks 2000 constructive-algorithms, greedy 2m...

Practice › Codeforces Solutions › April Fools Day Contest 2014 ›

CF 409H - A + B Strikes Back

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

Practice › Codeforces Solutions ›

Codeforces Round 122 (Div. 1)

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

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

CF 297A - Parity Game

CF 297A - Parity Game Rating: 1700 Tags: constructive algorithms Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given two binary strings, a and b . Our task is to transform a into b using only two operations. The first operation appends the parity of the current string a to its end, where parity is 1 if the number of 1s in a is odd, and 0...

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

CF 45E - Director

CF 45E - Director Rating: 2000 Tags: constructive algorithms, greedy Solve time: 1m 49s Verified: yes Solution Problem Understanding We have two independent lists, one containing names and one containing surnames. Every name must be paired with exactly one surname, and every surname must be used exactly once. After choosing the matching, we print all pairs in one comma-separated line. The optimization target has two layers. First, we want as...

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

CF 135C - Zero-One

CF 135C - Zero-One Rating: 1900 Tags: constructive algorithms, games, greedy Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given a string consisting of 0 , 1 , and ? . Each character represents a card in a row. During the game, players alternately remove one card until only two cards remain. Masha moves first and wants the final two-bit binary number to be as small as...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Finals

Yandex.Algorithm 2011: Finals Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 2200-2700 | Time: 11m 24s Problem Name Rating Tags Solve Time Verified A Domino 2400 brute-force, implementation 2m 46s ✗ B Superset 2300 constructive-algorithms, divide-and-conquer 2m 12s ✓ C Winning Strategy 2400 binary-search, graphs, math 1m 44s ✓ D Robot in Basement 2700 bitmasks, brute-force, implementation 2m 39s ✓ E Leaders 2200 dfs-and-similar, dsu, graphs 2m...

Practice › Codeforces Solutions › Codeforces Beta Round 8 ›

CF 8B - Obsession with Robots

CF 8B - Obsession with Robots Rating: 1400 Tags: constructive algorithms, graphs, implementation Solve time: 56s Verified: yes Solution Problem Understanding We are asked to analyze a robot's path on an infinite 2D grid. The robot can move up, down, left, or right, and its moves are recorded as a string of the characters U, D, L, R. The challenge is to determine whether there exists any possible arrangement of...

Practice › Codeforces Solutions ›

Codeforces Beta Round 96 (Div. 1)

Codeforces Beta Round 96 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-2700 | Time: 9m 16s Problem Name Rating Tags Solve Time Verified A Turing Tape 1300 implementation 1m 39s ✓ B Piet 2100 implementation 1m 56s ✓ C Logo Turtle 1800 dp 1m 52s ✓ D Constants in the language of Shakespeare 2100 constructive-algorithms, dp, greedy 2m 2s ✗ E Bits of...

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

CF 29D - Ant on the Tree

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

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

CF 63D - Dividing Island

CF 63D - Dividing Island Rating: 1900 Tags: constructive algorithms Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to divide an island into connected territories for multiple parties. The island is represented by two rectangles placed side by side: one of size a by b and another of size c by d . They share a horizontal alignment along one edge, but their heights may differ...

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

CF 85A - Domino

CF 85A - Domino Rating: 1300 Tags: constructive algorithms, implementation Solve time: 2m 9s Verified: yes Solution Problem Understanding We need to tile a 4 × n board using ordinary dominoes. Each domino covers exactly two neighboring cells, either horizontally or vertically. The tiling must satisfy an extra condition. Every vertical cut between column i and column i + 1 must slice through at least one horizontal domino. If a...

Practice › Codeforces Solutions ›

Codeforces Beta Round 55 (Div. 2)

Codeforces Beta Round 55 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2000 | Time: 8m 58s Problem Name Rating Tags Solve Time Verified A Word 800 implementation, strings 1m 11s ✓ B Fortune Telling 1200 implementation, number-theory 1m 57s ✗ C Title 1600 expression-parsing 1m 53s ✓ D Team Arrangement 2000 constructive-algorithms, greedy, implementation 2m 39s ✗ E Shortest Path 2000 graphs, shortest-paths...

Practice › Codeforces Solutions ›

Codeforces Beta Round 61 (Div. 2)

Codeforces Beta Round 61 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2000 | Time: 9m 20s Problem Name Rating Tags Solve Time Verified A Petya and Java 1300 implementation, strings 1m 33s ✓ B Petya and Countryside 1100 brute-force, implementation 1m 25s ✓ C Petya and File System 1800 data-structures, implementation 2m 13s ✓ D Petya and His Friends 1700 constructive-algorithms, math, number-theory...

Practice › Codeforces Solutions › Codeforces Beta Round 7 ›

CF 7A - Kalevitch and Chess

CF 7A - Kalevitch and Chess Rating: 1100 Tags: brute force, constructive algorithms Solve time: 1m 5s Verified: yes Solution Problem Understanding The problem asks us to simulate a painter working on an 8×8 chessboard. Every square starts white, and the painter can perform only two operations: paint an entire row black or paint an entire column black. Painting the same square multiple times has no effect beyond the first....

Practice › Codeforces Solutions › Codeforces Beta Round 36 ›

CF 36E - Two Paths

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

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

CF 26C - Parquet

CF 26C - Parquet Rating: 2000 Tags: combinatorics, constructive algorithms, greedy, implementation Solve time: 2m 9s Verified: no Solution Problem Understanding We are asked to tile a rectangular floor of size n × m using three types of parquet planks. The first type is a 1×2 horizontal plank, the second is a 2×1 vertical plank, and the third is a 2×2 square plank. The goal is to cover the entire...

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

CF 43D - Journey

CF 43D - Journey Rating: 2000 Tags: brute force, constructive algorithms, implementation Solve time: 1m 39s Verified: yes Solution Problem Understanding We have an n × m grid. The king starts at the top-left cell (1,1) and must end there as well. Every other cell must be visited exactly once. Normal movement is allowed only between side-adjacent cells, but we may additionally install directed teleporters. A teleporter is attached to...

Practice › Codeforces Solutions › Codeforces Testing Round 3 ›

CF 134C - Swaps

CF 134C - Swaps Rating: 2200 Tags: constructive algorithms, graphs, greedy Solve time: 2m 15s Verified: no Solution Problem Understanding Each player initially owns cards of exactly one color, their own color. Player i starts with a[i] cards, all of color i . During a swap, two players exchange one card each. A player may only give away cards of their own color, and may never receive a color they...

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

CF 78B - Easter Eggs

CF 78B - Easter Eggs Rating: 1200 Tags: constructive algorithms, implementation Solve time: 1m 59s Verified: no Solution Problem Understanding We need to build a circular sequence of colors for n eggs. There are exactly seven available colors: R, O, Y, G, B, I, V Two conditions must hold simultaneously. First, every color must appear at least once. Second, every block of four consecutive eggs on the circle must contain...

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

CF 45J - Planting Trees

CF 45J - Planting Trees Rating: 1800 Tags: constructive algorithms Solve time: 2m 23s Verified: no Solution Problem Understanding We need to place the integers from 1 to n * m into an n × m grid so that every pair of side-adjacent cells differs by at least 2 . Two cells are adjacent only if they share an edge, diagonal neighbors do not matter. The grid must contain every...

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

CF 110B - Lucky String

CF 110B - Lucky String Rating: 1100 Tags: constructive algorithms, strings Solve time: 2m 58s Verified: yes Solution Problem Understanding We need to build a lowercase string of length n that satisfies a special condition on repeated letters. For every character, we look at all positions where it appears. If a character appears multiple times, the difference between consecutive positions must always be a lucky number. In this problem, lucky...

Practice › Codeforces Solutions ›

Codeforces Testing Round 2

Codeforces Testing Round 2 Type: Special | Problems: 3 | Verified: 2/3 | Rating range: 1000-1600 | Time: 5m 4s Problem Name Rating Tags Solve Time Verified A Measuring Lengths in Baden 1400 math 1m 18s ✓ B Simple XML 1000 implementation 1m 41s ✓ C Hobbits' Party 1600 constructive-algorithms, greedy 2m 5s ✗

Practice › Codeforces Solutions ›

Codeforces Beta Round 46 (Div. 2)

Codeforces Beta Round 46 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2300 | Time: 8m 21s Problem Name Rating Tags Solve Time Verified A Sleuth 800 implementation 1m 21s ✓ B Sum 1500 math 1m 24s ✓ C Disposition 1700 constructive-algorithms, math 1m 48s ✓ D Game 1800 brute-force, dp, implementation 1m 47s ✓ E Common ancestor 2300 dp 2m 1s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 36

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 10

Codeforces Beta Round 10 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 900-2800 | Time: 8m 3s Problem Name Rating Tags Solve Time Verified A Power Consumption Calculation 900 implementation 1m 30s ✓ B Cinema Cashier 1500 dp, implementation 1m 24s ✓ C Digital Root 2000 number-theory 1m 41s ✓ D LCIS 2800 dp 2m ✗ E Greedy Change 2600 constructive-algorithms 1m 28s ✓

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 › Codeforces Beta Round 26 (Codeforces format) ›

CF 26E - Multithreading

CF 26E - Multithreading Rating: 2400 Tags: constructive algorithms Solve time: 1m 37s Verified: yes Solution Problem Understanding Each process repeatedly executes two atomic instructions: yi := y y := yi + 1 The shared variable y starts at 0 . Every process has its own private variable yi , so different processes never overwrite each other's local state. The important detail is that the two instructions are separate atomic...

Practice › Codeforces Solutions › Codeforces Beta Round 23 ›

CF 23C - Oranges and Apples

CF 23C - Oranges and Apples Rating: 2500 Tags: constructive algorithms, sortings Solve time: 2m 29s Verified: yes Solution Problem Understanding We have 2N - 1 boxes. Every box contains two numbers, the number of apples and the number of oranges inside it. We must choose exactly N boxes such that the chosen set contains at least half of all apples and at least half of all oranges across every...

Practice › Codeforces Solutions › Codeforces Beta Round 68 ›

CF 74E - Shift It!

CF 74E - Shift It! Rating: 2800 Tags: constructive algorithms Solve time: 16m 24s Verified: no Solution Problem Understanding We have a 6 × 6 board containing the characters 0-9 and A-Z , each appearing exactly once. The target configuration is fixed: characters must appear in row-major order. The only allowed moves are cyclic shifts of complete rows or complete columns. A row can rotate left or right by one...

Practice › Codeforces Solutions › Codeforces Beta Round 39 ›

CF 40A - Find Color

CF 40A - Find Color Rating: 1300 Tags: constructive algorithms, geometry, implementation, math Solve time: 1m 24s Verified: yes Solution Problem Understanding The plane is colored using concentric rings centered at the origin. Every ring between two consecutive integer distances alternates color. The borders themselves, meaning all points whose distance from the origin is an integer, are always black. For a point (x, y) , we need to determine whether...

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

CF 119B - Before Exam

CF 119B - Before Exam Rating: 1900 Tags: constructive algorithms, implementation, sortings Solve time: 2m 2s Verified: yes Solution Problem Understanding We have n theorems, and each theorem has a proficiency value assigned to it. The exam contains exactly k different cards. Every card contains exactly floor(n / k) distinct theorems, and no theorem appears in more than one card. Some theorems may remain unused if n is not divisible...

Practice › Codeforces Solutions ›

Codeforces Beta Round 8

Codeforces Beta Round 8 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1200-2600 | Time: 6m 59s Problem Name Rating Tags Solve Time Verified A Train and Peter 1200 strings 1m 17s ✓ B Obsession with Robots 1400 constructive-algorithms, graphs, implementation 56s ✓ C Looking for Order 2000 bitmasks, dp 1m 48s ✓ D Two Friends 2600 binary-search, geometry 1m 54s ✓ E Beads 2600 dp, graphs...

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

CF 91D - Grocer's Problem

CF 91D - Grocer's Problem Rating: 2600 Tags: constructive algorithms, graphs, greedy Solve time: 2m 25s Verified: yes Solution Problem Understanding We are given a permutation of jars. Jar i should finally stand at position i , but the current arrangement is shuffled. One operation allows us to choose any subset of at most five positions and permute the jars inside those positions arbitrarily. The positions do not need to...

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

CF 41E - 3-cycles

CF 41E - 3-cycles Rating: 1900 Tags: constructive algorithms, graphs, greedy Solve time: 1m 48s Verified: no Solution Problem Understanding We need to build an undirected graph on n cities such that no triangle exists. A triangle means three distinct cities where every pair is directly connected. Among all graphs with no 3-cycles, we want the one with the maximum possible number of roads, and we must also print one...

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

CF 14C - Four Segments

CF 14C - Four Segments Rating: 1700 Tags: brute force, constructive algorithms, geometry, implementation, math Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given exactly four line segments on the 2D plane. Every segment is axis-aligned, or may even degenerate into a single point. The task is to decide whether these four segments together form the border of one rectangle with positive area, where all rectangle sides...

Practice › Codeforces Solutions › Codeforces Testing Round 2 ›

CF 125C - Hobbits' Party

CF 125C - Hobbits' Party Rating: 1600 Tags: constructive algorithms, greedy Solve time: 2m 5s Verified: no Solution Problem Understanding We need to construct as many party days as possible using exactly n hobbits. Every day has a guest list. The construction must satisfy two conditions. First, every pair of different days must share at least one hobbit. If day A and day B exist, there must be some hobbit...

Practice › Codeforces Solutions › Codeforces Beta Round 23 ›

CF 23B - Party

CF 23B - Party Rating: 1600 Tags: constructive algorithms, graphs, math Solve time: 3m 27s Verified: yes Solution Problem Understanding We can think of the party as an undirected friendship graph. Every person is a vertex, and an edge means two people are friends. The process removes people in rounds. First, everyone with degree 0 leaves. After those removals, some remaining people may now have degree 1 , so they...

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

CF 53C - Little Frog

CF 53C - Little Frog Rating: 1200 Tags: constructive algorithms Solve time: 1m 35s Verified: yes Solution Problem Understanding We have n mounds placed on a straight line at positions 1, 2, ..., n . The frog wants to visit every mound exactly once, so we must output a permutation of these positions. The interesting restriction is on the jumps. If the frog visits mounds in order p1, p2, ...,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 23

Codeforces Beta Round 23 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1200-2600 | Time: 11m 15s Problem Name Rating Tags Solve Time Verified A You're Given a String... 1200 brute-force, greedy 1m 55s ✓ B Party 1600 constructive-algorithms, graphs, math 3m 27s ✓ C Oranges and Apples 2500 constructive-algorithms, sortings 2m 29s ✓ D Tetragon 2600 geometry, math 2m 11s ✗ E Tree 2500 dp 1m...

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

CF 128B - String

CF 128B - String Rating: 2100 Tags: brute force, constructive algorithms, hashing, implementation, string suffix structures, strings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a string of lowercase letters and an integer k . The task is to generate all possible substrings of the string, sort them lexicographically, and return the k -th substring in that order. Substrings can repeat, so multiple identical substrings must...

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

CF 27C - Unordered Subsequence

CF 27C - Unordered Subsequence Rating: 1900 Tags: constructive algorithms, greedy Solve time: 1m 18s Verified: no Solution Problem Understanding We are given a sequence of integers, and we are asked to extract the shortest subsequence that is not ordered . A sequence is considered ordered if it is either entirely non-decreasing or entirely non-increasing. In other words, if every consecutive pair either never decreases or never increases, the sequence...

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

CF 86B - Tetris revisited

CF 86B - Tetris revisited Rating: 2200 Tags: constructive algorithms, graph matchings, greedy, math Solve time: 2m 5s Verified: yes Solution Problem Understanding We have a rectangular board where some cells are already blocked by # and the remaining cells . must be covered by polyominoes. The allowed pieces are extremely flexible: any connected shape consisting of 2, 3, 4, or 5 cells may be used, with arbitrary rotations and...

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

CF 66D - Petya and His Friends

CF 66D - Petya and His Friends Rating: 1700 Tags: constructive algorithms, math, number theory Solve time: 1m 57s Verified: no Solution Problem Understanding We need to construct n distinct positive integers with two simultaneous properties. First, every pair of numbers must share a common divisor larger than 1 . In other words, for every pair (ai, aj) , their gcd cannot equal 1 . Second, the gcd of the...

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 12 (Div 2 Only) ›

CF 12E - Start of the session

CF 12E - Start of the session Rating: 2100 Tags: constructive algorithms Solve time: 1m 13s Verified: yes Solution Problem Understanding We are asked to construct a square matrix of size n × n , where n is an even number. The matrix must satisfy four properties. The main diagonal contains only zeroes. The matrix is symmetric, meaning the element at row i , column j equals the element at...

Practice › Codeforces Solutions › Codeforces Beta Round 11 ›

CF 11A - Increasing Sequence

CF 11A - Increasing Sequence Rating: 900 Tags: constructive algorithms, implementation, math Solve time: 1m 24s Verified: yes Solution Problem Understanding We have an array of integers, and we want every element to become strictly larger than the one before it. The only operation allowed is choosing a single element and increasing it by exactly d . Every use of this operation counts as one move. The task is to...

Practice › Codeforces Solutions › Codeforces Beta Round 41 ›

CF 42D - Strange town

CF 42D - Strange town Rating: 2300 Tags: constructive algorithms, math Solve time: 1m 50s Verified: no Solution Problem Understanding We are asked to construct a fully connected graph of N tourist attractions, where each road has a distinct positive integer cost not exceeding 1000. The unusual property of this town is that every Hamiltonian cycle -a cycle visiting each attraction exactly once-must have the same total cost. Our task...

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

CF 82B - Sets

CF 82B - Sets Rating: 1700 Tags: constructive algorithms, hashing, implementation Solve time: 2m 17s Verified: no Solution Problem Understanding We are given all pairwise unions of some hidden disjoint sets. The original sets themselves are not shown. Suppose the hidden sets are $S_1, S_2, \dots, S_n$. For every pair $i \neq j$, we are given the set $S_i \cup S_j$. These unions are shuffled, so we do not know...

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

CF 132D - Constants in the language of Shakespeare

CF 132D - Constants in the language of Shakespeare Rating: 2100 Tags: constructive algorithms, dp, greedy Solve time: 2m 2s Verified: no Solution Problem Understanding We are asked to represent a positive integer given in binary as a sum of powers of two, with the option of using negative powers, such that the total number of terms is minimized. Formally, we want to write the number as a sum of...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Round 2

Yandex.Algorithm 2011: Round 2 Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1600-2700 | Time: 11m 50s Problem Name Rating Tags Solve Time Verified A Reflection 1600 math 2m 9s ✓ B Tetris revisited 2200 constructive-algorithms, graph-matchings, greedy 2m 5s ✓ C Genetic engineering 2500 dp, string-suffix-structures, trees 2m 12s ✓ D Powerful array 2200 data-structures, implementation, math 3m 46s ✓ E Long sequence 2700 brute-force, math,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 7

Codeforces Beta Round 7 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1100-2600 | Time: 5m 10s Problem Name Rating Tags Solve Time Verified A Kalevitch and Chess 1100 brute-force, constructive-algorithms 1m 5s ✓ B Memory Manager 1600 implementation 1m 1s ✓ C Line 1800 math, number-theory 52s ✓ D Palindrome Degree 2200 hashing, strings 1m 5s ✓ E Defining Macros 2600 dp, expression-parsing, implementation 1m 7s...

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

CF 118B - Present from Lena

CF 118B - Present from Lena Rating: 1000 Tags: constructive algorithms, implementation Solve time: 1m 42s Verified: yes Solution Problem Understanding We need to print a symmetric diamond made from numbers. The middle row contains numbers increasing from 0 up to n , then decreasing back to 0 . Every row above and below follows the same pattern with a smaller maximum value. For example, when n = 3 ,...

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

Codeforces Beta Round 4 (Div. 2 Only) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 800-1700 | Time: 4m 57s Problem Name Rating Tags Solve Time Verified A Watermelon 800 brute-force, math 46s ✓ B Before an Exam 1200 constructive-algorithms, greedy 1m 12s ✓ C Registration System 1300 data-structures, hashing, implementation 1m 42s ✓ D Mysterious Present 1700 dp, sortings 1m 17s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 40 (Div. 2)

Codeforces Beta Round 40 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-1900 | Time: 7m 28s Problem Name Rating Tags Solve Time Verified A Translation 800 implementation, strings 1m 14s ✓ B Martian Dollar 1400 brute-force 1m 8s ✓ C Email address 1300 expression-parsing, implementation 1m 41s ✗ D Pawn 1900 dp 1m 37s ✓ E 3-cycles 1900 constructive-algorithms, graphs, greedy 1m 48s...

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

CF 128D - Numbers

CF 128D - Numbers Rating: 2000 Tags: constructive algorithms, implementation Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a multiset of numbers and asked whether it is possible to arrange them in a circle so that every pair of adjacent numbers differs by exactly one. Conceptually, this means each number is a vertex on a cycle, and the absolute difference between neighbors must be 1. The...

Practice › Codeforces Solutions ›

Codeforces Beta Round 39

Codeforces Beta Round 39 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2600 | Time: 7m 51s Problem Name Rating Tags Solve Time Verified A Find Color 1300 constructive-algorithms, geometry, implementation 1m 24s ✓ B Repaintings 1600 math 1m 44s ✓ C Berland Square 2300 implementation, math 1m 38s ✓ D Interesting Sequence 2600 math 1m 55s ✓ E Number Table 2500 combinatorics 1m 10s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 26 (Codeforces format)

Codeforces Beta Round 26 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 900-2400 | Time: 7m 38s Problem Name Rating Tags Solve Time Verified A Almost Prime 900 number-theory 1m 18s ✓ B Regular Bracket Sequence 1400 greedy 1m 20s ✓ C Parquet 2000 combinatorics, constructive-algorithms, greedy 2m 9s ✗ D Tickets 2400 combinatorics, math, probabilities 1m 14s ✓ E Multithreading 2400 constructive-algorithms 1m 37s...

Practice › Codeforces Solutions › Codeforces Beta Round 5 ›

CF 5C - Longest Regular Bracket Sequence

CF 5C - Longest Regular Bracket Sequence Rating: 1900 Tags: constructive algorithms, data structures, dp, greedy, sortings, strings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a string made only of ( and ) . Among all contiguous substrings, we need to find the maximum length of a substring that forms a valid bracket sequence. We also need to count how many substrings achieve that maximum...

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

CF 49C - Disposition

CF 49C - Disposition Rating: 1700 Tags: constructive algorithms, math Solve time: 1m 48s Verified: yes Solution Problem Understanding We need to build a permutation of numbers from 1 to n . Position j contains volume p(j) . A positive integer i is called a divisor of the disposition if there exists some position j such that both j and p(j) are divisible by i . The task is to...

Practice › Codeforces Solutions ›

Yandex.Algorithm Open 2011: Qualification 1

Yandex.Algorithm Open 2011: Qualification 1 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1400-2700 | Time: 13m 8s Problem Name Rating Tags Solve Time Verified A Plug-in 1400 implementation 1m 36s ✓ B Sequence Formatting 1700 implementation, strings 1m 43s ✓ C Average Score 1700 greedy, math, sortings 3m 31s ✓ D Polycarp's Picture Gallery 2100 constructive-algorithms, greedy 2m 48s ✗ E Pairs 2700 dfs-and-similar, dp, dsu...

Practice › Codeforces Solutions ›

Codeforces Beta Round 11

Codeforces Beta Round 11 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 900-2800 | Time: 8m 46s Problem Name Rating Tags Solve Time Verified A Increasing Sequence 900 constructive-algorithms, implementation, math 1m 24s ✓ B Jumping Jack 1600 math 1m 26s ✓ C How Many Squares? 2200 implementation 2m 42s ✓ D A Simple Task 2200 bitmasks, dp, graphs 1m 29s ✓ E Forward, march! 2800 binary-search,...

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

CF 59D - Team Arrangement

CF 59D - Team Arrangement Rating: 2000 Tags: constructive algorithms, greedy, implementation Solve time: 2m 39s Verified: no Solution Problem Understanding We have 3n students ranked by personal performance. Higher-ranked students become captains earlier. When a captain forms a team, they choose two currently unassigned students according to their personal preference list. The final teams are already known, and the teams are listed in the exact order they were created....

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

CF 48H - Black and White

CF 48H - Black and White Rating: 2800 Tags: constructive algorithms Solve time: 1m 46s Verified: no Solution Problem Understanding We are asked to tile an $n \times m$ rectangular floor with three types of 2x2 square tiles: black, white, and mixed tiles that have a black and a white section in a diagonal pattern. The counts of black-only tiles, white-only tiles, and mixed tiles are given as $a$, $b$,...

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

CF 97B - Superset

CF 97B - Superset Rating: 2300 Tags: constructive algorithms, divide and conquer Solve time: 2m 12s Verified: yes Solution Problem Understanding We start with a set of distinct lattice points on the plane. We may add more points, and the final set must satisfy a geometric condition for every pair of points. Take any two points. If they already share the same x-coordinate or the same y-coordinate, they are automatically...

Practice › Codeforces Solutions ›

Codeforces Beta Round 90

Codeforces Beta Round 90 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 800-2500 | Time: 9m 34s Problem Name Rating Tags Solve Time Verified A Epic Game 800 implementation 1m 29s ✓ B Before Exam 1900 constructive-algorithms, implementation, sortings 2m 2s ✓ C Education Reform 2000 dp 2m 59s ✗ D String Transformation 2500 hashing, strings 1m 34s ✓ E Alternative Reality 2400 geometry 1m 30s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 70 (Div. 2)

Codeforces Beta Round 70 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 12m 16s Problem Name Rating Tags Solve Time Verified A Haiku 800 implementation, strings 3m 30s ✓ B Easter Eggs 1200 constructive-algorithms, implementation 1m 59s ✗ C Beaver Game 2000 dp, games, number-theory 2m 6s ✓ D Archer's Shot 2300 binary-search, geometry, math 2m 7s ✓ E Evacuation 2300...

Practice › Codeforces Solutions ›

Codeforces Beta Round 49 (Div. 2)

Codeforces Beta Round 49 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1100-2500 | Time: 13m 28s Problem Name Rating Tags Solve Time Verified A Autocomplete 1100 implementation 3m 28s ✓ B Blog Photo 1700 binary-search, implementation 2m 21s ✓ C Little Frog 1200 constructive-algorithms 1m 35s ✓ D Physical Education 1500 sortings 2m 6s ✓ E Dead Ends 2500 bitmasks, dp 3m 58s...

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

CF 44J - Triminoes

CF 44J - Triminoes Rating: 2000 Tags: constructive algorithms, greedy Solve time: 4m 23s Verified: no Solution Problem Understanding We are given a rectangular board where some cells are missing. Every remaining cell is already colored either black or white in a chessboard pattern. The task is to cover all existing cells using straight triminoes of size 1 × 3 or 3 × 1 . A trimino always covers three...

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

CF 98D - Help Monks

CF 98D - Help Monks Rating: 2500 Tags: constructive algorithms Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given a Tower of Hanoi variant with three pillars and n disks stacked on the first pillar. The disks are listed from bottom to top, and unlike the classical problem, several disks may have the same diameter. A move still transfers exactly one disk between pillars. A larger disk...

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 5

Codeforces Beta Round 5 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1000-2400 | Time: 5m 59s Problem Name Rating Tags Solve Time Verified A Chat Servers Outgoing Traffic 1000 implementation 1m 9s ✓ B Center Alignment 1200 implementation, strings 1m 24s ✓ C Longest Regular Bracket Sequence 1900 constructive-algorithms, data-structures, dp 1m 21s ✓ D Follow Traffic Rules 2100 implementation, math 54s ✓ E Bindian Signalizing...

Practice › Codeforces Solutions ›

Codeforces Beta Round 12 (Div 2 Only)

Codeforces Beta Round 12 (Div 2 Only) Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 800-2400 | Time: 6m 41s Problem Name Rating Tags Solve Time Verified A Super Agent 800 implementation 1m 15s ✓ B Correct Solution? 1100 implementation, sortings 1m 19s ✓ C Fruits 1100 greedy, implementation, sortings 1m 2s ✓ D Ball 2400 data-structures, sortings 1m 52s ✓ E Start of the session 2100...

Practice › Codeforces Solutions ›

Codeforces Beta Round 42 (Div. 2)

Codeforces Beta Round 42 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2300 | Time: 9m 18s Problem Name Rating Tags Solve Time Verified A Football 1000 strings 1m 29s ✓ B Letter 1100 implementation, strings 1m 31s ✓ C Lucky Tickets 1300 greedy 1m 12s ✓ D Journey 2000 brute-force, constructive-algorithms, implementation 1m 39s ✓ E Race 2300 brute-force, implementation, two-pointers 3m 27s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 59 (Div. 2)

Codeforces Beta Round 59 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 900-2000 | Time: 8m 47s Problem Name Rating Tags Solve Time Verified A Sinking Ship 900 implementation, sortings, strings 1m 31s ✓ B Settlers' Training 1200 implementation 1m 35s ✓ C Bulls and Cows 1700 brute-force, implementation 1m 48s ✓ D Dividing Island 1900 constructive-algorithms 1m 40s ✗ E Sweets Game 2000...

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

Codeforces Beta Round 89 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2000 | Time: 10m 4s Problem Name Rating Tags Solve Time Verified A String Task 1000 implementation, strings 1m 38s ✓ B Present from Lena 1000 constructive-algorithms, implementation 1m 42s ✓ C Fancy Number 1900 brute-force, greedy, sortings 2m 51s ✓ D Caesar's Legions 1700 dp 1m 37s ✓ E Bertown roads...

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

CF 103C - Russian Roulette

CF 103C - Russian Roulette Rating: 1900 Tags: constructive algorithms, greedy Solve time: 2m Verified: yes Solution Problem Understanding The cylinder has n slots arranged in a circle, and exactly k of them contain bullets. Before the game starts, the cylinder is rotated uniformly at random, so every cyclic shift is equally likely. After the rotation, Sasha shoots first. If the current slot is empty, the cylinder advances by one...

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

CF 109D - Lucky Sorting

CF 109D - Lucky Sorting Rating: 2000 Tags: constructive algorithms, sortings Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given an array of positive integers, and we want to sort it in non-decreasing order. The twist is that we can only swap elements if at least one of the two numbers involved is lucky. A lucky number is defined as a number containing only the digits 4...

Practice › Codeforces Solutions › Codeforces Beta Round 10 ›

CF 10E - Greedy Change

CF 10E - Greedy Change Rating: 2600 Tags: constructive algorithms Solve time: 1m 28s Verified: yes Solution Problem Understanding We are asked to investigate whether the greedy algorithm for making change can fail with a given set of coin denominations. Specifically, you are given a list of coin values sorted in descending order, ending with 1, and you want to know if there exists some sum that greedy will make...

Practice › Codeforces Solutions ›

Codeforces Beta Round 84 (Div. 2 Only)

Codeforces Beta Round 84 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1100 | Time: 5m 34s Problem Name Rating Tags Solve Time Verified A Nearly Lucky Number 800 implementation 2m 36s ✓ B Lucky String 1100 constructive-algorithms, strings 2m 58s ✓

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

CF 81D - Polycarp's Picture Gallery

CF 81D - Polycarp's Picture Gallery Rating: 2100 Tags: constructive algorithms, greedy Solve time: 2m 48s Verified: no Solution Problem Understanding We have several photo albums. Album i contains a[i] photos. We must build a cyclic gallery containing exactly n photos. Instead of choosing concrete photo IDs, we only need to output the album number for each position. The gallery is circular, so every position has two neighbors. Position 1...

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

CF 30E - Tricky and Clever Password

CF 30E - Tricky and Clever Password Rating: 2800 Tags: binary search, constructive algorithms, data structures, greedy, hashing, strings Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given a single lowercase string. Somewhere inside this string, there exists a hidden palindrome of odd length, but the palindrome was split into three consecutive parts: a prefix, a middle part, a suffix. The prefix and suffix have the same...

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

CF 4B - Before an Exam

CF 4B - Before an Exam Rating: 1200 Tags: constructive algorithms, greedy Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given d days and a target total number of study hours, sumTime . For every day, Peter must study at least minTime[i] hours and at most maxTime[i] hours. The task is to construct any valid schedule whose total sum is exactly sumTime . This is not an...

#constructive-algorithms

Codeforces Round 1091 (Div. 2) and CodeCraft 26

CF 2217E - Definitely Larger

CF 171A - Mysterious numbers - 1

April Fools Day Contest

Codeforces Round 1090 (Div. 4)

CF 2218D - The 67th OEIS Problem

CF 2218F - The 67th Tree Problem

Codeforces Round 1093 (Div. 1)

CF 2219A - Grid L

CF 2222D - Permutation Construction

CF 2225E - Covering Points with Circles

Educational Codeforces Round 189 (Rated for Div. 2)

CF 2227C - Snowfall

Codeforces Round 1096 (Div. 3)

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

CF 2222E - Seek the Truth

CF 2226D - Reserved Reversals

CF 2227D - Palindromex

Codeforces Round 276 (Div. 1)

CF 1955H - The Most Reckless Defense

CF 1965E - Connected Cubes

CF 1966A - Card Exchange

CF 1954A - Painting the Ribbon

CF 1956C - Nene's Magical Matrix

CF 1951E - No Palindromes

CF 1948A - Special Characters

CF 1973C - Cat, Fox and Double Maximum

CF 1944B - Equal XOR

CF 493D - Vasya and Chess

CF 1945G - Cook and Porridge

CF 1974D - Ingenuity-2

CF 1956D - Nene and the Mex Operator

Educational Codeforces Round 164 (Rated for Div. 2)

Codeforces Round 275 (Div. 1)

Codeforces Round 940 (Div. 2) and CodeCraft-23

CF 1942A - Farmer John's Challenge

Testing Round 11

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

CF 1946D - Birthday Gift

Codeforces Round 941 (Div. 1)

CF 491A - Up the hill

Codeforces Round 934 (Div. 2)

CF 1943C - Tree Compass

CF 484A - Bits

CF 1942B - Bessie and MEX

CF 1958E - Yet Another Permutation Constructive

CF 1957A - Stickogon

Kotlin Heroes: Episode 10

Codeforces Round 941 (Div. 2)

Codeforces Round 278 (Div. 2)

Codeforces Global Round 25

CF 1945E - Binary Search

Educational Codeforces Round 163 (Rated for Div. 2)

CF 1949K - Make Triangle

Codeforces Round 278 (Div. 1)

CF 1951F - Inversion Composition

CF 1965B - Missing Subsequence Sum

Codeforces Round 938 (Div. 3)

CF 488B - Candy Boxes

CF 1955B - Progressive Square

CF 487C - Prefix Product Sequence

CF 1966B - Rectangle Filling

CF 1965C - Folding Strip

Codeforces Round 939 (Div. 2)

CF 1965D - Missing Subarray Sum

CF 1951I - Growing Trees

CF 482A - Diverse Permutation

CF 1957B - A BIT of a Construction

CF 1951D - Buying Jewels

CF 1951A - Dual Trigger

CF 1956F - Nene and the Passing Game

CF 484E - Sign on Fence

CF 1948E - Clique Partition

CF 1948C - Arrow Path

CF 1949D - Funny or Scary?

CF 459C - Pashmak and Buses

CF 472F - Design Tutorial: Change the Goal

Codeforces Round 267 (Div. 2)

CF 475C - Kamal-ol-molk's Painting