#math

Codeforces Round 609 (Div. 1)

Codeforces Round 609 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1700-3400 | 16m 7s # Problem Rating Tags Accepted Time ✓ A Long Beautiful Integer 1700 constructive-algorithms, greedy, implementation 9,069 4m 36s ✓ B Domino for Young 2000 dp, greedy, math 6,430 2m 12s ✓ C K Integers 2300 binary-search, data-structures 1,953 3m 43s D D 3200 brute force, divide and conquer, graphs 639 3m...

CF 1725E - Electrical Efficiency

CF 1725E - Electrical Efficiency Rating: 2500 Tags: combinatorics, data structures, dp, math, number theory, trees Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a tree of $N$ factories. Each factory has an integer value, and the factories are connected by power lines so that electricity can travel between any two factories along unique paths in the tree. For any triple of distinct factories $(x, y,...

CF 1725G - Garage

CF 1725G - Garage Rating: 1500 Tags: binary search, geometry, math Solve time: 1m 43s Verified: yes Solution Problem Understanding We are asked to generate an infinite increasing sequence of positive integers called “suitable” numbers. A number is suitable if it can be realized as the area of a square that appears in a specific geometric construction involving a right triangle attached to it, where the triangle has integer leg...

CF 1559E - Mocha and Stars

CF 1559E - Mocha and Stars Rating: 2200 Tags: combinatorics, dp, fft, math, number theory Solve time: 1m 15s Verified: yes Solution Problem Understanding We are counting how many ways we can assign an integer brightness value to each of $n$ stars. Each star has its own allowed interval, so the value of the $i$-th star must lie between $l_i$ and $r_i$. Among all such assignments, we only keep those...

CF 1552D - Array Differentiation

CF 1552D - Array Differentiation Rating: 1800 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dp, graphs, math Solve time: 5m 22s Verified: no Solution Problem Understanding We are given a list of integers, and we want to decide whether it is possible to assign another list of the same length, say $b_1, b_2, \dots, b_n$, such that every given number $a_i$ can be expressed as a difference between...

CF 1552I - Organizing a Music Festival

CF 1552I - Organizing a Music Festival Rating: 3400 Tags: dfs and similar, math Solve time: 2m 3s Verified: yes Solution Problem Understanding We are asked to count how many permutations of singers are valid under a set of “group contiguity” constraints. Each singer is a distinct element from $1$ to $n$. We must arrange all of them in a line. Each friend gives us a subset of singers they...

CF 1543D2 - RPD and Rap Sheet (Hard Version)

CF 1543D2 - RPD and Rap Sheet (Hard Version) Rating: 2200 Tags: brute force, constructive algorithms, interactive, math Solve time: 1m 8s Verified: no Solution Problem Understanding We are interacting with a hidden number that changes whenever we make a wrong guess. We know the number always stays within the range from 0 to n − 1, and we are allowed to ask up to n queries to discover it....

CF 1542E1 - Abnormal Permutation Pairs (easy version)

CF 1542E1 - Abnormal Permutation Pairs (easy version) Rating: 2400 Tags: combinatorics, dp, fft, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to count ordered pairs of permutations of size n . For each pair (p, q) , we require two conditions at the same time: in lexicographic order p comes before q , and the inversion count of p is strictly larger than that...

CF 1389E - Calendar Ambiguity

CF 1389E - Calendar Ambiguity Rating: 2200 Tags: math, number theory Solve time: 5m Verified: no Solution Problem Understanding We are given a fictional calendar system where time is structured in three layers. A year has m months, every month contains exactly d days, and the week repeats every w days. The very first day of the year starts at weekday index 1, and all later weekdays follow cyclically with...

CF 1267K - Key Storage

CF 1267K - Key Storage Rating: 2100 Tags: combinatorics, math Solve time: 2m 26s Verified: no Solution Problem Understanding A key is transformed into a sequence by repeatedly dividing it by growing divisors starting from 2. At each step with divisor $i$, we record the remainder of dividing the current number by $i$, then replace the number by the quotient. The process continues with $i = 2, 3, 4, \dots$...

CF 1267G - Game Relics

CF 1267G - Game Relics Rating: 3000 Tags: math, probabilities Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a collection of $n$ distinct items called relics. Each relic $i$ can be obtained in two ways: either by directly purchasing it at a fixed cost $c_i$, or by paying a fixed cost $x$ to receive a uniformly random relic among all $n$, where duplicates do not help...

CF 1266C - Diverse Matrix

CF 1266C - Diverse Matrix Rating: 1400 Tags: constructive algorithms, greedy, math, number theory Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to fill an $r \times c$ grid with positive integers so that a specific derived sequence of values becomes all distinct, while also making the largest of those values as small as possible. From each row we compute a single number: the gcd of...

CF 1263C - Everyone is a Winner!

CF 1263C - Everyone is a Winner! Rating: 1400 Tags: binary search, math, meet-in-the-middle, number theory Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a fixed amount of rating points, call it $n$. A draw splits these points equally among $k$ participants, but only whole units are distributed, so each participant receives $\lfloor n / k \rfloor$ points. Any leftover points are discarded. The task is...

Codeforces Round 601 (Div. 1)

Codeforces Round 601 (Div. 1) Div. 1 | 6 problems | 3/6 verified | Difficulty 1700-3300 | 12m 52s # Problem Rating Tags Accepted Time ✓ A Feeding Chicken 1700 constructive-algorithms, greedy, implementation 5,515 1m 26s B1 Send Boxes to Alice (Easy Version) 1800 constructive-algorithms, greedy, math 5,006 2m 18s ✓ B2 Send Boxes to Alice (Hard Version) 2100 constructive-algorithms, greedy, math 3,419 1m 20s ✓ C Point Ordering 2300...

CF 1254C - Point Ordering

CF 1254C - Point Ordering Rating: 2300 Tags: constructive algorithms, geometry, interactive, math Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a hidden set of points in the plane, each point identified only by an index from 1 to n. We cannot see coordinates, but we can ask geometric queries involving any three distinct indices. From these queries we can either obtain twice the signed area...

CF 1254B2 - Send Boxes to Alice (Hard Version)

CF 1254B2 - Send Boxes to Alice (Hard Version) Rating: 2100 Tags: constructive algorithms, greedy, math, number theory, ternary search, two pointers Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a line of boxes, each containing some number of chocolate pieces. A single move allows us to take one piece from a box and shift it to an adjacent box, so the cost of moving a...

CF 1252K - Addition Robot

CF 1252K - Addition Robot Rating: 2100 Tags: data structures, math, matrices Solve time: 1m 52s Verified: no Solution Problem Understanding The robot stores a binary instruction string over the alphabet {A, B}. When we process this string with an initial pair of values (A, B) , each character acts like a small transformation step. If the current character is A , the second value is added into the first,...

CF 1250B - The Feast and the Bus

CF 1250B - The Feast and the Bus Rating: 1800 Tags: brute force, constructive algorithms, greedy, math Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a collection of employees, where each employee belongs to exactly one team. The only meaningful structure in the input is the frequency of each team, since employees from the same team must always travel together. The transportation rules impose a strict...

CF 1242D - Number Discovery

CF 1242D - Number Discovery Rating: 3400 Tags: math Solve time: 1m 42s Verified: no Solution Problem Understanding We are asked to reconstruct a very unusual infinite sequence that is generated in rounds. Each round repeatedly looks at the smallest positive integers that have not yet appeared in the sequence. From those missing numbers, we take the smallest $k$ of them, append those $k$ numbers in increasing order, and then...

Kotlin Heroes: Episode 2

Kotlin Heroes: Episode 2 Kotlin | 9 problems | 6/9 verified | Difficulty 1000-3100 | 23m 44s # Problem Rating Tags Accepted Time ✓ A Three Problems 1000 *special, implementation 1,583 1m 42s B Traveling Around the Golden Ring of Berland 1500 *special, implementation 800 1m 38s ✓ C Ice Cream 1700 *special, greedy, sortings 567 1m 16s ✓ D Teams 2000 *special, binary-search, greedy 252 6m 33s ✓ E...

CF 1202D - Print a 1337-string...

CF 1202D - Print a 1337-string... Rating: 1900 Tags: combinatorics, constructive algorithms, math, strings Solve time: 2m 10s Verified: no Solution Problem Understanding We are asked to construct a string made only of the digits 1, 3, and 7 such that a very specific pattern appears a prescribed number of times as a subsequence. The pattern is the sequence “1 followed by 3 followed by 3 followed by 7”, and...

CF 1202C - You Are Given a WASD-string...

CF 1202C - You Are Given a WASD-string... Rating: 2100 Tags: brute force, data structures, dp, greedy, implementation, math, strings Solve time: 1m 37s Verified: no Solution Problem Understanding A command string describes how a robot walks on an infinite grid. Each character moves the robot one step in one of four directions. If we choose a starting position and execute the whole sequence, the robot traces a path and...

Kotlin Heroes: Episode 1

Kotlin Heroes: Episode 1 Kotlin | 9 problems | 4/9 verified | Difficulty - | 17m 12s # Problem Rating Tags Accepted Time ✓ A Three Integers Again *special, math 1,563 1m 40s B Bad Days *special, implementation 1,149 3m 12s ✓ C Minus and Minus Give Plus *special, implementation, strings 834 2m 39s D Decoding of Integer Sequences *special, data-structures, implementation 531 1m 22s E Sliding Doors *special, binary-search...

CF 1170A - Three Integers Again

CF 1170A - Three Integers Again Rating: - Tags: *special, math Solve time: 1m 40s Verified: no Solution Problem Understanding We are given two numbers per query, and each query hides a simple structure built from three unknown positive integers $a$, $b$, and $c$. From these three values we can form three pairwise sums: $a+b$, $a+c$, and $b+c$. The input guarantees that the two numbers we are shown correspond to...

CF 1167B - Lost Numbers

CF 1167B - Lost Numbers Rating: 1400 Tags: brute force, divide and conquer, interactive, math Solve time: 1m 25s Verified: no Solution Problem Understanding We are given an unknown ordering of six fixed numbers: 4, 8, 15, 16, 23, and 42. Each number appears exactly once in an array of length six, but their positions are hidden. Our only way to learn about the array is by asking queries of...

CF 1167F - Scalar Queries

CF 1167F - Scalar Queries Rating: 2300 Tags: combinatorics, data structures, math, sortings Solve time: 1m 24s Verified: no Solution Problem Understanding We are given an array of distinct numbers, and we look at every possible contiguous subarray. For each subarray, we temporarily reorder its elements in increasing order, then assign weights based on position in that sorted subarray: the smallest element gets weight 1, the next gets weight 2,...

CF 1106F - Lunar New Year and a Recursive Sequence

CF 1106F - Lunar New Year and a Recursive Sequence Rating: 2400 Tags: math, matrices, number theory Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a sequence that starts from a very simple base and then evolves through a multiplicative recurrence. The first $k-1$ terms are fixed to 1, while the remaining terms are determined by a sliding window rule: each new value is a product...

CF 933D - A Creative Cutout Rating: 2900 Tags: brute force, combinatorics, math Model: gpt-5-3-mini Solve time: 1m 39s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a3394e3-ca54-83ec-8e8b-862687b3958a Solution Problem Understanding We are working on a geometric counting problem on an infinite square lattice. Imagine every point with integer coordinates on the plane. Around a fixed center point, there are several concentric circles. Each circle has a radius that is not arbitrary but...

CF 988D - Points and Powers of Two Rating: 1800 Tags: brute force, math Model: gpt-5-3-mini Solve time: 1m 51s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33aa08-8d5c-83ec-a9f1-6f24da38c4ed Solution Problem Understanding We are given a set of distinct points placed on a number line. The task is to choose as many of these points as possible, but with a very strong geometric restriction: every pair of chosen points must have a distance...

CF 986D - Perfect Encoding Rating: 3100 Tags: fft, math Model: gpt-5-3-mini Solve time: 2m 3s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a93b-8adc-83ec-a1d3-f702b1745aca Solution Problem Understanding We are asked to design a multi-dimensional encoding system where each object receives an ID formed as an array of length $m$. Each position $i$ can take values from $1$ to $b_i$, so the total number of distinct IDs the system can represent is the...

CF 923E - Perpetual Subtraction Rating: 3100 Tags: fft, math, matrices Model: gpt-5-5 Solve time: 1m 42s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32d5ac-b580-83ec-9756-e063f3b8f5b7 Solution Problem Understanding We start with a random integer between 0 and N, described by a probability distribution P. At each step we erase the current number x and replace it with a uniformly random integer from the interval [0, x]. After performing this operation M times,...

CF 958D1 - Hyperspace Jump (easy) Rating: 1400 Tags: expression parsing, math Model: gpt-5-3-mini Solve time: 1m 35s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a339d94-f784-83ec-a7e6-3815fd55bbe8 Solution Problem Understanding Each ship independently computes a target coordinate from a short arithmetic expression of the form “(a + b) / c”, where a, b, and c are small positive integers. After evaluating this expression, the result is a rational number. Ships that obtain exactly...

CF 997B - Roman Digits Rating: 2000 Tags: brute force, combinatorics, dp, greedy, math Model: gpt-5-3-mini Solve time: 1m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33af7d-bf40-83ec-9286-1b6afde7d406 Solution Problem Understanding We are asked to count how many different integer values can be formed using exactly $n$ symbols chosen from four types of “Roman digits”: I, V, X, and L. Each symbol contributes a fixed numeric value, namely 1, 5, 10, and...

CF 1045D - Interstellar battle Rating: 2200 Tags: math, probabilities, trees Model: gpt-5-3-mini Solve time: 5m 14s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33be72-3674-83ec-a75f-4dce1447204e Solution Problem Understanding We are given a tree of planets where each planet can independently be destroyed during an enemy attack. When a planet falls, it is removed along with all incident edges, so the remaining structure becomes a forest. The number we care about after an...

CF 1036B - Diagonal Walking v.2 Rating: 1600 Tags: math Model: gpt-5-3-mini Solve time: 1m 17s Verified: no (0/1 samples) Solution Problem Understanding Mikhail moves on an infinite grid where each step lets him go to any of the eight neighboring cells. In other words, each move can change his x-coordinate by at most one unit and his y-coordinate by at most one unit simultaneously, independently. For each query, we...

CF 936A - Save Energy! Rating: 1700 Tags: binary search, implementation, math Model: gpt-5-3-mini Solve time: 3m 30s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a3395bc-4950-83ec-a6fb-89217cbf95f5 Solution Problem Understanding We are simulating a cooking process where heat is not constant over time. A stove alternates between being on and off: it automatically turns off after a fixed duration, and Julia occasionally returns to turn it back on if needed. The key complication...

CF 995D - Game Rating: 2500 Tags: math Model: gpt-5-3-mini Solve time: 1m 42s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33aca0-d960-83ec-bf23-3da8f05b0637 Solution Problem Understanding We are given a function defined on all binary strings of length $n$. Think of this as a table with $2^n$ entries, one value for each bitmask. Initially, every entry in this table is filled with some number. A game is played to determine which entry of...

CF 1103E - Radix sum Rating: 3400 Tags: fft, math, number theory Model: gpt-5-3-mini Solve time: 2m 2s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a338211-0f50-83ec-b937-2a330bd3ffc8 Solution Problem Understanding We are asked to count how many sequences can be formed by choosing elements from a given array repeatedly, where the length of the sequence is fixed at $n$. Each choice contributes a number, and these numbers are combined using a digitwise addition...

CF 926B - Add Points Rating: 1800 Tags: math, number theory Model: gpt-5-5 Solve time: 1m 8s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32df8a-1470-83ec-aaf1-85cacf87cba3 Solution Problem Understanding We are given several distinct points placed on a number line. Their positions are arbitrary and unsorted. The task is to insert the minimum number of additional points so that, after sorting all original and inserted points, every consecutive pair of points has exactly...

CF 1040B - Shashlik Cooking Rating: 1300 Tags: dp, greedy, math Model: gpt-5-3-mini Solve time: 1m 25s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33b8ae-772c-83ec-a3d7-73b862c99c7f Solution Problem Understanding We are given a line of $n$ skewers arranged from left to right. Each skewer has a binary state: either it is still in its initial state or it has been flipped. A single operation is performed by choosing a position $i$. That operation...

CF 983A - Finite or not? Rating: 1700 Tags: implementation, math Model: gpt-5-5 Solve time: 1m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33757e-78f4-83ec-b62c-055c2636f4e3 Solution Problem Understanding We are given a rational number $p/q$ and asked to determine whether its representation is finite when written in base $b$. A finite representation means that after some point, the expansion stops and no further digits are needed, similar to how $1/2 = 0.5$...

CF 925C - Big Secret Rating: 2200 Tags: constructive algorithms, math Model: gpt-5-5 Solve time: 4m 28s Verified: yes (1/1 samples) Solution Problem Understanding We are given a multiset of integers. We are allowed to reorder them arbitrarily. After choosing an order, we compute a running prefix XOR, starting from zero, where each next value is obtained by XOR-ing the previous prefix result with the next chosen element. The task...

CF 899D - Shovel Sale Rating: 1800 Tags: constructive algorithms, math Model: gpt-5-5 Solve time: 1m 6s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32d53b-2230-83ec-8174-9a3f0c65fd71 Solution Problem Understanding We are given a shop that contains items with prices from 1 up to n, where the i-th item costs exactly i. We must choose an unordered pair of distinct items, compute their total price, and look at the decimal representation of that sum....

CF 976B - Lara Croft and the New Game Rating: 1300 Tags: implementation, math Model: gpt-5-3-mini Solve time: 1m 19s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a48c-3e30-83ec-b76d-9101c2083b7c Solution Problem Understanding We are given a very large grid with n rows and m columns. A character starts at the top-left cell and walks through every cell exactly once in a fixed deterministic pattern. First, she goes straight down the first column until...

CF 996B - World Cup Rating: 1300 Tags: binary search, math Model: gpt-5-3-mini Solve time: 6m 53s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33af24-d630-83ec-81cc-bfd5349a0d02 Solution Problem Understanding We are given several entrances arranged in a cycle, each entrance having a queue of people already waiting. Each minute, exactly one person from the front of each queue is processed, meaning they enter the fan zone and leave their queue. Allen starts at...

CF 963E - Circles of Waiting Rating: 3100 Tags: math Model: gpt-5-3-mini Solve time: 2m 12s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a384-da9c-83ec-970d-7257bd131e0d Solution Problem Understanding A chip starts at the origin of the integer grid. Every second it performs a single random move in one of the four cardinal directions: left, down, right, or up, with probabilities derived from the input parameters. The motion is memoryless and independent across steps....

CF 985D - Sand Fortress Rating: 2100 Tags: binary search, constructive algorithms, math Model: gpt-5-3-mini Solve time: 1m 34s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a7dd-5220-83ec-9454-507fc8c0df4e Solution Problem Understanding We are building a sequence of sand pillars laid out on a line, starting from position 1 and extending to the right. Each position holds a non-negative integer height, and that height represents how many sand packs are placed there. All sand...

CF 1037F - Maximum Reduction Rating: 2500 Tags: combinatorics, data structures, math Model: gpt-5-3-mini Solve time: 5m 7s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33b6ee-5a88-83ec-87f4-ff56d9af8bf4 Solution Problem Understanding The process repeatedly transforms an array by replacing every contiguous block of length k with its maximum value, and accumulating the sum of those block maxima at each stage. After forming the new array from all sliding window maxima, the same operation is...

CF 1045H - Self-exploration Rating: 2400 Tags: math Model: gpt-5-3-mini Solve time: 1m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a337fdf-f9e8-83ec-869d-b9a7a7ebe667 Solution Problem Understanding We are given two binary strings that define a numeric interval, and we want to count how many binary integers in that interval satisfy a very specific structural constraint. Instead of describing numbers directly, the constraint is given in terms of adjacent digit statistics. For any binary...

CF 1041F - Ray in the tube Rating: 2500 Tags: data structures, divide and conquer, dp, math Model: gpt-5-3-mini Solve time: 1m 39s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33bb87-06c0-83ec-b667-3f627d49e575 Solution Problem Understanding We are given two horizontal lines, each containing a set of integer x-coordinates where sensors are placed. The lower line has height $y_1$, the upper line has height $y_2$, and $y_1 < y_2$. We choose one point $A$...

CF 986E - Prince's Problem Rating: 2800 Tags: brute force, data structures, math, number theory, trees Model: gpt-5-3-mini Solve time: 1m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a912-486c-83ec-87ce-50fb9a999e6f Solution Problem Understanding We are working with a tree of up to 100,000 vertices. Each vertex stores a positive integer value. For every query, we are given two vertices and a number $x$. The query asks us to walk along the unique...

CF 959F - Mahmoud and Ehab and yet another xor task Rating: 2400 Tags: bitmasks, dp, math, matrices Model: gpt-5-3-mini Solve time: 1m 11s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a339f5b-7da0-83ec-9af1-078177c4b240 Solution Problem Understanding We are given an array of integers where each value is treated as a 20-bit number. For every query, we look only at a prefix of the array, specifically the first $l$ elements, and we must count...

CF 955C - Sad powers Rating: 2100 Tags: binary search, math, number theory Model: gpt-5-3-mini Solve time: 6m 26s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339c9d-e228-83ec-a704-93166f6d0a1e Solution Problem Understanding The task is about counting numbers that can be expressed as a perfect power. For each query, we are given a segment of integers $[L, R]$, and we need to count how many integers inside this segment can be written in the...

CF 1041B - Buying a TV Set Rating: 1000 Tags: math Model: gpt-5-3-mini Solve time: 6m 43s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bb22-b27c-83ec-943d-62a14de8036c Solution Problem Understanding We are looking for how many screen sizes are possible under two simultaneous constraints. First, the width of the TV must not exceed a limit a , and the height must not exceed a limit b . Second, the screen must follow a fixed...

CF 900C - Remove Extra One Rating: 1700 Tags: brute force, data structures, math Model: gpt-5-5 Solve time: 1m 49s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a326bf7-e158-83ec-93da-3ee651a8b97a Solution Problem Understanding We are given a permutation and we look at it from left to right, marking a position as a “record” whenever its value is strictly larger than everything seen before it. Equivalently, records are the positions where a new prefix maximum...

CF 991E - Bus Number Rating: 1800 Tags: brute force, combinatorics, math Model: gpt-5-3-mini Solve time: 1m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3293b5-7180-83ec-b276-a21ec9c871a8 Solution Problem Understanding We are given a sequence of digits, obtained from a bus number that Vasya observed in a confused state. The key difficulty is that what he remembers is not the exact number, but a multiset of digits extracted from it. He may have...

CF 980D - Perfect Groups Rating: 2100 Tags: dp, math, number theory Model: gpt-5-3-mini Solve time: 1m 45s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3283e0-3a20-83ec-a82e-e369dd68d0ae Solution Problem Understanding We are given an array of integers, and for every contiguous segment of this array we imagine a separate partitioning task. Inside a chosen segment, we must split its elements into the smallest possible number of groups such that within each group, any...

CF 931C - Laboratory Work Rating: 1700 Tags: implementation, math Model: gpt-5-3-mini Solve time: 1m 27s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327606-d3c4-83ec-8000-99ae5512713a Solution Problem Understanding We are given a multiset of integers representing Kirill’s measurements. All values are very tightly clustered: every value lies within an interval of length at most two, so after shifting, the data contains only three possible integers at most. Anya must construct another multiset of...

CF 963A - Alternating Sum Rating: 1800 Tags: math, number theory Model: gpt-5-3-mini Solve time: 1m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a328192-f20c-83ec-a3a9-4d043e415a76 Solution Problem Understanding We are given a long weighted sum where each position contributes a power of two independent bases. At index $i$, the contribution is either $+1$ or $-1$, multiplied by $a^{n-i} b^i$. The sequence of signs is not arbitrary for all $n+1$ positions, instead only...

CF 946B - Weird Subtraction Process Rating: 1100 Tags: math, number theory Model: gpt-5-3-mini Solve time: 1m 3s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327b46-911c-83ec-af62-8431b2a8c956 Solution Problem Understanding We are given two positive integers representing the sizes of two piles. A deterministic process repeatedly modifies these two values using a very specific rule: if one value is at least twice the other, we subtract twice the smaller value from the larger...

CF 992C - Nastya and a Wardrobe Rating: 1600 Tags: math Model: gpt-5-5 Solve time: 1m 17s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a329408-7798-83ec-9cb4-a63340841c60 Solution Problem Understanding We start with a container holding some number of objects, call it dresses. Initially there are x dresses. Time progresses in discrete steps, and there are k + 1 steps in total. At each of the first k steps, the process is deterministic in...

CF 929C - Красивая команда Rating: 1700 Tags: *special, combinatorics, math Model: gpt-5-3-mini Solve time: 1m 31s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327448-f3dc-83ec-bae4-b1b6323e00ff Solution Problem Understanding We are given three independent groups of players: goalkeepers, defenders, and forwards. Each player has a unique jersey number. We must form a team consisting of exactly one goalkeeper, two defenders, and three forwards. A selection is valid only if the six chosen players...

CF 992D - Nastya and a Game Rating: 2100 Tags: brute force, implementation, math Model: gpt-5-3-mini Solve time: 1m 16s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a329461-c2e4-83ec-a9b4-c4f143a7a8d6 Solution Problem Understanding We are given a sequence of positive integers. From this sequence, we consider every contiguous block and compute two values for it: the sum of elements and the product of elements. A subarray is considered valid if the ratio between its...

CF 919E - Congruence Equation Rating: 2100 Tags: chinese remainder theorem, math, number theory Model: gpt-5-3-mini Solve time: 1m 24s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a326c6c-84c4-83ec-943a-e37852eb9f05 Solution Problem Understanding We are given four numbers: a base a , a target residue b , a prime modulus p , and a limit x . For every positive integer n up to x , we form the value n · a^n under...

CF 932E - Team Work Rating: 2400 Tags: combinatorics, dp, math Model: gpt-5-3-mini Solve time: 1m 26s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3276bd-8288-83ec-a06b-8326cbcd5f3b Solution Problem Understanding We are asked to evaluate a combinatorial sum over all non-empty subsets of a set of size $N$. Every subset contributes a cost that depends only on its size: if a subset contains $x$ elements, its cost is $x^k$. The final answer is the...

CF 896D - Nephren Runs a Cinema Rating: 2900 Tags: chinese remainder theorem, combinatorics, math, number theory Model: gpt-5-3-mini Solve time: 1m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32b535-d454-83ec-8f71-b009aec0fd7d Solution Problem Understanding We are counting how many ways a line of customers can be arranged such that a cinema cashier never runs out of change, and after serving everyone the number of remaining 50-yuan notes falls inside a given interval....

CF 995C - Leaving the Bar Rating: 2300 Tags: brute force, data structures, geometry, greedy, math, sortings Model: gpt-5-3-mini Solve time: 1m 17s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a329559-3654-83ec-b447-c240f12e5b40 Solution Problem Understanding We are given a sequence of planar displacement vectors, each representing a move from the origin or from the current position. For every vector, we are allowed to choose its direction independently: we either add it as given...

CF 899C - Dividing the numbers Rating: 1300 Tags: constructive algorithms, graphs, math Model: gpt-5-5 Solve time: 1m 36s Verified: yes (1/1 samples) Solution Problem Understanding We are given the first n positive integers, and we must split them into two non-empty groups. Every integer must go to exactly one group, and we want the sums of the two groups to be as close as possible. If we think in...

CF 965A - Paper Airplanes Rating: 800 Tags: math Model: gpt-5-3-mini Solve time: 1m 5s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3281e5-4e50-83ec-8a25-9981e3e4dcdf Solution Problem Understanding A group of people wants to produce identical paper airplanes, but the only way to make airplanes is indirectly through sheets of paper. Each sheet can be folded into a fixed number of airplanes, and paper is sold only in packs, each pack containing a fixed...

CF 975D - Ghosts Rating: 2000 Tags: geometry, math Model: gpt-5-3-mini Solve time: 1m 39s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32828a-02a0-83ec-ac7e-af818effabf6 Solution Problem Understanding We are given a set of points moving in the plane, each with a fixed velocity. At time zero (the snapshot time in the statement), every ghost lies on a single known straight line. After that moment, each ghost continues moving independently with constant velocity. Whenever...

CF 959D - Mahmoud and Ehab and another array construction task Rating: 1900 Tags: constructive algorithms, greedy, math, number theory Model: gpt-5-3-mini Solve time: 1m 39s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327fde-bec8-83ec-a888-da97defbad0b Solution Problem Understanding We are given an array of integers $a$, and we must construct another array $b$ of the same length under three simultaneous constraints. First, $b$ must not be lexicographically smaller than $a$, meaning we compare...

CF 900D - Unusual Sequences Rating: 2000 Tags: bitmasks, combinatorics, dp, math, number theory Model: gpt-5-3-mini Solve time: 1m 11s Verified: yes (1/1 samples) Solution Problem Understanding We are asked to count how many sequences of positive integers of a fixed length produce a specific greatest common divisor while also satisfying an additional constraint involving their sum. A cleaner way to view the problem is to think in terms of...

CF 898F - Restoring the Expression

CF 898F - Restoring the Expression Rating: 2300 Tags: brute force, hashing, math Solve time: 3m Verified: yes Solution Problem Understanding We are given a single long string consisting only of digits. This string is known to come from a correct arithmetic identity of the form a + b = c , but the symbols + and = were removed and the digits were concatenated. The task is to split...

Codeforces Round 451 (Div. 2)

Codeforces Round 451 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-2300 | 4m 3s # Problem Rating Tags Accepted Time ✓ A Rounding 800 implementation, math 17,579 1m 3s ✓ F Restoring the Expression 2300 brute-force, hashing, math 1,457 3m ✓

CF 898A - Rounding

CF 898A - Rounding Rating: 800 Tags: implementation, math Solve time: 1m 3s Verified: yes Solution Problem Understanding We are given a single non-negative integer, and we are asked to transform it into a nearby number whose last digit is zero. The rule is that Vasya wants to “round” the number so that it becomes divisible by 10, and among all such candidates he chooses the closest one in terms...

Codeforces Round 452 (Div. 2)

Codeforces Round 452 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-2100 | 4m 9s # Problem Rating Tags Accepted Time ✓ A Splitting in Teams 800 constructive-algorithms, greedy, math 11,096 1m 4s ✓ F Letters Removing 2100 data-structures, strings 2,030 3m 5s ✓

CF 899A - Splitting in Teams

CF 899A - Splitting in Teams Rating: 800 Tags: constructive algorithms, greedy, math Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given several groups of students. Each group has either one student or two students, and these groups are indivisible. The coach wants to form as many teams as possible, where each team must contain exactly three students. A group of size one contributes a single flexible...

CF 900B - Position in Fraction

CF 900B - Position in Fraction Rating: 1300 Tags: math, number theory Solve time: 3m 17s Verified: yes Solution Problem Understanding We are given a rational number formed by dividing two integers, and we are interested in its decimal representation after the decimal point. The task is to determine the earliest position where a specific digit appears in that infinite (or terminating) decimal expansion. The input consists of a numerator...

Codeforces Round 450 (Div. 2)

Codeforces Round 450 (Div. 2) Div. 2 | 1 problems | 1/1 verified | Difficulty 1300-1300 | 3m 17s # Problem Rating Tags Accepted Time ✓ B Position in Fraction 1300 math, number-theory 8,376 3m 17s ✓

VK Cup 2018 - Round 1

VK Cup 2018 - Round 1 Special | 2 problems | 1/2 verified | Difficulty 1700-3200 | 3m 7s # Problem Rating Tags Accepted Time ✓ A Primal Sport 1700 math, number-theory 5,419 1m 16s ✓ F Public Service 3200 constructive-algorithms, graphs, trees 131 1m 51s

CF 923A - Primal Sport

CF 923A - Primal Sport Rating: 1700 Tags: math, number theory Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given the value of the game after two moves, call it $X_2$. The game starts from some unknown integer $X_0 \ge 3$, and two players alternately modify this value. On each move, a player chooses a prime $p$ strictly smaller than the current number, and then replaces the...

VK Cup 2018 - Wild-card Round 1

VK Cup 2018 - Wild-card Round 1 Special | 2 problems | 2/2 verified | Difficulty 1300-2000 | 2m 25s # Problem Rating Tags Accepted Time ✓ A 2-3-numbers 1300 implementation, math 4,160 1m 11s ✓ F Mobile Communications 2000 324 1m 14s ✓

CF 926A - 2-3-numbers

CF 926A - 2-3-numbers Rating: 1300 Tags: implementation, math Solve time: 1m 11s Verified: yes Solution Problem Understanding We are asked to count how many integers in a closed interval $[l, r]$ can be written using only the prime factors 2 and 3. Any valid number must have the form $2^x \cdot 3^y$, where both exponents are non-negative integers. This includes 1, since choosing $x = 0, y = 0$...

Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round)

Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round) Div. 1 | 3 problems | 2/3 verified | Difficulty 1500-2900 | 4m 58s # Problem Rating Tags Accepted Time ✓ A Peculiar apple-tree 1500 dfs-and-similar, graphs, trees 8,386 1m 10s ✓ C Teodor is not a liar! 1900 data-structures, dp 2,373 1m 52s ✓ E Coins Exhibition 2900 data-structures, dp, math 519 1m 56s

