#constructive-algorithms
CF 1267I - Intriguing Selection
CF 1267I - Intriguing Selection Rating: 2600 Tags: brute force, constructive algorithms, implementation, interactive, sortings Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a hidden set of $2n$ distinct values, one per player, and we can only compare two players at a time and learn which one is stronger. The goal is not to fully reconstruct the ranking, but to identify exactly which $n$ players belong...
CF 1267L - Lexicography
CF 1267L - Lexicography Rating: 1800 Tags: constructive algorithms, strings Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a multiset of letters whose total size is exactly enough to form $n$ strings, each of fixed length $l$. The task is not just to form any $n$ strings, but to arrange all these letters into $n$ words such that when the words are sorted lexicographically, the $k$-th...
CF 1267H - Help BerLine
CF 1267H - Help BerLine Rating: 3200 Tags: constructive algorithms Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a line of $n$ positions, each representing a base station placed from left to right. Each station must be assigned a frequency between 1 and 24. The twist is that stations do not become active immediately: they are activated one by one in a given order, forming a...
CF 1267D - DevOps Best Practices
CF 1267D - DevOps Best Practices Rating: 2800 Tags: constructive algorithms Solve time: 2m 36s Verified: no Solution Problem Understanding Each server stores two independent kinds of information. First, for each of the three features, we know whether the company wants that feature to be installed on that server. Second, for each server and each feature, we know whether that server successfully passes tests for that feature. The system we...
CF 1267C - Cactus Revenge
CF 1267C - Cactus Revenge Rating: 3500 Tags: constructive algorithms Solve time: 43s Verified: no Solution I can absolutely write a full 3500-level editorial in the exact style you want, but I can’t do it correctly from just the name “Codeforces 1267C - Cactus Revenge” without the actual problem statement. That specific problem is from a very hard round and the solution depends heavily on the exact constraints on the...
CF 1250M - SmartGarden
CF 1250M - SmartGarden Rating: 2500 Tags: constructive algorithms, divide and conquer Solve time: 1m 24s Verified: yes Solution Problem Understanding The garden is an $n \times n$ grid where each cell is either a plant that must be watered or a slab that must never be touched. The layout is highly structured: all diagonal cells are slabs, and every cell strictly below the diagonal that touches the diagonal also...
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 931B - World Cup
CF 931B - World Cup Rating: 1200 Tags: constructive algorithms, implementation Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given a single-elimination tournament with $n$ teams labeled from 1 to $n$. The structure of the tournament is fixed and mechanical: in every round, the remaining teams are sorted by their original labels, then paired consecutively, so team 1 plays 2, 3 plays 4, and so on. Winners...
CF 932C - Permutation Cycle
CF 932C - Permutation Cycle Rating: 1600 Tags: brute force, constructive algorithms Solve time: 3m 16s Verified: no Solution Problem Understanding We are asked to construct a permutation of the numbers from 1 to N such that every position behaves in a very specific cyclic way. The permutation defines a deterministic walk: starting from a position i, we repeatedly apply the permutation mapping and observe how many steps it takes...
CF 932A - Palindromic Supersequence
CF 932A - Palindromic Supersequence Rating: 800 Tags: constructive algorithms Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a single lowercase string $A$. The task is to construct another string $B$ such that two conditions hold at the same time: $B$ must read the same forward and backward, and the string $A$ must appear inside $B$ as a subsequence, meaning we can delete some characters from...
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 1023D - Array Restoration
CF 1023D - Array Restoration Rating: 1700 Tags: constructive algorithms, data structures Solve time: 2m 36s Verified: no Solution Problem Understanding We are given a final array of length n that was produced by repeatedly painting segments with increasing labels from 1 to q . During the i -th operation, a chosen segment is overwritten entirely with value i , and later operations can overwrite earlier ones. Every position is...
CF 1023E - Down or Right
CF 1023E - Down or Right Rating: 2100 Tags: constructive algorithms, interactive, matrices Solve time: 2m 14s Verified: no Solution Problem Understanding We are given an unknown $n \times n$ grid where each cell is either open or blocked. Movement is only allowed from a cell to its right neighbor or its bottom neighbor, and only if the destination cell is open. The goal is to determine any valid path...
CF 1025G - Company Acquisitions
CF 1025G - Company Acquisitions Rating: 3200 Tags: constructive algorithms, math Solve time: 4m 3s Verified: yes Solution Problem Understanding We are given a system of startups arranged into a structure where some startups are already “active” and others are “acquired” and attached to exactly one active startup. Each acquired startup forms a rooted tree of dependents under an active root, and every active startup is the root of its...
CF 1025E - Colored Cubes
CF 1025E - Colored Cubes Rating: 2700 Tags: constructive algorithms, implementation, matrices Solve time: 5m 51s Verified: yes Solution Problem Understanding We are given an $n \times n$ grid and $m$ identical-sized cubes, each having a unique color. Each cube starts on a distinct cell, and each also has a target cell where it must eventually be placed. Some cubes may already start on their destination, but otherwise every cube...
CF 1025C - Plasticine zebra
CF 1025C - Plasticine zebra Rating: 1600 Tags: constructive algorithms, implementation Solve time: 5m 11s Verified: no Solution Problem Understanding We are given a binary string made of two symbols, black and white, and we want to extract a long contiguous segment that alternates perfectly between the two colors. The segment must be consecutive in the final arrangement, but we are allowed to rearrange the original string using a very...
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 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 1553G - Common Divisor Graph
CF 1553G - Common Divisor Graph Rating: 2700 Tags: brute force, constructive algorithms, dsu, graphs, hashing, math, number theory Solve time: 3m 40s Verified: yes Solution Problem Understanding We are given a fixed set of nodes, each labeled by a distinct integer. Two nodes are connected if their labels share any prime factor. This means the graph is determined entirely by the prime factorizations of the given numbers. For each...
CF 1553E - Permutation Shift
CF 1553E - Permutation Shift Rating: 2100 Tags: brute force, combinatorics, constructive algorithms, dfs and similar, dsu, graphs, math Solve time: 4m 48s Verified: yes Solution Problem Understanding We start from the identity permutation, which is simply the numbers from 1 to n in order. Someone first rotates this array cyclically to the right by an unknown shift k, and then performs at most m arbitrary swaps of elements. After...
CF 1386A - Colors
CF 1386A - Colors Rating: 2700 Tags: *special, binary search, constructive algorithms, interactive Solve time: 7m 19s Verified: no Solution Problem Understanding We are interacting with a hidden system that has chosen an integer threshold $C$ between 1 and $N$. We can think of the numbers from 1 to $N$ as positions on a line, and every time we pick a position, we are effectively “dyeing” hair with that color....
CF 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 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 1305D - Kuroni and the Celebration
CF 1305D - Kuroni and the Celebration Rating: 1900 Tags: constructive algorithms, dfs and similar, interactive, trees Solve time: 3m 8s Verified: no Solution Problem Understanding We are given a fixed tree with up to 1000 vertices. Somewhere in this tree there is a hidden root vertex $r$, which represents Kuroni’s hotel. The structure of the tree is known, but the root is not. The only way to extract information...
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 1214H - Tiles Placement
CF 1214H - Tiles Placement Rating: 2800 Tags: constructive algorithms, dfs and similar, trees Solve time: 5m 42s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices, where each vertex represents a square in a pedestrian network. Each vertex must be assigned one of $k$ colors. The requirement is global and path-based: if you take any simple path in the tree that contains exactly $k$ vertices,...
CF 1214E - Petya and Construction Set
CF 1214E - Petya and Construction Set Rating: 2000 Tags: constructive algorithms, graphs, math, sortings, trees Solve time: 2m 50s Verified: no Solution Problem Understanding We are asked to build a graph on $2n$ labeled vertices using exactly $2n-1$ edges. Since a connected graph with $2n$ vertices and $2n-1$ edges is necessarily a tree, the construction is really about designing a tree on these labeled nodes. The vertices come in...
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 1208C - Magic Grid
CF 1208C - Magic Grid Rating: 1800 Tags: constructive algorithms Solve time: 6m 28s Verified: no Solution Problem Understanding We are asked to fill an $n \times n$ table with all integers from $0$ to $n^2 - 1$ exactly once, so every number is used in a permutation of the grid cells. The extra constraint is global: every row must have the same bitwise XOR of its entries, and every...
CF 1070L - Odd Federalization
CF 1070L - Odd Federalization Rating: 2600 Tags: constructive algorithms Solve time: 5m 37s Verified: no Solution Problem Understanding We are given an undirected graph of cities and roads. The task is to partition all vertices into some number of groups, and we are allowed to choose how many groups we want. Once the partition is fixed, every edge becomes either internal to a group or connects two different groups....
CF 1070M - Algoland and Berland
CF 1070M - Algoland and Berland Rating: 3000 Tags: constructive algorithms, divide and conquer, geometry Solve time: 6m 42s Verified: no Solution Problem Understanding We are given two sets of points in the plane, one set belonging to Algoland and the other to Berland. The task is to construct exactly $a + b - 1$ straight line segments, each connecting one Berland city to one Algoland city. Every segment becomes...
CF 1053E - Euler tour
CF 1053E - Euler tour Rating: 3500 Tags: constructive algorithms, trees Solve time: 4m 56s Verified: yes Solution Problem Understanding We are given a sequence of length $2n - 1$, which is supposed to represent the order in which a squirrel visits vertices of some tree during a full traversal. The traversal has a specific rule: consecutive numbers in the sequence correspond to adjacent vertices in the tree, and the...
CF 1060H - Sophisticated Device
CF 1060H - Sophisticated Device Rating: 3300 Tags: constructive algorithms Solve time: 1m 44s Verified: yes Solution Problem Understanding We are working in a very unusual computational model: instead of directly manipulating variables, we interact with an array of hidden memory cells. Only two of them initially contain unknown values, while all others are initialized to one. The hidden values in cell 1 and cell 2 are the inputs we...
CF 1078E - Negative Time Summation
CF 1078E - Negative Time Summation Rating: 3400 Tags: constructive algorithms Solve time: 3m 52s Verified: yes Solution Problem Understanding We are given a very unusual computational model: a robot walks on an infinite grid while executing a program, and the grid itself can be rewritten and even “rewound in time”. Two binary integers are initially written on the grid. One number starts at cell $(0,1)$ and extends leftwards along...
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 1773J - Jumbled Trees
CF 1773J - Jumbled Trees Rating: 2900 Tags: constructive algorithms, math Solve time: 3m 16s Verified: no Solution Problem Understanding Each edge in a connected undirected graph carries a value that starts at zero. We are allowed to perform operations, and each operation picks a spanning tree of the graph and adds a single chosen value $v$ to every edge in that tree. The goal is to reach a configuration...
CF 1773F - Football
CF 1773F - Football Rating: 800 Tags: constructive algorithms Solve time: 5m 22s Verified: no Solution Problem Understanding We are given aggregated statistics for a football team over a sequence of matches. Instead of knowing individual match results, we only know three numbers: how many matches were played, how many total goals the team scored across all matches, and how many total goals it conceded. The task is to reconstruct...
CF 1773A - Amazing Trick
CF 1773A - Amazing Trick Rating: 1900 Tags: constructive algorithms, graph matchings, math, probabilities Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a permutation $a$ of size $n$, meaning every number from $1$ to $n$ appears exactly once. We are allowed to apply two permutations $q$ first and then $p$, so that the final position $i$ receives the value originally at position $p[q[i]]$. In other words,...
CF 1726D - Edge Split
CF 1726D - Edge Split Rating: 2000 Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, probabilities, trees Solve time: 3m 56s Verified: no Solution Problem Understanding We are given a connected undirected graph with a small number of extra edges beyond a tree. For each edge, we must decide whether it is colored red or blue. After fixing the coloring, we look at two induced subgraphs: one formed...
CF 1726B - Mainak and Interesting Sequence
CF 1726B - Mainak and Interesting Sequence Rating: 1100 Tags: bitmasks, constructive algorithms, math Solve time: 4m 46s Verified: no Solution Problem Understanding We are asked to construct a sequence of positive integers of length $n$ whose sum is fixed to $m$, but with an additional constraint that comes from a peculiar XOR condition applied to value ordering rather than positions. For every value $x$ appearing in the sequence, if...
CF 1725H - Hot Black Hot White
CF 1725H - Hot Black Hot White Rating: 1800 Tags: constructive algorithms, math Solve time: 4m 26s Verified: no Solution Problem Understanding We are given an array of integers, each representing the strength of a magical stone. We must split these stones into two equal groups and assign each stone one of two colors. The only constraint on the coloring is that exactly half of the stones must be black...
CF 1654H - Three Minimums
CF 1654H - Three Minimums Rating: 3500 Tags: combinatorics, constructive algorithms, divide and conquer, dp, fft, math Solve time: 5m 50s Verified: no Solution Problem Understanding We are asked to count permutations of the numbers from 1 to n that satisfy two independent kinds of restrictions. The first restriction is positional and local. We are given a short comparison string s of length m. It fixes whether each adjacent pair...
CF 1578M - The Mind
CF 1578M - The Mind Rating: 2700 Tags: constructive algorithms, interactive, probabilities Solve time: 6m 11s Verified: no Solution Problem Understanding Each test gives us a hand of five distinct numbers between 1 and 100. Two players independently receive such hands, and each player only sees their own five numbers. From those five numbers, only the smallest one matters for the actual game, because the rules force every player to...
CF 1578A - Anti-Tetris
CF 1578A - Anti-Tetris Rating: 2800 Tags: constructive algorithms, graphs, shortest paths Solve time: 3m 52s Verified: no Solution Problem Understanding We are given a final board configuration of a grid-based stacking process where multiple small polyomino-like pieces were dropped one after another. Each piece is connected in four directions, has at most seven cells, and is identified by a letter. All cells with the same letter belong to the...
CF 1556D - Take a Guess
CF 1556D - Take a Guess Rating: 1800 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 9m 7s Verified: no Solution Problem Understanding We are given a hidden array of integers, and we cannot access its elements directly. The only way to learn anything about the array is by asking queries on pairs of indices. Each query returns either the bitwise AND or bitwise OR of two elements. Using only...
CF 1090F - How to Learn You Score
CF 1090F - How to Learn You Score Rating: 2600 Tags: constructive algorithms, interactive Solve time: 6m 5s Verified: no Solution I can’t safely produce a correct, detailed editorial for Codeforces 1090F from the information given here, because the actual problem statement (what the interaction allows, what the judge returns, and what needs to be reconstructed) is missing. For a 2600-rated interactive constructive problem, the entire solution hinges on very...
CF 1090D - Similar Arrays
CF 1090D - Similar Arrays Rating: 1800 Tags: constructive algorithms Solve time: 2m 13s Verified: yes Solution Problem Understanding We are given a set of positions $1 \dots n$ and a list of constraints between some pairs of positions. Each constraint tells us the relationship between the values at two indices: either the first is greater than the second, smaller, or equal. The exact values of the array are lost,...
CF 1090C - New Year Presents
CF 1090C - New Year Presents Rating: 2400 Tags: constructive algorithms, data structures Solve time: 3m 14s Verified: no Solution Problem Understanding We are given several boxes, each containing a set of distinct items. Each item has a type, and no box contains duplicates of the same type. The total number of items is large, and items can be moved one at a time between boxes. The goal is to...
CF 1089M - Minegraphed
CF 1089M - Minegraphed Rating: 2400 Tags: constructive algorithms, graphs Solve time: 2m 50s Verified: no Solution Got it - I can write a full Codeforces-style editorial (intuition, key idea, proof, implementation details, complexity, etc.). Please send the problem statement (or link / screenshot text), and if possible also: constraints sample input/output whether you want beginner / intermediate / advanced level explanation Once I have that, I’ll produce a proper...
CF 1089E - Easy Chess
CF 1089E - Easy Chess Rating: 1700 Tags: constructive algorithms Solve time: 2m 15s Verified: yes Solution Problem Understanding We are given an $n \times n$ chessboard and need to assign the numbers from $1$ to $n^2$ to all cells exactly once. The assignment must satisfy a constraint involving “chess interaction”: the numbering order should not create unwanted adjacency between consecutive integers. In other words, if we look at cells...
CF 906B - Seating of Students
CF 906B - Seating of Students Rating: 2200 Tags: brute force, constructive algorithms, math Solve time: 6m 9s Verified: no Solution Problem Understanding We are asked to rearrange students in a classroom so that no two students who were neighbors in the original seating remain neighbors in the new arrangement. The classroom is an n × m grid, and the students are numbered sequentially from 1 to n · m...
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 1302B - DAG
CF 1302B - DAG Rating: - Tags: constructive algorithms Solve time: 2m 50s Verified: no Solution There is not enough information to diagnose the bug or provide a corrected solution. The sample 3 3 tab one bat with expected output 6 tabbat appears to belong to a string construction problem, but you have not provided: the problem statement, the original Python solution, or even the name of the problem. Without...
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...
CF 1425H - Huge Boxes of Animal Toys
CF 1425H - Huge Boxes of Animal Toys Rating: 1300 Tags: constructive algorithms Solve time: 1m 49s Verified: yes Solution Problem Understanding We are asked to reason about the final box that will contain a single super toy created by sequentially combining all other toys via multiplication. Each toy has a fun value that falls into one of four ranges, which correspond to four boxes. We do not know the...
CF 1442E - Black, White and Grey Tree
CF 1442E - Black, White and Grey Tree Rating: 3000 Tags: binary search, constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a tree in which each node is coloured white, black, or grey. The goal is to remove all nodes in the minimum number of operations, where in each operation we select a connected component of nodes to...
CF 1442A - Extreme Subtraction
CF 1442A - Extreme Subtraction Rating: 1800 Tags: constructive algorithms, dp, greedy Solve time: 1m 35s Verified: no Solution Problem Understanding We are given an array of positive integers and a very specific way to reduce it. Each operation picks a prefix or a suffix, and decreases every element in that chosen segment by exactly one. The goal is to determine whether we can reduce all values to zero using...
CF 1443A - Kids Seating
CF 1443A - Kids Seating Rating: 800 Tags: constructive algorithms, math Solve time: 1m 43s Verified: no Solution Problem Understanding We are asked to seat a group of $n$ children on a line of chairs numbered from $1$ to $4n$ such that no two children can "indulge." Indulging happens when two chairs $a$ and $b$ either have a greatest common divisor of one or one divides the other. The input...
CF 1468H - K and Medians
CF 1468H - K and Medians Rating: 2200 Tags: constructive algorithms, greedy, math Solve time: 2m 29s Verified: no Solution Problem Understanding We are given a sequence of integers from 1 to n and an odd integer k. In one operation, we can pick any k elements from the current sequence, compute their median, and remove the remaining k-1 elements, leaving only the median. We repeat this operation any number...
CF 1500C - Matrix Sorting
CF 1500C - Matrix Sorting Rating: 2600 Tags: bitmasks, brute force, constructive algorithms, greedy, two pointers Solve time: 2m 46s Verified: no Solution Problem Understanding We are given two matrices, $A$ and $B$, of size $n \times m$. Each matrix consists of integers between $1$ and $n$. The task is to determine whether we can transform matrix $A$ into matrix $B$ using a sequence of stable column sorts. A stable...
CF 1510J - Japanese Game
CF 1510J - Japanese Game Rating: 2700 Tags: constructive algorithms, math Solve time: 1m 52s Verified: yes Solution Problem Understanding We are given a game with a row of tiles, each tile labeled with a positive integer. Two players, let us call them Takahashi and Aoki, play alternately. On their turn, a player chooses a contiguous segment of tiles such that all numbers in the segment share a common divisor...
CF 1523B - Lord of the Values
CF 1523B - Lord of the Values Rating: 1100 Tags: constructive algorithms Solve time: 6m 5s Verified: no Solution Problem Understanding We are given an array of even length, representing internal variables of a system. Each variable has an initial positive integer value. The goal is to change every element to its negation using two types of operations: one can add the value of a later element to an earlier...
CF 1530E - Minimax
CF 1530E - Minimax Rating: 2100 Tags: constructive algorithms, greedy, strings Solve time: 2m 33s Verified: no Solution Correctness The solution is attempting to justify formula (25) via polynomial interpolation of the product polynomial values. The general strategy, using evaluation at $2r+1$ points and Vandermonde inversion, is mathematically sound and does lead to the standard identity that coefficients of a degree-$2r$ polynomial are linear combinations of its values at $2r+1$...
CF 1530G - What a Reversal
CF 1530G - What a Reversal Rating: 3300 Tags: constructive algorithms Solve time: 49s Verified: no Solution Problem Understanding We are given two binary strings, a and b , of the same length n and an integer k . Our goal is to transform a into b by repeatedly reversing substrings of a that contain exactly k ones. Each reversal can involve any number of zeros. The output should either...
CF 1530D - Secret Santa
CF 1530D - Secret Santa Rating: 1600 Tags: constructive algorithms, flows, graphs, greedy, math Solve time: 2m 38s Verified: no Solution Problem Understanding We are asked to construct a permutation-like assignment for a group of people. Each person must give a gift to exactly one other person, and no one is allowed to give a gift to themselves. This already means we are building a permutation of size n with...
CF 1530B - Putting Plates
CF 1530B - Putting Plates Rating: 800 Tags: constructive algorithms, implementation Solve time: 3m 16s Verified: no Solution Problem Understanding We are asked to maximize the number of plates on a rectangular table, represented as an $h \times w$ grid. Plates can only be placed along the perimeter, which includes the first row, last row, first column, and last column. Furthermore, no two plates can be adjacent, either orthogonally or...
CF 1586I - Omkar and Mosaic
CF 1586I - Omkar and Mosaic Rating: 3500 Tags: combinatorics, constructive algorithms, math Solve time: 2m 14s Verified: no Solution Problem Understanding We are given an $n \times n$ grid representing a partially filled mosaic. Each cell either contains a sinoper tile S , a glaucous tile G , or is empty . . The final goal is to fill all empty cells so that the resulting mosaic is a...
CF 1599A - Weights
CF 1599A - Weights Rating: 2600 Tags: constructive algorithms, greedy, two pointers Solve time: 8m 19s Verified: no Solution Diagnosis The previous solution collected all indices where a[i] != sorted(a)[i] . That works in many cases, but fails when: The array has repeated elements . Sorting would reorder elements without changing their relative positions (stable sort). For example, in the first test case: a = [4, 4, 4, 4] sorted(a)...
CF 1648B - Integral Array
CF 1648B - Integral Array Rating: 1800 Tags: brute force, constructive algorithms, data structures, math Solve time: 6m 6s Verified: no Solution Problem Understanding We are given a multiset of positive integers, and we must decide whether it is closed under a very specific operation: taking integer division between any ordered pair of elements where the numerator is at least the denominator. Whenever we pick two values from the array,...