#binary-search
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 1558E - Down Below
CF 1558E - Down Below Rating: 3000 Tags: binary search, dfs and similar, graphs, greedy, meet-in-the-middle, shortest paths Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a graph of caves connected by tunnels, and a hero who starts at cave 1 with some initial power. Every other cave initially contains a monster. The hero’s task is to visit and defeat the monster in every cave at...
CF 1250I - Show Must Go On
CF 1250I - Show Must Go On Rating: 3100 Tags: binary search, brute force, greedy, shortest paths Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a list of dancers, each with a fixed awkwardness value. A “concert” is defined as choosing a subset of these dancers. Not all subsets are allowed: the total awkwardness of a chosen subset must not exceed a limit $k$. Among all...
CF 983E - NN country
CF 983E - NN country Rating: 2800 Tags: binary search, data structures, trees Solve time: 1m 49s Verified: no Solution Problem Understanding The road network forms a tree of cities, so between any two cities there is exactly one simple path. On top of this fixed tree structure, there are additional “bus routes” between pairs of cities. A bus route between two endpoints does not behave like a single edge:...
CF 1039B - Subway Pursuit
CF 1039B - Subway Pursuit Rating: 2100 Tags: binary search, interactive, probabilities Solve time: 11m 23s Verified: no Solution Problem Understanding We are dealing with a single moving target on a very large numbered line of stations from 1 to n. At any moment there is exactly one station where the train is located, but after every query the train is allowed to move up to k stations left or...
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 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 1386A - Colors
CF 1386A - Colors Rating: 2700 Tags: *special, binary search, constructive algorithms, interactive Solve time: 7m 19s Verified: no Solution Problem Understanding We are interacting with a hidden system that has chosen an integer threshold $C$ between 1 and $N$. We can think of the numbers from 1 to $N$ as positions on a line, and every time we pick a position, we are effectively “dyeing” hair with that color....
CF 1315B - Homecoming
CF 1315B - Homecoming Rating: 1300 Tags: binary search, dp, greedy, strings Solve time: 2m 35s Verified: no Solution Problem Understanding We are given a one-dimensional town represented as a line of crossroads indexed from 1 to n. Each position has exactly one type of transport station: either type A (bus-compatible segment marker) or type B (tram-compatible segment marker). The string s encodes this layout. Petya starts at position 1...
CF 1305H - Kuroni the Private Tutor
CF 1305H - Kuroni the Private Tutor Rating: 3500 Tags: binary search, greedy Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given an exam with a fixed number of questions, where each question contributes either 0 or 1 point to each student. Instead of knowing the full student answers, we only know aggregate constraints: for each question, we know how many students solved it lies within a...
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 1208D - Restore Permutation
CF 1208D - Restore Permutation Rating: 1900 Tags: binary search, data structures, greedy, implementation Solve time: 5m 28s Verified: yes Solution Problem Understanding We are given a hidden permutation of numbers from 1 to n. Instead of seeing the permutation directly, we are given a derived value for each position. For position i, the value s[i] is the sum of all elements that appear before i and are smaller than...
CF 1208B - Uniqueness
CF 1208B - Uniqueness Rating: 1500 Tags: binary search, brute force, implementation, two pointers Solve time: 3m 49s Verified: yes Solution Problem Understanding We are given a sequence of numbers and we are allowed to remove one continuous block from it, or remove nothing at all. After this single deletion, the remaining elements must all be different from each other. The task is to choose a subarray to remove so...
CF 1060C - Maximum Subrectangle
CF 1060C - Maximum Subrectangle Rating: 1600 Tags: binary search, implementation, two pointers Solve time: 4m 48s Verified: yes Solution Problem Understanding The matrix in this problem is not given explicitly. Instead, every cell is formed by multiplying an element from array a with an element from array b . This creates a grid where each row is a scaled version of b , and each column is a scaled...
CF 1071E - Rain Protection
CF 1071E - Rain Protection Rating: 3500 Tags: binary search, geometry Solve time: 4m 36s Verified: no Solution Problem Understanding We are controlling a rigid but flexible “bar” formed by a rope whose endpoints are constrained to slide along two horizontal segments, one at height zero and one at height $h$. At any moment, the rope is a straight segment connecting a point on the bottom rail to a point...
CF 1773H - Hot and Cold
CF 1773H - Hot and Cold Rating: 2600 Tags: binary search, interactive Solve time: 2m 18s Verified: no Solution Problem Understanding We are playing a coordinate guessing game on a large integer grid. There is a hidden target point somewhere in the square from $(0,0)$ to $(10^6,10^6)$. We are allowed to “query” any point by printing its coordinates, and after each query the system tells us how our Euclidean distance...
CF 1773B - BinCoin
CF 1773B - BinCoin Rating: 2200 Tags: binary search, divide and conquer, hashing, implementation, probabilities, trees Solve time: 2m 27s Verified: no Solution Problem Understanding We are given a rooted binary tree with $n$ employees. Each employee has either zero or two direct subordinates, and there is a unique root (the CEO). The company runs a procedure that produces a full ordering of all employees, and this procedure is executed...
CF 1726H - Mainak and the Bleeding Polygon
CF 1726H - Mainak and the Bleeding Polygon Rating: 3500 Tags: binary search, geometry, implementation, math Solve time: 7m 13s Verified: no Solution Problem Understanding We are given a convex polygon described by its vertices in counter-clockwise order. The shape is not arbitrary: every corner is either a right angle or slightly wider than a right angle, but never sharp. That geometric restriction has a strong consequence on how “far...
CF 1725D - Deducing Sortability
CF 1725D - Deducing Sortability Rating: 2900 Tags: binary search, bitmasks, math Solve time: 4m 6s Verified: no Solution Problem Understanding We are asked to construct a very large hidden array indexed from 1 to N, where N can be up to one billion, without explicitly building it. This array is special because it is chosen so that it can be transformed, through a particular operation applied independently on elements,...
CF 1578L - Labyrinth
CF 1578L - Labyrinth Rating: 2400 Tags: binary search, dsu, greedy Solve time: 3m 48s Verified: no Solution Problem Understanding The labyrinth can be seen as a connected weighted graph where rooms are nodes and passages are undirected edges with capacities. Each room also has a one-time “growth value” that increases Lucy’s width if she chooses to eat that room’s candy. Lucy starts at room 1 with some initial width,...
CF 1184B1 - The Doctor Meets Vader (Easy)
CF 1184B1 - The Doctor Meets Vader (Easy) Rating: 1400 Tags: binary search, sortings Solve time: 5m 28s Verified: yes Solution Problem Understanding Each spaceship has an attack power. Each empire base has a defense value and a gold amount. A spaceship can destroy every base whose defense is not greater than the spaceship's attack power. Since destroying a base gives all of its gold, the answer for a spaceship...
CF 1250J - The Parade
CF 1250J - The Parade Rating: 1800 Tags: binary search, greedy Solve time: 1m 59s Verified: yes Solution Problem Understanding We are asked to arrange soldiers of various heights into a parade formation with exactly $k$ rows. Each row must have the same number of soldiers, and within a row, no two soldiers can differ in height by more than one. The army provides us with counts of soldiers for...
CF 1403A - The Potion of Great Power
CF 1403A - The Potion of Great Power Rating: 2400 Tags: *special, 2-sat, binary search, data structures, graphs, interactive, sortings, two pointers Solve time: 2m 3s Verified: no Solution Problem Understanding We have a dynamic friendship network among N shamans, each living at a specific altitude H[i] . Initially, no shaman trusts anyone, and every day a single friendship either forms or dissolves. Each shaman can trust at most D...
CF 1442E - Black, White and Grey Tree
CF 1442E - Black, White and Grey Tree Rating: 3000 Tags: binary search, constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a tree in which each node is coloured white, black, or grey. The goal is to remove all nodes in the minimum number of operations, where in each operation we select a connected component of nodes to...
CF 1443C - The Delivery Dilemma
CF 1443C - The Delivery Dilemma Rating: 1400 Tags: binary search, greedy, sortings Solve time: 5m 13s Verified: yes Solution Problem Understanding In this problem, Petya wants to get all his birthday dishes in the minimum amount of time. For each dish, he can either pick it up himself from a restaurant, taking b_i minutes, or order a delivery, which will arrive in a_i minutes. All couriers start delivering at...
CF 1468L - Prime Divisors Selection
CF 1468L - Prime Divisors Selection Rating: 2700 Tags: binary search, greedy, math, number theory Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a set of up to 1000 distinct large integers, and we must pick exactly k of them. After picking, each chosen number must be assigned a prime divisor, one prime per number. The assignment is considered valid if every chosen number is divisible...
CF 1468G - Hobbits
CF 1468G - Hobbits Rating: 2500 Tags: binary search, geometry Solve time: 2m 11s Verified: no Solution Working
CF 1468D - Firecrackers
CF 1468D - Firecrackers Rating: 1700 Tags: binary search, sortings Solve time: 3m 41s Verified: no Solution Problem Understanding A hooligan and a guard stand in a one dimensional corridor. Every second, the hooligan acts first, then already dropped firecrackers may explode, then the guard moves one step toward the hooligan. The hooligan owns several firecrackers. A firecracker with value s explodes exactly s seconds after it is lit. The...
CF 1500E - Subset Trick
CF 1500E - Subset Trick Rating: 3300 Tags: binary search, data structures Solve time: 56s Verified: no Solution Problem Understanding The task revolves around reasoning about subset sums in a set of distinct positive integers. You are given an initial set $S$ and a series of operations that either add or remove elements. For any positive integer $x$, we call it unsuitable if knowing only the size of a chosen...
CF 1500B - Two chandeliers
CF 1500B - Two chandeliers Rating: 2200 Tags: binary search, brute force, chinese remainder theorem, math, number theory Solve time: 1m 3s Verified: no Solution Problem Understanding We have two cyclic sequences of colors. The first chandelier repeats an array a of length n , and the second chandelier repeats an array b of length m . On day d , the first chandelier shows position (d - 1) mod...
CF 1530C - Pursuit
CF 1530C - Pursuit Rating: 1200 Tags: binary search, brute force, greedy, sortings Solve time: 45s Verified: no Solution Problem Understanding We have a contest with multiple stages, each stage giving between 0 and 100 points. You and Ilya have already completed n stages, and we know the scores for both of you. The contest ranks a contestant by taking only the highest k - floor(k / 4) scores out...
CF 1561C - Deep Down Below
CF 1561C - Deep Down Below Rating: 1300 Tags: binary search, greedy, sortings Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a hero facing a sequence of caves. Each cave contains a number of monsters, each with an armor value, and the hero can defeat a monster only if his current power is strictly greater than the monster's armor. After defeating a monster, the hero's power...
CF 1575J - Jeopardy of Dropped Balls
CF 1575J - Jeopardy of Dropped Balls Rating: 1500 Tags: binary search, brute force, dsu, implementation Solve time: 56s Verified: yes Solution Problem Understanding We have an n × m grid. Every cell stores one of three directions. A value of 1 means a ball moves one cell to the right. A value of 2 means the ball moves one cell downward. A value of 3 means the ball moves...
CF 1575B - Building an Amusement Park
CF 1575B - Building an Amusement Park Rating: 2300 Tags: binary search, geometry Solve time: 5m 18s Verified: no Solution Problem Understanding We want to place a circular amusement park so that it touches the origin. If the park has radius $r$, then its center must lie exactly $r$ units from the origin, because the origin lies on the boundary of the park. Each bird habitat is a point in...
CF 1588F - Jumping Through the Array
CF 1588F - Jumping Through the Array Rating: 3500 Tags: binary search, data structures, graphs, two pointers Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given an array of integers a and a permutation p of size n . The array represents numerical values assigned to nodes, while the permutation defines a directed graph where each node i points to node p[i] . Queries come in three...
CF 1609C - Complex Market Analysis
CF 1609C - Complex Market Analysis Rating: 1400 Tags: binary search, dp, implementation, number theory, schedules, two pointers Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given an array of integers and a step size e . For each starting index i , we can form a subsequence by taking every e -th element: a[i], a[i+e], a[i+2e], ... up to the point where the index does not...
CF 1666E - Even Split
CF 1666E - Even Split Rating: 2500 Tags: binary search, constructive algorithms, greedy, math Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a one-dimensional segment representing the entire country, stretching from position 0 to position l . Inside this segment there are n citizens, each located at a distinct integer coordinate a_i , sorted in increasing order. The task is to divide the whole segment [0,...
CF 1725B - Basketball Together
CF 1725B - Basketball Together Rating: 1000 Tags: binary search, greedy, sortings Solve time: 1m 59s Verified: yes Solution Problem Understanding We are asked to form teams from a list of candidate basketball players, each with an integer power. There is an opposing team with power $D$, and a team we form wins if the total power of its members exceeds $D$. The twist is that before each match, the...
CF 1765H - Hospital Queue
CF 1765H - Hospital Queue Rating: 2200 Tags: binary search, graphs, greedy, implementation Solve time: 7m 24s Verified: no Solution Got it. Let’s carefully trace what is happening. The previous solution attempt fails because it misinterprets the keyboard behavior. Mishka’s keyboard alternates between single-letter and double-letter presses globally , not per character. That is the key subtlety. Let’s analyze the sample input ossu : First press → single letter →...
CF 1765D - Watch the Videos
CF 1765D - Watch the Videos Rating: 1700 Tags: binary search, constructive algorithms, two pointers Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a sequence of videos, each with a download size, and a fixed disk capacity that limits how many megabytes can be stored at once. Each video takes time proportional to its size to download, and once downloaded it can be watched in exactly...
CF 1776M - Parmigiana With Seafood
CF 1776M - Parmigiana With Seafood Rating: 3000 Tags: binary search, dp, greedy, trees Solve time: 2m 20s Verified: no Solution Problem-Type Check This is a Type B (prove inequality) problem, not Type C. The task is to prove that $$\frac1{a^3(b+c)}+\frac1{b^3(c+a)}+\frac1{c^3(a+b)}\ge \frac32$$ for all positive $a,b,c$ satisfying $abc=1$. A valid solution must establish the inequality for all admissible triples and correctly identify any equality case if it arises from the...
CF 1776L - Controllers
CF 1776L - Controllers Rating: 1500 Tags: binary search, math Solve time: 3m 41s Verified: no Solution Problem Understanding We are asked to determine whether a player can reach exactly zero score after a sequence of game rounds, given a controller with two buttons labeled with arbitrary positive integers. Each round presents either a + or - sign, and pressing a button either increases or decreases the score by that...
CF 1856C - To Become Max
CF 1856C - To Become Max Rating: 1600 Tags: binary search, brute force, data structures, dp Solve time: 1m 38s Verified: no Solution Problem Understanding We are given an array of integers and a number of allowed operations. Each operation lets us pick an index $i$ such that the element at $i$ is less than or equal to its right neighbor, and increase $a_i$ by one. Our goal is to...
CF 1906D - Spaceship Exploration
CF 1906D - Spaceship Exploration Rating: 2800 Tags: binary search, geometry Solve time: 4m 37s Verified: no Solution Problem Understanding We are working in a geometric setting where a large convex polygon represents a forbidden region. A spaceship starts outside this region and must travel to another point, with the constraint that it is never allowed to enter the interior of the polygon, though touching its boundary is permitted. Each...
CF 1877B - Helmets in Night Light
CF 1877B - Helmets in Night Light Rating: 1000 Tags: binary search, greedy, sortings Solve time: 1m 46s Verified: no Solution Problem Understanding We are tasked with spreading an announcement to all residents of a village in the cheapest way possible. There are two ways to inform residents: Pak Chanek can directly tell someone at a fixed cost p , or a resident who already knows can inform others using...
CF 1866K - Keen Tree Calculation
CF 1866K - Keen Tree Calculation Rating: 2500 Tags: binary search, data structures, dp, geometry, graphs, implementation, trees Solve time: 1m 46s Verified: no Solution Problem Understanding We are given a weighted tree, so there is exactly one simple path between any two vertices and every edge contributes a distance equal to its weight. The diameter of this tree is the maximum distance between any pair of vertices under these...
CF 1866G - Grouped Carriages
CF 1866G - Grouped Carriages Rating: 2100 Tags: binary search, data structures, dp, flows, greedy Solve time: 3m 10s Verified: yes Solution Problem Understanding Each carriage initially contains some number of passengers. A passenger starting in carriage i may move left or right, but cannot cross more than D_i doors. That means every passenger from carriage i must end up somewhere inside the interval $$[i-D_i,; i+D_i]$$ after clipping the endpoints...
CF 1866F - Freak Joker Process
CF 1866F - Freak Joker Process Rating: 3100 Tags: binary search, data structures, sortings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are maintaining a group of players, each described by two evolving attributes: an offensive value and a defensive value. Over time, both attributes can change independently through updates. At any moment, we need to evaluate a ranking system that depends not only on the current values...
CF 1876G - Clubstep
CF 1876G - Clubstep Rating: 3500 Tags: binary search, brute force, data structures, greedy, trees Solve time: 2m 28s Verified: no Solution Problem Understanding Chaneka is trying to master a challenging video game level divided into n sequential parts. She starts with some familiarity value for each part, given as an array a of size n . Each attempt in the game fails at a specific part p , which...
CF 1876F - Indefinite Clownfish
CF 1876F - Indefinite Clownfish Rating: 3500 Tags: binary search, graphs Solve time: 2m 16s Verified: no Solution Problem Understanding We are asked to pick exactly k clownfish from a sequence of n available fish, each with a given size. Each fish can be assigned either a female or male gender at the time of selection, but the genders follow strict sequence rules. Female clownfish must form a strictly increasing...
CF 2002D2 - DFS Checker (Hard Version)
CF 2002D2 - DFS Checker (Hard Version) Rating: 2300 Tags: binary search, data structures, dfs and similar, graphs, hashing, trees Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is the root. Alongside the tree, we maintain a permutation stored in an array indexed by positions, and we repeatedly swap two positions in this array. After each swap, we must decide...