CF 930E - Coins Exhibition

CF 930E - Coins Exhibition Rating: 2900 Tags: data structures, dp, math Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a line of $k$ coins, each independently oriented either “obverse” (call it O) or “reverse” (call it R). A full configuration is simply a binary string of length $k$, but $k$ can be extremely large, so we cannot enumerate configurations. Two people remember constraints coming from...

Codeforces Round 468 (Div. 2, based on Technocup 2018 Final Round)

Codeforces Round 468 (Div. 2, based on Technocup 2018 Final Round) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1200 | 2m 16s # Problem Rating Tags Accepted Time ✓ A Friends Meeting 800 brute-force, greedy, implementation 13,088 1m 8s ✓ B World Cup 1200 constructive-algorithms, implementation 7,456 1m 8s ✓

CF 931A - Friends Meeting

CF 931A - Friends Meeting Rating: 800 Tags: brute force, greedy, implementation, math Solve time: 1m 8s Verified: yes Solution Problem Understanding Two people stand on a number line at integer coordinates $a$ and $b$. They want to end up at the same integer position, and each of them can move one step left or right any number of times. The twist is that movement cost is not linear. If...

Codeforces Round 462 (Div. 1)

Codeforces Round 462 (Div. 1) Div. 1 | 3 problems | 3/3 verified | Difficulty 1800-3200 | 3m 54s # Problem Rating Tags Accepted Time ✓ A A Twisty Movement 1800 dp 5,400 1m 15s ✓ B A Determined Cleanup 2000 math 2,054 1m 10s ✓ E A Preponderant Reunion 3200 constructive-algorithms, dp 288 1m 29s ✓

CF 933B - A Determined Cleanup

CF 933B - A Determined Cleanup Rating: 2000 Tags: math Solve time: 1m 10s Verified: yes Solution Problem Understanding We are asked to construct a polynomial whose coefficients are non-negative integers strictly less than a given base $k$, such that when this polynomial is divided by $x + k$, the remainder is exactly the constant polynomial $p$. Dividing by $x + k$ means that if we evaluate the polynomial at...

Codeforces Round 467 (Div. 2)

Codeforces Round 467 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1400 | 2m 7s # Problem Rating Tags Accepted Time ✓ A Olympiad 800 implementation, sortings 16,399 1m 2s ✓ B Vile Grasshoppers 1400 brute-force, math, number-theory 7,256 1m 5s ✓

CF 937B - Vile Grasshoppers

CF 937B - Vile Grasshoppers Rating: 1400 Tags: brute force, math, number theory Solve time: 1m 5s Verified: yes Solution Problem Understanding We are given two integers that describe a vertical structure of branches on a tree. The branches are numbered in increasing order, starting from a low level up to some maximum height. A subset of the lower branches contains grasshoppers, and each grasshopper has a deterministic jumping pattern:...

Educational Codeforces Round 38 (Rated for Div. 2)

