#binary search

CF 975C - Valhalla Siege Rating: 1400 Tags: binary search Model: gpt-5-3-mini Solve time: 58s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a436-0e7c-83ec-85b7-473ad67f57cb Solution Problem Understanding We are simulating a repeated battle on a line of warriors. Each warrior has a fixed amount of health, and arrows always hit the first still-alive warrior before moving forward to the next. When a warrior accumulates damage equal to or exceeding his health, he is...

CF 958F2 - Lightsabers (medium) Rating: 1800 Tags: binary search, two pointers Model: gpt-5-3-mini Solve time: 2m 35s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339f05-474c-83ec-8348-d5aef0244721 Solution Problem Understanding We are given a line of Jedi, each Jedi wearing a lightsaber of one of several colors. We are also given a target requirement: for every color, we want to see a fixed number of knights of that color. The goal is not...

CF 938C - Constructing Tests Rating: 1700 Tags: binary search, brute force, constructive algorithms Model: gpt-5-3-mini Solve time: 5m 52s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33978e-1a88-83ec-9ecc-90b2407c42fb Solution Problem Understanding The problem is not asking us to construct a matrix directly, but instead to reason about an optimal packing property of binary grids under a sliding-window restriction. We imagine an $n \times n$ grid filled with zeros and ones. The constraint...

CF 1041D - Glider Rating: 1700 Tags: binary search, data structures, two pointers Model: gpt-5-3-mini Solve time: 1m 35s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a337e1b-8584-83ec-825a-6d7235a7a6fb Solution Problem Understanding A glider is released from a moving airplane at some integer x-coordinate while the plane is fixed at height h. Once released, the glider always moves one unit to the right per second. At the same time, its height decreases by one...

CF 958E2 - Guard Duty (medium) Rating: 2200 Tags: binary search, dp, greedy, sortings Model: gpt-5-3-mini Solve time: 3m 26s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339e66-d274-83ec-9c8a-9aa9396149de Solution Problem Understanding We are given a strictly increasing sequence of time moments when Heidi temporarily leaves hyperspace. These moments are the only valid endpoints at which meetings can begin or end. Heidi must organize exactly $K$ disjoint meetings, where each meeting is defined...

CF 932B - Recursive Queries Rating: 1300 Tags: binary search, data structures, dfs and similar Model: gpt-5-3-mini Solve time: 1m 34s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a32e3b7-e7dc-83ec-a17b-6d7184217e41 Solution Problem Understanding We are given a function defined on positive integers that repeatedly transforms a number by taking its digit product and then collapsing it again in a recursive way until a single digit remains. That final digit is what we call...

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 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 940D - Alena And The Heater Rating: 1600 Tags: binary search, implementation Model: gpt-5-3-mini Solve time: 1m 29s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33993a-5810-83ec-96dd-8f9cf39a0fa3 Solution Problem Understanding We are given a sequence of integers and a second sequence of bits that was produced by a very specific “state machine” driven by an unknown interval $[l, r]$. Our task is to recover any such interval that could have generated the...

CF 1070E - Getting Deals Done Rating: 2100 Tags: binary search, data structures Model: gpt-5-3-mini Solve time: 1m 33s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bee1-54b8-83ec-8078-dc30aeae57f9 Solution Problem Understanding We are given a sequence of tasks, each with a processing time. Polycarp scans tasks from left to right and decides whether to execute or skip each one based on a threshold value $d$. Any task with duration greater than $d$ is...

CF 1033E - Hidden Bipartite Graph Rating: 2800 Tags: binary search, constructive algorithms, dfs and similar, graphs, interactive Model: gpt-5-3-mini Solve time: 2m 27s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33b4bd-0d58-83ec-9581-09aa8217a4ba Solution Problem Understanding We are given an unknown connected simple graph with up to 600 vertices. We cannot see its edges directly. Instead, we can only ask questions of the form: choose a subset of vertices, and receive the number...

CF 925F - Parametric Circulation Rating: 3100 Tags: binary search, flows Model: gpt-5-3-mini Solve time: 37s Verified: no (0/0 samples) Solution Problem Understanding We are given a directed graph where every edge can carry a non-negative flow, and flows must satisfy standard conservation: at every vertex, total incoming flow equals total outgoing flow. This is a circulation problem with no external source or sink. The twist is that each edge...

