ternary-search

Practice › Codeforces Solutions ›

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

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

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

Practice › Codeforces Solutions ›

Codeforces Round 464 (Div. 2)

Codeforces Round 464 (Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 800-2400 | 8m 3s # Problem Rating Tags Accepted Time ✓ A Love Triangle 800 graphs 29,697 1m 8s ✓ B Hamster Farm 1000 implementation 11,270 1m 6s ✓ E Maximize! 1800 binary-search, greedy, ternary-search 3,538 1m 44s F Cutlet 2400 data-structures, dp 1,198 4m 5s

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

CF 939E - Maximize!

CF 939E - Maximize! Rating: 1800 Tags: binary search, greedy, ternary search, two pointers Solve time: 1m 44s Verified: no Solution Problem Understanding We are maintaining a growing collection of positive integers. The collection starts empty, and we process two types of operations: we either insert a new number, or we ask a question about the current collection. The insertion rule is special: every new number is guaranteed to be...

Practice › Codeforces Solutions ›

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

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

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

Practice › Codeforces Solutions › Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) ›

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

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

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

Practice › Codeforces Solutions ›

Codeforces Round 619 (Div. 2)

Codeforces Round 619 (Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 800-2600 | 22m 8s # Problem Rating Tags Accepted Time ✓ A Three Strings 800 implementation, strings 20,108 2m 46s ✓ B Motarack's Birthday 1500 binary-search, greedy, ternary-search 14,969 4m 39s C Ayoub's function 1700 binary-search, combinatorics, greedy 9,875 2m 53s D Time to Run 2000 constructive-algorithms, graphs, implementation 4,236 5m 58s ✓ E Nanosoft...

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

CF 1301B - Motarack's Birthday

CF 1301B - Motarack's Birthday Rating: 1500 Tags: binary search, greedy, ternary search Solve time: 4m 39s Verified: no Solution Problem Understanding We are given an array of length $n$ where some positions contain fixed integers and some positions are marked as missing. All missing positions will be filled with a single chosen value $k$. After this replacement, we look at every pair of adjacent elements and measure their absolute...

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

CF 1244E - Minimizing Difference

CF 1244E - Minimizing Difference Rating: 2000 Tags: binary search, constructive algorithms, greedy, sortings, ternary search, two pointers Solve time: 7m 31s Verified: no Solution Problem Understanding We are given a list of integers and a limited budget of unit operations. Each operation lets us pick a single element and move it by exactly one step, either up or down. The goal is not to make all numbers equal, but...

Practice › Codeforces Solutions ›

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

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

CF 1059D - Nature Reserve

CF 1059D - Nature Reserve Rating: 2200 Tags: binary search, geometry, ternary search Solve time: 4m 38s Verified: yes Solution Problem Understanding We are given a set of points in the plane, each representing an animal’s location. We need to place a circle that covers all these points. At the same time, there is a fixed horizontal river, which after transformation becomes the x-axis, so the line is $y =...

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

CF 1730B - Meeting on the Line

CF 1730B - Meeting on the Line Rating: 1600 Tags: binary search, geometry, greedy, implementation, math, ternary search Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a line with people standing at different coordinates. Each person has a fixed position and also a personal preparation time before they can start moving. Once a meeting point is chosen, a person’s arrival time is the sum of their...

Practice › Codeforces Solutions › Codeforces Global Round 2 ›

CF 1119E - Pavel and Triangles

CF 1119E - Pavel and Triangles Rating: 1900 Tags: brute force, dp, fft, greedy, ternary search Solve time: 1m 5s Verified: yes Solution Problem Understanding We are given many sticks whose lengths are powers of two. For each exponent i, there are a_i sticks of length 2^i. Each stick can be used at most once, and we want to form as many non-degenerate triangles as possible, where each triangle uses...

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

CF 1156C - Match Points

CF 1156C - Match Points Rating: 2000 Tags: binary search, greedy, sortings, ternary search, two pointers Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a collection of points placed on a number line, and the goal is to form as many disjoint pairs as possible. A pair is valid only if the two chosen points are far enough apart, meaning the absolute difference between their coordinates...

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

CF 1254B1 - Send Boxes to Alice (Easy Version)

CF 1254B1 - Send Boxes to Alice (Easy Version) Rating: 1800 Tags: constructive algorithms, greedy, math, number theory, ternary search, two pointers Solve time: 2m 18s Verified: yes Solution Problem Understanding We are asked to rearrange chocolates among boxes so that Alice will be happy. Each of the $n$ boxes has either zero or one chocolate, and at least one box contains a chocolate. Alice is happy if all non-empty...

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

CF 1288A - Deadline

CF 1288A - Deadline Rating: 1100 Tags: binary search, brute force, math, ternary search Solve time: 1m 57s Verified: yes Solution Problem Understanding For each test case, we have a deadline of n days and a program that normally needs d days to finish. Before running the program, we may spend x days optimizing it. After spending those x days, the running time becomes: $$\left\lceil \frac{d}{x+1} \right\rceil$$ Since optimization and...

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

CF 1312C - Adding Powers

CF 1312C - Adding Powers Rating: 1400 Tags: bitmasks, greedy, implementation, math, number theory, ternary search Solve time: 1m 8s Verified: no Solution Problem Understanding We are given an array of non-negative integers, and a base $k \ge 2$. Starting from an array of zeroes of the same length, we can repeatedly pick a step $i$ and add $k^i$ to any single element of the array, or skip the step....

Practice › Codeforces Solutions › CodeCraft-20 (Div. 2) ›

CF 1316C - Primitive Primes

CF 1316C - Primitive Primes Rating: 1800 Tags: constructive algorithms, math, ternary search Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given two polynomials, each represented by an array of positive integers, which are their coefficients. The first polynomial has $n$ terms and coefficients $a_0, a_1, \dots, a_{n-1}$, the second has $m$ terms with coefficients $b_0, b_1, \dots, b_{m-1}$. Both sets of coefficients have a greatest common...

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

CF 1374E2 - Reading Books (hard version)

CF 1374E2 - Reading Books (hard version) Rating: 2500 Tags: data structures, greedy, implementation, sortings, ternary search, two pointers Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a collection of books, where each book has a reading time and two independent preference flags, one for Alice and one for Bob. We must select exactly $m$ books. The chosen set is shared, so both of them read...

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

CF 1394C - Boboniu and String

CF 1394C - Boboniu and String Rating: 2600 Tags: binary search, geometry, ternary search Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given several strings composed only of two characters, which we can think of as two symbols, say B and N. The task is to choose another string t over the same alphabet such that all given strings can be transformed into something “equivalent” to t...

Practice › Codeforces Solutions › Technocup 2021 - Elimination Round 1 ›

CF 1413E - Solo mid Oracle

CF 1413E - Solo mid Oracle Rating: 2100 Tags: greedy, math, ternary search Solve time: 1m 50s Verified: yes Solution Problem Understanding We repeatedly cast a spell on an enemy. Each cast immediately deals a damage. After that, the same cast heals the enemy by b health every second for exactly c seconds. Casts happen every d seconds because of the cooldown, and all effects stack. The enemy dies if,...

Practice › Codeforces Solutions › Codeforces Global Round 11 ›

CF 1427H - Prison Break

CF 1427H - Prison Break Rating: 3500 Tags: binary search, games, geometry, ternary search Solve time: 1m 32s Verified: no Solution Problem Understanding We are asked to compute the minimum speed $v$ at which two guards can prevent a prisoner from escaping a convex polygonal prison. The prisoner starts outside the main perimeter on a fixed point far to the left. He can move freely at speed 1 toward any...

Practice › Codeforces Solutions ›

Educational Codeforces Round 80 (Rated for Div. 2)

Educational Codeforces Round 80 (Rated for Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 1100-2900 | 25m 31s # Problem Rating Tags Accepted Time ✓ A Deadline 1100 binary-search, brute-force, math 19,316 1m 57s ✓ C Two Arrays 1600 combinatorics, dp 15,271 3m 31s ✓ E Messenger Simulator 2000 data-structures 4,015 10m 11s F Red-Blue Graph 2900 constructive-algorithms, flows 646 9m 52s

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

CF 1455E - Four Points

CF 1455E - Four Points Rating: 2400 Tags: brute force, constructive algorithms, flows, geometry, greedy, implementation, math, ternary search Solve time: 1m 49s Verified: no Solution Problem Understanding We are given four distinct points on a 2D integer grid and can move any point by one unit in either the x or y direction per move. The goal is to transform these points into the vertices of an axis-aligned square...

Practice › Codeforces Solutions ›

Codeforces Round 700 (Div. 1)

Codeforces Round 700 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1700-3500 | Time: 14m 35s Problem Name Rating Tags Solve Time Verified A Searching Local Minimum 1700 binary-search, interactive, ternary-search 2m 8s ✓ B1 Painting the Array I 1900 constructive-algorithms, data-structures, dp 1m 44s ✓ B2 Painting the Array II 2100 constructive-algorithms, data-structures, dp 2m 53s ✗ C Continuous City 2500 bitmasks, constructive-algorithms...

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

CF 1479A - Searching Local Minimum

CF 1479A - Searching Local Minimum Rating: 1700 Tags: binary search, interactive, ternary search Solve time: 2m 8s Verified: yes Solution Problem Understanding We are asked to find a local minimum in a hidden permutation of integers from 1 to $n$. The permutation is a rearrangement of numbers $1$ to $n$ without repetition. A local minimum is an index $k$ such that the value at $a_k$ is strictly smaller than...

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

CF 1538G - Gift Set

CF 1538G - Gift Set Rating: 2100 Tags: binary search, greedy, math, ternary search Solve time: 54s Verified: no Solution Problem Understanding We have two piles of candies. One pile contains x red candies and the other contains y blue candies. Each gift set must use exactly a + b candies. There are two possible compositions: a red and b blue b red and a blue The two types are...

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

CF 1574C - Slay the Dragon

CF 1574C - Slay the Dragon Rating: 1300 Tags: binary search, greedy, sortings, ternary search Solve time: 5m 53s Verified: no Solution Problem Understanding We have a squad of heroes, each with a fixed strength. For every dragon, we must choose exactly one hero to fight it, while all remaining heroes stay behind to defend the castle. A dragon has two requirements. The chosen attacker must have strength at least...

Practice › Codeforces Solutions › Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1) ›

CF 1599C - Bubble Strike

CF 1599C - Bubble Strike Rating: 2000 Tags: combinatorics, math, probabilities, ternary search Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to determine how many maps Johnny must study to ensure that the probability he ends up playing on a studied map is at least $P$. The game process is as follows: from $N$ total maps, three are randomly presented, and each player discards one map....

Practice › Codeforces Solutions › SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1662K - Pandemic Restrictions

CF 1662K - Pandemic Restrictions Rating: - Tags: geometry, ternary search Solve time: 2m 11s Verified: no Solution Problem Understanding We are tasked with finding a residence point in a 2D plane from which you can meet any pair of three friends such that the sum of distances from each attendee to the meeting point does not exceed a certain threshold $r$. The friends live at three distinct coordinates, and...

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

CF 1716C - Robot in a Hallway

CF 1716C - Robot in a Hallway Rating: 2000 Tags: data structures, dp, greedy, implementation, ternary search Solve time: 2m 24s Verified: no Solution Problem Understanding We have a 2-row grid with $m$ columns, where each cell becomes accessible only at a certain time. The robot starts at the top-left cell $(1,1)$ and must visit every cell exactly once, moving only to adjacent cells or staying in place for a...

Practice › Codeforces Solutions › Codeforces Global Round 23 ›

CF 1746E1 - Joking (Easy Version)

CF 1746E1 - Joking (Easy Version) Rating: 2500 Tags: binary search, constructive algorithms, interactive, ternary search Solve time: 2m 18s Verified: no Solution Problem Understanding In this problem, you are trying to identify a hidden integer x between 1 and n . You can ask whether x belongs to any subset of numbers you choose. Each response is either "YES" or "NO". However, some responses may be false - we...

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

CF 1848D - Vika and Bonuses

CF 1848D - Vika and Bonuses Rating: 2200 Tags: binary search, brute force, math, ternary search Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to maximize the total discount Vika can obtain from her bonus system in a cosmetics store. She currently has s bonuses and will make k more purchases. On each purchase, she can either take a discount equal to her current number of...

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

CF 2102E - 23 Kingdom

CF 2102E - 23 Kingdom Rating: 2200 Tags: data structures, greedy, ternary search, two pointers Solve time: 1m 35s Verified: no Solution Problem Understanding We are asked to maximize the "beauty" of a derived array based on an input array. The input array a gives an upper bound on each element of a new array b , which must have the same length. Each element of b satisfies 1 ≤...

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

CF 1924F - Anti-Proxy Attendance

CF 1924F - Anti-Proxy Attendance Rating: 3500 Tags: constructive algorithms, dp, interactive, ternary search Solve time: 42s Verified: no Solution I can't write a correct editorial for Codeforces 1924F from the problem statement alone. This problem is a 3500-rated interactive problem with a highly nontrivial strategy. To produce the editorial you've requested, I would need the actual solution idea, editorial, accepted code, or at least a detailed description of the...

Practice › Codeforces Solutions ›

Codeforces Round 990 (Div. 1)

Codeforces Round 990 (Div. 1) Div. 1 | 8 problems | 0/8 verified | Difficulty 1200-3500 | 16m 20s # Problem Rating Tags Accepted Time ✓ A Swap Columns and Find a Path 1200 greedy, sortings 16,791 2m 19s B Move Back at a Cost 1600 binary-search, data-structures, greedy 10,863 1m 42s C Adventurers 2100 binary-search, data-structures, greedy 2,346 3m 19s D For the Emperor! 3100 flows, graphs 550 1m...

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

CF 1928D - Lonely Mountain Dungeons

CF 1928D - Lonely Mountain Dungeons Rating: 1900 Tags: brute force, data structures, greedy, math, ternary search Solve time: 2m 3s Verified: yes Solution Problem Understanding We are asked to assemble an army from multiple races, each with a certain number of creatures. Each creature pair from the same race, if they are placed in different squads, contributes a fixed amount b to the army’s strength. On the other hand,...

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

CF 1933E - Turtle vs. Rabbit Race: Optimal Trainings

CF 1933E - Turtle vs. Rabbit Race: Optimal Trainings Rating: 1500 Tags: binary search, implementation, math, ternary search Solve time: 2m 24s Verified: no Solution Problem Understanding We are asked to model Isaac's training across multiple running tracks. Each track consists of a number of equal-length sections, and each section completed increases his performance in a linearly decreasing manner. The first section contributes u , the second u-1 , the...

Practice › Codeforces Solutions ›

Codeforces Round 953 (Div. 2)

Codeforces Round 953 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-2400 | Time: 13m 40s Problem Name Rating Tags Solve Time Verified A Alice and Books 800 constructive-algorithms, greedy, sortings 2m 26s ✗ B New Bakery 800 binary-search, greedy, math 2m 7s ✓ C Manhattan Permutations 1300 constructive-algorithms, data-structures, greedy 2m 33s ✗ D Elections 1600 data-structures, greedy, implementation 1m 38s ✗ E...

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

CF 1978B - New Bakery

CF 1978B - New Bakery Rating: 800 Tags: binary search, greedy, math, ternary search Solve time: 2m 7s Verified: yes Solution Problem Understanding In this problem, Bob is trying to maximize his profit from selling buns with a special promotion. He has n buns to sell, a usual price a for each bun, and a promotional parameter b . The promotion allows him to choose an integer k and sell...

Practice › Codeforces Solutions ›

Codeforces Round 962 (Div. 3)

Codeforces Round 962 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 6/7 | Rating range: 800-2200 | Time: 18m 25s Problem Name Rating Tags Solve Time Verified A Legs 800 binary-search, math, ternary-search 2m 12s ✓ B Scale 800 greedy, implementation 2m 31s ✓ C Sort 1200 dp, greedy, sortings 2m 35s ✓ D Fun 1500 binary-search, brute-force, combinatorics 2m 17s ✓ E Decode 1600 combinatorics, data-structures, implementation...

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

CF 1996A - Legs

CF 1996A - Legs Rating: 800 Tags: binary search, math, ternary search Solve time: 2m 12s Verified: yes Solution Problem Understanding The farm has only chickens and cows, and Farmer John counts a total of n legs. Chickens contribute 2 legs each and cows contribute 4 legs each. The question asks for the smallest possible number of animals consistent with the total leg count. Essentially, we are distributing n legs...

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

CF 1999G2 - Ruler (hard version)

CF 1999G2 - Ruler (hard version) Rating: 1700 Tags: binary search, interactive, ternary search Solve time: 2m 34s Verified: no Solution Problem Understanding We are asked to find a missing number on a special ruler, which behaves almost like a normal ruler but skips a single value $x$ between 2 and 999. If you try to measure an object smaller than $x$, the ruler gives the correct length. If the...

Practice › Codeforces Solutions ›

Codeforces Round 971 (Div. 4)

Codeforces Round 971 (Div. 4) Type: Div. 4 | Problems: 9 | Verified: 3/9 | Rating range: 800-2700 | Time: 14m 27s Problem Name Rating Tags Solve Time Verified A Minimize! 800 brute-force, math 1m 5s ✓ B osu!mania 800 brute-force, implementation 2m ✗ C The Legend of Freya the Frog 1100 implementation, math 55s ✗ D Satyam and Counting 1400 geometry, math 1m 8s ✗ E Klee's SUPER DUPER...

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

CF 2009E - Klee's SUPER DUPER LARGE Array!!!

CF 2009E - Klee's SUPER DUPER LARGE Array!!! Rating: 1400 Tags: binary search, math, ternary search Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given a conceptual array that contains a strictly increasing sequence of integers starting at $k$ and ending at $k+n-1$. Klee wants to choose a prefix of the array such that the absolute difference between the sum of the prefix and the sum of...

Practice › Codeforces Solutions › Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 ›

CF 2020C - Bitwise Balancing

CF 2020C - Bitwise Balancing Rating: 1400 Tags: bitmasks, hashing, implementation, math, schedules, ternary search Solve time: 2m 10s Verified: no Solution Problem Understanding We are given three non-negative integers b , c , and d . We must construct a non-negative integer a such that $$(a \mid b) - (a & c) = d$$ where | is bitwise OR and & is bitwise AND. The task is not to...

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

CF 2028D - Alice's Adventures in Cards

CF 2028D - Alice's Adventures in Cards Rating: 2000 Tags: constructive algorithms, data structures, dp, graphs, greedy, implementation, ternary search Solve time: 1m 29s Verified: no Solution Problem Understanding The problem can be viewed as a graph traversal on a set of n card types. Alice starts with card 1 and wants to acquire card n by trading with three other players: Queen, King, and Jack. Each player has a...

Practice › Codeforces Solutions › Codeforces Global Round 27 ›

CF 2035E - Monster

CF 2035E - Monster Rating: 2300 Tags: binary search, brute force, constructive algorithms, greedy, implementation, math, ternary search Solve time: 2m 11s Verified: no Solution Problem Understanding We are fighting a monster with z health points using a weapon whose damage starts at zero. We can perform two operations: increase the weapon’s damage by one at a cost of x coins, or attack the monster for d damage at a...

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

CF 2046C - Adventurers

CF 2046C - Adventurers Rating: 2100 Tags: binary search, data structures, greedy, sortings, ternary search, two pointers Solve time: 3m 19s Verified: no Solution Problem Understanding Each city is a point on the plane. We choose a dividing point $(x_0,y_0)$, which splits the plane into four regions: $$\begin{aligned} &x \ge x_0,\ y \ge y_0 \ &x < x_0,\ y \ge y_0 \ &x \ge x_0,\ y < y_0 \ &x...

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

CF 2063D - Game With Triangles

CF 2063D - Game With Triangles Rating: 2000 Tags: binary search, brute force, data structures, geometry, greedy, implementation, math, ternary search, two pointers Solve time: 1m 46s Verified: no Solution Problem Understanding We are given two horizontal layers of points. One layer lies on the line $y=0$, the other lies on $y=2$. Each layer contains distinct x-coordinates. A move consists of selecting three remaining points that do not lie on...

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

CF 2101C - 23 Kingdom

CF 2101C - 23 Kingdom Rating: 2200 Tags: binary search, brute force, data structures, greedy, ternary search, two pointers Solve time: 1m 39s Verified: no Solution Problem Understanding We are asked to maximize the "beauty" of an array derived from a given array a . For each position in a , the new array b must satisfy 1 ≤ b_i ≤ a_i . The beauty of b is the sum...

Practice › Codeforces Solutions › Codeforces Round 1033 (Div. 2) and CodeNite 2025 ›

CF 2120E - Lanes of Cars

CF 2120E - Lanes of Cars Rating: 2300 Tags: binary search, dp, ternary search Solve time: 2m 32s Verified: yes Solution Problem Understanding Each lane initially contains a_i cars. If nobody moves, the cars in a lane leave one per second, so a lane of size x contributes $$1+2+\dots+x=\frac{x(x+1)}2$$ to the total angriness. Cars may switch lanes. A moved car is appended to the back of another lane and receives...

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

CF 2132E - Arithmetics Competition

CF 2132E - Arithmetics Competition Rating: 1700 Tags: binary search, data structures, greedy, sortings, ternary search Solve time: 1m 37s Verified: yes Solution Problem Understanding The problem presents a team of two players, Vadim and Kostya, who each have a collection of cards with numeric values. In each round, they are asked to select exactly a given number of cards, but each player has a personal upper limit on how...

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

CF 2149F - Nezuko in the Clearing

CF 2149F - Nezuko in the Clearing Rating: 1900 Tags: binary search, math, ternary search Solve time: 1m 41s Verified: no Solution Problem Understanding Nezuko starts at position 0 on a number line with a certain number of health points, and she wants to reach position d . In each turn, she can either rest to gain one health point or move forward by one. Each consecutive move in a...

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

CF 2154E - No Mind To Think

CF 2154E - No Mind To Think Rating: 2500 Tags: binary search, divide and conquer, greedy, sortings, ternary search, two pointers Solve time: 1m 42s Verified: no Solution Problem Understanding We are given an array of positive integers. We are allowed to choose one odd length $x$, and then repeatedly perform an operation up to $k$ times. Each operation picks any subsequence of length $x$, computes its median, and overwrites...

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

CF 2157F - Git Gud

CF 2157F - Git Gud Rating: 2400 Tags: brute force, constructive algorithms, divide and conquer, math, ternary search Solve time: 3m 8s Verified: yes Solution Problem Understanding We are asked to simulate a sequence of missions that guarantees our skill reaches at least a target value n regardless of our starting skill s , which is unknown and can be any integer from 1 to n . Each mission has...

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

CF 2157D - Billion Players Game

CF 2157D - Billion Players Game Rating: 1600 Tags: binary search, greedy, math, sortings, ternary search, two pointers Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a hidden integer position $p$ that will eventually be chosen somewhere inside a fixed interval $[l, r]$. We do not know the exact value, and our goal is to prepare a strategy before seeing $p$. We are also given a...

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

CF 2159F - Grand Finale: Snakes

CF 2159F - Grand Finale: Snakes Rating: 3500 Tags: binary search, interactive, ternary search Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a permutation grid of size $n \times n$, where every number from $1$ to $n^2$ appears exactly once. Instead of directly using this grid, we interact with a hidden process that defines, for each snake length $l$ and time $T$, a value $f(l,T)$. This...

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

CF 2203E - Probabilistic Card Game

CF 2203E - Probabilistic Card Game Rating: 2200 Tags: binary search, data structures, games, greedy, math, ternary search Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to compute the expected score for Bob in a turn-based card game where Alice and Bob play optimally. Each round, a new card is added to a deck. Once the deck has at least three cards, Alice selects a card,...

Practice › Codeforces Solutions ›

Codeforces Round 177 (Div. 2)

Codeforces Round 177 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 1100-1400 | 2m 24s # Problem Rating Tags Accepted Time ✓ A Polo the Penguin and Segments 1100 brute-force, implementation 10,325 1m 19s ✓ B Polo the Penguin and Matrix 1400 brute-force, dp, implementation 18,961 1m 5s ✓

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

CF 289B - Polo the Penguin and Matrix

CF 289B - Polo the Penguin and Matrix Rating: 1400 Tags: brute force, dp, implementation, sortings, ternary search Solve time: 1m 5s Verified: yes Solution Problem Understanding We are given a rectangular grid of integers, and we are allowed to perform a very specific operation: pick a single cell and add or subtract a fixed value d to it. Each such operation costs one move. The goal is to transform...

Practice › Codeforces Solutions ›

Codeforces Round 118 (Div. 1)

Codeforces Round 118 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1300-3000 | 6m 18s # Problem Rating Tags Accepted Time ✓ A Plant 1300 math 6,519 1m 30s ✓ B Mushroom Scientists 1800 math, ternary-search 1,786 1m 23s ✓ C Clever Fat Rat 2500 dp 151 1m 41s ✓ D Visit of the Great 2600 math, number-theory 503 1m 21s E Soap Time! - 2...

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

CF 200E - Tractor College

CF 200E - Tractor College Rating: 2400 Tags: implementation, math, number theory, ternary search Solve time: 1m 11s Verified: no Solution Problem Understanding We are asked to distribute a fixed scholarship budget among students based on their exam grades. Each student receives a mark of 3, 4, or 5, and students with the same mark must receive the same scholarship. Let c3 , c4 , c5 be the counts of...

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

CF 185B - Mushroom Scientists

CF 185B - Mushroom Scientists Rating: 1800 Tags: math, ternary search Solve time: 1m 23s Verified: yes Solution Problem Understanding We are asked to maximize a function defined on three non-negative real variables x , y , and z subject to a sum constraint. The function has the form f(x, y, z) = x^a · y^b · z^c , where a , b , c are non-negative integers. The variables...

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

CF 455C - Civilization

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

Practice › Codeforces Solutions ›

CROC-MBTU 2012, Final Round (Online version, Div. 2)

CROC-MBTU 2012, Final Round (Online version, Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2000 | 11m 54s # Problem Rating Tags Accepted Time ✓ A Paper Work 1000 greedy 4,804 3m 9s B Restoring IPv6 1500 implementation, strings 2,238 1m 5s ✓ C Movie Critics 1600 greedy 2,229 3m 12s D Building Bridge 1900 geometry, ternary-search, two-pointers 1,009 1m 13s ✓ E Mad Joe 2000...

Practice › Codeforces Solutions ›

Codeforces Round 127 (Div. 1)

Codeforces Round 127 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1700-2600 | 7m 7s # Problem Rating Tags Accepted Time ✓ A Clear Symmetry 1700 constructive-algorithms, dp, math 3,246 1m 9s ✓ B Guess That Car! 1800 math, ternary-search 1,391 1m ✓ C Fragile Bridges 2000 dp 1,513 1m 40s ✓ D Brand New Problem 2600 bitmasks, brute-force, dp 454 1m 39s ✓ E Thoroughly...

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

CF 201B - Guess That Car!

CF 201B - Guess That Car! Rating: 1800 Tags: math, ternary search Solve time: 1m Verified: yes Solution Problem Understanding The problem places us in a grid-like parking lot of size 4·n by 4·m meters, divided into squares of 4 by 4 meters, each containing a car with a known "rarity" value. Yura, the player, must choose a starting point at one of the intersections of these dividing lines and...

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

CF 439D - Devu and his Brother

CF 439D - Devu and his Brother Rating: 1700 Tags: binary search, sortings, ternary search, two pointers Solve time: 57s Verified: yes Solution Problem Understanding We are given two integer arrays, one belonging to Devu and the other to his brother. We are allowed to repeatedly increase or decrease any single element of either array by 1 in one operation. The goal is to transform the arrays so that the...

Practice › Codeforces Solutions › CROC-MBTU 2012, Final Round (Online version, Div. 2) ›

CF 250D - Building Bridge

CF 250D - Building Bridge Rating: 1900 Tags: geometry, ternary search, two pointers Solve time: 1m 13s Verified: yes Solution Problem Understanding We are choosing a path from a western village at the origin to a river bank located at a vertical line $x = a$, then crossing the river in a straight line to another point on the eastern bank $x = b$, and finally following a pre-determined path...

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

CF 431E - Chemistry Experiment

CF 431E - Chemistry Experiment Rating: 2200 Tags: binary search, data structures, ternary search Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given a set of containers, each containing some fixed amount of mercury. Over time, two kinds of operations happen. The first operation changes the mercury amount in a single container. Conceptually, that tube is emptied and then refilled so that its mercury level becomes exactly...

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

CF 427E - Police Patrol

CF 427E - Police Patrol Rating: 2000 Tags: greedy, implementation, math, ternary search Solve time: 1m 54s Verified: yes Solution Problem Understanding All criminals stand on the x-axis, and we must choose one integer coordinate for the police station. The patrol car starts from the station, visits some criminals, brings them back to the station, then repeats until everyone is arrested. Each trip can carry at most m criminals. The...

Practice › Codeforces Solutions ›

Codeforces Beta Round 82 (Div. 2)

Codeforces Beta Round 82 (Div. 2) Div. 2 | 5 problems | 4/5 verified | Difficulty 1000-2100 | 13m 18s # Problem Rating Tags Accepted Time ✓ A Card Game 1000 implementation 8,535 1m 37s ✓ B Choosing Laptop 1000 brute-force, implementation 6,867 2m 3s ✓ C Buns 1700 dp 7,059 1m 50s ✓ D Treasure Island 1700 brute-force, implementation 1,471 2m 25s ✓ E Space Rescuers 2100 geometry, ternary-search...

Practice › Codeforces Solutions ›

Codeforces Beta Round 78 (Div. 1 Only)

Codeforces Beta Round 78 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1700-2700 | 10m 13s # Problem Rating Tags Accepted Time ✓ A Help Victoria the Wise 1700 brute-force, implementation 1,348 2m 12s ✓ B Help King 2200 implementation, probabilities, trees 152 1m 17s ✓ C Help Greg the Dwarf 2500 geometry, ternary-search 347 2m 29s ✓ D Help Monks 2500 constructive-algorithms 200 1m...

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

CF 106E - Space Rescuers

CF 106E - Space Rescuers Rating: 2100 Tags: geometry, ternary search Solve time: 5m 23s Verified: no Solution Problem Understanding We are asked to place a space rescue station in three-dimensional space such that the maximum distance from it to any of the given planets is minimized. Each planet is represented by its coordinates $(x, y, z)$. The input consists of an integer $n$ representing the number of planets followed...

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

CF 98C - Help Greg the Dwarf

CF 98C - Help Greg the Dwarf Rating: 2500 Tags: geometry, ternary search Solve time: 2m 29s Verified: yes Solution Problem Understanding We have an L-shaped corridor with widths a and b on the two branches. A rectangular coffin of fixed length l must be moved through the corner. The coffin can slide and rotate freely in the plane, but it can never leave the floor, so every intermediate position...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Discrete Ternary Search

Discrete Ternary Search Discrete ternary search finds the maximum or minimum of a unimodal function defined over integer indices. A function is unimodal if it strictly increases up to a point and then strictly decreases, or the reverse. Unlike binary search, which relies on a monotone predicate, ternary search relies on a unimodal shape. Problem Given a function $f(i)$ defined on integer indices $i \in [0, n-1]$, find an index...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Continuous Ternary Search

Continuous Ternary Search Continuous ternary search finds the maximum or minimum of a unimodal function defined over a real interval. It applies when the domain is continuous and the function has a single peak or valley. Unlike the discrete version, there is no final scan. The algorithm stops when the interval becomes sufficiently small. Problem Given a function $f(x)$ defined over a real interval $[l, r]$, find a point $x$...

#ternary-search

Codeforces Round 601 (Div. 1)

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

Codeforces Round 464 (Div. 2)

CF 939E - Maximize!

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

CF 1542D - Priority Queue

CF 1387A - Graph

CF 1354C1 - Simple Polygon Embedding

Codeforces Round 619 (Div. 2)

CF 1301B - Motarack's Birthday

CF 1244E - Minimizing Difference

Codeforces Round 514 (Div. 2)

CF 1059D - Nature Reserve

CF 1730B - Meeting on the Line

CF 1119E - Pavel and Triangles

CF 1156C - Match Points

CF 1254B1 - Send Boxes to Alice (Easy Version)

CF 1288A - Deadline

CF 1312C - Adding Powers

CF 1316C - Primitive Primes

CF 1374E2 - Reading Books (hard version)

CF 1394C - Boboniu and String

CF 1413E - Solo mid Oracle

CF 1427H - Prison Break

Educational Codeforces Round 80 (Rated for Div. 2)

CF 1455E - Four Points

Codeforces Round 700 (Div. 1)

CF 1479A - Searching Local Minimum

CF 1538G - Gift Set

CF 1574C - Slay the Dragon

CF 1599C - Bubble Strike

CF 1662K - Pandemic Restrictions

CF 1716C - Robot in a Hallway

CF 1746E1 - Joking (Easy Version)

CF 1848D - Vika and Bonuses

CF 2102E - 23 Kingdom

CF 1924F - Anti-Proxy Attendance

Codeforces Round 990 (Div. 1)

CF 1928D - Lonely Mountain Dungeons

CF 1933E - Turtle vs. Rabbit Race: Optimal Trainings

Codeforces Round 953 (Div. 2)

CF 1978B - New Bakery

Codeforces Round 962 (Div. 3)

CF 1996A - Legs

CF 1999G2 - Ruler (hard version)

Codeforces Round 971 (Div. 4)

CF 2009E - Klee's SUPER DUPER LARGE Array!!!

CF 2020C - Bitwise Balancing

CF 2028D - Alice's Adventures in Cards

CF 2035E - Monster

CF 2046C - Adventurers

CF 2063D - Game With Triangles

CF 2101C - 23 Kingdom

CF 2120E - Lanes of Cars

CF 2132E - Arithmetics Competition

CF 2149F - Nezuko in the Clearing

CF 2154E - No Mind To Think

CF 2157F - Git Gud

CF 2157D - Billion Players Game

CF 2159F - Grand Finale: Snakes

CF 2203E - Probabilistic Card Game

Codeforces Round 177 (Div. 2)

CF 289B - Polo the Penguin and Matrix

Codeforces Round 118 (Div. 1)

CF 200E - Tractor College

CF 185B - Mushroom Scientists

CF 455C - Civilization

CROC-MBTU 2012, Final Round (Online version, Div. 2)

Codeforces Round 127 (Div. 1)

CF 201B - Guess That Car!

CF 439D - Devu and his Brother

CF 250D - Building Bridge

CF 431E - Chemistry Experiment

CF 427E - Police Patrol

Codeforces Beta Round 82 (Div. 2)

Codeforces Beta Round 78 (Div. 1 Only)

CF 106E - Space Rescuers

CF 98C - Help Greg the Dwarf

Discrete Ternary Search