Educational Codeforces Round 38 (Rated for Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 800-2700 | 6m 30s # Problem Rating Tags Accepted Time ✓ A Word Correction 800 implementation 12,042 1m 21s B Run For Your Prize 1100 brute-force, greedy 9,303 1m 10s ✓ E Max History 2300 combinatorics, math 1,555 1m 25s F Erasing Substrings 2700 bitmasks, dp, greedy 613 2m 34s

CF 938E - Max History

CF 938E - Max History Rating: 2300 Tags: combinatorics, math Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a multiset of values, where each value is attached to a distinct position. The task is not to process a single ordering of these values, but to consider every possible permutation of indices, treating identical values at different positions as distinct. For any fixed permutation of indices, we...

Codeforces Round 466 (Div. 2)

Codeforces Round 466 (Div. 2) Div. 2 | 3 problems | 3/3 verified | Difficulty 1200-2000 | 5m 58s # Problem Rating Tags Accepted Time ✓ A Points on the line 1200 brute-force, greedy, sortings 8,815 3m 1s ✓ B Our Tanya is Crying Out Loud 1400 dp, greedy 9,505 1m 11s ✓ E Cashback 2000 data-structures, dp, greedy 4,390 1m 46s ✓

CF 940E - Cashback

CF 940E - Cashback Rating: 2000 Tags: data structures, dp, greedy, math Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given a sequence of numbers, and we need to break it into contiguous segments. Each segment is evaluated independently, and then we sum up the segment scores. The score of a segment is defined in an unusual way: we take all elements in the segment, remove the...

Codeforces Round 469 (Div. 1)

Codeforces Round 469 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1600-3300 | 14m 46s # Problem Rating Tags Accepted Time ✓ A Zebras 1600 greedy 5,655 1m 32s B A Leapfrog in the Array 1700 constructive-algorithms, math 3,833 1m 32s C Data Center Maintenance 1900 dfs-and-similar, graphs 2,252 5m 25s D Curfew 2300 binary-search, brute-force, greedy 881 3m 41s E Binary Cards 2700 brute-force 769...

CF 949B - A Leapfrog in the Array

CF 949B - A Leapfrog in the Array Rating: 1700 Tags: constructive algorithms, math Solve time: 1m 32s Verified: no Solution Problem Understanding We start with numbers from 1 to $n$. Instead of placing them directly into positions $1$ through $n$, each number $i$ is initially placed at position $2i-1$. So the array of length $2n$ has numbers only in odd positions, while even positions are empty. Then a process...

Codeforces Round 469 (Div. 2)

Codeforces Round 469 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1100 | 2m 28s # Problem Rating Tags Accepted Time ✓ A Left-handers, Right-handers and Ambidexters 800 implementation, math 16,375 1m 20s ✓ B Intercepted Message 1100 greedy, implementation 7,999 1m 8s ✓

CF 950A - Left-handers, Right-handers and Ambidexters

CF 950A - Left-handers, Right-handers and Ambidexters Rating: 800 Tags: implementation, math Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given three groups of players at a training session: people who can only use the left hand, people who can only use the right hand, and ambidextrous players who can be assigned to either hand. The coach wants to build a team of even size such that...

April Fools Contest 2018

April Fools Contest 2018 April Fools | 4 problems | 3/4 verified | Difficulty 800-2400 | 7m 7s # Problem Rating Tags Accepted Time ✓ A Quirky Quantifiers 800 *special, math 11,974 1m 11s ✓ B A Map of the Cat 1900 *special, brute-force, interactive 2,116 1m 2s ✓ E Cheese Board 2000 *special 679 3m 39s F 2 + 2 != 4 2400 *special 424 1m 15s ✓

CF 952A - Quirky Quantifiers

CF 952A - Quirky Quantifiers Rating: 800 Tags: *special, math Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a single integer a , guaranteed to be a three-digit or two-digit number between 10 and 999. The task is to output either 0 or 1 based on a hidden property of this number. The key idea is that the number is not meant to be processed through...

CF 954I - Yet Another String Matching Problem

CF 954I - Yet Another String Matching Problem Rating: 2200 Tags: fft, math Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given two strings, one long string and one pattern string, both over a very small alphabet of size six. We slide the pattern across the long string, and for each position we take a substring of the same length as the pattern. For every such pair...

Codeforces Round 471 (Div. 2)

Codeforces Round 471 (Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 1100-2900 | 8m 25s # Problem Rating Tags Accepted Time ✓ A Feed the cat 1100 greedy, math 7,023 1m 21s ✓ B Not simply beatiful strings 1400 implementation 5,162 1m 18s E Icicles 2900 102 2m 26s F Heaps 2600 dp, trees 1,963 3m 20s

CF 955A - Feed the cat

CF 955A - Feed the cat Rating: 1100 Tags: greedy, math Solve time: 1m 21s Verified: yes Solution Problem Understanding Andrew wakes up at a given time of day and realizes his cat is hungry. The cat starts with some initial hunger value, and this hunger grows steadily over time at a fixed rate per minute. Andrew can reduce the cat’s hunger only by buying buns. Each bun reduces hunger...

CF 958E1 - Guard Duty (easy)

CF 958E1 - Guard Duty (easy) Rating: 1600 Tags: brute force, geometry, greedy, math Solve time: 39s Verified: yes Solution Problem Understanding We are given two small point sets in the plane, one representing Rebel ships and the other representing bases. Each ship must be assigned to exactly one base, and each base must also receive exactly one ship, so the assignment is a bijection between the two sets. Once...

Codeforces Round 473 (Div. 2)

Codeforces Round 473 (Div. 2) Div. 2 | 3 problems | 3/3 verified | Difficulty 800-1900 | 4m 23s # Problem Rating Tags Accepted Time ✓ A Mahmoud and Ehab and the even-odd game 800 games, math 55,647 58s ✓ C Mahmoud and Ehab and the wrong algorithm 1500 constructive-algorithms, trees 6,207 1m 13s ✓ E Mahmoud and Ehab and the xor-MST 1900 bitmasks, dp, graphs 3,765 2m 12s ✓

CF 959E - Mahmoud and Ehab and the xor-MST

CF 959E - Mahmoud and Ehab and the xor-MST Rating: 1900 Tags: bitmasks, dp, graphs, implementation, math Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a complete graph on vertices labeled from 0 to n − 1. Every pair of distinct vertices is connected, and the weight of the edge between u and v is the bitwise XOR of their labels. The task is to compute...

CF 959A - Mahmoud and Ehab and the even-odd game

CF 959A - Mahmoud and Ehab and the even-odd game Rating: 800 Tags: games, math Solve time: 58s Verified: yes Solution Problem Understanding The game starts with a single integer value, and two players alternately reduce it. On Mahmoud’s turn, he is only allowed to subtract an even positive number that does not exceed the current value. On Ehab’s turn, he is only allowed to subtract an odd positive number...

CF 960G - Bandit Blues

CF 960G - Bandit Blues Rating: 2900 Tags: combinatorics, dp, fft, math Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to N, and we simulate a simple “record-breaking” process on it. We start with a virtual value 0. Scanning from left to right, we maintain the maximum value seen so far; every time we encounter a number larger than...

CF 961G - Partitions

CF 961G - Partitions Rating: 2700 Tags: combinatorics, math, number theory Solve time: 25s Verified: no Solution Problem Understanding We are given $n$ weighted elements. Each element $i$ has a weight $w_i$. We consider all ways to split these $n$ elements into exactly $k$ non-empty groups. Each such grouping is an unordered partition, so only the membership structure matters, not any labeling of groups. For any fixed partition, its value...

Educational Codeforces Round 42 (Rated for Div. 2)

Educational Codeforces Round 42 (Rated for Div. 2) Div. 2 | 4 problems | 3/4 verified | Difficulty 1300-2800 | 4m 22s # Problem Rating Tags Accepted Time ✓ A Equator 1300 implementation 13,431 1m 14s ✓ C Make a Square 1400 brute-force, implementation, math 8,357 1m 20s ✓ F Simple Cycles Edges 2400 dfs-and-similar, graphs, trees 1,581 1m 16s ✓ G Visible Black Areas 2800 data-structures, dsu, geometry 207...

CF 962C - Make a Square

CF 962C - Make a Square Rating: 1400 Tags: brute force, implementation, math Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a single positive integer written in decimal form. We are allowed to repeatedly remove digits from it, with the only restriction that the remaining number must always stay positive and must not acquire leading zeros. Each deletion reduces the length of the number by one...

CF 963C - Cutting Rectangle

CF 963C - Cutting Rectangle Rating: 2600 Tags: brute force, math, number theory Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a final collection of axis-aligned rectangles that come from cutting an unknown larger rectangle using only straight cuts parallel to its sides. Every cut is either horizontal or vertical, so the original rectangle is partitioned into a grid. If there are $p$ horizontal cuts and...

Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 2)

Tinkoff Internship Warmup Round 2018 and Codeforces Round 475 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1300 | 2m 48s # Problem Rating Tags Accepted Time ✓ A Splits 800 math 10,304 1m 29s ✓ B Messages 1300 math 4,584 1m 19s ✓

CF 964A - Splits

CF 964A - Splits Rating: 800 Tags: math Solve time: 1m 29s Verified: yes Solution Problem Understanding We are working with ways of writing an integer $n$ as a nonincreasing sequence of positive integers. In other words, we break $n$ into parts that never increase as we move to the right, and all parts must be positive. This is the same as a standard integer partition written in sorted form....

CF 964B - Messages

CF 964B - Messages Rating: 1300 Tags: math Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a sequence of messages that arrive over time. Each message arrives at a known minute and starts with a fixed value. After it appears, its value decreases linearly every minute until it is read, and once read it immediately contributes its current value to Vasya’s money. At the same time,...

Codeforces Round 476 (Div. 2) [Thanks, Telegram!]

Codeforces Round 476 (Div. 2) [Thanks, Telegram!] Div. 2 | 3 problems | 1/3 verified | Difficulty 1300-2200 | 3m 22s # Problem Rating Tags Accepted Time ✓ B Battleship 1300 implementation 4,767 1m 21s ✓ C Greedy Arkady 2000 math 2,215 38s E Short Code 2200 data-structures, dp, greedy 1,880 1m 23s

CF 965C - Greedy Arkady

CF 965C - Greedy Arkady Rating: 2000 Tags: math Solve time: 38s Verified: no Solution Problem Understanding We are given a linear stream of $n$ candies and a fixed number of people $k$. A single parameter $x$ determines how the candies are distributed: candies are processed in consecutive blocks of size $x$. Each block is assigned to one person in cyclic order, starting from Arkady (person 1), then person 2,...

CF 967B - Watering System

CF 967B - Watering System Rating: 1000 Tags: math, sortings Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given a system of pipe holes, each hole having a fixed size that determines how much water it can drain when water is poured into the system. Arkady pours a fixed amount of water, but only one hole, the first one, is considered useful to him. His goal is...

Codeforces Round 477 (rated, Div. 2, based on VK Cup 2018 Round 3)

Codeforces Round 477 (rated, Div. 2, based on VK Cup 2018 Round 3) Div. 2 | 2 problems | 1/2 verified | Difficulty 1000-1100 | 1m 55s # Problem Rating Tags Accepted Time ✓ A Mind the Gap 1100 implementation 4,641 27s B Watering System 1000 math, sortings 7,885 1m 28s ✓

Codeforces Round 479 (Div. 3)

Codeforces Round 479 (Div. 3) Div. 3 | 5 problems | 3/5 verified | Difficulty 800-1700 | 6m 59s # Problem Rating Tags Accepted Time ✓ A Wrong Subtraction 800 implementation 217,381 1m 11s ✓ B Two-gram 900 implementation, strings 49,745 1m 15s C Less or Equal 1200 sortings 43,322 1m 33s ✓ D Divide by three, multiply by two 1400 dfs-and-similar, math, sortings 20,523 1m 26s ✓ F Consecutive...

CF 977D - Divide by three, multiply by two

CF 977D - Divide by three, multiply by two Rating: 1400 Tags: dfs and similar, math, sortings Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a multiset of integers that originally came from a single starting value that Polycarp repeatedly transformed. Each transformation either doubles the current number or divides it by three when it is divisible. After applying these operations exactly $n-1$ times, we observe...

CF 978D - Almost Arithmetic Progression

CF 978D - Almost Arithmetic Progression Rating: 1500 Tags: brute force, implementation, math Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a sequence of integers, and we are allowed to slightly “tweak” each element independently by choosing to either decrease it by one, increase it by one, or leave it unchanged. After applying these tiny adjustments, we want the resulting sequence to form an arithmetic progression,...

CF 978E - Bus Video System

CF 978E - Bus Video System Rating: 1400 Tags: combinatorics, math Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a sequence of recorded changes in the number of passengers on a bus. Each value tells us how the passenger count changes after a stop, so if we denote the starting number of passengers by $x$, then after each stop we repeatedly add the given deltas and...

Codeforces Round 482 (Div. 2)

Codeforces Round 482 (Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2400 | 8m 57s # Problem Rating Tags Accepted Time ✓ A Pizza, Pizza, Pizza!!! 1000 math 14,574 1m 6s ✓ B Treasure Hunt 1800 greedy 4,779 1m 14s ✓ C Kuro and Walking Route 1600 dfs-and-similar, trees 7,333 2m 52s D Kuro and GCD and XOR and SUM 2200 binary-search, bitmasks, brute-force 2,176 1m...

CF 979D - Kuro and GCD and XOR and SUM

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

CF 979A - Pizza, Pizza, Pizza!!!

CF 979A - Pizza, Pizza, Pizza!!! Rating: 1000 Tags: math Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a number of friends attending a pizza party, and the host must divide a circular pizza into exactly equal slices so that there are one slice per person, including the host. If there are $n$ friends, the pizza must be split into $n + 1$ equal parts. The...

Codeforces Round 480 (Div. 2)

Codeforces Round 480 (Div. 2) Div. 2 | 4 problems | 3/4 verified | Difficulty 900-2900 | 6m 21s # Problem Rating Tags Accepted Time ✓ A Links and Pearls 900 implementation, math 10,950 1m 7s ✓ B Marlin 1600 constructive-algorithms 4,923 1m 29s ✓ E The Number Games 2200 data-structures, greedy, trees 2,117 1m 46s ✓ F Cactus to Tree 2900 dp, graphs, trees 215 1m 59s

CF 980A - Links and Pearls

CF 980A - Links and Pearls Rating: 900 Tags: implementation, math Solve time: 1m 7s Verified: yes Solution Problem Understanding We are given a circular arrangement made of two kinds of characters: pearls represented by o and links represented by - . Because the structure is a necklace, the string is considered cyclic, meaning the last character is adjacent to the first. The allowed operation does not change the multiset...

CF 981H - K Paths

CF 981H - K Paths Rating: 3100 Tags: combinatorics, data structures, dp, fft, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a tree and we choose an ordered list of $k$ simple paths, where each path is defined by two endpoints in the tree. Because paths are on a tree, each pair of vertices determines a unique simple path. For every edge in the tree,...

Codeforces Round 485 (Div. 1)

Codeforces Round 485 (Div. 1) Div. 1 | 3 problems | 3/3 verified | Difficulty 1600-3300 | 4m 10s # Problem Rating Tags Accepted Time ✓ A Fair 1600 graphs, greedy, number-theory 8,326 1m 26s ✓ B Petr and Permutations 1800 combinatorics, math 5,054 1m 18s ✓ F Oppa Funcan Style Remastered 3300 graphs, math, number-theory 743 1m 26s ✓

CF 986F - Oppa Funcan Style Remastered

CF 986F - Oppa Funcan Style Remastered Rating: 3300 Tags: graphs, math, number theory, shortest paths Solve time: 1m 26s Verified: yes Solution Problem Understanding We are asked whether it is possible to design a function on a very large set of positions, up to $10^{18}$, that behaves like a deterministic jump rule applied every second. Each position points to exactly one next position, and every element moves according to...

CF 986B - Petr and Permutations

CF 986B - Petr and Permutations Rating: 1800 Tags: combinatorics, math Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a permutation of size $n$, and we are told it was produced by one of two random procedures. Both procedures start from the identity permutation $[1, 2, 3, \dots, n]$, then repeatedly pick two distinct positions uniformly at random and swap them. The only difference is the...

CF 987B - High School: Become Human

CF 987B - High School: Become Human Rating: 1100 Tags: math Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given two positive integers $x$ and $y$, and we are asked to compare the values of two exponentials: $x^y$ and $y^x$. The task is not to compute these values directly, since they can become astronomically large even for moderate inputs, but to determine which one is larger or...

Codeforces Round 485 (Div. 2)

Codeforces Round 485 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 1100-1400 | 2m 48s # Problem Rating Tags Accepted Time ✓ B High School: Become Human 1100 math 12,222 1m 37s ✓ C Three displays 1400 brute-force, dp, implementation 15,059 1m 11s ✓

CF 989D - A Shade of Moonlight

CF 989D - A Shade of Moonlight Rating: 2500 Tags: binary search, geometry, math, sortings, two pointers Solve time: 2m 41s Verified: no Solution Problem Understanding We are given several “clouds” moving along a line. Each cloud is a segment of fixed length $l$, initially placed at position $x_i$, and then moving over time with constant velocity $v_i + w$, where $v_i$ is either $+1$ or $-1$, and $w$ is...

Educational Codeforces Round 45 (Rated for Div. 2)

Educational Codeforces Round 45 (Rated for Div. 2) Div. 2 | 3 problems | 1/3 verified | Difficulty 1000-2100 | 4m 49s # Problem Rating Tags Accepted Time ✓ A Commentary Boxes 1000 implementation, math 11,209 1m 26s ✓ C Bracket Sequences Concatenation Problem 1500 implementation 6,293 1m 36s E Post Lamps 2100 brute-force, greedy 2,163 1m 47s

CF 990A - Commentary Boxes

CF 990A - Commentary Boxes Rating: 1000 Tags: implementation, math Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given an initial number of commentary boxes and a required number of delegations. Every delegation must receive exactly the same number of boxes, and all existing boxes must be used so that nothing remains idle. This requirement translates into a single arithmetic condition: the final number of boxes must...

Codeforces Round 491 (Div. 2)

Codeforces Round 491 (Div. 2) Div. 2 | 4 problems | 4/4 verified | Difficulty 1000-2700 | 5m 27s # Problem Rating Tags Accepted Time ✓ A If at first you don't succeed... 1000 implementation 11,232 1m 14s ✓ C Candies 1500 binary-search, implementation 11,509 1m 9s ✓ D Bishwock 1500 dp, greedy 7,736 1m 33s ✓ F Concise and clear 2700 brute-force, greedy, implementation 340 1m 31s ✓

CF 991F - Concise and clear

CF 991F - Concise and clear Rating: 2700 Tags: brute force, greedy, implementation, math Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given a single integer $n$ up to $10^{10}$. The task is not to compute anything from it, but to rewrite it as a mathematical expression using only digits, plus, multiplication, and exponentiation. The expression must evaluate exactly to $n$, and among all valid expressions, we...

Codeforces Round 489 (Div. 2)

Codeforces Round 489 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1600 | 2m 25s # Problem Rating Tags Accepted Time ✓ A Nastya and an Array 800 implementation, sortings 14,315 1m 8s ✓ B Nastya Studies Informatics 1600 math, number-theory 6,766 1m 17s ✓

CF 992B - Nastya Studies Informatics

CF 992B - Nastya Studies Informatics Rating: 1600 Tags: math, number theory Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given four integers $l, r, x, y$. The task is to count ordered pairs $(a, b)$ such that both numbers lie inside the interval $[l, r]$, and their greatest common divisor is exactly $x$ while their least common multiple is exactly $y$. Instead of thinking in terms...

CF 993E - Nikita and Order Statistics

CF 993E - Nikita and Order Statistics Rating: 2300 Tags: chinese remainder theorem, fft, math Solve time: 1m 42s Verified: no Solution Problem Understanding We are given an array and a threshold value x . For every possible integer k from 0 to n , we need to count how many subarrays have exactly k elements strictly smaller than x . Each subarray contributes to exactly one k , depending...

CF 995F - Cowmpany Cowmpensation

CF 995F - Cowmpany Cowmpensation Rating: 2700 Tags: combinatorics, dp, math, trees Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a rooted tree of employees where employee 1 is the CEO. Every other employee has exactly one direct superior, forming a hierarchy. We must assign each employee an integer salary between 1 and D, with the constraint that no employee can earn more than their direct...

Codeforces Round 492 (Div. 1) [Thanks, uDebug!]

Codeforces Round 492 (Div. 1) [Thanks, uDebug!] Div. 1 | 3 problems | 2/3 verified | Difficulty 1400-2700 | 4m 40s # Problem Rating Tags Accepted Time ✓ A Tesla 2100 constructive-algorithms, implementation 1,807 2m B Suit and Tie 1400 greedy, implementation, math 7,444 1m 18s ✓ F Cowmpany Cowmpensation 2700 combinatorics, dp, math 1,625 1m 22s ✓

CF 995B - Suit and Tie

CF 995B - Suit and Tie Rating: 1400 Tags: greedy, implementation, math Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a lineup of $2n$ people where each integer label from $1$ to $n$ appears exactly twice. Each label represents a couple, so the goal is to rearrange the line so that both occurrences of every number sit next to each other. The only operation allowed is...

Codeforces Round 493 (Div. 1)

Codeforces Round 493 (Div. 1) Div. 1 | 3 problems | 3/3 verified | Difficulty 1500-3000 | 4m # Problem Rating Tags Accepted Time ✓ A Convert to Ones 1500 brute-force, greedy, implementation 8,662 1m 14s ✓ C Sky Full of Stars 2500 combinatorics, math 2,176 1m 19s ✓ E Good Subsegments 3000 data-structures 1,662 1m 27s ✓

CF 997C - Sky Full of Stars

CF 997C - Sky Full of Stars Rating: 2500 Tags: combinatorics, math Solve time: 1m 19s Verified: yes Solution Problem Understanding We are working with an $n \times n$ grid where each cell independently takes one of three colors. A coloring is considered “good” if at least one full row or at least one full column ends up monochromatic, meaning every cell in that row or column shares the same...

CF 997A - Convert to Ones

CF 997A - Convert to Ones Rating: 1500 Tags: brute force, greedy, implementation, math Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a binary string and we want to transform it into a string of all ones. Two types of operations are available: we can reverse any contiguous segment for a cost, or we can flip all bits in a contiguous segment for a cost. Both...

Codeforces Round 494 (Div. 3)

Codeforces Round 494 (Div. 3) Div. 3 | 6 problems | 2/6 verified | Difficulty 800-2200 | 11m 26s # Problem Rating Tags Accepted Time ✓ A Polycarp's Pockets 800 implementation 29,976 1m 15s ✓ B Binary String Constructing 1300 constructive-algorithms 12,222 1m 51s C Intense Heat 1300 brute-force, implementation, math 11,525 1m 30s D Coins and Queries 1600 greedy 8,560 1m 58s E Tree Constructing 2100 constructive-algorithms, graphs 3,029...

CF 1003C - Intense Heat

CF 1003C - Intense Heat Rating: 1300 Tags: brute force, implementation, math Solve time: 1m 30s Verified: no Solution Problem Understanding We are given a sequence of daily temperatures and asked to evaluate all contiguous time intervals whose length is at least a given threshold. For each such interval, we compute its average temperature, meaning the sum of its values divided by its length. The task is to find the...

Codeforces Round 495 (Div. 2)

Codeforces Round 495 (Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 900-2600 | 11m 39s # Problem Rating Tags Accepted Time ✓ A Sonya and Hotels 900 implementation 11,853 1m 38s ✓ B Sonya and Exhibition 1300 constructive-algorithms, greedy, implementation 9,935 2m 1s C Sonya and Robots 1400 constructive-algorithms, implementation 7,880 1m 14s ✓ D Sonya and Matrix 2300 brute-force, constructive-algorithms, implementation 1,499 1m 59s E...

CF 1004B - Sonya and Exhibition

CF 1004B - Sonya and Exhibition Rating: 1300 Tags: constructive algorithms, greedy, implementation, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a row of positions, each of which must be filled with one of two possible types. You can think of this as constructing a binary string of length $n$, where each position is either type A or type B. There are several visitors, and...

Codeforces Round 497 (Div. 1)

Codeforces Round 497 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1300-3400 | 11m 58s # Problem Rating Tags Accepted Time ✓ A Reorder the Array 1300 combinatorics, data-structures, math 13,066 3m 11s ✓ B Pave the Parallelepiped 2400 bitmasks, brute-force, combinatorics 1,037 2m 4s ✓ C Guess two numbers 3000 binary-search, interactive 527 2m 36s D Ants 3200 2-sat, data-structures, trees 322 2m 5s ✓...

CF 1007A - Reorder the Array

CF 1007A - Reorder the Array Rating: 1300 Tags: combinatorics, data structures, math, sortings, two pointers Solve time: 3m 11s Verified: yes Solution Problem Understanding We are given an array of numbers and allowed to freely reorder them. After rearranging, we compare the new array against the original array position by position. A position is considered “good” if the value placed there after permutation is strictly larger than the value...

CF 1007B - Pave the Parallelepiped

CF 1007B - Pave the Parallelepiped Rating: 2400 Tags: bitmasks, brute force, combinatorics, math, number theory Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a fixed rectangular box with side lengths $A, B, C$. We want to count how many different triples $(a,b,c)$, ordered so that $a \le b \le c$, can serve as a building block such that copies of this smaller box can exactly...

Educational Codeforces Round 47 (Rated for Div. 2)

Educational Codeforces Round 47 (Rated for Div. 2) Div. 2 | 7 problems | 5/7 verified | Difficulty 800-2400 | 19m 17s # Problem Rating Tags Accepted Time ✓ A Game Shopping 800 implementation 12,310 1m 26s ✓ B Minimum Ternary String 1400 greedy, implementation 10,719 2m 39s C Annoying Present 1700 greedy, math 5,557 3m 45s ✓ D Relatively Prime Graph 1700 brute-force, constructive-algorithms, graphs 6,658 1m 55s E...

CF 1009E - Intercity Travelling

CF 1009E - Intercity Travelling Rating: 2000 Tags: combinatorics, math, probabilities Solve time: 3m 58s Verified: yes Solution Problem Understanding We are given a road split into $n$ unit segments, and each segment has a “base fatigue cost” $a_i$ that applies when Leha starts a fresh driving session. The key twist is that fatigue does not depend only on the kilometer index, but also on how many kilometers have been...

CF 1009C - Annoying Present

CF 1009C - Annoying Present Rating: 1700 Tags: greedy, math Solve time: 3m 45s Verified: yes Solution Problem Understanding We start with an array of length $n$ that initially contains only zeros. Bob performs $m$ operations. Each operation is defined by a pair $(x, d)$, and Bob is allowed to pick a center position $i$ in the array. Once he does, every position $j$ receives an additive contribution that depends...

CF 1009D - Relatively Prime Graph

CF 1009D - Relatively Prime Graph Rating: 1700 Tags: brute force, constructive algorithms, graphs, greedy, math Solve time: 1m 55s Verified: no Solution Problem Understanding We are asked to build a simple undirected graph on vertices numbered from 1 to n. The graph must have exactly m edges, must be connected, and must avoid both self-loops and repeated edges. The extra constraint is that every edge we include must connect...

Codeforces Round 499 (Div. 1)

Codeforces Round 499 (Div. 1) Div. 1 | 6 problems | 4/6 verified | Difficulty 1500-3400 | 15m 26s # Problem Rating Tags Accepted Time ✓ A Fly 1500 binary-search, math 9,003 1m 41s ✓ B Rocket 1800 binary-search, interactive 6,386 2m 23s C Border 1800 number-theory 5,930 4m 4s ✓ D Mars rover 2000 dfs-and-similar, graphs, implementation 2,563 1m 48s ✓ E Store 2700 data-structures 386 2m 29s ✓...

CF 1010A - Fly

CF 1010A - Fly Rating: 1500 Tags: binary search, math Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a fixed route of space travel that starts at Earth, visits several intermediate planets in order, reaches Mars, and then returns back to Earth. Each leg of travel involves a take-off from the current planet and a landing on the next one, and fuel is consumed both when...

Codeforces Round 500 (Div. 1) [based on EJOI]

Codeforces Round 500 (Div. 1) [based on EJOI] Div. 1 | 6 problems | 3/6 verified | Difficulty 1500-3400 | 15m 11s # Problem Rating Tags Accepted Time ✓ A Photo of The Sky 1500 brute-force, implementation, math 6,689 1m 29s ✓ B Chemical table 1900 constructive-algorithms, dfs-and-similar, dsu 4,385 1m 39s ✓ C Hills 1900 dp 3,827 2m 10s D AB-Strings 2800 constructive-algorithms, strings 426 2m 15s E Cycle...

CF 1012E - Cycle sort

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

CF 1012A - Photo of The Sky

CF 1012A - Photo of The Sky Rating: 1500 Tags: brute force, implementation, math, sortings Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a multiset of numbers of size 2n , and we are told that these numbers originally came from n points in the plane, where each point contributes exactly two integers: its x-coordinate and its y-coordinate. The catch is that the pairing is completely...

Codeforces Round 500 (Div. 2) [based on EJOI]

Codeforces Round 500 (Div. 2) [based on EJOI] Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1200 | 2m 47s # Problem Rating Tags Accepted Time ✓ A Piles With Stones 800 math 11,706 1m 15s ✓ B And 1200 greedy 8,300 1m 32s ✓

CF 1013A - Piles With Stones

CF 1013A - Piles With Stones Rating: 800 Tags: math Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given two snapshots of the same system of stone piles. In the first snapshot, each pile has some number of stones, and in the second snapshot the piles have different counts. Between the two moments, during the night, two types of operations may happen any number of times: a...

Educational Codeforces Round 48 (Rated for Div. 2)

Educational Codeforces Round 48 (Rated for Div. 2) Div. 2 | 7 problems | 3/7 verified | Difficulty 900-2700 | 17m 27s # Problem Rating Tags Accepted Time ✓ A Death Note 900 greedy, implementation, math 15,969 1m 24s ✓ B Segment Occurrences 1300 brute-force, implementation 10,149 1m 56s ✓ C Vasya And The Mushrooms 1800 dp, implementation 3,991 2m 8s D Vasya And The Matrix 1800 constructive-algorithms, flows, math...

CF 1016G - Appropriate Team

CF 1016G - Appropriate Team Rating: 2700 Tags: bitmasks, math, number theory Solve time: 3m 12s Verified: no Solution Problem Understanding We are given a list of candidate values, and we want to count how many ordered pairs of candidates can simultaneously support a hidden integer value $v$ under two arithmetic constraints involving gcd and lcm with fixed constants $X$ and $Y$. For a chosen pair of indices $(i, j)$,...

CF 1016D - Vasya And The Matrix

CF 1016D - Vasya And The Matrix Rating: 1800 Tags: constructive algorithms, flows, math Solve time: 4m 3s Verified: no Solution Problem Understanding We are asked to construct a grid of size n by m where each cell contains a non-negative integer. What we know in advance is not the grid itself, but two sets of constraints derived from it: the XOR of every row is fixed, and the XOR...

CF 1016A - Death Note

CF 1016A - Death Note Rating: 900 Tags: greedy, implementation, math Solve time: 1m 24s Verified: yes Solution Problem Understanding We are simulating how writing progresses through an infinite notebook where each page can store a fixed number of names. Over a sequence of days, we are given how many names are written each day, and writing is continuous across days: if a page is not full at the end...

Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)

Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) Div. 1+2 | 8 problems | 6/8 verified | Difficulty 800-3300 | 18m 34s # Problem Rating Tags Accepted Time ✓ A The Rank 800 implementation 21,583 1m 30s ✓ B The Bits 1200 implementation, math 9,623 1m 47s ✓ C The Phone Number 1600 constructive-algorithms, greedy 6,470 1m 29s ✓ D The Wu 1900 bitmasks, brute-force,...

CF 1017F - The Neutral Zone

CF 1017F - The Neutral Zone Rating: 2500 Tags: brute force, math Solve time: 3m 31s Verified: yes Solution Problem Understanding We are asked to evaluate a number-theoretic sum over all integers from 1 to $n$, where each integer contributes a value defined through its prime factorization. For a number $x$, we factor it as a product of primes $x = \prod p_i^{a_i}$. A function $f$ is defined on integers,...

CF 1017B - The Bits

CF 1017B - The Bits Rating: 1200 Tags: implementation, math Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given two binary strings of equal length. You are allowed to pick any two positions in the first string and swap their bits. The second string stays fixed. After each swap, we recompute the bitwise OR of the two strings position by position, and we want to count how...

Codeforces Round 503 (by SIS, Div. 2)

Codeforces Round 503 (by SIS, Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 1000-1000 | 4m 30s # Problem Rating Tags Accepted Time ✓ A New Building for SIS 1000 math 9,453 3m ✓ B Badge 1000 brute-force, dfs-and-similar, graphs 25,118 1m 30s ✓

CF 1020A - New Building for SIS

CF 1020A - New Building for SIS Rating: 1000 Tags: math Solve time: 3m Verified: yes Solution Problem Understanding The building can be thought of as a grid of points arranged in $n$ vertical columns (towers) and $h$ horizontal levels (floors). From any point, you can always move vertically within the same tower, going up or down one floor at a time, and each such move costs exactly one minute....

Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) Div. 1+2 | 7 problems | 4/7 verified | Difficulty 1000-3400 | 16m 18s # Problem Rating Tags Accepted Time ✓ A Single Wildcard Pattern Matching 1200 brute-force, implementation, strings 9,263 1m 56s ✓ B Pair of Toys 1000 math 11,663 1m 52s ✓ C Bracket Subsequence 1200 greedy 10,753 1m 53s ✓ D Array...

CF 1023B - Pair of Toys

CF 1023B - Pair of Toys Rating: 1000 Tags: math Solve time: 1m 52s Verified: yes Solution Problem Understanding We are given a range of toy prices that is completely regular: there are toys priced from 1 up to n, each integer price appearing exactly once. We want to count how many distinct unordered pairs of different toys have a combined price exactly equal to k. Each pair is determined...

CF 1025G - Company Acquisitions

CF 1025G - Company Acquisitions Rating: 3200 Tags: constructive algorithms, math Solve time: 4m 3s Verified: yes Solution Problem Understanding We are given a system of startups arranged into a structure where some startups are already “active” and others are “acquired” and attached to exactly one active startup. Each acquired startup forms a rooted tree of dependents under an active root, and every active startup is the root of its...

CF 1025D - Recovering BST

CF 1025D - Recovering BST Rating: 2100 Tags: brute force, dp, math, number theory, trees Solve time: 3m 32s Verified: yes Solution Problem Understanding We are given a sorted list of distinct integers, and we want to build a binary search tree using exactly these values as node keys. The in-order traversal of any valid BST with these keys is fixed and already matches the given order, so the only...

Educational Codeforces Round 49 (Rated for Div. 2)

Educational Codeforces Round 49 (Rated for Div. 2) Div. 2 | 7 problems | 4/7 verified | Difficulty 1000-2600 | 35m 5s # Problem Rating Tags Accepted Time ✓ A Palindromic Twist 1000 implementation, strings 18,799 6m 17s ✓ B Numbers on the Chessboard 1200 implementation, math 8,744 3m 37s C Minimum Value Rectangle 1600 greedy 7,152 6m 46s D Mouse Hunt 1700 dfs-and-similar, graphs 8,366 3m 49s ✓ E...

CF 1027G - X-mouse in the Campus

CF 1027G - X-mouse in the Campus Rating: 2600 Tags: bitmasks, math, number theory Solve time: 5m 3s Verified: yes Solution Problem Understanding We are given a system of rooms labeled from 0 to $m-1$. A token, called the x-mouse, starts in an unknown room and evolves deterministically: if it is in room $i$, after one second it moves to $i \cdot x \bmod m$. We are allowed to place...

CF 1027E - Inverse Coloring

CF 1027E - Inverse Coloring Rating: 2100 Tags: combinatorics, dp, math Solve time: 2m 36s Verified: yes Solution Problem Understanding We are counting binary matrices of size $n \times n$, where each cell is either black or white, but with two structural restrictions. The first restriction is a strong symmetry condition called “beauty”. If you look at any two adjacent rows, then for every column, the two rows must either...

CF 1027B - Numbers on the Chessboard

CF 1027B - Numbers on the Chessboard Rating: 1200 Tags: implementation, math Solve time: 3m 37s Verified: no Solution Problem Understanding We are working with an $n \times n$ grid whose cells are filled with the numbers from $1$ to $n^2$, but not in a simple linear order. Instead, the grid is split into two disjoint groups of cells based on the parity of the sum of coordinates. Cells where...

AIM Tech Round 5 (rated, Div. 1 + Div. 2)

AIM Tech Round 5 (rated, Div. 1 + Div. 2) Div. 1+2 | 8 problems | 3/8 verified | Difficulty 800-3000 | 21m 57s # Problem Rating Tags Accepted Time ✓ A Find Square 800 implementation 11,517 1m 44s ✓ B Unnatural Conditions 1200 constructive-algorithms, math 10,234 2m 29s C Rectangles 1600 geometry, implementation, sortings 5,050 2m 30s ✓ D Order book 2100 combinatorics, data-structures, greedy 1,822 2m 46s E...

CF 1028H - Make Square

CF 1028H - Make Square Rating: 2900 Tags: math Solve time: 3m 45s Verified: no Solution Problem Understanding We are given a long array, and we repeatedly answer queries on subsegments of it. For each query range, we are allowed to slightly modify numbers in that segment by multiplying or dividing by primes, where each such operation changes a number by a single prime factor. The goal for a segment...

CF 1028B - Unnatural Conditions

CF 1028B - Unnatural Conditions Rating: 1200 Tags: constructive algorithms, math Solve time: 2m 29s Verified: no Solution Problem Understanding We are asked to construct two positive integers, call them $a$ and $b$, such that their digit sums are both large enough, while the digit sum of their sum is kept small. More concretely, we want $a$ and $b$ so that each of them has a decimal representation whose digits...

Codeforces Round 506 (Div. 3)

Codeforces Round 506 (Div. 3) Div. 3 | 6 problems | 5/6 verified | Difficulty 1200-2100 | 22m 31s # Problem Rating Tags Accepted Time ✓ A Many Equal Substrings 1300 implementation, strings 13,430 2m 24s ✓ B Creating the Contest 1200 dp, greedy, math 18,462 2m 25s ✓ C Maximal Intersection 1600 greedy, math, sortings 8,272 2m 50s ✓ D Concatenated Multiples 1900 implementation, math 4,234 5m 17s E...

CF 1029D - Concatenated Multiples

CF 1029D - Concatenated Multiples Rating: 1900 Tags: implementation, math Solve time: 5m 17s Verified: no Solution Problem Understanding We are given a list of positive integers and a modulus $k$. For every ordered pair of distinct indices $(i, j)$, we form a new number by writing $a_i$ directly followed by $a_j$ in decimal representation. We need to count how many such ordered concatenations are divisible by $k$. The key...

CF 1029F - Multicolored Markers

CF 1029F - Multicolored Markers Rating: 2000 Tags: binary search, brute force, math, number theory Solve time: 3m 41s Verified: yes Solution Problem Understanding We are given two counts, $a$ red tiles and $b$ blue tiles, and we must place them on an infinite grid so that all colored tiles together form a single axis-aligned rectangle of area $a+b$. Inside that rectangle, exactly $a$ cells are red and exactly $b$...

CF 1029C - Maximal Intersection

CF 1029C - Maximal Intersection Rating: 1600 Tags: greedy, math, sortings Solve time: 2m 50s Verified: yes Solution Problem Understanding We are given a collection of segments on a number line, and we want to understand how much they overlap if we remove exactly one of them. For any subset of segments, their common intersection is also a segment (or empty), and its length is determined by how tightly all...

CF 1029B - Creating the Contest

CF 1029B - Creating the Contest Rating: 1200 Tags: dp, greedy, math Solve time: 2m 25s Verified: yes Solution Problem Understanding We are given a sorted list of distinct problem difficulties. From this list, we must choose a subsequence, not necessarily contiguous, that will form a contest. The only restriction is local: if we sort the chosen difficulties increasingly, every consecutive pair must satisfy that the next difficulty is at...

Technocup 2019 - Elimination Round 2

Technocup 2019 - Elimination Round 2 Special | 6 problems | 1/6 verified | Difficulty 800-2800 | 1h 4m # Problem Rating Tags Accepted Time ✓ A Golden Plate 800 implementation, math 13,396 6m 26s ✓ B Curiosity Has No Limits 1500 4,064 17m 21s C Cram Time 1600 greedy 5,608 13m 38s D Minimum path 1900 greedy 2,985 6m 46s E Triple Flips 2600 constructive-algorithms 571 8m 34s F...

CF 1031F - Familiar Operations

CF 1031F - Familiar Operations Rating: 2800 Tags: brute force, graphs, math Solve time: 11m 31s Verified: no Solution Stopped thinking

CF 1031A - Golden Plate

CF 1031A - Golden Plate Rating: 800 Tags: implementation, math Solve time: 6m 26s Verified: yes Solution Problem Understanding We are working with a rectangular grid of size $w \times h$, where each cell can be thought of as a unit square on a plate. We repeatedly draw “rings” of gilding on this grid. The first ring covers the outer border of the whole rectangle. The second ring is drawn...

Technocup 2019 - Elimination Round 3

Technocup 2019 - Elimination Round 3 Special | 6 problems | 2/6 verified | Difficulty 900-2900 | 45m 9s # Problem Rating Tags Accepted Time ✓ A Kitchen Utensils 900 7,335 10m 29s ✓ B Personalized Cup 1200 5,145 9m 12s ✓ D Barcelonian Distance 1900 geometry, implementation 2,976 5m 6s E The Unbearable Lightness of Weights 2100 dp, math 1,865 3m 25s F Vasya and Maximum Matching 2400 dp,...

CF 1032E - The Unbearable Lightness of Weights

CF 1032E - The Unbearable Lightness of Weights Rating: 2100 Tags: dp, math Solve time: 3m 25s Verified: no Solution Problem Understanding We are given a multiset of weights, each weight having an integer mass between 1 and 100, but the weights are indistinguishable to us. We do not know which physical item corresponds to which mass, only the full list of masses exists somewhere in our friend’s knowledge. We...

Lyft Level 5 Challenge 2018 - Elimination Round

Lyft Level 5 Challenge 2018 - Elimination Round Special | 6 problems | 3/6 verified | Difficulty 1000-3500 | 50m 45s # Problem Rating Tags Accepted Time ✓ A King Escape 1000 dfs-and-similar, graphs, implementation 16,031 4m 19s ✓ B Square Difference 1100 math, number-theory 11,951 4m 51s ✓ C Permutation Game 1600 brute-force, dp, games 6,216 11m 39s ✓ D Divisors 2000 interactive, math, number-theory 2,611 8m 46s F...

CF 1033F - Boolean Computer

CF 1033F - Boolean Computer Rating: 2800 Tags: bitmasks, brute force, fft, math Solve time: 15m 35s Verified: no Solution Problem Understanding We are given a collection of up to 30,000 integers, each representable in at most 12 bits. Alongside this, we are given many “bitwise machines”, where each machine defines a transformation from two input numbers into one output number. The transformation works bit by bit: for every bit...

CF 1033D - Divisors

CF 1033D - Divisors Rating: 2000 Tags: interactive, math, number theory Solve time: 8m 46s Verified: no Solution Problem Understanding We are given a collection of integers, each of which is known to be “almost prime structured” in the sense that its number of divisors is very small, between 3 and 5. We multiply all these numbers together into one huge number and are asked to compute how many divisors...

CF 1033B - Square Difference

CF 1033B - Square Difference Rating: 1100 Tags: math, number theory Solve time: 4m 51s Verified: yes Solution Problem Understanding We start with a large square piece of cloth with side length $a$. From one corner, a smaller square of side $b$ is cut out. The remaining cloth is an L-shaped region whose area is simply the area of the big square minus the area of the removed square, so...

CF 1034E - Little C Loves 3 III

CF 1034E - Little C Loves 3 III Rating: 3200 Tags: bitmasks, dp, math Solve time: 6m 38s Verified: yes Solution Problem Understanding We are given two arrays indexed by bitmasks of length n , so each index represents a subset of an n -element universe encoded as a binary number from 0 to 2^n - 1 . For each mask i , we need to compute a value c[i]...

Educational Codeforces Round 50 (Rated for Div. 2)

Educational Codeforces Round 50 (Rated for Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2700 | 46m 7s # Problem Rating Tags Accepted Time ✓ A Function Height 1000 math 10,583 6m ✓ C Classy Numbers 1900 combinatorics, dp 13,367 12m 55s E Covered Points 2400 fft, geometry, number-theory 1,772 13m 58s F Relatively Prime Powers 2400 combinatorics, math, number-theory 1,858 7m 42s G Sources and...

CF 1036F - Relatively Prime Powers

CF 1036F - Relatively Prime Powers Rating: 2400 Tags: combinatorics, math, number theory Solve time: 7m 42s Verified: no Solution Problem Understanding We are looking at integers through the lens of their prime factorizations. Every number (x \ge 2) can be uniquely written as a product of primes, and we focus on the exponents in that decomposition. If we write [ x = \prod p_i^{k_i}, ] then the sequence of...

CF 1036A - Function Height

CF 1036A - Function Height Rating: 1000 Tags: math Solve time: 6m Verified: yes Solution Problem Understanding The figure is a broken line made from points at integer x-coordinates from 0 to 2n. Initially every point lies on the x-axis, so every y-coordinate is zero. The only way to modify the shape is to pick an odd-indexed point and increase its height by one unit per move. Even-indexed points are...

Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))

Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine)) Div. 1 | 6 problems | 1/6 verified | Difficulty 1300-3300 | 24m 56s # Problem Rating Tags Accepted Time ✓ A Charmed by the Game 1300 brute-force, math 11,495 5m 8s B Up the Strip 1900 brute-force, dp, math 5,269 6m 35s ✓ C Bottom-Tier Reversals 2000 constructive-algorithms, greedy 3,714 4m 30s D Top-Notch Insertions 2600...