CF 939C - Convenient For Everybody Rating: 1600 Tags: binary search, two pointers Model: gpt-5-3-mini Solve time: 1m 29s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339882-e2e8-83ec-ad7b-d55e1e16e616 Solution Problem Understanding We are given a circular timeline with $n$ discrete hours, where hour labels wrap around so that after $n$ comes 1 again. Each of the $n$ timezones shifts local time by exactly one hour relative to its neighbor, so a global start...

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 965D - Single-use Stones Rating: 1900 Tags: binary search, flows, greedy, two pointers Model: gpt-5-3-mini Solve time: 1m 25s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a3ef-c198-83ec-ab18-235bfb734e32 Solution Problem Understanding We are given a river of width $w$. Along the river, at each integer position $i$ from $1$ to $w-1$, there are $a_i$ stones initially placed at that distance from the starting bank. A frog starts at the left bank (position...

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 923B - Producing Snow Rating: 1600 Tags: binary search, data structures Model: gpt-5-3-mini Solve time: 2m 45s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339128-9068-83ec-9ae9-9b98168b3b3f Solution Problem Understanding Each day, Bob adds a new pile of snow with a fixed initial volume. From that day onward, every existing pile loses the same amount of volume every day, determined by that day’s temperature. If a pile’s remaining volume becomes zero or negative...

CF 925A - Stairs and Elevators Rating: 1600 Tags: binary search Model: gpt-5-3-mini Solve time: 1m 51s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a326f66-d5a4-83ec-8424-637d475b2a1e Solution Problem Understanding We are working with a very large hotel grid that has n floors and m rooms per floor, forming an n × m lattice. Each room is identified by coordinates (floor, section) . Some vertical columns are special: they either contain stairs or elevators....

CF 992E - Nastya and King-Shamans Rating: 2500 Tags: binary search, data structures Model: gpt-5-3-mini Solve time: 1m 19s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32940b-b21c-83ec-b060-e3a9e4fcea32 Solution Problem Understanding We are given a sequence of values representing shamans ordered by time. Each position holds a “power”, and we continuously update single positions. After every update, we must determine whether there exists an index $j$ such that the value at $j$ equals...

CF 954G - Castle Defense Rating: 2000 Tags: binary search, data structures, greedy, two pointers Model: gpt-5-3-mini Solve time: 1m 46s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327d26-ccf4-83ec-bcbf-87461eeed768 Solution Problem Understanding Each position on the wall can be thought of as a segment that needs protection strength. You are given an initial arrangement of archers, and each archer does not only defend its own position but also helps nearby positions within...

CF 981F - Round Marriage Rating: 2500 Tags: binary search, graph matchings, greedy Model: gpt-5-3-mini Solve time: 1m 43s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3284af-5acc-83ec-9eff-e07fab19626d Solution Problem Understanding We are given two sets of points placed on a circle of circumference $L$. One set represents bridegrooms’ castles and the other represents brides’ palaces. Each set has exactly $n$ points, and every point lies on the circle boundary, measured as a...

CF 924B - Three-level Laser Rating: 1600 Tags: binary search, greedy, two pointers Model: gpt-5-3-mini Solve time: 1m 25s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a326e6b-2cbc-83ec-b7fb-a28cecb0a5b4 Solution Problem Understanding We are given a strictly increasing array of energy levels. We must pick three indices $i < j < k$ and interpret them as a three-step physical process that produces a ratio between useful energy and spent energy. The process depends only...

CF 896B - Ithea Plays With Chtholly Rating: 2000 Tags: binary search, constructive algorithms, games, greedy, interactive Model: gpt-5-3-mini Solve time: 3m 12s Verified: yes (1/1 samples) Solution Problem Understanding We are maintaining a row of n positions, each initially empty. Over time, we receive a sequence of m numbers. After each number arrives, we must immediately assign it to one of the n positions, possibly overwriting what was there...

CF 932D - Tree Rating: 2200 Tags: binary search, dp, trees Model: gpt-5-3-mini Solve time: 1m 28s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327666-dc20-83ec-bfaf-a06758f8815b Solution Problem Understanding We maintain a rooted tree that grows over time. The root is node 1 with weight 0. Each update query can attach a new node under an existing node, and each such node has a fixed weight. Over time, the structure becomes a rooted...

CF 1322B - Present Rating: 2100 Tags: binary search, bitmasks, constructive algorithms, data structures, math, sortings Model: gpt-5-3-mini Solve time: 1m 28s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2deae4-fc9c-83ec-aeba-66f8cbbf4563 Solution Problem Understanding We are given an array of integers, and we consider every unordered pair of distinct elements. For each pair, we compute their sum. After collecting all these pairwise sums, instead of summing or minimizing them, we combine them using...

CF 1366A - Shovels and Swords Rating: 1100 Tags: binary search, greedy, math Model: gpt-5-5 Solve time: 2m Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e4b06-3048-83ec-8673-f24f28d482e2 Solution Problem Understanding We are given a resource management problem where each test case describes two kinds of materials: sticks and diamonds. From these materials, we can craft two different items. One item consumes two sticks and one diamond, and the other consumes one stick and...

CF 1334F - Strange Function Rating: 2500 Tags: binary search, data structures, dp, greedy Model: gpt-5-5 Solve time: 4m 14s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e0c97-a080-83ec-9041-d62451cff5ef Solution Problem Understanding We are given a sequence of values where each position has a value and a cost of removal. From the original sequence, we are allowed to delete any subset of elements, paying or gaining coins depending on the deletion cost. After...

CF 1379F1 - Chess Strikes Back (easy version) Rating: 2700 Tags: binary search, data structures Model: gpt-5-3-mini Solve time: 3m 30s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e6458-0154-83ec-bc02-c35ba3e8f716 Solution Problem Understanding We are given a chessboard with $2n$ rows and $2m$ columns. Only the white cells are relevant, and those are exactly the cells where $i + j$ is even. Initially all white cells are usable, but over time some of...

CF 1358F - Tasty Cookie Rating: 2700 Tags: binary search, constructive algorithms, greedy, implementation Model: gpt-5-3-mini Solve time: 3m 13s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e3967-76d0-83ec-96a5-f2c93add7538 Solution Problem Understanding We are given an initial array A and a target array B , both of the same length. We are allowed to transform A using two operations: we can reverse the entire array, or we can replace it by its prefix...

CF 1352C - K-th Not Divisible by n Rating: 1200 Tags: binary search, math Model: gpt-5-3-mini Solve time: 2m 37s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e2bb2-e3e0-83ec-8dea-7fd34d7f3a5f Solution Problem Understanding We are looking at a filtered sequence of positive integers where every multiple of a fixed number is removed. Instead of working with the full list of natural numbers, imagine marking all numbers that are divisible by n as forbidden, then...

CF 1379D - New Passenger Trams Rating: 2300 Tags: binary search, brute force, data structures, sortings, two pointers Model: gpt-5-3-mini Solve time: 4m 36s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e6460-6b3c-83ec-8292-9e3f9f8e4c60 Solution Problem Understanding We are given a full-day timetable where freight trains already depart at fixed times. The day is cyclic with h hours and m minutes per hour, so every train time can be treated as a point on...

CF 1288D - Minimax Problem Rating: 2000 Tags: binary search, bitmasks, dp Model: gpt-5-3-mini Solve time: 2m 41s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2db7e1-74b8-83ec-b93f-88d597a14c54 Solution Problem Understanding We are given a collection of n vectors, each of length m. Think of each vector as describing m attributes of an object. We are allowed to pick two objects, possibly the same one twice. Once we pick them, we build a new...

CF 1323B - Count Subrectangles Rating: 1500 Tags: binary search, greedy, implementation Model: gpt-5-3-mini Solve time: 3m 30s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2ded2f-7b30-83ec-ae4c-241598b69c4b Solution Problem Understanding The matrix in this problem is not arbitrary. Every cell is determined by a simple outer-product rule: row i is either fully “active” or fully “inactive” depending on whether $a_i$ is 1 or 0, and column j is similarly controlled by $b_j$. A...

CF 1271E - Common Number Rating: 2100 Tags: binary search, combinatorics, dp, math Model: gpt-5-3-mini Solve time: 1m 31s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d9230-36e8-83ec-ae0f-62fb73351209 Solution Problem Understanding Each positive integer defines a deterministic walk down to 1. If the number is even, we divide it by 2, otherwise we subtract 1. Repeating this process always eventually reaches 1, and the sequence of visited values forms a chain that only...

CF 1342D - Multiple Testcases Rating: 1900 Tags: binary search, constructive algorithms, data structures, greedy, sortings, two pointers Model: gpt-5-3-mini Solve time: 8m 41s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e1bc3-6528-83ec-be3b-9d57dd5c8d13 Solution Problem Understanding We are given a collection of arrays, but the actual contents of these arrays do not matter at all. Each array is characterized only by its size. Our task is to pack all these arrays into several...

CF 1290B - Irreducible Anagrams Rating: 1800 Tags: binary search, constructive algorithms, data structures, strings, two pointers Model: gpt-5-5 Solve time: 5m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2dbb0a-a9b0-83ec-bfb3-954d543b2b2f Solution Problem Understanding We are given a base string and many queries over its substrings. Each query asks whether the chosen substring admits at least one “irreducible anagram”. To interpret this, imagine we take the substring and consider all possible permutations...

CF 1328B - K-th Beautiful String Rating: 1300 Tags: binary search, brute force, combinatorics, implementation, math Model: gpt-5-5 Solve time: 3m 51s Verified: no (0/0 samples) Share: https://chatgpt.com/share/6a2dfc6a-d998-83ec-acae-ab74293c87ce Solution Problem Understanding We are looking at all binary strings of length n that contain exactly two occurrences of the letter b , while every other position is filled with a . Since the alphabet is ordered with a < b ,...

CF 1366F - Jog Around The Graph Rating: 2700 Tags: binary search, dp, geometry, graphs Model: gpt-5-3-mini Solve time: 2m 30s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e4b1c-15e8-83ec-9c91-18e935817a8a Solution Problem Understanding We are working with a connected undirected graph where each edge has a positive weight. We start at vertex 1 and we are allowed to walk along edges, revisiting vertices and edges as many times as we want. What matters...

CF 1370F1 - The Hidden Pair (Easy Version) Rating: 2400 Tags: binary search, dfs and similar, graphs, interactive, shortest paths, trees Model: gpt-5-5 Solve time: 2m 35s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e5372-8200-83ec-8cd2-b905527f64bf Solution Problem Understanding We are working with a tree where two unknown vertices have been chosen as hidden targets. The only way to gain information is through queries on subsets of nodes. When we query a set,...

CF 1360H - Binary Median Rating: 2100 Tags: binary search, bitmasks, brute force, constructive algorithms Model: gpt-5-3-mini Solve time: 4m 37s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e3ffc-019c-83ec-9f2e-0b9dbb143a88 Solution Problem Understanding We start with the full space of all binary strings of length m , ordered in standard lexicographic order, which is equivalent to sorting them as fixed-length binary numbers from 0...0 up to 1...1 . From this complete ordered set,...

CF 1359C - Mixing Water Rating: 1700 Tags: binary search, math Model: gpt-5-5 Solve time: 4m 32s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e3b5e-cf00-83ec-bfa5-935e02eb4aca Solution Problem Understanding We are given two infinite supplies of water: one at temperature h and another at temperature c , with c < h . We build a sequence of pours into an empty container. The pouring order is fixed and alternates starting from hot: first...

CF 1355E - Restorer Distance Rating: 2100 Tags: binary search, greedy, math, sortings, ternary search Model: gpt-5-3-mini Solve time: 2m 28s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e330b-04a4-83ec-b54e-ca818cfda1d4 Solution Problem Understanding We are given a row of pillars, each with an initial height. The goal is to transform these heights so that every pillar ends up at the same final height. We are allowed to either add bricks, remove bricks, or...

CF 1335E1 - Three Blocks Palindrome (easy version) Rating: 1700 Tags: binary search, brute force, data structures, dp, two pointers Model: gpt-5-3-mini Solve time: 3m 26s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e0ec6-5db8-83ec-a770-f21d2987bf2e Solution Problem Understanding We are given a sequence of integers and asked to extract a subsequence that has a very specific structure. The subsequence must look like a block of repeated value x , followed by a block...

CF 1355C - Count Triangles Rating: 1800 Tags: binary search, implementation, math, two pointers Model: gpt-5-5 Solve time: 4m 30s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e337e-c354-83ec-b9bf-1c6c92a28cf3 Solution Problem Understanding We are given four integers $A \le B \le C \le D$. From these bounds we must choose three integers $x, y, z$ such that each side comes from a different interval: $x$ is chosen from $[A, B]$, $y$ from $[B,...

CF 1260B - Obtain Two Zeroes Rating: 1300 Tags: binary search, math Model: gpt-5-3-mini Solve time: 4m 49s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d7f9c-3e08-83ec-a865-d8e20e6df5bb Solution Problem Understanding We are given two piles of units, described by integers $a$ and $b$. In one move we are allowed to pick a positive integer $x$ and apply one of two transformations: either we subtract $x$ from $a$ and $2x$ from $b$, or we...

CF 2013F2 - Game in Tree (Hard Version) Rating: 3500 Tags: binary search, data structures, trees Model: gpt-5-5 Solve time: 2m 3s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a265c22-e058-83ec-9a73-b3865082b590 Solution Problem Understanding We are given a tree with n vertices. Alice starts at vertex 1 and Bob starts at a vertex along a path between two other nodes, u and v . They take turns moving along unvisited neighboring vertices. A...