#greedy
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 1267E - Elections
CF 1267E - Elections Rating: 1700 Tags: greedy Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a voting system with multiple candidates and multiple polling stations. Each station reports how many votes each candidate received. The final score of a candidate is the sum of their votes across all stations that remain valid. There is a special candidate, the last one, who represents the opposition. The...
CF 1250N - Wires
CF 1250N - Wires Rating: 2000 Tags: dfs and similar, graphs, greedy Solve time: 2m Verified: no Solution Problem Understanding Each wire connects two contact points, and we say two wires are related if they share at least one endpoint, or if there is a chain of wires where consecutive wires share endpoints. This creates a notion of connectivity over the wires themselves: wires are nodes, and sharing a contact...
CF 1250G - Discarding Game
CF 1250G - Discarding Game Rating: 2300 Tags: dp, greedy, two pointers Solve time: 1m 59s Verified: no Solution Problem Understanding We are given two sequences that evolve in lockstep over time. In each round, the human gains some amount of points while the computer also gains points. Both totals accumulate independently across rounds. The game ends as soon as one of the players reaches or exceeds a threshold value...
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 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 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 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 960C - Subsequence Counting Rating: 1700 Tags: bitmasks, constructive algorithms, greedy, implementation Model: gpt-5-3-mini Solve time: 4m 22s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a069-6ac8-83ec-b946-bc1675dc98b7 Solution Problem Understanding We are given two numbers: a target count of subsequences and a threshold value. We must construct an integer array such that when we look at all its non-empty subsequences and keep only those subsequences whose maximum minus minimum is strictly less...
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...
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...
CF 958B2 - Maximum Control (medium)
CF 958B2 - Maximum Control (medium) Rating: 2200 Tags: data structures, dfs and similar, graphs, greedy, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given a tree with $N$ nodes, meaning every pair of nodes is connected by exactly one simple path. We are allowed to choose $K$ nodes as “active stations”. Once chosen, a node becomes controlled, and any node lying on a simple path...
CF 960B - Minimize the error
CF 960B - Minimize the error Rating: 1500 Tags: data structures, greedy, sortings Solve time: 1m 14s Verified: yes Solution Problem Understanding We are working with two integer arrays of equal length. Each position contributes independently to a total “error”, where the error of an index is the square of the difference between the two values at that index. The total cost is the sum of these squared differences over...
CF 963B - Destruction of a Tree
CF 963B - Destruction of a Tree Rating: 2000 Tags: constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a tree where each vertex has an associated current degree that changes as vertices are removed. A vertex is eligible for removal only when its degree is even at the moment we choose it. When a vertex is removed, all...
CF 1017C - The Phone Number
CF 1017C - The Phone Number Rating: 1600 Tags: constructive algorithms, greedy Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a number $n$, and we must construct a permutation of the integers from $1$ to $n$. Among all such permutations, we are asked to minimize a quantity defined on the permutation. This quantity is the sum of two classical subsequence measures. One is the length of...
CF 1023C - Bracket Subsequence
CF 1023C - Bracket Subsequence Rating: 1200 Tags: greedy Solve time: 1m 53s Verified: yes Solution Problem Understanding We are given a correctly balanced bracket sequence, meaning every prefix of the string never has more closing brackets than opening ones, and in total the counts match perfectly. From this long sequence, we are asked to extract a shorter sequence of fixed even length, keeping the original order of characters, such...
CF 1025B - Weakened Common Divisor
CF 1025B - Weakened Common Divisor Rating: 1600 Tags: brute force, greedy, number theory Solve time: 2m 43s Verified: yes Solution Problem Understanding We are given a collection of pairs of integers. From each pair, we are allowed to pick exactly one number. After making one choice per pair, we obtain a multiset of selected values. The task is to find an integer greater than 1 that divides every chosen...
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...
CF 1040A - Palindrome Dance
CF 1040A - Palindrome Dance Rating: 1000 Tags: greedy Solve time: 2m 28s Verified: no Solution Problem Understanding We are given a line of dancers, each occupying a fixed position. Every dancer must end up wearing either a white suit or a black suit, and some of these suits are already fixed while others are undecided. The goal is to assign colors to all undecided positions so that the final...
CF 1558C - Bottom-Tier Reversals
CF 1558C - Bottom-Tier Reversals Rating: 2000 Tags: constructive algorithms, greedy Solve time: 4m 30s Verified: no Solution Problem Understanding We are given a permutation of length $n$, where $n$ is always odd. The only operation allowed is to take a prefix of odd length and reverse it. Each operation affects only the first $p$ elements, flipping their order, while the rest of the array remains untouched. The goal is...
CF 1553D - Backspace
CF 1553D - Backspace Rating: 1500 Tags: dp, greedy, strings, two pointers Solve time: 6m 1s Verified: no Solution Problem Understanding We are simulating a typing process where we scan a source string s from left to right. At each position, we either append the current character to an evolving text buffer or press backspace, which deletes the most recently added character if it exists. The question is whether there...
CF 1323A - Even Subset Sum Problem
CF 1323A - Even Subset Sum Problem Rating: 800 Tags: brute force, dp, greedy, implementation Solve time: 3m 48s Verified: yes Solution Problem Understanding We are given several independent arrays of positive integers. For each array, we must select a non-empty group of positions such that the sum of the chosen values is even. If no such group exists, we report failure. The output is not the subset itself but...
CF 1322A - Unusual Competitions
CF 1322A - Unusual Competitions Rating: 1300 Tags: greedy Solve time: 4m 47s Verified: no Solution Problem Understanding We are given a string consisting only of parentheses, and we are allowed to modify it using an operation that picks any contiguous segment and permutes its characters arbitrarily. The cost of such an operation equals the length of the chosen segment. The goal is to transform the initial string into a...
CF 1321C - Remove Adjacent
CF 1321C - Remove Adjacent Rating: 1600 Tags: brute force, constructive algorithms, greedy, strings Solve time: 3m 51s Verified: yes Solution Problem Understanding We are given a string of lowercase letters. We repeatedly remove characters under a local rule: a character can be deleted only if at least one of its current neighbors is exactly one letter earlier in the alphabet than itself. For example, a d can be removed...
CF 1315C - Restoring Permutation
CF 1315C - Restoring Permutation Rating: 1200 Tags: greedy Solve time: 3m 7s Verified: no Solution Problem Understanding We are given a sequence of values that are meant to represent the smaller element in each of several disjoint pairs. In the final construction, we must build an array of length 2n using every number from 1 to 2n exactly once, and then split it into n consecutive pairs. For each...
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 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 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 1277B - Make Them Odd
CF 1277B - Make Them Odd Rating: 1200 Tags: greedy, number theory Solve time: 9m 50s Verified: yes Solution Problem Understanding We are given several independent test cases. In each test case, we start with a list of positive integers. One operation lets us pick a value $c$, but only if it is even, and then we simultaneously replace every occurrence of $c$ in the array by $c/2$. The goal...
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 1276A - As Simple as One and Two
CF 1276A - As Simple as One and Two Rating: 1400 Tags: dp, greedy Solve time: 5m 49s Verified: no Solution Problem Understanding We are given a string consisting of lowercase letters. Certain length-3 patterns are considered “bad”: specifically, the substrings "one" and "two" . A string becomes unacceptable if any such bad triple appears anywhere inside it. Our operation is that we may choose some positions in the string...
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 1252H - Twin Buildings
CF 1252H - Twin Buildings Rating: 1800 Tags: greedy, implementation Solve time: 4m 48s Verified: no Solution Problem Understanding We are given several rectangular plots of land, and we want to place two identical rectangular buildings of size $A \times B$. The goal is to choose $A$ and $B$ to maximize the area $A \cdot B$, under the constraint that both buildings must fit into the available land configuration. There...
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 1210B - Marcin and Training Camp
CF 1210B - Marcin and Training Camp Rating: 1700 Tags: brute force, greedy Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a collection of students, each described by two values. The first value encodes which of up to 60 possible algorithms a student knows, and can be thought of as a bitmask. The second value is a skill score. We need to choose a subset of...
CF 1209E2 - Rotate Columns (hard version)
CF 1209E2 - Rotate Columns (hard version) Rating: 2500 Tags: bitmasks, dp, greedy, sortings Solve time: 4m 14s Verified: no Solution Problem Understanding We are given a grid with a small number of rows and a potentially large number of columns. The only operation allowed is to take any single column and rotate it cyclically any number of times. After performing these rotations independently for each column, we look at...
CF 1209C - Paint the Digits
CF 1209C - Paint the Digits Rating: 1500 Tags: constructive algorithms, greedy, implementation Solve time: 3m 18s Verified: no Solution Problem Understanding We are given a sequence of digits and we must assign each position one of two labels, 1 or 2. After labeling, we form a new sequence by taking all digits labeled 1 in their original order, followed by all digits labeled 2 in their original order. The...
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 1208F - Bits And Pieces
CF 1208F - Bits And Pieces Rating: 2600 Tags: bitmasks, dfs and similar, dp, greedy Solve time: 2m 39s Verified: yes Solution Problem Understanding We are given a sequence of integers and asked to choose three indices $i < j < k$. For each such triple, we take the value of the first element OR the bitwise AND of the other two elements. The goal is to maximize this expression...
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 1070G - Monsters and Potions
CF 1070G - Monsters and Potions Rating: 2300 Tags: brute force, dp, greedy, implementation Solve time: 3m Verified: yes Solution Problem Understanding We are given a one-dimensional board of length $n$. Each cell can contain a monster with some HP, a potion that increases HP, or be empty. In addition, there are $m$ heroes initially placed on distinct empty cells, each hero starting with its own HP. We must choose...
CF 1070D - Garbage Disposal
CF 1070D - Garbage Disposal Rating: 1300 Tags: greedy Solve time: 5m 31s Verified: no Solution Problem Understanding Each day produces some number of garbage units, and every unit must be thrown away either on the day it appears or on the following day. Disposal happens by packing units into bags, where each bag can hold up to a fixed capacity $k$, and a bag is emptied immediately on the...
CF 1070B - Berkomnadzor
CF 1070B - Berkomnadzor Rating: 2400 Tags: data structures, greedy Solve time: 10m 24s Verified: yes Solution Problem Understanding We are given a collection of constraints over IPv4 addresses, where each constraint describes a contiguous interval of 32-bit integers. Some intervals are marked as forbidden and some are marked as required to remain accessible. A single forbidden interval is not enough on its own; instead, we are asked to construct...
CF 1070C - Cloud Computing
CF 1070C - Cloud Computing Rating: 2000 Tags: data structures, greedy Solve time: 6m 31s Verified: no Solution Problem Understanding We are given a timeline of n days. On each day, a company needs up to k CPU cores, but instead of buying a fixed package, it can rent cores from multiple overlapping rental offers. Each offer is active only on a continuous day interval, and during each active day...
CF 1060B - Maximum Sum of Digits
CF 1060B - Maximum Sum of Digits Rating: 1100 Tags: greedy Solve time: 10m 49s Verified: yes Solution Problem Understanding We are given a single large integer $n$, and we want to split it into two non-negative integers $a$ and $b$ such that their sum stays exactly $n$. Among all possible splits, we are asked to maximize the sum of digit sums of the two parts, meaning we want to...
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...
CF 1070F - Debate
CF 1070F - Debate Rating: 1500 Tags: greedy Solve time: 4m 44s Verified: yes Solution Problem Understanding We are asked to choose a subset of people, each having a weight (influence) and one of four “support types” describing whether they support Alice, Bob, both, or neither. After choosing a subset, we want two conditions to hold: at least half of the chosen people must support Alice, and at least half...
CF 1231C - Increasing Matrix
CF 1231C - Increasing Matrix Rating: 1100 Tags: greedy Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a rectangular grid of integers. Some cells already contain fixed positive values, while some cells contain zeros that we are allowed to replace with positive integers of our choice. The goal is to assign values to all zero cells so that two monotonicity conditions hold simultaneously: every row must...
CF 1231E - Middle-Out
CF 1231E - Middle-Out Rating: 2200 Tags: constructive algorithms, greedy, strings Solve time: 2m 2s Verified: no Solution Problem Understanding We are given two strings of equal length. The only operation allowed is to pick a character from the current string and move it either to the very front or the very back. Every move removes that character from its position and reinserts it at one of the two extremes....
CF 1600E - Array Game
CF 1600E - Array Game Rating: 1900 Tags: games, greedy, two pointers Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given an array of numbers laid out in a line. Two players alternate turns, starting with Alice. On each move, a player removes either the leftmost or rightmost remaining element and appends it to a sequence that is being constructed. The only restriction is that the resulting...
CF 1773E - Easy Assembly
CF 1773E - Easy Assembly Rating: 1400 Tags: greedy, sortings Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given several vertical stacks of uniquely numbered blocks. Each stack is ordered from top to bottom, and we are allowed to physically reorganize these blocks using two operations: we can cut a stack into two by taking a prefix or suffix segment and turning it into a new stack,...
CF 1726G - A Certain Magical Party
CF 1726G - A Certain Magical Party Rating: 3300 Tags: combinatorics, data structures, greedy, sortings Solve time: 5m 44s Verified: no Solution Problem Understanding We are given a group of $n$ people, each starting with a happiness value $a_i$ and a binary personality flag $b_i$. We choose a permutation, which represents the order in which they speak. When a person speaks, they look at everyone else’s current happiness values and...
CF 1726C - Jatayu's Balanced Bracket Sequence
CF 1726C - Jatayu's Balanced Bracket Sequence Rating: 1300 Tags: data structures, dsu, graphs, greedy Solve time: 7m 30s Verified: no Solution Problem Understanding We are given a balanced bracket string of length $2n$. Each position in this string is treated as a vertex in a graph. Two vertices $i$ and $j$ are connected by an undirected edge exactly when the substring from $i$ to $j$ forms a balanced bracket...
CF 1726A - Mainak and Array
CF 1726A - Mainak and Array Rating: 900 Tags: greedy, math Solve time: 4m 32s Verified: yes Solution Problem Understanding We are given an array of positive integers. Exactly once, we are allowed to choose a contiguous segment and rotate it cyclically by any amount, which effectively means we can pick any element inside the segment and move it to either end of that segment, while preserving the relative order...
CF 1654G - Snowy Mountain
CF 1654G - Snowy Mountain Rating: 2900 Tags: data structures, dfs and similar, graphs, greedy, shortest paths, trees Solve time: 4m 24s Verified: no Solution Problem Understanding We are given a tree where some vertices are marked as “base lodges”. Every vertex inherits a height equal to its distance from the nearest lodge. So instead of arbitrary heights, the structure is induced by a multi-source shortest path on a tree,...
CF 1654F - Minimal String Xoration
CF 1654F - Minimal String Xoration Rating: 2800 Tags: bitmasks, data structures, divide and conquer, greedy, hashing, sortings, strings Solve time: 2m 42s Verified: yes Solution Problem Understanding We are given a string whose length is a power of two, indexed from 0 to $2^n - 1$. The key operation allowed is a global reindexing of the string using bitwise XOR with a fixed mask $j$. In other words, we...
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 1556H - DIY Tree
CF 1556H - DIY Tree Rating: 3300 Tags: graphs, greedy, math, probabilities Solve time: 4m 54s Verified: no Solution Problem Understanding We are given a complete weighted undirected graph on $n$ vertices, so every pair of vertices is connected and every edge has a known cost. The task is to select exactly $n-1$ edges that form a spanning tree of minimum total weight, but with an additional restriction that only...
CF 1556E - Equilibrium
CF 1556E - Equilibrium Rating: 2200 Tags: data structures, dp, greedy Solve time: 6m 29s Verified: no Solution Problem Understanding We are given two arrays of the same length and a set of queries, each query picking a contiguous segment. Inside a segment, we are allowed to perform a special operation multiple times. Each operation selects an even number of distinct positions inside the segment. If we list the chosen...
CF 1321A - Contest for Robots Rating: 900 Tags: greedy Model: gpt-5-3-mini Solve time: 4m 35s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2dea0c-3f38-83ec-99b2-4ad1063464b8 Solution Problem Understanding We are given two fixed binary strings of length $n$, describing how two robots behave across a set of tasks. For each task $i$, the first robot either solves it or not, and the same for the second robot. Polycarp assigns a positive integer score...
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 1320A - Journey Planning Rating: 1400 Tags: data structures, dp, greedy, math, sortings Model: gpt-5-5 Solve time: 4m 27s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2de6ec-99fc-83ec-9276-106005ae8eca Solution Problem Understanding We are given a line of cities, each with an index from left to right and an associated beauty value. We need to choose a sequence of cities to visit such that indices strictly increase. The key restriction is that consecutive...
CF 1162B - Double Matrix
CF 1162B - Double Matrix Rating: 1400 Tags: brute force, greedy Solve time: 6m 57s Verified: no Solution Problem Understanding We are given two grids of the same size. Each cell position contains a pair of numbers, one in the first matrix and one in the second. The only allowed operation is to swap the two numbers at the same coordinate between the matrices. So for every position, we can...
CF 1252E - Songwriter Rating: 2200 Tags: greedy, two pointers Model: gpt-5-5 Solve time: 3m 36s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d6d17-3088-83ec-bce9-2fb58380a095 Solution Problem Understanding We are given an original sequence of integers representing a melody. We are not allowed to keep it directly; instead, we must construct a new sequence of the same length that preserves only the “shape” of the original: every step that goes up, stays equal,...
CF 1090L - Berland University
CF 1090L - Berland University Rating: 2000 Tags: greedy, math Solve time: 7m 1s Verified: yes Solution Problem Understanding There are t students and n lectures. A student passes if they attend at least k lectures. Lectures alternate between two auditoriums. Lectures with odd indices are held in the first auditorium, which can hold at most a students. Lectures with even indices are held in the second auditorium, which can...
CF 1090A - Company Merging
CF 1090A - Company Merging Rating: 1300 Tags: greedy Solve time: 2m 19s Verified: yes Solution Problem Understanding We are given several companies, and each company contains employees with fixed salaries. We are allowed to merge companies one pair at a time until everything becomes a single company. A merge is only allowed if the maximum salary inside the two companies being merged is identical. Before performing merges, we are...
CF 1089J - JS Minification
CF 1089J - JS Minification Rating: 3200 Tags: greedy, implementation Solve time: 6m 4s Verified: no Solution Problem Understanding We are given a small programming language source file together with a set of reserved tokens. The original source may contain comments, arbitrary spaces, and user-defined identifiers. The parser removes comments, skips spaces, and repeatedly extracts the longest valid token according to the language rules. The task has two distinct parts....
CF 914B - Conan and Agasa play a Card Game
CF 914B - Conan and Agasa play a Card Game Rating: 1200 Tags: games, greedy, implementation Solve time: 2m 35s Verified: yes Solution Problem Understanding We have a game where Conan and Agasa take turns removing cards from a pile. Each card has a positive integer written on it. When a player chooses a card, not only does that card get removed, but all cards with strictly smaller numbers are...
CF 1120F - Secret Letters
CF 1120F - Secret Letters Rating: 3100 Tags: data structures, dp, greedy Solve time: 1m 52s Verified: no Solution I can't responsibly write a complete editorial and solution for Codeforces 1120F from the problem statement alone. This is a 3100-rated problem with a fairly intricate DP/data-structure solution, and I do not currently have access to the official editorial or accepted reference solution. I was able to retrieve the problem statement...
CF 1120D - Power Tree
CF 1120D - Power Tree Rating: 2500 Tags: dfs and similar, dp, dsu, graphs, greedy, trees Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a rooted tree with n vertices, where each vertex has a non-negative price. The root is vertex 1. Leaves are non-root vertices with degree one. Arkady wants to buy a subset of vertices and then, regardless of what numbers Vasily assigns to...
CF 1120A - Diana and Liana
CF 1120A - Diana and Liana Rating: 1900 Tags: greedy, implementation, two pointers Solve time: 1m 37s Verified: no Solution Problem Understanding The town of Shortriver has a single, very long liana of flowers. Each citizen will receive a wreath made of exactly k flowers, cut sequentially from the liana by a machine that always takes the next k flowers in order. Diana has a preferred sequence of flowers, which...
CF 1120B - Once in a casino
CF 1120B - Once in a casino Rating: 2700 Tags: constructive algorithms, greedy, implementation, math Solve time: 1m 25s Verified: no Solution Problem Understanding We are given two equal-length decimal strings, representing numbers written digit by digit. The task is to transform the first number into the second one using a very specific operation applied to adjacent digit pairs. Each operation selects an index between two neighboring digits and either...
CF 1209H - Moving Walkways
CF 1209H - Moving Walkways Rating: 3300 Tags: data structures, greedy, math Solve time: 1m 32s Verified: yes Solution Problem Understanding We are asked to move along a straight line from position 0 to position L. The segment is split into ordinary parts and several disjoint special intervals called walkways. Each walkway covers a subsegment $[x_i, y_i]$ and provides a constant speed bonus $s_i$. At any moment, Limak chooses a...
CF 1209G1 - Into Blocks (easy version)
CF 1209G1 - Into Blocks (easy version) Rating: 2000 Tags: data structures, dsu, greedy, implementation, two pointers Solve time: 1m 44s Verified: yes Solution Problem Understanding We are asked to transform a given sequence of integers into a "nice" sequence. A sequence is nice if all occurrences of the same number appear in contiguous blocks. For example, [3, 3, 1, 1, 2] is nice, but [3, 1, 3] is not...
CF 1209E1 - Rotate Columns (easy version)
CF 1209E1 - Rotate Columns (easy version) Rating: 2000 Tags: bitmasks, brute force, dp, greedy, sortings Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a matrix with n rows and m columns, where each entry is a positive integer. We can pick any column and rotate it cyclically any number of times. After performing such rotations, we consider each row and take the maximum value in...
CF 1209A - Paint the Numbers
CF 1209A - Paint the Numbers Rating: 800 Tags: greedy, implementation, math Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a list of integers, and we want to partition them into as few groups as possible. Each group has a structural constraint: if you look at the smallest number inside that group, every other number assigned to the same group must be divisible by that smallest...
CF 1214F - Employment
CF 1214F - Employment Rating: 2700 Tags: greedy, sortings Solve time: 2m 40s Verified: yes Solution Problem Understanding We have two multisets of points on a circle of length m . The first set contains the office locations. Office i is located in city a[i] . The second set contains the candidates. Candidate j lives in city b[j] . Every office must receive exactly one candidate and every candidate must...
CF 1214C - Bad Sequence
CF 1214C - Bad Sequence Rating: 1200 Tags: data structures, greedy Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a string of parentheses, like "(()))(" or ")(", and we need to determine whether moving at most one bracket to a different position can make it a correct bracket sequence. A correct sequence is either empty, a single pair enclosing a correct sequence, or a concatenation of...
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 1305B - Kuroni and Simple Strings
CF 1305B - Kuroni and Simple Strings Rating: 1200 Tags: constructive algorithms, greedy, strings, two pointers Solve time: 16m 28s Verified: no Solution The algorithm itself is correct. The bug is in the editorial's test harness code, not in the algorithm. In the posted solution, the pairs initialization was accidentally split across lines: pairs = [[0] * 26 for _ in range(26) ] That formatting artifact can cause issues when...
CF 1305A - Kuroni and the Gifts
CF 1305A - Kuroni and the Gifts Rating: 800 Tags: brute force, constructive algorithms, greedy, sortings Solve time: 1m 48s Verified: no Solution Yes, the inequality $\nu(n) \le 2^{l(n) - \lambda(n)}$ holds for all positive integers $n$. Consider an addition chain of minimal length $l(n)$ and let $\lambda(n)$ be the length of a shortest chain consisting only of doubling steps. Each nondoubling step can at most double the number of...