Codeforces Round 737 (Div. 2)

Codeforces Round 737 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2800 | 19m 9s # Problem Rating Tags Accepted Time ✓ A Ezzat and Two Subsequences 800 brute-force, math, sortings 29,144 3m 16s ✓ B Moamen and k-subarrays 1100 greedy, sortings 24,608 3m 16s ✓ C Moamen and XOR 1700 bitmasks, combinatorics, dp 10,496 5m 29s ✓ D Ezzat and Grid 2200 data-structures, dp, greedy...

Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

Manthan, Codefest 18 (rated, Div. 1 + Div. 2) Div. 1+2 | 6 problems | 3/6 verified | Difficulty 1300-3200 | 38m 34s # Problem Rating Tags Accepted Time ✓ A Packets 1300 constructive-algorithms, greedy, math 11,828 10m 19s B Reach Median 1300 greedy 10,877 3m 15s ✓ C Equalize 1300 dp, greedy, strings 20,111 9m 29s ✓ D Valid BFS? 1700 dfs-and-similar, graphs, shortest-paths 19,089 4m 53s G A...

CF 1037A - Packets

CF 1037A - Packets Rating: 1300 Tags: constructive algorithms, greedy, math Solve time: 10m 19s Verified: no Solution

Codeforces Round 730 (Div. 2)

Codeforces Round 730 (Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 900-2700 | 32m 37s # Problem Rating Tags Accepted Time ✓ A Exciting Bets 900 greedy, math, number-theory 40,917 8m 6s ✓ B Customising the Track 900 combinatorics, greedy, math 24,475 4m 35s ✓ C Need for Pink Slips 1900 bitmasks, brute-force, dfs-and-similar 5,625 6m 31s D1 RPD and Rap Sheet (Easy Version) 1700 bitmasks,...

Codeforces Round 729 (Div. 2)

Codeforces Round 729 (Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2700 | 33m 36s # Problem Rating Tags Accepted Time ✓ A Odd Set 800 math 51,621 5m 9s ✓ B Plus and Multiply 1500 constructive-algorithms, math, number-theory 26,531 16m 20s ✓ C Strange Function 1600 math, number-theory 16,178 2m 39s D Priority Queue 2200 combinatorics, dp, implementation 2,921 6m 14s E1 Abnormal Permutation Pairs...

Codeforces Round 663 (Div. 2)

Codeforces Round 663 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2600 | 17m 2s # Problem Rating Tags Accepted Time ✓ A Suborrays 800 constructive-algorithms, math 25,062 4m 35s B Fix You 800 brute-force, greedy, implementation 29,778 55s ✓ C Cyclic Permutations 1500 combinatorics, dp, graphs 16,025 1m 29s ✓ D 505 2000 bitmasks, brute-force, constructive-algorithms 5,762 7m 33s ✓ E Pairs of Pairs 2600...

Codeforces Round 508 (Div. 2)

Codeforces Round 508 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2900 | 25m 51s # Problem Rating Tags Accepted Time ✓ A Equality 800 implementation, strings 15,644 11m 47s B Non-Coprime Partition 1100 constructive-algorithms, math 14,714 2m 54s ✓ D Slime 1800 dp, greedy, implementation 8,861 1m 47s E Maximum Matching 2400 bitmasks, brute-force, dfs-and-similar 1,095 4m 42s ✓ F Wrap Around 2900 dp, strings...

Educational Codeforces Round 92 (Rated for Div. 2)

Educational Codeforces Round 92 (Rated for Div. 2) Div. 2 | 7 problems | 2/7 verified | Difficulty 800-2800 | 27m 24s # Problem Rating Tags Accepted Time ✓ A LCM Problem 800 constructive-algorithms, greedy, math 49,851 5m 28s B Array Walk 1600 brute-force, dp, greedy 20,339 1m 57s ✓ C Good String 1500 brute-force, dp, greedy 20,560 5m 10s D D 2100 brute force, greedy, implementation 4,553 4m 57s...

Codeforces Round 660 (Div. 2)

Codeforces Round 660 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2700 | 13m 36s # Problem Rating Tags Accepted Time ✓ A Captain Flint and Crew Recruitment 800 brute-force, greedy, math 25,953 4m 57s B Captain Flint and a Long Voyage 1000 greedy, math 22,819 2m 12s ✓ C C 1800 dfs and similar, greedy, math 10,413 2m 35s ✓ D Captain Flint and Treasure...

Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)

Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) ICPC/IOI | 4 problems | 1/4 verified | Difficulty 2100-2900 | 17m 38s # Problem Rating Tags Accepted Time ✓ A Graph 2100 *special, binary-search, dfs-and-similar 905 6m 59s B1 Village (Minimum) 2100 *special, dp, greedy 1,890 1m 47s ✓ B2 Village (Maximum) 2500 *special, dfs-and-similar, trees 1,276 7m 9s C Viruses 2900 *special, dp, shortest-paths 204 1m...

CF 1038B - Non-Coprime Partition

CF 1038B - Non-Coprime Partition Rating: 1100 Tags: constructive algorithms, math Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given the integers from 1 to n, and we must split them into two non-empty groups so that every number is used exactly once. After splitting, we compute the sum of numbers in each group and look at the greatest common divisor of these two sums. The task...

Codeforces Round 507 (Div. 1, based on Olympiad of Metropolises)

Codeforces Round 507 (Div. 1, based on Olympiad of Metropolises) Div. 1 | 5 problems | 3/5 verified | Difficulty 2100-3400 | 34m 14s # Problem Rating Tags Accepted Time ✓ A Timetable 2300 constructive-algorithms, data-structures, greedy 861 6m 10s B Subway Pursuit 2100 binary-search, interactive, probabilities 2,589 11m 23s C Network Safety 2200 dfs-and-similar, dsu, graphs 1,490 8m 24s ✓ D You Are Given a Tree 2800 data-structures, dp,...

Codeforces Global Round 9

Codeforces Global Round 9 Global | 9 problems | 1/9 verified | Difficulty 1100-3500 | 36m 35s # Problem Rating Tags Accepted Time ✓ A Sign Flipping 1100 constructive-algorithms, math 18,842 2m 18s B Neighbor Grid 1200 constructive-algorithms, greedy 17,850 2m 18s C Element Extermination 1400 constructive-algorithms, data-structures, greedy 22,944 2m 34s D Replace by MEX 1900 brute-force, constructive-algorithms, sortings 10,140 1m 24s E Inversion SwapSort 2500 constructive-algorithms, greedy, sortings...

CF 1039C - Network Safety

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

CF 1039A - Timetable

CF 1039A - Timetable Rating: 2300 Tags: constructive algorithms, data structures, greedy, math Solve time: 6m 10s Verified: no Solution Problem Understanding We are given a fixed sequence of departure times from station A, strictly increasing, and for each bus we also know a constraint on how “late” it can possibly appear in the arrival order at station B. The arrival station has an unknown strictly increasing timetable, and we...

Codeforces Round 621 (Div. 1 + Div. 2)

Codeforces Round 621 (Div. 1 + Div. 2) Div. 1+2 | 7 problems | 4/7 verified | Difficulty 800-3300 | 36m 29s # Problem Rating Tags Accepted Time ✓ A A 800 greedy, implementation 15,626 3m 1s ✓ B Cow and Friend 1300 geometry, greedy, math 13,855 1m 55s ✓ C Cow and Message 1500 brute-force, dp, math 12,591 13m 13s ✓ D Cow and Fields 1900 binary-search, data-structures, dfs-and-similar...

Codeforces Round 510 (Div. 2)

Codeforces Round 510 (Div. 2) Div. 2 | 3 problems | 1/3 verified | Difficulty 1100-2300 | 10m 10s # Problem Rating Tags Accepted Time ✓ A Benches 1100 binary-search, implementation 14,077 2m 16s ✓ C Array Product 1700 constructive-algorithms, greedy, math 4,969 5m 5s E Vasya and Magic Matrix 2300 dp, math, probabilities 2,080 2m 49s

CF 1042E - Vasya and Magic Matrix

CF 1042E - Vasya and Magic Matrix Rating: 2300 Tags: dp, math, probabilities Solve time: 2m 49s Verified: no Solution Problem Understanding We are given a grid where every cell has a numeric value, and a chip starts at a specific cell. From its current position, the chip can only move to cells that have strictly smaller values than the current one. Among all such eligible cells, the next position...

CF 1042C - Array Product

CF 1042C - Array Product Rating: 1700 Tags: constructive algorithms, greedy, math Solve time: 5m 5s Verified: no Solution Problem Understanding We are given an array of integers, and we repeatedly reduce it until only one value remains. Each reduction step either merges two positions by multiplying their values and storing the result into one of the positions, or removes a single element entirely, but that removal operation can be...

Codeforces Round 519 by Botan Investments

Codeforces Round 519 by Botan Investments Special | 7 problems | 5/7 verified | Difficulty 800-3500 | 29m 20s # Problem Rating Tags Accepted Time ✓ A Elections 800 implementation, math 11,279 3m 25s ✓ B Lost Array 1200 implementation 6,551 3m 43s ✓ C Smallest Word 1500 constructive-algorithms, greedy, implementation 7,221 4m 31s D Mysterious Crime 1700 brute-force, combinatorics, math 4,761 4m 37s ✓ E Train Hard, Win Easy...

CF 1043D - Mysterious Crime

CF 1043D - Mysterious Crime Rating: 1700 Tags: brute force, combinatorics, math, meet-in-the-middle, two pointers Solve time: 4m 37s Verified: yes Solution Problem Understanding We are given several different observations of the same set of people, each observation being a full ordering of the same $n$ elements. Each observer saw a complete permutation, but their viewpoints are inconsistent, so the relative positions of the same element differ across permutations. The...

CF 1043E - Train Hard, Win Easy

CF 1043E - Train Hard, Win Easy Rating: 1900 Tags: constructive algorithms, greedy, math, sortings Solve time: 4m 14s Verified: yes Solution Problem Understanding We are given a set of participants, each described by two numbers. These two numbers represent how much penalty a participant contributes depending on whether they solve the first task or the second task in a two-person training contest. When two participants form a team, they...

CF 1043F - Make It One

CF 1043F - Make It One Rating: 2500 Tags: bitmasks, combinatorics, dp, math, number theory, shortest paths Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a multiset of positive integers, and we are allowed to choose any subset of these numbers. For a chosen subset, we compute the greatest common divisor of all selected elements. The goal is not to maximize this gcd, but instead to...

CF 1043A - Elections

CF 1043A - Elections Rating: 800 Tags: implementation, math Solve time: 3m 25s Verified: yes Solution Problem Understanding Each student in the school is forced to distribute a fixed number of votes, denoted by $k$, between two candidates. For every student, we are given how many votes they intend to give to Elodreip. If a student gives $a_i$ votes to Elodreip, then the remaining $k - a_i$ votes automatically go...

CF 1045F - Shady Lady

CF 1045F - Shady Lady Rating: 3400 Tags: geometry, math Solve time: 3m 49s Verified: yes Solution Problem Understanding We are given a fixed set of monomials in two variables, each monomial having the form $x^{a_k}y^{b_k}$, but with an unknown positive integer coefficient. Before the coefficients are chosen, Ani is allowed to remove at most one monomial. After that, Borna assigns arbitrary positive integers to all remaining coefficients. Once coefficients...

CF 2013B - Battle for Survive

CF 2013B - Battle for Survive Rating: 900 Tags: constructive algorithms, greedy, math Solve time: 6m 22s Verified: no Solution Problem Understanding We are given a group of fighters, each starting with a positive strength value. We repeatedly pick two still-alive fighters, and the one with the smaller index is always removed. The survivor’s strength is updated by subtracting the removed fighter’s strength from theirs. After exactly $n-1$ such operations,...

CF 1725C - Circular Mirror

CF 1725C - Circular Mirror Rating: 2000 Tags: binary search, combinatorics, geometry, math, two pointers Solve time: 5m 43s Verified: no Solution Problem Understanding We are given a circle with lamps placed on its boundary in a fixed clockwise order. Between consecutive lamps we know the arc lengths, so the geometry of the circle is fully determined up to rotation. Any triple of lamps defines a triangle by taking their...

CF 1561D1 - Up the Strip (simplified version)

CF 1561D1 - Up the Strip (simplified version) Rating: 1700 Tags: brute force, data structures, dp, math, number theory Solve time: 5m 59s Verified: no Solution Problem Understanding We are standing on a vertical strip of numbered cells from 1 at the top down to n at the bottom. A token starts at cell n, and we repeatedly move it upward until it reaches cell 1. Each move is a...

CF 1560C - Infinity Table

CF 1560C - Infinity Table Rating: 800 Tags: implementation, math Solve time: 4m 6s Verified: no Solution Problem Understanding We are given a rule that fills an infinite grid with positive integers starting from 1. The placement does not proceed row by row or column by column in a simple linear fashion. Instead, the filling moves in alternating vertical and horizontal “runs” that form a diagonal-like pattern. The process can...

CF 1560B - Who's Opposite?

CF 1560B - Who's Opposite? Rating: 800 Tags: math Solve time: 2m 3s Verified: no Solution Problem Understanding We are given three distinct labels that refer to people placed on a perfectly even circle. The circle size is even, but unknown, and the labels are not guaranteed to be consecutive or small. The only structural rule is that opposite positions in the circle are fixed: if you stand at some...

CF 1558A - Charmed by the Game

CF 1558A - Charmed by the Game Rating: 1300 Tags: brute force, math Solve time: 5m 8s Verified: no Solution Problem Understanding We are given only the final match statistics of a tennis game: Alice has won a individual games and Borys has won b individual games. We do not know the order of these games, and we also do not know who served first. What we do know is...

CF 1557A - Ezzat and Two Subsequences

CF 1557A - Ezzat and Two Subsequences Rating: 800 Tags: brute force, math, sortings Solve time: 3m 16s Verified: yes Solution Problem Understanding We are given an array of integers, and we must split it into two non-empty groups while preserving every element exactly once. Each group has a score equal to its arithmetic mean, and the goal is to maximize the sum of these two means. So if we...

CF 1553G - Common Divisor Graph

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

CF 1553F - Pairwise Modulo

CF 1553F - Pairwise Modulo Rating: 2300 Tags: data structures, math Solve time: 4m 38s Verified: no Solution Problem Understanding We are given a sequence of distinct positive integers. After reading the first k elements, we define a score p_k that aggregates the remainder produced by dividing every ordered pair (a_i, a_j) among the first k elements. In other words, for each prefix, we consider all possible pairs where the...

CF 1553E - Permutation Shift

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

CF 1551D1 - Domino (easy version)

CF 1551D1 - Domino (easy version) Rating: 1700 Tags: constructive algorithms, math Solve time: 7m 9s Verified: no Solution Problem Understanding We are given a rectangular board with $n$ rows and $m$ columns, containing $n \cdot m$ unit cells. Since this product is even, the board can be fully tiled by dominoes, where each domino always covers exactly two adjacent cells sharing a side. Every valid tiling uses exactly $\frac{n...

CF 1543A - Exciting Bets

CF 1543A - Exciting Bets Rating: 900 Tags: greedy, math, number theory Solve time: 8m 6s Verified: yes Solution Problem Understanding We are given two non-negative integers, and we can move them in lockstep: every operation changes both values by exactly the same amount, either increasing both by one or decreasing both by one (as long as we do not go below zero). The score we care about is the...

CF 1543D1 - RPD and Rap Sheet (Easy Version)

CF 1543D1 - RPD and Rap Sheet (Easy Version) Rating: 1700 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 6m 17s Verified: no Solution Problem Understanding We are playing an interactive game with a hidden number that always stays in the range from 0 to n − 1. We repeatedly submit guesses. If a guess is correct, the interaction ends immediately. If the guess is incorrect, the system does not...

CF 1542D - Priority Queue

CF 1542D - Priority Queue Rating: 2200 Tags: combinatorics, dp, implementation, math, ternary search Solve time: 6m 14s Verified: no Solution Problem Understanding We are given a sequence of operations that can either insert a value into a multiset or delete the smallest value currently present. The twist is that we do not evaluate this process once, but over every possible subsequence of the given operations, and each subsequence contributes...

CF 1542A - Odd Set

CF 1542A - Odd Set Rating: 800 Tags: math Solve time: 5m 9s Verified: yes Solution Problem Understanding We are given a collection of numbers with even size, specifically 2n integers per test case. The task is to decide whether it is possible to partition these numbers into n disjoint pairs such that every pair consists of two numbers whose sum is odd. A sum is odd exactly when one...

CF 1538D - Another Problem About Dividing Numbers

CF 1538D - Another Problem About Dividing Numbers Rating: 1700 Tags: constructive algorithms, math, number theory Solve time: 7m 9s Verified: no Solution Problem Understanding We start with two numbers, and we are allowed to repeatedly “divide” either of them by some integer greater than one, as long as it divides cleanly. Each operation reduces exactly one of the two numbers, and we want to end in a state where...

CF 1391A - Suborrays

CF 1391A - Suborrays Rating: 800 Tags: constructive algorithms, math Solve time: 4m 35s Verified: no Solution Problem Understanding We are asked to construct a permutation of the numbers from 1 to n such that every contiguous segment behaves in a very specific way under the bitwise OR operation. For any subarray, we take all values inside it and compute their bitwise OR. The requirement is that this OR value...

CF 1389A - LCM Problem

CF 1389A - LCM Problem Rating: 800 Tags: constructive algorithms, greedy, math, number theory Solve time: 5m 28s Verified: no Solution Problem Understanding We are given many independent ranges of integers. For each range $[l, r]$, we need to pick two different integers $x$ and $y$ inside this interval such that their least common multiple is also inside the same interval. So the task is not to optimize anything like...

CF 1388A - Captain Flint and Crew Recruitment

CF 1388A - Captain Flint and Crew Recruitment Rating: 800 Tags: brute force, greedy, math, number theory Solve time: 4m 57s Verified: no Solution Problem Understanding We are given multiple independent queries, each asking whether a target number can be broken into four distinct positive integers. The extra restriction is that at least three of those four numbers must come from a special class: numbers that can be written as...

CF 1387A - Graph

CF 1387A - Graph Rating: 2100 Tags: *special, binary search, dfs and similar, dp, math, ternary search Solve time: 6m 59s Verified: no Solution Problem Understanding We are given an undirected graph where every edge enforces a linear constraint between its endpoints. Each vertex must be assigned a real value, and every edge says exactly what the sum of its two endpoint values must be. Black edges force a sum...

CF 1386B - Mixture

CF 1386B - Mixture Rating: 2900 Tags: *special, data structures, geometry, math, sortings Solve time: 7m 15s Verified: no Solution Problem Understanding We are maintaining a dynamic multiset of 3D vectors, each vector representing the amounts of salt, pepper, and garlic powder in a bottle. After each update, either adding or removing a bottle, we must determine the smallest number of available bottles whose positive linear combination can produce a...

CF 1380G - Circular Dungeon

CF 1380G - Circular Dungeon Rating: 2600 Tags: greedy, math, probabilities Solve time: 6m 14s Verified: yes Solution Problem Understanding We are placing a multiset of values into a circular array of rooms. Each room contains exactly one item, and each item is either a regular chest with a reward value or a mimic that immediately stops the run when entered. A player starts from a uniformly random room and...

Codeforces Round 657 (Div. 2)

Codeforces Round 657 (Div. 2) Div. 2 | 5 problems | 0/5 verified | Difficulty 1500-2800 | 27m 51s # Problem Rating Tags Accepted Time ✓ A Acacius and String 1500 brute-force, implementation, strings 12,327 6m 47s B Dubious Cyrpto 1500 binary-search, brute-force, math 13,180 2m 14s C Choosing flowers 2000 binary-search, brute-force, data-structures 6,080 6m 47s E Inverse Genealogy 2800 constructive-algorithms, divide-and-conquer, dp 473 1m 20s F2 Chess Strikes...

CF 1375F - Integer Game

CF 1375F - Integer Game Rating: 2600 Tags: constructive algorithms, games, interactive, math Solve time: 6m 23s Verified: no Solution Problem Understanding Three numbers represent the sizes of three piles of stones. The interaction alternates between us and the opponent. On our turn we output a positive integer y , and on the opponent’s turn they must add exactly y stones to one of the three piles, with the restriction...

CF 1375A - Sign Flipping

CF 1375A - Sign Flipping Rating: 1100 Tags: constructive algorithms, math Solve time: 2m 18s Verified: no Solution Stopped thinking

Educational Codeforces Round 90 (Rated for Div. 2)

Educational Codeforces Round 90 (Rated for Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 900-2400 | 16m 42s # Problem Rating Tags Accepted Time ✓ A Donut Shops 1000 greedy, implementation, math 29,473 4m 37s B 01 Game 900 games 52,643 2m 24s ✓ E Sum of Digits 2200 brute-force, constructive-algorithms, dp 2,951 7m 2s F Network Coverage 2400 binary-search, constructive-algorithms, data-structures 1,878 2m 39s

CF 1373A - Donut Shops

CF 1373A - Donut Shops Rating: 1000 Tags: greedy, implementation, math Solve time: 4m 37s Verified: no Solution Problem Understanding We are comparing two different ways of buying the same number of donuts, and for each way we want to know when it becomes strictly cheaper than the other. In the first shop, the price is linear: buying $x$ donuts costs exactly $a \cdot x$. In the second shop, purchases...

Codeforces Round 655 (Div. 2)

Codeforces Round 655 (Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 800-2900 | 14m 47s # Problem Rating Tags Accepted Time ✓ A Omkar and Completion 800 constructive-algorithms, implementation 33,480 6m 44s B Omkar and Last Class of Math 1300 greedy, math, number-theory 36,364 1m 29s E Omkar and Last Floor 2900 dp, greedy, two-pointers 1,432 2m 3s ✓ F Omkar and Modes 2700 binary-search, divide-and-conquer,...

CF 1371C - A Cookie for You

CF 1371C - A Cookie for You Rating: 1300 Tags: greedy, implementation, math Solve time: 3m 54s Verified: no Solution Problem Understanding We are given two types of cookies and two types of guests. The cookies are split into vanilla and chocolate counts, and guests also come in two behavioral types. Guests arrive in some order that we are allowed to choose, and each guest makes a decision based only...

CF 1370B - GCD Compression

CF 1370B - GCD Compression Rating: 1100 Tags: constructive algorithms, math, number theory Solve time: 4m 11s Verified: no Solution Problem Understanding We are given an array of length $2n$. We are allowed to remove exactly two elements permanently. After that, the remaining $2n-2$ elements must be partitioned into pairs. Each pair is replaced by the sum of its two elements, producing an array $b$ of length $n-1$. The requirement...

CF 1369D - TediousLee

CF 1369D - TediousLee Rating: 1900 Tags: dp, graphs, greedy, math, trees Solve time: 2m 30s Verified: no Solution Problem Understanding The structure in this problem is a very specific rooted tree that grows level by level. Starting from a single node, each level expands every vertex depending on how many children it already has. A leaf gets one new child, a node with exactly one child gets two new...

CF 1368F - Lamps on a Circle

CF 1368F - Lamps on a Circle Rating: 2600 Tags: games, implementation, interactive, math Solve time: 2m 16s Verified: yes Solution Problem Understanding We are playing an interactive game on a circular array of n positions. All positions start empty. On each turn, the player is allowed to pick a number k and activate any k positions. Immediately after that, an adversary removes a block of exactly k consecutive positions...

CF 1367B - Even Array

CF 1367B - Even Array Rating: 800 Tags: greedy, math Solve time: 3m 58s Verified: yes Solution Problem Understanding We are given an array where each position has a fixed “required parity”: even indices must contain even numbers, and odd indices must contain odd numbers. We are allowed to rearrange the array using swaps between any two positions, and we want to know the minimum number of swaps needed to...

CF 1366D - Two Divisors

CF 1366D - Two Divisors Rating: 2000 Tags: constructive algorithms, math, number theory Solve time: 5m 59s Verified: no Solution Problem Understanding Each input value can be viewed as a box labeled with an integer, and for every box we must choose two non-trivial divisors of that number. The chosen divisors must both be greater than one, must divide the number exactly, and their sum must be “incompatible” with the...

CF 1365G - Secure Password

CF 1365G - Secure Password Rating: 2800 Tags: bitmasks, combinatorics, constructive algorithms, interactive, math Solve time: 2m 3s Verified: no Solution Problem Understanding We are given an unknown array of non-negative integers, each up to 64-bit range. We cannot see the array directly. Instead, we can query any subset of indices, and the judge returns the bitwise OR of the elements at those positions. From this hidden array, a second...

CF 1363D - Guess The Maximums

CF 1363D - Guess The Maximums Rating: 2100 Tags: binary search, implementation, interactive, math Solve time: 6m 18s Verified: no Solution Problem Understanding We are given an array $A$ of length $n$, but we cannot see it directly. Instead, we can ask queries: pick any subset of indices and the judge returns the maximum value of $A$ over those indices. Along with this hidden array, we are given $k$ special...

Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!

Codeforces Round 647 (Div. 2) - Thanks, Algo Muse! Div. 2 | 3 problems | 2/3 verified | Difficulty 1000-1400 | 13m 41s # Problem Rating Tags Accepted Time ✓ A Johnny and Ancient Computer 1000 implementation 34,050 3m 46s ✓ B Johnny and His Hobbies 1200 bitmasks, brute-force 21,033 2m 2s ✓ C Johnny and Another Rating Drop 1400 bitmasks, greedy, math 23,690 7m 53s

CF 1362C - Johnny and Another Rating Drop

CF 1362C - Johnny and Another Rating Drop Rating: 1400 Tags: bitmasks, greedy, math Solve time: 7m 53s Verified: no Solution Problem Understanding We are given a sequence that always contains consecutive integers starting from 0 up to some number n. Each number is viewed in binary, and all numbers are conceptually padded with leading zeros so they share the same bit length. For every adjacent pair in this sequence,...

CF 1361D - Johnny and James

CF 1361D - Johnny and James Rating: 2900 Tags: greedy, implementation, math, trees Solve time: 4m 33s Verified: no Solution Problem Understanding We are given a set of points on the plane, one of which is guaranteed to be the origin. From these points, we must keep exactly k points and delete the rest. The goal is to maximize a global score defined over all pairs of kept points, where...

CF 1360G - A/B Matrix

CF 1360G - A/B Matrix Rating: 1900 Tags: constructive algorithms, greedy, math Solve time: 7m 12s Verified: no Solution Problem Understanding We are asked to construct a binary grid of size $n \times m$, where each cell is either 0 or 1, under two simultaneous constraints that tightly couple rows and columns. Every row must contain exactly $a$ ones, and every column must contain exactly $b$ ones. If it is...

CF 1359E - Modular Stability

CF 1359E - Modular Stability Rating: 2000 Tags: combinatorics, math, number theory Solve time: 5m 8s Verified: no Solution Problem Understanding We are asked to count how many strictly increasing sequences of length $k$, chosen from the integers $1$ to $n$, have a very strong invariance property under repeated modulo operations. Given such a sequence, imagine taking any starting value $x$ and repeatedly applying modulo operations by the sequence elements...

CF 1359F - RC Kaboom Show

CF 1359F - RC Kaboom Show Rating: 2900 Tags: binary search, brute force, data structures, geometry, math Solve time: 4m 38s Verified: no Solution Problem Understanding We are given a collection of moving objects on an infinite plane. Each object starts from a fixed point, has a fixed direction, and moves in a straight line with a fixed speed. However, unlike standard motion problems, we are allowed to delay the...

CF 1355D - Game With Array

CF 1355D - Game With Array Rating: 1400 Tags: constructive algorithms, math Solve time: 2m 50s Verified: yes Solution Problem Understanding We are asked to construct a positive integer array of length $N$ whose total sum is exactly $S$. After building this array, we also choose an integer $K$ between $0$ and $S$. Vasya’s task is to defeat Petya by finding a non-empty contiguous segment of the array whose sum...

CF 1354C2 - Not So Simple Polygon Embedding

CF 1354C2 - Not So Simple Polygon Embedding Rating: 2000 Tags: binary search, brute force, geometry, math Solve time: 5m 12s Verified: yes Solution Problem Understanding We are given a regular polygon with $2n$ vertices, all edges equal to 1. The polygon is convex, and we are allowed to rotate it freely. We must place it inside a square, also freely rotatable, such that every point of the polygon lies...

CF 1354C1 - Simple Polygon Embedding

CF 1354C1 - Simple Polygon Embedding Rating: 1400 Tags: binary search, geometry, math, ternary search Solve time: 4m 38s Verified: yes Solution Problem Understanding We are working with a fixed geometric object: a regular polygon with $2n$ sides, each side having length 1. This polygon is convex and highly symmetric, so its shape is completely determined once we fix how it is oriented and scaled in the plane. The task...

Codeforces Round 640 (Div. 4)

Codeforces Round 640 (Div. 4) Div. 4 | 3 problems | 0/3 verified | Difficulty 800-1500 | 29m 36s # Problem Rating Tags Accepted Time ✓ A Sum of Round Numbers 800 implementation, math 104,056 6m 16s B Same Parity Summands 1200 constructive-algorithms, math 44,806 6m 28s F Binary String Reconstruction 1500 constructive-algorithms, dfs-and-similar, math 19,400 16m 52s

CF 1352B - Same Parity Summands

CF 1352B - Same Parity Summands Rating: 1200 Tags: constructive algorithms, math Solve time: 6m 28s Verified: no Solution Problem Understanding We are asked to split a given integer $n$ into exactly $k$ positive parts such that all parts share the same parity. This means we must choose either all odd numbers or all even numbers, and these $k$ numbers must sum exactly to $n$. The output is either a...

CF 1352A - Sum of Round Numbers

CF 1352A - Sum of Round Numbers Rating: 800 Tags: implementation, math Solve time: 6m 16s Verified: no Solution Problem Understanding The task is about breaking a given integer into simpler building blocks, where each building block is a number that looks like a single non-zero digit followed only by zeros. These are numbers such as 7, 40, 900, or 3000. The goal is to express the given number as...

CF 1350A - Orac and Factors

CF 1350A - Orac and Factors Rating: 900 Tags: math Solve time: 5m 48s Verified: yes Solution Problem Understanding We start with a number and repeatedly apply a very specific transformation: find its smallest divisor greater than 1, and add that value to the number. This operation changes the number itself, so the divisor we use may change at every step. After doing this exactly k times, we are asked...

Codeforces Round 641 (Div. 2)

Codeforces Round 641 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 900-1400 | 7m 24s # Problem Rating Tags Accepted Time ✓ A Orac and Factors 900 math 27,374 5m 48s ✓ B Orac and Models 1400 dp, math, number-theory 29,431 1m 36s ✓

CF 1348E - Phoenix and Berries

CF 1348E - Phoenix and Berries Rating: 2400 Tags: brute force, dp, greedy, math Solve time: 6m 19s Verified: yes Solution Problem Understanding We are given several shrubs, each containing two independent piles of berries: red and blue. From these sources we want to form as many baskets as possible, where every basket must contain exactly $k$ berries. A basket is only allowed to mix berries if they obey one...

CF 1345B - Card Constructions

CF 1345B - Card Constructions Rating: 1100 Tags: binary search, brute force, dp, math Solve time: 7m 18s Verified: yes Solution Problem Understanding We are given a supply of identical cards and we repeatedly build structures called pyramids. A pyramid of height 1 is the smallest possible structure, and every higher pyramid is built in layers: a taller pyramid consists of a smaller pyramid placed on top of a wider...

CF 1344D - Résumé Review

CF 1344D - R\u00e9sum\u00e9 Review Rating: 2700 Tags: binary search, greedy, math Solve time: 3m 49s Verified: no Solution Problem Understanding We are given several categories of projects, and for each category we know how many projects exist. From each category we choose some number of projects to place on a résumé, with the constraint that the total number of chosen projects is exactly $k$, and we cannot pick more...

CF 1344C - Quantifier Question

CF 1344C - Quantifier Question Rating: 2600 Tags: dfs and similar, dp, graphs, math Solve time: 3m 29s Verified: no Solution Problem Understanding We are given a directed graph on variables $x_1, x_2, \dots, x_n$. Each constraint $x_j < x_k$ behaves like an edge $j \to k$, and a full assignment of real values satisfies the formula only if every edge points from a smaller value to a larger value....

CF 1342C - Yet Another Counting Problem

CF 1342C - Yet Another Counting Problem Rating: 1600 Tags: math, number theory Solve time: 4m 50s Verified: no Solution Problem Understanding We are working with integers and modular arithmetic, but the structure becomes clearer if we think of the infinite number line as being colored by a periodic rule. For any integer $x$, we compute two values: first we take $x \bmod a$, then reduce that result modulo $b$....

CF 1338C - Perfect Triples

CF 1338C - Perfect Triples Rating: 2200 Tags: bitmasks, brute force, constructive algorithms, divide and conquer, math Solve time: 6m 54s Verified: no Solution Problem Understanding We are building an infinite sequence by repeatedly selecting groups of three unused positive integers. Each group must satisfy a strict bitwise condition: the XOR of the three numbers is zero. Among all valid unused triples, we always pick the lexicographically smallest one, append...

CF 1338D - Nested Rubber Bands

CF 1338D - Nested Rubber Bands Rating: 2700 Tags: constructive algorithms, dfs and similar, dp, math, trees Solve time: 6m 25s Verified: yes Solution Problem Understanding We are given a tree, and the problem asks us to think about a geometric construction that can be performed on it. Each vertex becomes a closed non-self-intersecting curve on a plane. These curves are required to interact in a very rigid way: two...

Codeforces Round 635 (Div. 2)

Codeforces Round 635 (Div. 2) Div. 2 | 1 problems | 0/1 verified | Difficulty 800-800 | 6m 25s # Problem Rating Tags Accepted Time ✓ A Ichihime and Triangle 800 constructive-algorithms, math 42,897 6m 25s

CF 1337A - Ichihime and Triangle

CF 1337A - Ichihime and Triangle Rating: 800 Tags: constructive algorithms, math Solve time: 6m 25s Verified: no Solution Problem Understanding We are given four integers in non-decreasing order, and we need to choose three lengths from three separate intervals. The first length must come from the first interval, the second from the second interval, and the third from the third interval. After choosing these three values, we must ensure...

CF 1334C - Circle of Monsters

CF 1334C - Circle of Monsters Rating: 1600 Tags: brute force, constructive algorithms, greedy, math Solve time: 3m 30s Verified: yes Solution Problem Understanding We are given a ring of monsters. Each monster has an initial health value, and also a fixed explosion damage value that is applied to its next neighbor when it dies. We can shoot any monster directly, spending one bullet per unit of damage, and once...

CF 1332E - Height All the Same

CF 1332E - Height All the Same Rating: 2100 Tags: combinatorics, constructive algorithms, math, matrices Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given a rectangular grid with $n \times m$ cells, and each cell starts with some integer height $a_{i,j}$. The game allows two types of moves that increase heights: either we add one cube to two adjacent cells at the same time, or we add...

Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!

Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov! Div. 1 | 5 problems | 2/5 verified | Difficulty 1700-3300 | 23m 52s # Problem Rating Tags Accepted Time ✓ A Dreamoon Likes Coloring 1800 constructive-algorithms, greedy, implementation 9,669 5m 5s B Dreamoon Likes Sequences 1700 bitmasks, combinatorics, math 7,056 6m 56s ✓ C Drazil Likes Heap 2400 constructive-algorithms, data-structures, greedy 1,804 5m 42s D Dreamoon Likes Strings 3100...

CF 1329B - Dreamoon Likes Sequences

CF 1329B - Dreamoon Likes Sequences Rating: 1700 Tags: bitmasks, combinatorics, math Solve time: 6m 56s Verified: yes Solution Problem Understanding We are asked to count how many strictly increasing sequences of integers we can choose from the range $[1, d]$, with an extra constraint that depends on cumulative XORs of the chosen values. Concretely, we pick a non-empty increasing sequence $a_1 < a_2 < \dots < a_n$, all within...

CF 1329A - Dreamoon Likes Coloring

CF 1329A - Dreamoon Likes Coloring Rating: 1800 Tags: constructive algorithms, greedy, implementation, math Solve time: 5m 5s Verified: no Solution Problem Understanding We are given a row of cells initially all unpainted. We will perform a sequence of painting operations, where each operation paints a contiguous segment of fixed length, but we are free to choose the starting position of that segment. Each operation has its own color, and...

CF 1328D - Carousel

CF 1328D - Carousel Rating: 1800 Tags: constructive algorithms, dp, graphs, greedy, math Solve time: 3m 4s Verified: no Solution Problem Understanding We are given a circular arrangement of positions, each holding an animal type. The positions are connected in a cycle, so after the last position comes the first again. We must assign a color to each position. The constraint is local: whenever two neighboring positions on the cycle...

Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics) Div. 1 | 3 problems | 1/3 verified | Difficulty 1300-3500 | 12m 47s # Problem Rating Tags Accepted Time ✓ A Unusual Competitions 1300 greedy 12,886 4m 47s C Instant Noodles 2300 graphs, hashing, math 2,703 2m 42s F Assigning Fares 3500 dp, trees 162 5m 18s ✓

Codeforces Round 622 (Div. 2)

Codeforces Round 622 (Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 900-2500 | 11m 20s # Problem Rating Tags Accepted Time ✓ A Fast Food Restaurant 900 brute-force, greedy, implementation 16,230 4m 17s ✓ B Different Rules 1700 constructive-algorithms, greedy, implementation 7,007 1m 39s ✓ C1 Skyscrapers (easy version) 1500 brute-force, data-structures, dp 11,058 2m 51s D Happy New Year 2500 bitmasks, dp, implementation 1,501 2m...

Educational Codeforces Round 83 (Rated for Div. 2)

Educational Codeforces Round 83 (Rated for Div. 2) Div. 2 | 4 problems | 0/4 verified | Difficulty 1000-2600 | 9m 40s # Problem Rating Tags Accepted Time ✓ B Bogosort 1000 constructive-algorithms, sortings 39,027 4m 47s C Adding Powers 1400 bitmasks, greedy, implementation 18,342 1m 8s D Count the Arrays 1700 combinatorics, math 10,525 2m 54s G Autocompletion 2600 data-structures, dfs-and-similar, dp 1,081 51s

CF 1307B - Cow and Friend

CF 1307B - Cow and Friend Rating: 1300 Tags: geometry, greedy, math Solve time: 1m 55s Verified: yes Solution Problem Understanding A rabbit starts at the origin in the plane and wants to land exactly at the point $(x, 0)$. He moves by making a sequence of jumps, and each jump can have any direction, but its length must match one of the allowed values given in the input. The...

CF 1305E - Kuroni and the Score Distribution

CF 1305E - Kuroni and the Score Distribution Rating: 2200 Tags: constructive algorithms, greedy, implementation, math Solve time: 7m 11s Verified: no Solution Problem Understanding We are asked to construct a strictly increasing sequence of integers $a_1 < a_2 < \dots < a_n$, all between 1 and $10^9$, such that a specific combinatorial condition on triples is satisfied. The condition counts how many index triples $i < j < k$...

CF 1303B - National Project

CF 1303B - National Project Rating: 1400 Tags: math Solve time: 3m 33s Verified: no Solution Problem Understanding We are building a road of length $n$, where each unit of road must eventually be asphalted exactly once. The construction proceeds day by day, and on each day we may either work on exactly one unit or do nothing. The weather is periodic. It starts with a block of $g$ good...

CF 1299E - So Mean

CF 1299E - So Mean Rating: 3400 Tags: interactive, math Solve time: 9m 8s Verified: no Solution Problem Understanding We are given a hidden permutation of numbers from $1$ to $n$, where $n$ is even. We cannot directly see it, but we can query any subset of indices. For a chosen subset, the judge tells us only whether the average value of the selected positions is an integer. That condition...

CF 1297G - M-numbers

CF 1297G - M-numbers Rating: - Tags: *special, dp, math Solve time: 5m 1s Verified: no Solution Problem Understanding We are given a target value $m$ and asked to consider all positive integers whose digits multiply exactly to $m$. These integers form an infinite set in general, and we are asked to sort this set in increasing numerical order and return the $k$-th element. The key object is not just...

CF 1296B - Food Buying

CF 1296B - Food Buying Rating: 900 Tags: math Solve time: 2m 13s Verified: yes Solution Problem Understanding We are given an initial amount of money, and we repeatedly perform a very specific type of purchase operation. In each operation, we choose some amount $x$ that we can afford at that moment, spend it, and immediately receive back $\lfloor x/10 \rfloor$. That cashback can be reused in future purchases, so...

CF 1295D - Same GCDs

CF 1295D - Same GCDs Rating: 1800 Tags: math, number theory Solve time: 3m 37s Verified: yes Solution Problem Understanding We are working with a fixed number $a$ and a modulus-like bound $m$. For every integer shift $x$ in the range $[0, m-1]$, we look at the number $a + x$ and compare its greatest common divisor with $m$ against the original value $\gcd(a, m)$. The task is to count...

CF 1293B - JOE is on TV!

CF 1293B - JOE is on TV! Rating: 1000 Tags: combinatorics, greedy, math Solve time: 9m 25s Verified: no Solution Problem Understanding The game can be seen as a process where we start with n opponents and repeatedly trigger rounds that remove some of them. In each round, if there are s opponents still in the game and exactly t of them fail the current question, JOE earns t/s dollars...

CF 1292D - Chaotic V.

CF 1292D - Chaotic V. Rating: 2700 Tags: dp, graphs, greedy, math, number theory, trees Solve time: 7m 22s Verified: no Solution Problem Understanding The graph in this problem is not given explicitly, but fully determined by the structure of integers. Every positive integer is a node, and each number $x > 1$ has a directed edge to $x / f(x)$, where $f(x)$ is the smallest prime factor of $x$....

CF 1292E - Rin and The Unknown Flower

CF 1292E - Rin and The Unknown Flower Rating: 3500 Tags: constructive algorithms, greedy, interactive, math Solve time: 4m 51s Verified: no Solution Problem Understanding We are trying to reconstruct a hidden string of length up to 50. The string is guaranteed to use only three symbols: C, H, and O. The only way to obtain information is through a substring query mechanism: we send a pattern string, and we...

Codeforces Round 616 (Div. 2)

Codeforces Round 616 (Div. 2) Div. 2 | 3 problems | 0/3 verified | Difficulty 900-2800 | 15m 2s # Problem Rating Tags Accepted Time ✓ A Even But Not Even 900 greedy, math, strings 20,680 4m 55s B Array Sharpening 1300 greedy, implementation 15,358 5m 13s F Coffee Varieties (easy version) 2800 graphs, interactive 726 4m 54s

CF 1291A - Even But Not Even

CF 1291A - Even But Not Even Rating: 900 Tags: greedy, math, strings Solve time: 4m 55s Verified: no Solution Problem Understanding We are given a digit string and we are allowed to delete some of its digits while keeping the remaining digits in the same relative order. The goal is to form a non-empty subsequence that represents a number satisfying two conditions at the same time: the sum of...

CF 1286C2 - Madhouse (Hard version)

CF 1286C2 - Madhouse (Hard version) Rating: 2800 Tags: brute force, constructive algorithms, hashing, interactive, math Solve time: 6m 2s Verified: no Solution Problem Understanding A hidden string of length $n$ is fixed before the game starts. The player’s goal is to recover this exact string. Instead of being given it directly, the only way to gain information is by querying substrings of ranges. When a range $[l, r]$ is...

CF 1286C1 - Madhouse (Easy version)

CF 1286C1 - Madhouse (Easy version) Rating: 2400 Tags: brute force, constructive algorithms, interactive, math Solve time: 4m 5s Verified: no Solution Problem Understanding We are dealing with a hidden string of length $n$, made of lowercase English letters. We cannot see the string directly. Instead, we can query any segment $s[l..r]$, and the judge returns all substrings of that segment, but with two distortions: the order of substrings is...

CF 1284F - New Year and Social Network

CF 1284F - New Year and Social Network Rating: 3200 Tags: data structures, graph matchings, graphs, math, trees Solve time: 10m Verified: no Solution Problem Understanding We are given two different spanning trees over the same set of $n$ vertices. One tree, call it $T_1$, represents the main network, and the second tree $T_2$ is a backup structure. Each edge in $T_1$ is a potential failure point. If an edge...

CF 1284E - New Year and Castle Construction

CF 1284E - New Year and Castle Construction Rating: 2500 Tags: combinatorics, geometry, math, sortings Solve time: 7m 49s Verified: no Solution Problem Understanding We are given a set of points in the plane, with the restriction that no three points lie on a single line. For every point (p), we want to count how many subsets of exactly four other points can form a simple quadrilateral that strictly contains...

Codeforces Round 611 (Div. 3)

Codeforces Round 611 (Div. 3) Div. 3 | 5 problems | 3/5 verified | Difficulty 900-2200 | 30m 30s # Problem Rating Tags Accepted Time ✓ B Candies Division 900 math 23,081 5m 8s ✓ C Friends and Gifts 1500 constructive-algorithms, data-structures, math 14,153 1m 32s ✓ D Christmas Trees 1800 graphs, greedy, shortest-paths 9,438 5m 22s E New Year Parties 1800 dp, greedy 7,325 11m 52s ✓ F DIY...

CF 1283B - Candies Division

CF 1283B - Candies Division Rating: 900 Tags: math Solve time: 5m 8s Verified: yes Solution Problem Understanding We are distributing a fixed number of identical candies among a fixed number of children. Each child must receive a non-negative integer number of candies, and we are allowed to leave some candies unused. The distribution is considered valid only if the values assigned to children are tightly balanced: the largest and...

CF 1280E - Kirchhoff's Current Loss

CF 1280E - Kirchhoff's Current Loss Rating: 2900 Tags: math Solve time: 5m 37s Verified: no Solution Problem Understanding The circuit is given as a fully parenthesized expression that builds a tree of components. Leaves are individual resistors, each represented by * . Internal nodes are either series connections or parallel connections over two or more subcircuits. The structure is fixed and cannot be changed. The only freedom we have...

CF 1280B - Beingawesomeism

CF 1280B - Beingawesomeism Rating: 1800 Tags: implementation, math Solve time: 6m 37s Verified: no Solution Problem Understanding We are given a grid of size $r \times c$, where each cell is either $A$ or $P$. The goal is to convert every $P$ into $A$ using a special operation that behaves like a directional flood from a chosen line segment. Each operation works like this: we pick a full row...

CF 1276C - Beautiful Rectangle

CF 1276C - Beautiful Rectangle Rating: 2300 Tags: brute force, combinatorics, constructive algorithms, data structures, greedy, math Solve time: 11m 51s Verified: no Solution Problem Understanding We are given a multiset of integers, and we are allowed to select some of them and arrange the selected elements into a rectangular grid. Every chosen element occupies exactly one cell, and the grid is completely filled with chosen values. The grid has...

CF 1271B - Blocks

CF 1271B - Blocks Rating: 1300 Tags: greedy, math Solve time: 4m 12s Verified: no Solution Problem Understanding We are given a line of blocks, each painted either black or white. The only allowed move is to pick two neighboring blocks and flip both of them at the same time, turning white into black and black into white. The task is not to optimize the number of moves, but to...

CF 1270I - Xor on Figures

CF 1270I - Xor on Figures Rating: 3500 Tags: constructive algorithms, fft, math Solve time: 16m 22s Verified: no Solution Problem Understanding We are given a toroidal grid of size $2^k \times 2^k$, where each cell contains a 60-bit integer. The grid wraps around both horizontally and vertically, so shifting beyond an edge brings us back to the opposite side. Alongside this grid, we are also given a fixed pattern...

CF 1270G - Subset with Zero Sum

CF 1270G - Subset with Zero Sum Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs, math Solve time: 5m 39s Verified: no Solution Problem Understanding We are given an array of integers where each position i has a value a[i] constrained in a tight interval that depends on its index. The i-th element is never too negative and never too large: it always lies between i − n and...

CF 1270B - Interesting Subarray

CF 1270B - Interesting Subarray Rating: 1200 Tags: constructive algorithms, greedy, math Solve time: 10m 31s Verified: no Solution Problem Understanding We are given several test cases, and each test case provides an array of integers. The task is to determine whether there exists a contiguous segment of this array whose spread is large enough compared to its length. More precisely, we want a subarray where the difference between its...

CF 1270F - Awesome Substrings

CF 1270F - Awesome Substrings Rating: 2600 Tags: math, strings Solve time: 2m 22s Verified: yes Solution Problem Understanding We are given a binary string and asked to count how many of its contiguous substrings satisfy a very specific structural constraint. A substring is considered valid if it contains at least one 1 , and if its total length is divisible by the number of 1 s inside it. So...

CF 1270E - Divide Points

CF 1270E - Divide Points Rating: 2300 Tags: constructive algorithms, geometry, math Solve time: 4m 59s Verified: no Solution Problem Understanding We are given a collection of points on a plane, each with integer coordinates, and we must split them into two nonempty groups. After splitting, every pair of points produces a distance value, since we consider Euclidean distances between all pairs. Each pair contributes exactly one number, but it...

CF 1270C - Make Good

CF 1270C - Make Good Rating: 1400 Tags: bitmasks, constructive algorithms, math Solve time: 5m 12s Verified: no Solution Problem Understanding We are given an array of nonnegative integers, and we are allowed to append at most three additional numbers. The goal is to make the final multiset of numbers satisfy a very specific algebraic condition: the sum of all elements must equal twice their bitwise XOR. This condition couples...

CF 1270D - Strange Device

CF 1270D - Strange Device Rating: 1900 Tags: constructive algorithms, interactive, math, sortings Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given an unknown array of distinct integers. We cannot read it directly. Instead, we can query any subset of exactly k positions, and the device returns the position and value of the element that would rank as the m -th smallest among those k values. The...

CF 1267J - Just Arrange the Icons

CF 1267J - Just Arrange the Icons Rating: 1800 Tags: greedy, implementation, math Solve time: 3m 21s Verified: yes Solution Problem Understanding We are given a multiset of applications, each belonging to a category. The only thing that matters about a category is how many apps it contains, so the input can be compressed into frequencies of each distinct category. We must place all apps into “screens”. Each screen has...

CF 1250L - Divide The Students

CF 1250L - Divide The Students Rating: 1500 Tags: binary search, greedy, math Solve time: 7m 8s Verified: yes Solution Problem Understanding We are given three groups of students determined by their preferred programming language. The task is to split all students into exactly three practice groups. The only restriction is that a single group is not allowed to contain both Assembler fans and C++ fans at the same time....

CF 1249C2 - Good Numbers (hard version)

CF 1249C2 - Good Numbers (hard version) Rating: 1500 Tags: binary search, greedy, math, meet-in-the-middle Solve time: 1m 37s Verified: no Solution Problem Understanding We are given several independent queries. Each query provides a large integer $n$, and we must output the smallest integer $m \ge n$ such that $m$ can be expressed as a sum of distinct powers of 3. In other words, every valid number corresponds to choosing...

CF 1249B1 - Books Exchange (easy version)

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

CF 1249B2 - Books Exchange (hard version)

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

CF 1248B - Grow The Tree

CF 1248B - Grow The Tree Rating: 900 Tags: greedy, math, sortings Solve time: 5m 32s Verified: no Solution Problem Understanding We are given a multiset of stick lengths, and we must arrange all of them into a polyline starting at the origin. Each stick becomes one segment of this polyline, and every segment must be axis-aligned, meaning it is either horizontal or vertical. The only structural constraint is that...

Codeforces Round 592 (Div. 2)

Codeforces Round 592 (Div. 2) Div. 2 | 7 problems | 2/7 verified | Difficulty 800-2400 | 32m 42s # Problem Rating Tags Accepted Time ✓ A Pens and Pencils 800 math 20,065 2m 33s B Rooms and Staircases 1000 brute-force, implementation 17,542 2m 33s C The Football Season 2000 brute-force, math, number-theory 8,285 5m 25s D Paint the Tree 1800 brute-force, constructive-algorithms, dp 8,299 2m 52s ✓ E Minimizing...

CF 1244G - Running in Pairs

CF 1244G - Running in Pairs Rating: 2400 Tags: constructive algorithms, greedy, math Solve time: 6m 34s Verified: no Solution Problem Understanding We are given two groups of runners, each group containing the integers from 1 to n. We must arrange each group into a permutation, one for the first track and one for the second track. When the competition runs, the i-th pair consists of the i-th runner on...

CF 1244C - The Football Season

CF 1244C - The Football Season Rating: 2000 Tags: brute force, math, number theory Solve time: 5m 25s Verified: no Solution Problem Understanding We are given a season summary for a football team, but instead of individual match results, only aggregated information is known. The team played exactly $n$ matches and accumulated a total of $p$ points. Each match contributes to the score in one of two ways: a win...

CF 1244A - Pens and Pencils

CF 1244A - Pens and Pencils Rating: 800 Tags: math Solve time: 2m 33s Verified: no Solution Problem Understanding Polycarp has two types of work tomorrow: writing lectures and drawing during practical classes. For lectures he must use pens, and each pen can be used for a limited number of lectures before it dries out. For practical classes he must use pencils, and each pencil can be reused across a...

CF 1238C - Standard Free2play

CF 1238C - Standard Free2play Rating: 1600 Tags: dp, greedy, math Solve time: 6m 2s Verified: no Solution Problem Understanding We can think of the cliff as a vertical line of heights from 1 up to h, with a special starting platform at height h. Some of these heights already contain usable platforms, while the rest are empty. You are standing at the top platform and want to reach ground...

Codeforces Global Round 5

Codeforces Global Round 5 Global | 9 problems | 3/9 verified | Difficulty 1000-3500 | 44m 41s # Problem Rating Tags Accepted Time ✓ A Balanced Rating Changes 1000 implementation, math 22,113 4m 41s ✓ B Balanced Tunnel 1300 data-structures, sortings, two-pointers 22,758 3m 15s ✓ C1 Balanced Removals (Easier) 1700 constructive-algorithms, geometry, greedy 6,300 3m 18s C2 Balanced Removals (Harder) 1900 binary-search, constructive-algorithms, divide-and-conquer 4,534 3m 53s D Balanced...

CF 1237A - Balanced Rating Changes

CF 1237A - Balanced Rating Changes Rating: 1000 Tags: implementation, math Solve time: 4m 41s Verified: yes Solution Problem Understanding We are given a list of integers representing rating changes from a contest. The total sum of all these changes is exactly zero, meaning gains and losses perfectly balance out before any modification. The task is to transform each value independently into a “halved” version. For each original value $a_i$,...

Codeforces Round 593 (Div. 2)

Codeforces Round 593 (Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 800-3000 | 39m 57s # Problem Rating Tags Accepted Time ✓ A Stones 800 brute-force, greedy, math 17,249 5m 9s ✓ B Alice and the List of Presents 1500 combinatorics, math 12,052 6m 11s ✓ C Labs 1300 constructive-algorithms, greedy, implementation 10,553 9m 52s D Alice and the Doll 2300 brute-force, data-structures, greedy 1,737 6m...

CF 1236F - Alice and the Cactus

CF 1236F - Alice and the Cactus Rating: 3000 Tags: dfs and similar, graphs, math, probabilities Solve time: 5m 7s Verified: no Solution Problem Understanding We are given a connected undirected graph with a special structure: it is a cactus, meaning every edge belongs to at most one simple cycle. On this graph, each vertex independently survives with probability $1/2$, otherwise it is deleted together with all incident edges. After...

CF 1236A - Stones

CF 1236A - Stones Rating: 800 Tags: brute force, greedy, math Solve time: 5m 9s Verified: yes Solution Problem Understanding We are given three piles of stones. From these piles, Alice can repeatedly perform two kinds of moves. One move consumes one stone from the first pile and two stones from the second pile. The other move consumes one stone from the second pile and two stones from the third...

CF 1228B - Filling the Grid

CF 1228B - Filling the Grid Rating: 1400 Tags: implementation, math Solve time: 5m 8s Verified: no Solution Problem Understanding We are given a grid of size (h \times w), initially completely empty, and two sets of constraints that describe how far blocks of filled cells must extend from the top and from the left. For each row (i), the value (r_i) tells us that the first (r_i) cells in...

CF 1228E - Another Filling the Grid

CF 1228E - Another Filling the Grid Rating: 2300 Tags: combinatorics, dp, math Solve time: 2m 31s Verified: yes Solution Problem Understanding We are filling an $n \times n$ grid with integers from $1$ to $k$. The restriction is not about individual cells, but about structure: every row must contain at least one occurrence of the value $1$, and every column must also contain at least one occurrence of $1$....

CF 1225D - Power Products

CF 1225D - Power Products Rating: 1800 Tags: hashing, math, number theory Solve time: 3m 50s Verified: yes Solution Problem Understanding We are given a sequence of positive integers and asked to count how many pairs of indices produce a product that is a perfect k-th power. In other words, for two distinct elements $a_i$ and $a_j$, we want to know whether their product can be written as $x^k$ for...

CF 1225C - p-binary

CF 1225C - p-binary Rating: 1600 Tags: bitmasks, brute force, math Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a positive target number $n$. We also fix an integer $p$, which shifts a family of numbers of the form $2^x + p$, where $x \ge 0$. Each such value is a single “building block”, and we are allowed to reuse the same block any number of...

Technocup 2020 - Elimination Round 1

Technocup 2020 - Elimination Round 1 Special | 7 problems | 6/7 verified | Difficulty 800-3200 | 27m 26s # Problem Rating Tags Accepted Time ✓ A CME 800 math 22,285 5m 7s ✓ B Strings Equalization 1000 strings 15,893 5m 14s ✓ C Save the Nature 1600 binary-search, greedy 9,761 1m 52s ✓ D Sequence Sorting 2000 dp, greedy, two-pointers 4,467 4m 23s ✓ E Paint the Tree 2100...

CF 1223G - Wooden Raft

CF 1223G - Wooden Raft Rating: 3200 Tags: binary search, math, number theory Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a collection of logs, each with an integer length. From these logs we are allowed to cut pieces, but we are not allowed to glue pieces together. The goal is to assemble a rectangular raft structure that requires two kinds of side lengths, call them...

CF 1223A - CME

CF 1223A - CME Rating: 800 Tags: math Solve time: 5m 7s Verified: yes Solution Problem Understanding We are given a number of matches and we want to arrange them into a valid arithmetic equation of the form “a + b = c”, where each number is strictly positive. Each digit is represented using matchsticks in the usual seven-segment style implied by the classic problem, but the key simplification is...

Codeforces Round 586 (Div. 1 + Div. 2)

Codeforces Round 586 (Div. 1 + Div. 2) Div. 1+2 | 7 problems | 4/7 verified | Difficulty 800-3400 | 26m 51s # Problem Rating Tags Accepted Time ✓ A Cards 800 implementation, sortings, strings 32,791 2m 11s ✓ B Multiplication Table 1300 math, number-theory 12,135 3m 19s ✓ C Substring Game in the Lesson 1300 games, greedy, strings 10,811 1m 34s ✓ D Alex and Julian 1900 bitmasks, math,...

CF 1220D - Alex and Julian

CF 1220D - Alex and Julian Rating: 1900 Tags: bitmasks, math, number theory Solve time: 5m 37s Verified: no Solution Problem Understanding We are given a finite set of positive integers, but the structure we build from it is infinite. Every integer is a vertex, and each number in the set is interpreted as a “distance type”. For every value d in the set, we connect every pair of integers...

COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)

COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) ICPC/IOI | 13 problems | 6/13 verified | Difficulty 800-2900 | 42m 39s # Problem Rating Tags Accepted Time ✓ A Accumulation of Dominoes 800 math 10,130 3m 15s ✓ B Basketball Together 1000 binary-search, greedy, sortings 28,235 1m 59s ✓ C Circular Mirror 2000 binary-search, combinatorics, geometry 1,947 5m 43s D Deducing Sortability 2900 binary-search, bitmasks, math 232...

Educational Codeforces Round 72 (Rated for Div. 2)

Educational Codeforces Round 72 (Rated for Div. 2) Div. 2 | 6 problems | 5/6 verified | Difficulty 1300-2600 | 25m 8s # Problem Rating Tags Accepted Time ✓ A Creating a Character 1300 binary-search, math 15,823 5m 30s ✓ B Zmei Gorynich 1600 greedy, math 11,856 5m 17s ✓ C The Number Of Good Substrings 1700 binary-search, bitmasks, brute-force 7,856 1m 48s ✓ D Coloring Edges 2100 constructive-algorithms, dfs-and-similar,...

CF 1217A - Creating a Character

CF 1217A - Creating a Character Rating: 1300 Tags: binary search, math Solve time: 5m 30s Verified: yes Solution Problem Understanding We are given a character with two base attributes: strength and intelligence. We are also given a pool of extra experience points that must all be distributed. Each point can increase either strength or intelligence by exactly one unit. After distributing all points, we obtain a final pair of...

CF 1217E - Sum Queries?

CF 1217E - Sum Queries? Rating: 2300 Tags: data structures, greedy, implementation, math Solve time: 4m 41s Verified: yes Solution Problem Understanding We are given an array of integers that changes over time, and we are repeatedly asked to inspect a chosen segment of this array. For each query segment, we are not interested in the sum itself, but in selecting a subset of elements whose sum violates a specific...

Codeforces Round 587 (Div. 3)

Codeforces Round 587 (Div. 3) Div. 3 | 7 problems | 5/7 verified | Difficulty 800-2200 | 19m 54s # Problem Rating Tags Accepted Time ✓ A Prefixes 800 strings 19,549 2m 38s B Shooting 900 greedy, implementation, sortings 19,677 2m 12s ✓ C White Sheet 1700 geometry, math 10,357 2m 28s ✓ D Swords 1300 math 12,216 6m 10s E1 Numerical Sequence (easy version) 1900 binary-search, brute-force, math 3,730...

CF 1216D - Swords

CF 1216D - Swords Rating: 1300 Tags: math Solve time: 6m 10s Verified: no Solution Problem Understanding We are given a collection of sword types, each type having some remaining count after a theft. For each type $i$, the value $a_i$ tells us how many swords of that type are still present in the basement. Originally, every type had the same unknown quantity $x$. Then some number of people $y$...

CF 1214E - Petya and Construction Set

CF 1214E - Petya and Construction Set Rating: 2000 Tags: constructive algorithms, graphs, math, sortings, trees Solve time: 2m 50s Verified: no Solution Problem Understanding We are asked to build a graph on $2n$ labeled vertices using exactly $2n-1$ edges. Since a connected graph with $2n$ vertices and $2n-1$ edges is necessarily a tree, the construction is really about designing a tree on these labeled nodes. The vertices come in...

Codeforces Round 582 (Div. 3)

Codeforces Round 582 (Div. 3) Div. 3 | 8 problems | 7/8 verified | Difficulty 900-2100 | 24m 43s # Problem Rating Tags Accepted Time ✓ A Chips Moving 900 math 25,602 1m 54s ✓ B Bad Prices 1100 data-structures, implementation 31,550 1m 20s ✓ C Book Reading 1200 math 19,621 1m 36s ✓ D1 Equalizing by Division (easy version) 1500 brute-force, implementation 12,077 3m 32s ✓ D2 Equalizing by...

CF 1213A - Chips Moving

CF 1213A - Chips Moving Rating: 900 Tags: math Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given several chips placed on integer positions on a line. Our goal is to move all chips so that they end up on a single shared coordinate, using the cheapest possible sequence of moves. Each chip can move in two different ways. A chip can jump by 2 units left...

CF 1211G - King's Path

CF 1211G - King's Path Rating: 2500 Tags: *special, math, trees Solve time: 2m 51s Verified: yes Solution Problem Understanding We are given a tree where each node initially holds a color. There is also a target color for every node. The King performs a single walk on the tree. During this walk, whenever he traverses an edge, the endpoints of that edge swap their current flags. Because vertices can...

CF 1208G - Polygons

CF 1208G - Polygons Rating: 2800 Tags: greedy, math, number theory Solve time: 6m 55s Verified: yes Solution Problem Understanding We are asked to build several regular polygons that all lie on the same circle, and we want to reuse the circle’s boundary points as much as possible. Each polygon is determined only by how many vertices it has. If a polygon has $l$ sides, then it uses $l$ equally...

CF 1207E - XOR Guessing

CF 1207E - XOR Guessing Rating: 1900 Tags: bitmasks, interactive, math Solve time: 3m 8s Verified: no Solution Problem Understanding We are playing an interactive guessing game where a hidden number $x$ is fixed in advance, and it lies in the range from $0$ to $2^{14}-1$. We are allowed to ask up to two questions. Each question consists of a list of 100 distinct numbers within the same range, and...

CF 1201B - Zero Array

CF 1201B - Zero Array Rating: 1500 Tags: greedy, math Solve time: 5m 5s Verified: yes Solution Problem Understanding We are given a list of numbers, and we repeatedly perform an operation that picks two different positions and reduces both values by one. The goal is to decide whether we can eventually bring every value down exactly to zero using some sequence of such operations. Each operation consumes exactly one...

Educational Codeforces Round 66 (Rated for Div. 2)

Educational Codeforces Round 66 (Rated for Div. 2) Div. 2 | 7 problems | 6/7 verified | Difficulty 900-3000 | 19m 39s # Problem Rating Tags Accepted Time ✓ A From Hero to Zero 900 implementation, math 19,761 3m 42s ✓ B Catch Overflow! 1600 data-structures, expression-parsing, implementation 12,430 1m 24s ✓ C Electrification 1600 binary-search, brute-force, greedy 7,259 1m 28s ✓ D Array Splitting 1900 greedy, sortings 7,063 3m...

CF 1175F - The Number of Subpermutations

CF 1175F - The Number of Subpermutations Rating: 2500 Tags: brute force, data structures, divide and conquer, hashing, math Solve time: 6m 21s Verified: no Solution Problem Understanding We are given a sequence of integers, and we want to count how many contiguous segments behave like a perfect permutation of consecutive integers starting from 1. A segment is valid if, after taking all values inside it, every number from 1...

CF 1175A - From Hero to Zero

CF 1175A - From Hero to Zero Rating: 900 Tags: implementation, math Solve time: 3m 42s Verified: yes Solution Problem Understanding We are given a number $n$ and a parameter $k$. Starting from $n$, we want to reach zero using two allowed operations: subtract one, or if the current value is divisible by $k$, replace it with the quotient after dividing by $k$. Each operation costs one step, and the...

Codeforces Round 533 (Div. 2)

Codeforces Round 533 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 1100-2200 | 18m 57s # Problem Rating Tags Accepted Time ✓ A Salem and Sticks 1100 brute-force, implementation 11,550 3m 55s ✓ B Zuhair and Strings 1100 brute-force, implementation, strings 10,555 7m 18s ✓ C Ayoub and Lost Array 1500 combinatorics, dp, math 11,365 1m 25s ✓ D Kilani and the Game 1900 dfs-and-similar, graphs,...

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1200 | 3m 21s # Problem Rating Tags Accepted Time ✓ A The King's Race 800 implementation, math 9,130 2m 24s ✓ B Taxi drivers and Lyft 1200 implementation, sortings 4,527 57s ✓

CF 1163E - Magical Permutation

CF 1163E - Magical Permutation Rating: 2400 Tags: bitmasks, brute force, constructive algorithms, data structures, graphs, math Solve time: 4m 34s Verified: yes Solution Problem Understanding We are given a set of integers that represent allowed XOR “moves”. We are asked to build a permutation of all integers from 0 up to some power of two minus one, such that every adjacent pair in the permutation differs by a value...

CF 1103C - Johnny Solving

CF 1103C - Johnny Solving Rating: 2700 Tags: constructive algorithms, dfs and similar, graphs, math Solve time: 4m 21s Verified: yes Solution Problem Understanding We are given a connected undirected simple graph where every vertex has degree at least three. Along with the graph, we are also given an integer $k$. The task is not to compute a single structure, but to decide between two fundamentally different constructions. One option...

Codeforces Round 530 (Div. 2)

Codeforces Round 530 (Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 800-2400 | 24m 24s # Problem Rating Tags Accepted Time ✓ A Snowball 800 implementation 13,348 6m 22s ✓ B Squares and Segments 1100 binary-search, constructive-algorithms, math 11,476 1m 10s ✓ C Postcard 1200 constructive-algorithms, implementation 10,420 10m 9s F Cookies 2400 binary-search, data-structures, dfs-and-similar 1,036 6m 43s

Codeforces Round 530 (Div. 1)

Codeforces Round 530 (Div. 1) Div. 1 | 6 problems | 3/6 verified | Difficulty 1600-3500 | 37m 57s # Problem Rating Tags Accepted Time ✓ A Sum in the tree 1600 constructive-algorithms, dfs-and-similar, greedy 9,547 9m 13s B Nice table 2100 brute-force, constructive-algorithms, greedy 1,797 5m 15s ✓ C Construct a tree 2400 binary-search, constructive-algorithms, dfs-and-similar 1,161 5m 19s ✓ D Eels 2800 data-structures 882 4m 20s ✓ E...

CF 1098E - Fedya the Potter

CF 1098E - Fedya the Potter Rating: 3400 Tags: binary search, implementation, math, number theory Solve time: 5m 43s Verified: no Solution Problem Understanding We are given an array and asked to repeatedly build new structures on top of derived information from its subarrays. The first transformation takes every contiguous segment and replaces it with the greatest integer that divides all elements inside that segment. This produces a multiset of...

CF 1098B - Nice table

CF 1098B - Nice table Rating: 2100 Tags: brute force, constructive algorithms, greedy, math Solve time: 5m 15s Verified: yes Solution Problem Understanding We are given a grid of size $n \times m$, where each cell contains one of four characters: A, G, C, or T. We need to construct a new grid of the same dimensions that satisfies a strict local rule: every 2 by 2 subgrid must contain...

Educational Codeforces Round 57 (Rated for Div. 2)

Educational Codeforces Round 57 (Rated for Div. 2) Div. 2 | 7 problems | 4/7 verified | Difficulty 800-2500 | 44m 37s # Problem Rating Tags Accepted Time ✓ A Find Divisible 800 greedy, implementation, math 19,630 4m 16s B Substring Removal 1300 combinatorics, math, strings 11,680 3m 50s C Polygon for the Angle 1600 brute-force, geometry 7,239 5m 30s ✓ D Easy Problem 1800 dp 9,397 6m 4s ✓...

CF 1096A - Find Divisible

CF 1096A - Find Divisible Rating: 800 Tags: greedy, implementation, math Solve time: 4m 16s Verified: no Solution Problem Understanding We are given multiple independent queries, each describing a numeric interval from $l$ to $r$. For each interval, we must pick two different integers inside it such that one of them is a divisor of the other. The output for each query is just one valid pair; if several exist,...

CF 1096F - Inversion Expectation

CF 1096F - Inversion Expectation Rating: 2300 Tags: dp, math, probabilities Solve time: 4m 15s Verified: no Solution Problem Understanding We are given a sequence of length $n$ that is supposed to be a permutation, except some positions are unknown and marked with $-1$. The missing values are precisely the numbers that do not appear among the fixed entries, and every completion of the array that forms a valid permutation...

CF 1096B - Substring Removal

CF 1096B - Substring Removal Rating: 1300 Tags: combinatorics, math, strings Solve time: 3m 50s Verified: no Solution Problem Understanding We are given a string made of lowercase letters, and we are allowed to remove one contiguous segment from it. After removing that segment, the remaining characters must all be identical, meaning either nothing remains or every remaining character is the same letter. The operation is flexible because the removed...

Educational Codeforces Round 56 (Rated for Div. 2)

Educational Codeforces Round 56 (Rated for Div. 2) Div. 2 | 7 problems | 4/7 verified | Difficulty 800-2400 | 38m 7s # Problem Rating Tags Accepted Time ✓ A Dice Rolling 800 math 18,356 6m 28s B Letters Rearranging 900 constructive-algorithms, greedy, sortings 17,700 6m 33s C Mishka and the Last Exam 1300 greedy 9,719 9m 12s D Beautiful Graph 1700 dfs-and-similar, graphs 11,323 3m 33s ✓ E Intersection...

CF 1093A - Dice Rolling

CF 1093A - Dice Rolling Rating: 800 Tags: math Solve time: 6m 28s Verified: no Solution Problem Understanding We are given a standard six-faced dice, but instead of the usual values 1 to 6, its faces contain the integers 2, 3, 4, 5, 6, and 7, all distinct. Each roll produces one of these numbers, and the score for a sequence of rolls is the sum of the visible faces....

Technocup 2019 - Elimination Round 4

Technocup 2019 - Elimination Round 4 Special | 7 problems | 5/7 verified | Difficulty 800-2900 | 23m 43s # Problem Rating Tags Accepted Time ✓ A Right-Left Cipher 800 implementation, strings 12,697 3m 55s ✓ B Div Times Mod 1100 math 10,086 1m 45s ✓ C Connect Three 1600 implementation, math 5,643 2m 25s ✓ D Minimum Diameter Tree 1700 constructive-algorithms, implementation, trees 5,907 2m 20s E Vasya and...

Educational Codeforces Round 54 (Rated for Div. 2)

Educational Codeforces Round 54 (Rated for Div. 2) Div. 2 | 7 problems | 6/7 verified | Difficulty 1200-3000 | 50m 17s # Problem Rating Tags Accepted Time ✓ A Minimizing the String 1200 greedy, strings 14,100 1m 28s ✓ B Divisor Subtraction 1200 implementation, math, number-theory 14,583 1m 51s ✓ C Meme Problem 1300 binary-search, math 13,422 12m 41s ✓ D Edge Deletion 1800 graphs, greedy, shortest-paths 5,913 11m...

CF 1076C - Meme Problem

CF 1076C - Meme Problem Rating: 1300 Tags: binary search, math Solve time: 12m 41s Verified: yes Solution Problem Understanding We are given a number $d$, and we want to decide whether we can split it into two non-negative real numbers $a$ and $b$ such that two conditions hold at the same time: their sum equals $d$, and their product also equals $d$. So geometrically, we are looking for two...

Educational Codeforces Round 53 (Rated for Div. 2)

Educational Codeforces Round 53 (Rated for Div. 2) Div. 2 | 7 problems | 6/7 verified | Difficulty 1000-2600 | 32m 32s # Problem Rating Tags Accepted Time ✓ A Diverse Substring 1000 implementation, strings 17,051 4m 49s ✓ B Vasya and Books 1000 implementation, math 11,219 4m 39s ✓ C Vasya and Robot 1800 binary-search, two-pointers 5,435 4m 25s ✓ D Berland Fair 1700 binary-search, brute-force, data-structures 6,722 4m...

CF 1073B - Vasya and Books

CF 1073B - Vasya and Books Rating: 1000 Tags: implementation, math Solve time: 4m 39s Verified: yes Solution Problem Understanding We are given a stack of books where each book has a unique label. The stack order matters: the first array describes which book is at the top, and the last element is at the bottom. We also receive a second sequence that describes a fixed order in which Vasya...

Codeforces Round 518 (Div. 2) [Thanks, Mail.Ru!]

Codeforces Round 518 (Div. 2) [Thanks, Mail.Ru!] Div. 2 | 3 problems | 2/3 verified | Difficulty 1200-1700 | 17m 32s # Problem Rating Tags Accepted Time ✓ A Birthday 1400 math 7,261 4m 29s ✓ B LCM 1200 math, number-theory 13,026 5m 21s ✓ C Colored Rooks 1700 constructive-algorithms, graphs 3,348 7m 42s

CF 1068A - Birthday

CF 1068A - Birthday Rating: 1400 Tags: math Solve time: 4m 29s Verified: yes Solution Problem Understanding We are dealing with a fixed universe of distinct coin types, where there are N possible different coins in total. Ivan already owns K distinct coins from this universe. Now M friends will each give him gifts, and each friend must contribute the same number of coins. All gifted coins must be distinct...

CF 1067E - Random Forest Rank

CF 1067E - Random Forest Rank Rating: 2800 Tags: dp, graph matchings, math, trees Solve time: 9m Verified: no Solution Problem Understanding We are given a tree with $n$ vertices. Each edge is independently kept with probability $1/2$, so after the process we obtain a random forest. For every such resulting forest, we can build its adjacency matrix over real numbers and take its linear algebraic rank. The task is...

CF 1067D - Computer Game

CF 1067D - Computer Game Rating: 3100 Tags: dp, greedy, math, probabilities Solve time: 5m 2s Verified: no Solution Problem Understanding We are given a collection of quests, each with two reward values and a success probability. Every second, Ivan chooses one quest and attempts it. If the attempt succeeds, he receives the base reward for that quest and also gains the ability to upgrade any single quest once, which...

Codeforces Round 515 (Div. 3)

Codeforces Round 515 (Div. 3) Div. 3 | 6 problems | 6/6 verified | Difficulty 1100-2100 | 24m 11s # Problem Rating Tags Accepted Time ✓ A Vova and Train 1100 math 15,427 6m 16s ✓ B Heaters 1500 greedy, two-pointers 9,379 4m 14s ✓ C Books Queries 1400 implementation 10,358 2m 55s ✓ D Boxes Packing 1800 binary-search, implementation 5,945 2m 51s ✓ E Binary Numbers AND Sum 1700...

CF 1066E - Binary Numbers AND Sum

CF 1066E - Binary Numbers AND Sum Rating: 1700 Tags: data structures, implementation, math Solve time: 3m 13s Verified: yes Solution Problem Understanding We are given two very large binary numbers, not as integers but as strings. The first number is fixed throughout the process, while the second number keeps shrinking. The process is mechanical: start with the full value of b . At each step, compute the bitwise AND...

Mail.Ru Cup 2018 Round 3

Mail.Ru Cup 2018 Round 3 Special | 8 problems | 7/8 verified | Difficulty 800-3200 | 29m 37s # Problem Rating Tags Accepted Time ✓ A Determine Line 800 implementation 7,307 3m 25s ✓ B Divide Candies 1600 math, number-theory 4,546 6m 37s ✓ C Pick Heroes 1700 greedy, implementation, interactive 2,579 5m D Decorate Apple Tree 1600 constructive-algorithms, dfs-and-similar, dp 6,719 2m 24s ✓ E Check Transcription 2100 brute-force,...

Mail.Ru Cup 2018 Round 2

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

CF 1055C - Lucky Days

CF 1055C - Lucky Days Rating: 1900 Tags: math, number theory Solve time: 2m 17s Verified: yes Solution Problem Understanding Two people have periodic patterns of “good intervals” on the number line of days. Each pattern consists of a fixed segment of consecutive days inside a repeating cycle. For Alice, within every block of length t_a , the days from l_a to r_a (inclusive) are good, and everything outside that...

CF 914G - Sum the Fibonacci

CF 914G - Sum the Fibonacci Rating: 2600 Tags: bitmasks, divide and conquer, dp, fft, math Solve time: 5m 10s Verified: no Solution Problem Understanding We are given a sequence of integers, each of which can be thought of as a 17-bit mask. From this array we must form ordered selections of five positions. Each selection contributes a value computed from bitwise combinations of the chosen elements, followed by evaluating...

CF 912E - Prime Gift

CF 912E - Prime Gift Rating: 2400 Tags: binary search, dfs and similar, math, meet-in-the-middle, number theory, two pointers Solve time: 7m 30s Verified: yes Solution Problem Understanding We are asked to enumerate a very specific set of integers and then pick a particular element from that ordered list. The allowed numbers are those whose prime factors all come from a fixed small set of given primes. In other words,...

CF 909B - Segments

CF 909B - Segments Rating: 1300 Tags: constructive algorithms, math Solve time: 7m 55s Verified: yes Solution Problem Understanding We are given an integer $N$. From the points $0, 1, 2, \dots, N$ on a number line, consider every possible segment whose endpoints are chosen among these points. That means every pair $(l, r)$ with $0 \le l < r \le N$ defines a segment. We want to place all...

CF 901E - Cyclic Cipher

CF 901E - Cyclic Cipher Rating: 3300 Tags: fft, math Solve time: 2m 20s Verified: yes Solution Problem Understanding We are given two integer sequences of length $n$. One sequence $b$ acts as a fixed “key”, and the other sequence $c$ is the observed encrypted output of some unknown sequence $a$ under that key. The encryption rule does not directly reveal $a$; instead, it computes, for every cyclic shift of...

Codeforces Round 453 (Div. 1)

Codeforces Round 453 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1500-3300 | 12m 51s # Problem Rating Tags Accepted Time ✓ A Hashing Trees 1500 constructive-algorithms, trees 5,377 2m 56s B GCD of Polynomials 2200 constructive-algorithms, math 1,640 2m 34s ✓ C Bipartite Segments 2300 binary-search, data-structures, dfs-and-similar 1,298 2m 44s ✓ D Weighting a Tree 2700 constructive-algorithms, dfs-and-similar, graphs 630 2m 17s E Cyclic...

CF 901B - GCD of Polynomials

CF 901B - GCD of Polynomials Rating: 2200 Tags: constructive algorithms, math Solve time: 2m 34s Verified: yes Solution Problem Understanding We are asked to construct two integer polynomials, each of degree at most $n$, with very small coefficients (each coefficient is either -1, 0, or 1), and both leading coefficients equal to 1. On these two polynomials, we run the standard Euclidean algorithm for polynomials, where each step replaces...

CF 1047B - Cover Points

CF 1047B - Cover Points Rating: 900 Tags: geometry, math Solve time: 6m 39s Verified: no Solution Problem Understanding We are given a set of points on a plane. We must place a very specific triangle shape so that every point lies either inside it or on its boundary. The triangle is not arbitrary, it is constrained to be isosceles and aligned with the coordinate axes in the sense that...

Codeforces Round 511 (Div. 2)

Codeforces Round 511 (Div. 2) Div. 2 | 2 problems | 1/2 verified | Difficulty 800-900 | 11m 16s # Problem Rating Tags Accepted Time ✓ A Little C Loves 3 I 800 math 21,282 4m 37s ✓ B Cover Points 900 geometry, math 18,775 6m 39s

CF 1047A - Little C Loves 3 I

CF 1047A - Little C Loves 3 I Rating: 800 Tags: math Solve time: 4m 37s Verified: yes Solution Problem Understanding We are given a single integer $n$, and we need to represent it as a sum of three positive integers $a, b, c$. The extra restriction is that none of these three numbers is allowed to be divisible by 3. Any valid triple is acceptable, so there is no...

Educational Codeforces Round 51 (Rated for Div. 2)

Educational Codeforces Round 51 (Rated for Div. 2) Div. 2 | 7 problems | 2/7 verified | Difficulty 1000-2900 | 45m 6s # Problem Rating Tags Accepted Time ✓ A Vasya And Password 1200 greedy, implementation, strings 8,886 5m 3s B Relatively Prime Pairs 1000 greedy, math, number-theory 18,808 6m 39s C Vasya and Multisets 1500 brute-force, dp, greedy 9,875 13m 40s D Bicolorings 1700 bitmasks, dp 8,158 8m 54s...

CF 1051C - Vasya and Multisets

CF 1051C - Vasya and Multisets Rating: 1500 Tags: brute force, dp, greedy, implementation, math Solve time: 13m 40s Verified: no Solution Problem Understanding We are given a sequence of numbers, but it behaves like a multiset, meaning duplicates matter and order only matters for output assignment. Each occurrence of a value must be assigned to one of two groups, A or B. A value is considered “nice” inside a...

CF 1051B - Relatively Prime Pairs

CF 1051B - Relatively Prime Pairs Rating: 1000 Tags: greedy, math, number theory Solve time: 6m 39s Verified: no Solution Problem Understanding We are given a contiguous segment of integers from $l$ to $r$, and the task is to partition all these numbers into pairs. Every number must appear in exactly one pair, so the segment is fully covered. For each pair $(a, b)$, the requirement is that $\gcd(a, b)...

Mail.Ru Cup 2018 Round 1

Mail.Ru Cup 2018 Round 1 Special | 8 problems | 3/8 verified | Difficulty 800-3500 | 37m 21s # Problem Rating Tags Accepted Time ✓ A Elevator or Stairs? 800 implementation 9,591 2m 27s ✓ B Appending Mex 1000 implementation 7,068 2m 32s ✓ C Candies Distribution 1500 constructive-algorithms, implementation 4,483 9m 3s D Changing Array 1900 greedy, implementation 2,415 3m 46s ✓ E Chips Puzzle 2400 constructive-algorithms, implementation, math...

CF 1054H - Epic Convolution

CF 1054H - Epic Convolution Rating: 3500 Tags: chinese remainder theorem, fft, math, number theory Solve time: 7m 10s Verified: no Solution Problem Understanding We are given two sequences, one indexed by $i$ and one indexed by $j$, and we are asked to combine every pair $(i, j)$ into a single weighted contribution. The weight is not linear or even separable in the usual sense: each pair contributes $$a_i \cdot...

CF 1054G - New Road Network

CF 1054G - New Road Network Rating: 3300 Tags: constructive algorithms, greedy, math Solve time: 3m 39s Verified: no Solution Problem Understanding We are asked to construct a tree on $n$ labeled vertices, representing citizens, using exactly $n-1$ edges so that the graph is connected and acyclic. On top of that, we are given $m$ subsets of vertices, each subset representing a secret community, and each such subset must induce...

CF 1054E - Chips Puzzle

CF 1054E - Chips Puzzle Rating: 2400 Tags: constructive algorithms, implementation, math Solve time: 4m 54s Verified: no Solution Problem Understanding We are given a grid where each cell contains a short string made of characters 0 and 1 . Think of each cell as a small stack of chips written in a row, where we can see the order of chips from left to right. We are given two...

CF 1056F - Write The Contest

CF 1056F - Write The Contest Rating: 2500 Tags: binary search, dp, math Solve time: 4m 4s Verified: yes Solution Problem Understanding The problem describes a scheduling process where each task depends heavily on a continuously changing “skill level”. You are given several problems, each with a difficulty value and a reward. To solve a problem, Polycarp must first spend a fixed preparation phase (watching an episode), which always takes...

CF 1056B - Divide Candies

CF 1056B - Divide Candies Rating: 1600 Tags: math, number theory Solve time: 6m 37s Verified: yes Solution Problem Understanding Each cell in an $n \times n$ grid defines a number of candies equal to $i^2 + j^2$, where $i$ and $j$ are the row and column indices. For every cell, we imagine taking that many identical candies and trying to split them evenly among $m$ friends. A cell is...

Codeforces Round 514 (Div. 2)

Codeforces Round 514 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 1000-2400 | 20m 28s # Problem Rating Tags Accepted Time ✓ A Cashier 1000 implementation 13,810 1m 25s ✓ B Forgery 1300 implementation 7,585 3m 39s ✓ C Sequence Transformation 1600 constructive-algorithms, math 7,533 5m 19s D Nature Reserve 2200 binary-search, geometry, ternary-search 2,997 4m 38s ✓ E Split the Tree 2400 binary-search, data-structures, dp...

CF 1059C - Sequence Transformation

CF 1059C - Sequence Transformation Rating: 1600 Tags: constructive algorithms, math Solve time: 5m 19s Verified: no Solution Problem Understanding We start with a fixed sequence containing the integers from 1 up to n. We repeatedly perform an operation where we look at all remaining elements, compute their greatest common divisor, record that value, and then delete exactly one element of our choice. This continues until no elements remain, so...

Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)

Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) Div. 1+2 | 8 problems | 4/8 verified | Difficulty 800-3400 | 54m 21s # Problem Rating Tags Accepted Time ✓ A Phone Numbers 800 brute-force 15,712 4m 44s ✓ B Maximum Sum of Digits 1100 greedy 9,496 10m 49s ✓ C Maximum Subrectangle 1600 binary-search, implementation, two-pointers 5,209 4m 48s ✓ D Social Circles 1900 greedy, math...

CF 1060D - Social Circles

CF 1060D - Social Circles Rating: 1900 Tags: greedy, math Solve time: 6m 2s Verified: no Solution Problem Understanding We are given several guests, and each guest has a personal requirement about how they sit in a circular arrangement. If a guest is placed in a circle, then looking around the circle there are two directions, and the guest needs enough empty chairs on both sides: at least $l_i$ empty...

Codeforces Round 523 (Div. 2)

Codeforces Round 523 (Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 800-2600 | 30m 19s # Problem Rating Tags Accepted Time ✓ A Coins 800 greedy, implementation, math 24,100 1m 58s ✓ B Views Matter 1400 greedy, implementation, sortings 7,642 5m 49s ✓ C Multiplicity 1700 data-structures, dp, implementation 10,709 3m 7s D TV Shows 2000 data-structures, greedy, implementation 2,560 3m 52s E Politics 2600 flows,...

CF 1061C - Multiplicity

CF 1061C - Multiplicity Rating: 1700 Tags: data structures, dp, implementation, math, number theory Solve time: 3m 7s Verified: no Solution Problem Understanding We are asked to count how many subsequences of a given array are “valid” under a position-based divisibility rule. A subsequence here is defined by choosing any subset of indices while preserving order, and different subsequences are distinguished by which indices are chosen, even if values repeat....

CF 1061A - Coins

CF 1061A - Coins Rating: 800 Tags: greedy, implementation, math Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a collection of coin denominations that includes every integer value from 1 up to n, and we are allowed to use any number of coins of any of these values. The task is to represent a target sum S using as few coins as possible, where repetition of...

Codeforces Round 520 (Div. 2)

Codeforces Round 520 (Div. 2) Div. 2 | 6 problems | 4/6 verified | Difficulty 1300-2900 | 22m 46s # Problem Rating Tags Accepted Time ✓ A A Prank 1300 greedy, implementation 9,306 2m 47s ✓ B Math 1500 greedy, math, number-theory 9,890 7m 36s ✓ C Banh-mi 1600 greedy, implementation, math 5,950 3m 30s D Fun with Integers 1800 dfs-and-similar, graphs, implementation 4,170 2m 39s ✓ E Company 2300...

CF 1062B - Math

CF 1062B - Math Rating: 1500 Tags: greedy, math, number theory Solve time: 7m 36s Verified: yes Solution Problem Understanding We are given a single integer as a starting point, and we are allowed to transform it using two operations. One operation multiplies the current number by any positive integer we choose, effectively letting us inflate the number arbitrarily. The other operation replaces the number with its integer square root,...

CF 1062D - Fun with Integers

CF 1062D - Fun with Integers Rating: 1800 Tags: dfs and similar, graphs, implementation, math Solve time: 2m 39s Verified: yes Solution Problem Understanding We are given a set of integers from the range of absolute values 2 up to n, and each number also has its negative counterpart available. Think of every integer i in this range as a node in a graph, including both i and -i. A...

CF 1062C - Banh-mi

CF 1062C - Banh-mi Rating: 1600 Tags: greedy, implementation, math Solve time: 3m 30s Verified: no Solution Problem Understanding We are given a binary array where each position has a value of either zero or one. We repeatedly remove elements from a chosen segment, and every time we remove an element, two things happen: we gain its value immediately, and all remaining elements in that segment get increased by that...

CF 1063D - Candies for Children

CF 1063D - Candies for Children Rating: 2600 Tags: brute force, math Solve time: 5m 59s Verified: no Solution Problem Understanding We are simulating a deterministic passing process on a circular arrangement of $n$ children. A box starts at position $l$ and is passed clockwise. Each time a child receives the box, they remove candies according to a fixed personal rule: some children are “sweet tooth” types who always take...

CF 1063E - Lasers and Mirrors

CF 1063E - Lasers and Mirrors Rating: 3000 Tags: constructive algorithms, math Solve time: 5m 33s Verified: no Solution Problem Understanding The maze is an $n \times n$ grid where each cell can either be empty or contain a fixed type of mirror that behaves like a 45-degree reflector. A laser starts from each column on the southern boundary and travels northward into the grid. When it hits a mirror,...

Codeforces Round 516 (Div. 2, by Moscow Team Olympiad)

Codeforces Round 516 (Div. 2, by Moscow Team Olympiad) Div. 2 | 2 problems | 1/2 verified | Difficulty 800-1200 | 6m 25s # Problem Rating Tags Accepted Time ✓ A Make a triangle! 800 brute-force, geometry, math 25,148 3m 20s B Equations of Mathematical Magic 1200 math 7,936 3m 5s ✓

CF 1064A - Make a triangle!

CF 1064A - Make a triangle! Rating: 800 Tags: brute force, geometry, math Solve time: 3m 20s Verified: no Solution Problem Understanding We are given three positive integers representing the current lengths of three sticks. In one move, we are allowed to pick exactly one stick and increase its length by one unit. The goal is to reach a situation where these three lengths can form a non-degenerate triangle, meaning...

CF 1064B - Equations of Mathematical Magic

CF 1064B - Equations of Mathematical Magic Rating: 1200 Tags: math Solve time: 3m 5s Verified: yes Solution Problem Understanding The equation links a number a with a variable x using two operations: subtraction and bitwise XOR. For each given value of a , we are asked to count how many non-negative integers x satisfy the identity a - (a XOR x) - x = 0 . The input consists...

Educational Codeforces Round 52 (Rated for Div. 2)

Educational Codeforces Round 52 (Rated for Div. 2) Div. 2 | 7 problems | 3/7 verified | Difficulty 800-2700 | 26m 32s # Problem Rating Tags Accepted Time ✓ A Vasya and Chocolate 800 implementation, math 15,264 3m 48s ✓ B Vasya and Isolated Vertices 1300 constructive-algorithms, graphs 11,597 5m 51s C Make It Equal 1600 greedy 8,290 2m 44s ✓ D Three Pieces 2200 dfs-and-similar, dp, shortest-paths 1,445 3m...

CF 1065A - Vasya and Chocolate

CF 1065A - Vasya and Chocolate Rating: 800 Tags: implementation, math Solve time: 3m 48s Verified: yes Solution Problem Understanding Vasya has a fixed amount of money and wants to maximize how many chocolate bars he ends up with under a repeating promotion. Every bar has a fixed price, so his initial purchasing power is simply how many bars he can buy directly. The twist is that the shop gives...

CF 1066A - Vova and Train

CF 1066A - Vova and Train Rating: 1100 Tags: math Solve time: 6m 16s Verified: yes Solution Problem Understanding The setting is a one-dimensional path from position 1 to position L, where time and position are synchronized so that at minute i, Vova is at coordinate i. Along this path there are regularly spaced light sources placed every v units, so only positions divisible by v contain lanterns. At the...

CF 1068B - LCM

CF 1068B - LCM Rating: 1200 Tags: math, number theory Solve time: 5m 21s Verified: yes Solution Problem Understanding We are given a single integer $b$, and we conceptually iterate over every positive integer $a$. For each $a$, we compute a value derived from the least common multiple of $a$ and $b$, specifically $\frac{\mathrm{lcm}(a,b)}{a}$. Ivan writes this value on a board, and we are asked how many distinct values appear...

CF 1073E - Segment Sum

CF 1073E - Segment Sum Rating: 2300 Tags: bitmasks, combinatorics, dp, math Solve time: 3m 54s Verified: yes Solution Problem Understanding We are asked to consider every integer inside a range $[l, r]$ and filter it by a digit constraint: we only keep numbers that use at most $k$ distinct decimal digits in their usual base-10 representation. Among all such valid numbers, we must compute their total sum modulo $998244353$....

CF 1075A - The King's Race

CF 1075A - The King's Race Rating: 800 Tags: implementation, math Solve time: 2m 24s Verified: yes Solution Problem Understanding We are given an $n \times n$ grid. One king starts at the bottom-left corner $(1,1)$ and the other starts at the top-right corner $(n,n)$. A coin is placed at $(x,y)$, and both kings try to reach it as fast as possible. They move like a chess king, so in...

CF 1076B - Divisor Subtraction

CF 1076B - Divisor Subtraction Rating: 1200 Tags: implementation, math, number theory Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given a single large integer and we repeatedly apply a deterministic process that always reduces it. At each step, we inspect the current number, find its smallest prime factor, subtract that factor from the number, and continue until the value becomes zero. The task is to determine...

Codeforces Round 521 (Div. 3)

Codeforces Round 521 (Div. 3) Div. 3 | 7 problems | 6/7 verified | Difficulty 800-2100 | 20m 23s # Problem Rating Tags Accepted Time ✓ A Frog Jumping 800 math 32,248 1m 58s ✓ B Disturbed People 1000 greedy 20,435 1m 58s ✓ C Good Array 1300 25,584 4m 23s D Cutting Out 1600 binary-search, sortings 10,474 2m 20s ✓ E Thematic Contests 1800 greedy, sortings 5,092 2m 57s...

CF 1077A - Frog Jumping

CF 1077A - Frog Jumping Rating: 800 Tags: math Solve time: 1m 58s Verified: yes Solution Problem Understanding A frog moves along a number line starting from position zero. Its movement is strictly alternating: it first jumps to the right by a fixed distance a , then to the left by b , then right again by a , and so on. Each query describes one such frog independently, and...

Codeforces Round 524 (Div. 2)

Codeforces Round 524 (Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 800-2400 | 26m 36s # Problem Rating Tags Accepted Time ✓ A Petya and Origami 800 math 19,175 5m 14s ✓ B Margarite and the best present 900 math 12,636 2m 38s ✓ C Masha and two friends 1500 implementation 4,218 3m 5s ✓ D Olya and magical square 2000 constructive-algorithms, implementation, math 1,666 7m...

CF 1080D - Olya and magical square

CF 1080D - Olya and magical square Rating: 2000 Tags: constructive algorithms, implementation, math Solve time: 7m 33s Verified: no Solution Problem Understanding We start with a square grid whose side length is a power of two, specifically $2^n \times 2^n$. The only allowed operation is to take any existing square of side $a$ and split it into four equal smaller squares of side $a/2$. This process can be repeated,...

CF 1080A - Petya and Origami

CF 1080A - Petya and Origami Rating: 800 Tags: math Solve time: 5m 14s Verified: yes Solution Problem Understanding Petya is preparing invitation cards for a party, and each invitation consumes a fixed amount of colored paper sheets. Every invitation requires 2 red sheets, 5 green sheets, and 8 blue sheets. If there are $n$ friends, then $n$ invitations must be produced, so the total demand scales linearly with $n$:...

CF 1080B - Margarite and the best present

CF 1080B - Margarite and the best present Rating: 900 Tags: math Solve time: 2m 38s Verified: yes Solution Problem Understanding We are given a very large infinite sequence where each position has a deterministic value based only on its index. The value alternates sign and grows in magnitude linearly: position 1 contributes −1, position 2 contributes +2, position 3 contributes −3, and so on. In general, the element at...

Avito Cool Challenge 2018

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

CF 1081E - Missing Numbers

CF 1081E - Missing Numbers Rating: 1900 Tags: binary search, constructive algorithms, greedy, math, number theory Solve time: 3m 44s Verified: no Solution Problem Understanding We are given only half of a hidden sequence of positive integers, specifically every even-positioned value. The full sequence has even length $n$, and has a very rigid structure: if you look at prefix sums, every prefix sum must be a perfect square. Formally, if...