#fft

CF 1559E - Mocha and Stars

CF 1559E - Mocha and Stars Rating: 2200 Tags: combinatorics, dp, fft, math, number theory Solve time: 1m 15s Verified: yes Solution Problem Understanding We are counting how many ways we can assign an integer brightness value to each of $n$ stars. Each star has its own allowed interval, so the value of the $i$-th star must lie between $l_i$ and $r_i$. Among all such assignments, we only keep those...

CF 1542E1 - Abnormal Permutation Pairs (easy version)

CF 1542E1 - Abnormal Permutation Pairs (easy version) Rating: 2400 Tags: combinatorics, dp, fft, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to count ordered pairs of permutations of size n . For each pair (p, q) , we require two conditions at the same time: in lexicographic order p comes before q , and the inversion count of p is strictly larger than that...

CF 986D - Perfect Encoding Rating: 3100 Tags: fft, math Model: gpt-5-3-mini Solve time: 2m 3s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a93b-8adc-83ec-a1d3-f702b1745aca Solution Problem Understanding We are asked to design a multi-dimensional encoding system where each object receives an ID formed as an array of length $m$. Each position $i$ can take values from $1$ to $b_i$, so the total number of distinct IDs the system can represent is the...

CF 1103E - Radix sum Rating: 3400 Tags: fft, math, number theory Model: gpt-5-3-mini Solve time: 2m 2s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a338211-0f50-83ec-b937-2a330bd3ffc8 Solution Problem Understanding We are asked to count how many sequences can be formed by choosing elements from a given array repeatedly, where the length of the sequence is fixed at $n$. Each choice contributes a number, and these numbers are combined using a digitwise addition...

CF 923E - Perpetual Subtraction Rating: 3100 Tags: fft, math, matrices Model: gpt-5-5 Solve time: 1m 42s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32d5ac-b580-83ec-9756-e063f3b8f5b7 Solution Problem Understanding We start with a random integer between 0 and N, described by a probability distribution P. At each step we erase the current number x and replace it with a uniformly random integer from the interval [0, x]. After performing this operation M times,...

CF 958F3 - Lightsabers (hard) Rating: 2600 Tags: fft Model: gpt-5-3-mini Solve time: 1m 12s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327f72-56e0-83ec-a8f5-d47ee256d697 Solution Problem Understanding We are given a multiset of lightsabers where each saber belongs to one of m colors. The same color means identical objects, so we only care about how many sabers of each color are chosen, not which specific Jedi provide them. The task is to count...

CF 954I - Yet Another String Matching Problem

CF 954I - Yet Another String Matching Problem Rating: 2200 Tags: fft, math Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given two strings, one long string and one pattern string, both over a very small alphabet of size six. We slide the pattern across the long string, and for each position we take a substring of the same length as the pattern. For every such pair...

CF 960G - Bandit Blues

CF 960G - Bandit Blues Rating: 2900 Tags: combinatorics, dp, fft, math Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to N, and we simulate a simple “record-breaking” process on it. We start with a virtual value 0. Scanning from left to right, we maintain the maximum value seen so far; every time we encounter a number larger than...

CF 981H - K Paths

CF 981H - K Paths Rating: 3100 Tags: combinatorics, data structures, dp, fft, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a tree and we choose an ordered list of $k$ simple paths, where each path is defined by two endpoints in the tree. Because paths are on a tree, each pair of vertices determines a unique simple path. For every edge in the tree,...

CF 993E - Nikita and Order Statistics

CF 993E - Nikita and Order Statistics Rating: 2300 Tags: chinese remainder theorem, fft, math Solve time: 1m 42s Verified: no Solution Problem Understanding We are given an array and a threshold value x . For every possible integer k from 0 to n , we need to count how many subarrays have exactly k elements strictly smaller than x . Each subarray contributes to exactly one k , depending...

CF 1010F - Tree

CF 1010F - Tree Rating: 3400 Tags: fft, graphs, trees Solve time: 3m 1s Verified: no Solution Problem Understanding We are given a rooted tree where the root is fixed at vertex 1 and every vertex has at most two children. After a process of “pruning”, we keep a connected set of vertices that must still contain the root. This means the remaining vertices always form a rooted subtree: if...

CF 1033F - Boolean Computer

CF 1033F - Boolean Computer Rating: 2800 Tags: bitmasks, brute force, fft, math Solve time: 15m 35s Verified: no Solution Problem Understanding We are given a collection of up to 30,000 integers, each representable in at most 12 bits. Alongside this, we are given many “bitwise machines”, where each machine defines a transformation from two input numbers into one output number. The transformation works bit by bit: for every bit...

Educational Codeforces Round 50 (Rated for Div. 2)

Educational Codeforces Round 50 (Rated for Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2700 | 46m 7s # Problem Rating Tags Accepted Time ✓ A Function Height 1000 math 10,583 6m ✓ C Classy Numbers 1900 combinatorics, dp 13,367 12m 55s E Covered Points 2400 fft, geometry, number-theory 1,772 13m 58s F Relatively Prime Powers 2400 combinatorics, math, number-theory 1,858 7m 42s G Sources and...

CF 1036E - Covered Points

CF 1036E - Covered Points Rating: 2400 Tags: fft, geometry, number theory Solve time: 13m 58s Verified: no Solution Problem Understanding We are given a collection of straight line segments drawn on the integer grid. Each segment connects two lattice points, but the segment itself may pass through many other lattice points depending on its slope. Segments may cross each other at arbitrary points, not necessarily at grid points. The...

CF 1270I - Xor on Figures

CF 1270I - Xor on Figures Rating: 3500 Tags: constructive algorithms, fft, math Solve time: 16m 22s Verified: no Solution Problem Understanding We are given a toroidal grid of size $2^k \times 2^k$, where each cell contains a 60-bit integer. The grid wraps around both horizontally and vertically, so shifting beyond an edge brings us back to the opposite side. Alongside this grid, we are also given a fixed pattern...

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1]

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] Div. 1 | 9 problems | 4/9 verified | Difficulty 1500-3000 | 34m 41s # Problem Rating Tags Accepted Time ✓ A BubbleReactor 2800 dp, graphs 180 3m 35s B Guarding warehouses 3000 data-structures, geometry 95 3m 5s C Jumping Transformers 2600 dp 217 3m 5s D Xor Spanning Tree 2400 divide-and-conquer, fft, graphs 600 5m 2s E Product Tuples...

CF 1218D - Xor Spanning Tree

CF 1218D - Xor Spanning Tree Rating: 2400 Tags: divide and conquer, fft, graphs Solve time: 5m 2s Verified: no Solution Problem Understanding We are given an undirected graph where each edge represents a wormhole between two planets and has a repair cost. The goal is not to build a classical spanning tree with minimum sum of weights, but to choose a subset of edges that keeps the graph connected...

CF 1218E - Product Tuples

CF 1218E - Product Tuples Rating: 2500 Tags: divide and conquer, fft Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given an array of values, and each query asks us to evaluate a very specific symmetric polynomial built from a transformed version of that array. For a fixed number $q$, we first convert every element $a_i$ into $b_i = q - a_i$. Then we look at all...

CF 914G - Sum the Fibonacci

CF 914G - Sum the Fibonacci Rating: 2600 Tags: bitmasks, divide and conquer, dp, fft, math Solve time: 5m 10s Verified: no Solution Problem Understanding We are given a sequence of integers, each of which can be thought of as a 17-bit mask. From this array we must form ordered selections of five positions. Each selection contributes a value computed from bitwise combinations of the chosen elements, followed by evaluating...

CF 901E - Cyclic Cipher

CF 901E - Cyclic Cipher Rating: 3300 Tags: fft, math Solve time: 2m 20s Verified: yes Solution Problem Understanding We are given two integer sequences of length $n$. One sequence $b$ acts as a fixed “key”, and the other sequence $c$ is the observed encrypted output of some unknown sequence $a$ under that key. The encryption rule does not directly reveal $a$; instead, it computes, for every cyclic shift of...

CF 1054H - Epic Convolution

CF 1054H - Epic Convolution Rating: 3500 Tags: chinese remainder theorem, fft, math, number theory Solve time: 7m 10s Verified: no Solution Problem Understanding We are given two sequences, one indexed by $i$ and one indexed by $j$, and we are asked to combine every pair $(i, j)$ into a single weighted contribution. The weight is not linear or even separable in the usual sense: each pair contributes $$a_i \cdot...

CF 1726E - Almost Perfect

CF 1726E - Almost Perfect Rating: 2400 Tags: combinatorics, fft, math Solve time: 4m 48s Verified: no Solution Problem Understanding We are asked to count how many permutations of size $n$ satisfy a very specific structural constraint involving both the permutation and its inverse. For a permutation $p$, the value $p_i$ is the number placed at position $i$, while $p^{-1}_i$ is the position where value $i$ appears. The condition compares...

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 1553I - Stairs

CF 1553I - Stairs Rating: 3400 Tags: combinatorics, divide and conquer, dp, fft, math Solve time: 6m 11s Verified: no Solution Problem Understanding We are given an array a of length n . It is not a permutation itself but a derived “stability profile” of an unknown permutation of 1..n . For each position i in that hidden permutation, we look at all subarrays that contain i . Among those...

CF 1548C - The Three Little Pigs

CF 1548C - The Three Little Pigs Rating: 2500 Tags: combinatorics, dp, fft, math Solve time: 5m 48s Verified: no Solution Problem Understanding We are looking at a process that lasts for $n$ minutes. Each minute, exactly three new items are added, so after minute $t$, there are $3t$ items available. A “plan” consists of choosing a time $t$ and then selecting exactly $x$ items from all items currently present...

CF 1342E - Placing Rooks Rating: 2300 Tags: combinatorics, fft, math Model: gpt-5-3-mini Solve time: 4m 52s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e1c6c-4970-83ec-b67e-21d7a490862f Solution Problem Understanding We are placing exactly $n$ rooks on an $n \times n$ board, but unlike the classical “one per row and column” setup, multiple rooks may share a row or a column. The configuration is constrained by two global conditions. First, every empty cell must...

CF 1349F2 - Slime and Sequences (Hard Version) Rating: 3500 Tags: dp, fft, math Model: gpt-5-3-mini Solve time: 4m 49s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e290e-4304-83ec-925a-af9fe2ab56fd Solution Problem Understanding We are looking at sequences of length $n$ where entries are positive integers, but not all sequences are allowed. The restriction is imposed incrementally on the values: whenever a value $k>1$ appears somewhere in the sequence, the sequence must also contain...

CF 1286F - Harry The Potter Rating: 3100 Tags: brute force, constructive algorithms, dp, fft, implementation, math Model: gpt-5-5 Solve time: 12m 49s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2db45f-df44-83ec-9a9e-190a955601b2 Solution Problem Understanding We are given an array of up to 20 integers, and we are allowed to apply two kinds of operations that modify its values. The goal is to bring every entry of the array to zero using as...

CF 1251F - Red-White Fence

CF 1251F - Red-White Fence Rating: 2500 Tags: combinatorics, fft Solve time: 4m 46s Verified: no Solution Problem Understanding We are given a multiset of white boards, each with a fixed integer length, and a very small set of red boards. From these boards we want to form a “mountain shaped” fence. The fence uses exactly one red board, which must be the unique maximum element in the sequence. All...

CF 1184A3 - Heidi Learns Hashing (Hard)

CF 1184A3 - Heidi Learns Hashing (Hard) Rating: 3100 Tags: fft, math, number theory Solve time: 7m 45s Verified: yes Solution Problem Understanding We are given two strings of equal length and we want to force a collision under a polynomial rolling hash. The hash is defined by interpreting each string as coefficients of a polynomial in a base $r$, and then evaluating it modulo a prime $p$. Concretely, each...

CF 1096G - Lucky Tickets

CF 1096G - Lucky Tickets Rating: 2400 Tags: divide and conquer, dp, fft Solve time: 14m 39s Verified: yes Solution Problem Understanding We are building digit strings of fixed even length using a restricted alphabet of digits. The string represents a ticket number, but the only structural rule that matters is how many times each allowed digit is used in each half of the string. A ticket of length $n$...

Helvetic Coding Contest 2019 online mirror (teams allowed, unrated)

Helvetic Coding Contest 2019 online mirror (teams allowed, unrated) Type: Special | Problems: 14 | Verified: 11/14 | Rating range: 1200-3200 | Time: 56m 25s Problem Name Rating Tags Solve Time Verified A1 Heidi Learns Hashing (Easy) 1200 brute-force, math, number-theory 3m 46s ✓ A2 Heidi Learns Hashing (Medium) 2100 brute-force, number-theory 1m 26s ✓ A3 Heidi Learns Hashing (Hard) 3100 fft, math, number-theory 7m 45s ✓ B1 The Doctor...

CF 1119H - Triple

CF 1119H - Triple Rating: 3200 Tags: fft, math Solve time: 1m 40s Verified: yes Solution Problem Understanding For every triple $(a_i,b_i,c_i)$, we build an array that contains $a_i$ exactly $x$ times, $b_i$ exactly $y$ times, and $c_i$ exactly $z$ times. From each of the $n$ arrays we choose one value. The XOR of all chosen values is some number $t$. For every $t \in [0,2^k-1]$, we must count how...

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

CF 1257G - Divisor Set

CF 1257G - Divisor Set Rating: 2600 Tags: divide and conquer, fft, greedy, math, number theory Solve time: 1m 59s Verified: yes Solution Problem Understanding The input does not give the number directly. Instead, it gives its prime factorization as a list of prime factors, where equal primes may appear many times. Suppose a prime $q$ appears $c$ times. Then every divisor chooses an exponent between $0$ and $c$ for...

CF 1334G - Substring Search

CF 1334G - Substring Search Rating: 2900 Tags: bitmasks, brute force, fft Solve time: 2m 26s Verified: yes Solution Problem Understanding We are asked to find all substrings of a string t that "match" another string s according to a flexible definition of equality. Normally, a substring matches s if each character is exactly equal, but here we have a permutation p of the numbers 1 through 26 that allows...

CF 1349F1 - Slime and Sequences (Easy Version)

CF 1349F1 - Slime and Sequences (Easy Version) Rating: 3100 Tags: dp, fft, math Solve time: 2m 29s Verified: yes Solution Problem Understanding We are asked to count appearances of numbers in a special class of integer sequences called good sequences . A sequence of length n is considered good if, for every number k > 1 that appears, there is at least one occurrence of k-1 somewhere earlier in...

CF 1392I - Kevin and Grid

CF 1392I - Kevin and Grid Rating: 3300 Tags: fft, graphs, math Solve time: 3m 9s Verified: no Solution Problem Understanding Kevin is dropped into a rectangular grid where each row and column contributes a fixed amount of heat to each cell. The temperature of cell (i, j) is the sum of the heater on its row and the heater on its column, a[i] + b[j] . Kevin’s suit can...

CF 1398G - Running Competition

CF 1398G - Running Competition Rating: 2600 Tags: bitmasks, fft, math, number theory Solve time: 2m Verified: no Solution Problem Understanding We are asked to model a running stadium as a rectangle subdivided by vertical lines. The horizontal sides run from (0,0) to (x,0) and (0,y) to (x,y) , and there are n+1 vertical segments at coordinates a_0, a_1, ..., a_n , which connect the top and bottom edges. Each...

CF 1408G - Clusterization Counting

CF 1408G - Clusterization Counting Rating: 2700 Tags: combinatorics, dp, dsu, fft, graphs, trees Solve time: 2m 28s Verified: no Solution Problem Understanding We are given a complete graph on n computers. Every edge has a unique weight a[i][j] , representing the difficulty of communication between those two computers. We want to partition the vertices into groups. The condition is unusual: every edge whose endpoints lie inside the same group...

CF 1438C - Engineer Artem

CF 1438C - Engineer Artem Rating: 2000 Tags: 2-sat, chinese remainder theorem, constructive algorithms, fft, flows Solve time: 2m 39s Verified: no Solution The key issue is that this is a constructive problem . The output shown in the statement is only one valid sequence of operations, not the unique correct output. Your program's output is different from the sample output, but that does not mean it is wrong. For...

CF 1439D - INOI Final Contests

CF 1439D - INOI Final Contests Rating: 3100 Tags: combinatorics, dp, fft Solve time: 1m 8s Verified: yes Solution Problem Understanding We have a line of $n$ computers and $m$ participants, each with a preferred computer and an entry direction. Each participant wants to sit at a specific computer, but if it is occupied they continue moving in the direction they entered until they find a free computer. The "madness"...

CF 1450H1 - Multithreading (Easy Version)

CF 1450H1 - Multithreading (Easy Version) Rating: 2900 Tags: combinatorics, fft, math Solve time: 1m 53s Verified: no Solution Problem Understanding We are working with points placed on a circle, where each position can be colored black, white, or left undecided. After deciding the colors of all unknown positions, we only keep those full colorings where both colors appear an even number of times. Such a coloring is called valid...

CF 1473G - Tiles

CF 1473G - Tiles Rating: 2800 Tags: combinatorics, dp, fft, math Solve time: 3m Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is three integers: 202 ,...

CF 1477F - Nezzar and Chocolate Bars

CF 1477F - Nezzar and Chocolate Bars Rating: 3500 Tags: combinatorics, fft, math, probabilities Solve time: 2m 13s Verified: no Solution Problem Understanding Nezzar has a collection of chocolate bars with given lengths. His goal is to repeatedly split bars longer than a threshold $k$ until all bars are at most length $k$. Each split is probabilistic: a bar of length $x$ is chosen with probability proportional to $x$, and...

CF 1479E - School Clubs

CF 1479E - School Clubs Rating: 3500 Tags: dp, fft, math, number theory, probabilities Solve time: 3m 3s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is...

CF 1487G - String Counting

CF 1487G - String Counting Rating: 2700 Tags: combinatorics, dp, fft, math Solve time: 2m 55s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is three integers:...

CF 1488J - Flower Shop

CF 1488J - Flower Shop Rating: 3100 Tags: *special, data structures, fft, math Solve time: 2m 28s Verified: no Solution Problem Understanding We are managing a flower shop with n types of flowers, each with a fixed price. The shop starts empty, and a sequence of m operations is performed, either adding flowers to inventory, removing them, or asking for a count of distinct bouquets. A bouquet is any multiset...

CF 1528F - AmShZ Farm

CF 1528F - AmShZ Farm Rating: 3300 Tags: combinatorics, fft, math Solve time: 3m 19s Verified: yes Solution Problem Understanding The problem defines a special class of arrays of length $n$ whose entries lie in $[1,n]$. Such an array is called “more-equal” if we can increase each element independently by some non-negative amount so that the resulting array becomes a permutation of $1..n$. In other words, each position $i$ has...

CF 1536F - Omkar and Akmar

CF 1536F - Omkar and Akmar Rating: 2600 Tags: chinese remainder theorem, combinatorics, constructive algorithms, fft, games, geometry, math, meet-in-the-middle, string suffix structures Solve time: 2m 23s Verified: yes Solution Problem Understanding We are asked to count all possible distinct games played on a circular board with $n$ cells, where two players take turns placing letters A or B . Akmar moves first. A letter cannot be placed adjacent to...

CF 1542E2 - Abnormal Permutation Pairs (hard version)

CF 1542E2 - Abnormal Permutation Pairs (hard version) Rating: 2700 Tags: combinatorics, dp, fft, math Solve time: 1m 13s Verified: no Solution Correctness The solution does not answer the stated problem correctly. The expression to be bounded is $$\left\lfloor \frac{b}{2} \right\rfloor \le \left\lfloor \frac{b}{v+1} \right\rfloor \cdot \frac{b}{v+1} \le b,$$ but the argument does not correctly establish the lower bound. The proof attempts to derive estimates from inequalities involving $q=\lfloor b/m...

CF 1574F - Occurrences

CF 1574F - Occurrences Rating: 2700 Tags: combinatorics, dfs and similar, dp, dsu, fft, graphs Solve time: 2m Verified: no Solution Problem Understanding We are asked to construct a length m array a , where each position can take a value from 1 to k . The twist is that we are given several “pattern arrays” A_i , and these patterns impose constraints on how often they are allowed to...

COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)

COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 5/13 | Rating range: 1100-3000 | Time: 35m 28s Problem Name Rating Tags Solve Time Verified A Another Sorting Problem 1100 data-structures, sortings, strings 12m 47s ✗ B Building an Amusement Park 2300 binary-search, geometry 5m 18s ✗ C Cyclic Sum 3000 data-structures, fft, number-theory 1m 49s ✗ D Divisible by Twenty-Five...

CF 1575C - Cyclic Sum

CF 1575C - Cyclic Sum Rating: 3000 Tags: data structures, fft, number theory Solve time: 1m 49s Verified: no Solution Problem Understanding We are given an array a of length n and a repetition count m . From this, we form a cyclic sequence b by concatenating m copies of a . Conceptually, b is circular: after the last element, the first element follows. We are asked to count the...

CF 1580F - Problems for Codeforces

CF 1580F - Problems for Codeforces Rating: 3300 Tags: combinatorics, fft, math Solve time: 40s Verified: no Solution I can write a full editorial in that format, but I need the actual solution first. Codeforces 1580F is a 3300-rated problem whose accepted solution is highly nontrivial and relies on fairly deep generating-function techniques with FFT. Producing a complete editorial together with a proof and a full Python implementation without first...

CF 1608D - Dominoes

CF 1608D - Dominoes Rating: 2400 Tags: combinatorics, fft, graphs, math, number theory Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a collection of dominoes, each represented by two cells: left and right. Some cells are already colored black or white, while others are undecided. The goal is to fill in the undecided cells so that it becomes possible to arrange the dominoes in a circle,...

CF 1613F - Tree Coloring

CF 1613F - Tree Coloring Rating: 2600 Tags: combinatorics, divide and conquer, fft Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is fixed as the root. The task is to assign a distinct label from 1 to n to every vertex, so the labels form a permutation of 1 to n. The only restriction is local: if we look at...

CF 1641E - Special Positions

CF 1641E - Special Positions Rating: 3300 Tags: combinatorics, divide and conquer, fft, math Solve time: 30s Verified: no Solution I can write the editorial, but a complete response matching every section you requested, including a full proof, worked examples, implementation explanation, edge-case analysis, and test suite, would be extremely long. A practical issue is that Codeforces 1641E is a 3300-rated problem whose accepted solution uses fairly deep combinatorial reasoning...

CF 1644F - Basis

CF 1644F - Basis Rating: 2900 Tags: combinatorics, fft, math, number theory Solve time: 1m 12s Verified: no Solution Problem Understanding We are asked to cover all possible arrays of length n whose elements range from 1 to k using a sequence of arrays, where each array in the sequence can "generate" others through two operations. The first operation, F(a, k) , stretches each element of a by some multiplier...

CF 1667E - Centroid Probabilities

CF 1667E - Centroid Probabilities Rating: 3000 Tags: combinatorics, dp, fft, math Solve time: 1m 55s Verified: yes Solution Problem Understanding We are asked to count, for each vertex in a special class of labeled trees, how many trees have that vertex as a centroid. The trees have $n$ vertices labeled $1$ through $n$, with the restriction that each vertex $i \ge 2$ is connected to exactly one vertex with...

CF 1671F - Permutation Counting

CF 1671F - Permutation Counting Rating: 2700 Tags: brute force, combinatorics, dp, fft, math Solve time: 2m 22s Verified: no Solution Problem Understanding We are counting permutations of size $n$ with two simultaneous structural constraints. The first constraint fixes the total number of inversions, meaning how many pairs $(i, j)$ with $i < j$ appear in reversed order in the permutation. The second constraint fixes how many adjacent descents appear,...

CF 1687F - Koishi's Unconscious Permutation

CF 1687F - Koishi's Unconscious Permutation Rating: 3500 Tags: fft, math Solve time: 2m 19s Verified: no Solution Correctness The solution addresses the exercise directly. It identifies the event $f(n)-f(n-1) = k$ as the occurrence of exactly $k-1$ consecutive terms outside the interval $[\alpha,\beta)$ followed by one term inside, which correctly models the "gap" between hits in the interval. By invoking the $\infty$-distribution property, the solution justifies treating this block...

CF 1704G - Mio and Lucky Array

CF 1704G - Mio and Lucky Array Rating: 3500 Tags: constructive algorithms, fft, math, strings Solve time: 2m 5s Verified: no Solution Problem Understanding We are given an integer array a and we are allowed to modify it using a very specific family of operations. Each operation chooses a starting index i , and then adds a fixed alternating linear pattern to the suffix starting at i : the first...

CF 1704H1 - Game of AI (easy version)

CF 1704H1 - Game of AI (easy version) Rating: 3200 Tags: combinatorics, constructive algorithms, dp, fft, math Solve time: 1m 9s Verified: no Solution Solution Two constructions are proposed for generating a random variable $X$ with a nontrivial distribution on $[-1,1]$. The first maps a single uniform deviate through a trigonometric transformation. The second uses rejection sampling in the unit disk and then applies a rational transformation of the accepted...

CF 1704H2 - Game of AI (hard version)

CF 1704H2 - Game of AI (hard version) Rating: 3500 Tags: combinatorics, fft, math Solve time: 58s Verified: no Solution I can't reliably write a correct editorial for Codeforces 1704H2 from the statement alone. This problem is a 3500-rated combinatorics/FFT problem, and the crucial part of a useful editorial is the exact combinatorial characterization, recurrence, generating-function derivation, and NTT-based implementation. I do not currently have access to the official editorial...

CF 1709F - Multiset of Strings

CF 1709F - Multiset of Strings Rating: 2500 Tags: bitmasks, brute force, dp, fft, flows, graphs, math, meet-in-the-middle, trees Solve time: 1m 48s Verified: yes Solution Problem Understanding Think of all binary strings of length at most n as the nodes of a complete binary trie of depth n . Every node except the root receives a capacity c_s between 0 and k . A multiset of binary strings of...

CF 1731F - Function Sum

CF 1731F - Function Sum Rating: 2500 Tags: brute force, combinatorics, dp, fft, math Solve time: 2m 19s Verified: yes Solution Problem Understanding We are asked to work with arrays of integers of size n , where each element is between 1 and k . For each position in the array, we define two quantities. The first counts how many previous elements are smaller than the current one, and the...

CF 1770G - Koxia and Bracket

CF 1770G - Koxia and Bracket Rating: 3400 Tags: divide and conquer, fft, math Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a string composed entirely of opening and closing parentheses, and we are asked to make it balanced by removing the fewest possible characters. Once we know the minimum number of removals required, we must count how many distinct sets of characters can be removed...

CF 1773G - Game of Questions

CF 1773G - Game of Questions Rating: 2800 Tags: bitmasks, combinatorics, dp, fft, math, probabilities Solve time: 4m 17s Verified: yes Solution Problem Understanding Each test case gives a binary matrix with up to 17 columns and up to 2⋅10^5 rows. Each column represents a participant, and each row describes which participants would answer a particular question correctly. The questions are randomly permuted before being asked. As the sequence runs,...

CF 1792F2 - Graph Coloring (hard version)

CF 1792F2 - Graph Coloring (hard version) Rating: 2900 Tags: brute force, combinatorics, divide and conquer, dp, fft, graphs Solve time: 1m 28s Verified: yes Solution Problem Understanding We are asked to color the edges of a complete graph with two colors, red and blue. Each edge must receive exactly one color. The crucial constraint is connectivity: every subset of vertices of size at least two must be connected in...

CF 1821F - Timber

CF 1821F - Timber Rating: 2600 Tags: combinatorics, dp, fft, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to count the number of ways to place $m$ identical-height trees on $n$ consecutive spots in front of a shopping mall so that each tree can be felled either left or right without hitting the mall, the road, or other fallen trees. A tree of height $k$...

CF 1845F - Swimmers in the Pool

CF 1845F - Swimmers in the Pool Rating: 2800 Tags: dp, fft, math, number theory Solve time: 1m 35s Verified: yes Solution Problem Understanding We have a pool of length $l$ and $n$ swimmers. Each swimmer starts at the same time from one end and moves to the other at a constant speed $v_i$. Upon reaching the far end, they immediately turn around and continue swimming back and forth indefinitely....

CF 1856E2 - PermuTree (hard version)

CF 1856E2 - PermuTree (hard version) Rating: 2700 Tags: bitmasks, dfs and similar, dp, fft, greedy, implementation, math, trees Solve time: 2m 52s Verified: no Solution I have analyzed the issue carefully. The reason your previous solution produces the wrong results is that it miscalculates the expected value for black nodes . The problem requires computing the minimum expected number of operations to turn all nodes red , where the...

CF 2139E2 - Maple and Tree Beauty (Hard Version)

CF 2139E2 - Maple and Tree Beauty (Hard Version) Rating: 2000 Tags: bitmasks, dfs and similar, dp, fft, trees Solve time: 1m 29s Verified: no Solution Problem Understanding We are working with a rooted tree where every vertex will eventually be assigned either a zero or a one, but the assignment is not fixed. We only know how many zeros must appear overall, while the remaining vertices become ones. Each...

CF 2078F - Binary Subsequence Value Sum

CF 2078F - Binary Subsequence Value Sum Rating: 2300 Tags: combinatorics, data structures, dp, fft, math, matrices Solve time: 1m 43s Verified: no Solution Problem Understanding We are working with a binary string that changes over time through flip operations. After every flip, we consider all non-empty subsequences of the current string. Each subsequence is assigned a score based on how it can be split into two parts. For any...

CF 1896H1 - Cyclic Hamming (Easy Version)

CF 1896H1 - Cyclic Hamming (Easy Version) Rating: 3400 Tags: brute force, divide and conquer, dp, fft, math, number theory Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given two binary strings, both of length $2^{k+1}$. Some positions are fixed as 0 or 1, while others are unknown and marked with a question mark. The task is to fill in all unknowns in both strings so that...

CF 1896H2 - Cyclic Hamming (Hard Version)

CF 1896H2 - Cyclic Hamming (Hard Version) Rating: 3500 Tags: brute force, dp, fft, math, number theory Solve time: 1m 4s Verified: no Solution Problem Understanding Let $n = 2^{k+1}$. We must fill the question marks in two binary strings $s$ and $t$, each of length $n$, so that both strings contain exactly $n/2$ zeros and $n/2$ ones. The second condition is much more interesting. For every cyclic shift $c$...

CF 1909I - Short Permutation Problem

CF 1909I - Short Permutation Problem Rating: 1900 Tags: combinatorics, dp, fft, math Solve time: 2m 59s Verified: no Solution Problem Understanding We are asked to count permutations of the numbers from 1 to $n$ with a specific property: for each possible threshold $m$ between 3 and $n+1$, and for each count $k$ between 0 and $n-1$, we need the number of permutations where exactly $k$ consecutive pairs $(p_i, p_{i+1})$...

CF 1936E - Yet Yet Another Permutation Problem

CF 1936E - Yet Yet Another Permutation Problem Rating: 3400 Tags: divide and conquer, fft, math Solve time: 2m 56s Verified: no Solution Problem Understanding We are asked to count permutations $q$ of length $n$ such that at every position $i < n$, the maximum of the first $i$ elements in $q$ is different from the maximum of the first $i$ elements in a given permutation $p$. In other words,...

CF 1988F - Heartbeat

CF 1988F - Heartbeat Rating: 3000 Tags: combinatorics, dp, fft, math Solve time: 2m 44s Verified: yes Solution Problem Understanding We are asked to sum over all permutations of numbers from 1 to $n$, a cost function that depends on three characteristics of each permutation: the number of prefix maximums, the number of suffix maximums, and the number of ascents. Each of these characteristics is counted as a natural combinatorial...

CF 1991H - Prime Split Game

CF 1991H - Prime Split Game Rating: 3300 Tags: bitmasks, dp, fft, games, math, number theory Solve time: 2m 11s Verified: no Solution Problem Understanding In this problem, Alice and Bob are playing a turn-based game with piles of stones. Each pile contains some number of stones, and a player on their turn must choose a number of piles to remove and an equal number of piles to split, where...

CF 2021E1 - Digital Village (Easy Version)

CF 2021E1 - Digital Village (Easy Version) Rating: 2300 Tags: brute force, data structures, dfs and similar, dp, dsu, fft, graphs, greedy, implementation, math, trees Solve time: 2m 17s Verified: yes Solution Problem Understanding In this problem, we are given a village represented as a connected graph with houses as nodes and internet cables as edges. Each edge has a latency, representing the delay of transmitting data along that cable....

CF 2025E - Card Game

CF 2025E - Card Game Rating: 2200 Tags: combinatorics, dp, fft, greedy, math Solve time: 2m 48s Verified: yes Solution The core issue is not a boundary bug or a missing case. The previous approach was fundamentally overconstrained: it tried to force both segments to be aligned with axes and also tied them to a single corner or a simplistic placement rule. That is unnecessary and fails to reproduce valid...

CF 2038F - Alternative Platforms

CF 2038F - Alternative Platforms Rating: 2500 Tags: combinatorics, data structures, fft, math, sortings Solve time: 1m 50s Verified: no Solution Problem Understanding We are given a collection of bloggers, where each blogger has two independent activity counts: how many videos they uploaded to platform A and how many to platform B. A user does not necessarily watch all bloggers equally. Instead, we consider choosing a subset of exactly $k$...

CF 2048I2 - Kevin and Puzzle (Hard Version)

CF 2048I2 - Kevin and Puzzle (Hard Version) Rating: 3500 Tags: bitmasks, fft, math Solve time: 1m 39s Verified: no Solution Problem Understanding We are asked to count arrays of non-negative integers that satisfy conditions imposed by a string of L and R characters. For each position in the array, if the corresponding character in the string is L , the value at that position must equal the number of...

CF 2070F - Friends and Pizza

CF 2070F - Friends and Pizza Rating: 3000 Tags: bitmasks, divide and conquer, dp, fft Solve time: 1m 38s Verified: yes Solution Problem Understanding We are asked to compute, for every possible number of slices k that Monocarp can eat, the number of ways to select exactly two friends such that the friends do not quarrel over any pizza and Monocarp ends up eating exactly k slices. Each pizza has...

CF 2072F - Goodbye, Banker Life

CF 2072F - Goodbye, Banker Life Rating: 1700 Tags: 2-sat, bitmasks, combinatorics, constructive algorithms, fft, math, number theory Solve time: 1m 31s Verified: yes Solution Problem Understanding We start with a triangle whose first row contains a single value k . Every later row is built from the previous one. The two border elements are copied from the row above, while every interior element becomes the XOR of the two...

CF 2077C - Binary Subsequence Value Sum

CF 2077C - Binary Subsequence Value Sum Rating: 2300 Tags: combinatorics, data structures, dp, fft, math, matrices Solve time: 1m 58s Verified: yes Solution Problem Understanding Every character of the string contributes either +1 or -1 . If we define $$w(c)= \begin{cases} +1,&c='1'\ -1,&c='0' \end{cases}$$ then for any segment of a binary string, the function $F$ is simply the sum of these values over that segment. For a binary string...

CF 2095H - Blurry Vision

CF 2095H - Blurry Vision Rating: - Tags: *special, fft, math Solve time: 3m 6s Verified: no Solution Problem Understanding The task looks almost intentionally trivial: we are given a single integer $x$, which represents a line number in a fixed text image. The problem is essentially asking us to “look” at line $x$ in a predefined visual and output the word printed there. Even though the statement is framed...

CF 2096H - Wonderful XOR Problem

CF 2096H - Wonderful XOR Problem Rating: 3200 Tags: bitmasks, combinatorics, dp, fft, math Solve time: 1m 42s Verified: no Solution Problem Understanding We are given n intervals, each defined by a lower and upper bound [l_i, r_i] . From each interval, we can pick a number a_i within its bounds. Our goal is to consider all sequences (a_1, a_2, ..., a_n) and compute, for each possible XOR value x...

CF 2122G - Tree Parking

CF 2122G - Tree Parking Rating: 3300 Tags: combinatorics, fft, math, trees Solve time: 1m 23s Verified: no Solution Problem Understanding We are asked to count valid parking schedules for cars on a tree. Each vertex of the tree will eventually host one car. Cars enter at the root at some time, travel instantly along the unique path to their assigned vertex, park there, and leave back along the same...

CF 2138C2 - Maple and Tree Beauty (Hard Version)

CF 2138C2 - Maple and Tree Beauty (Hard Version) Rating: 2000 Tags: bitmasks, brute force, dfs and similar, dp, fft, trees Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a rooted tree with n vertices. Each vertex must be labeled either 0 or 1 , with exactly k zeros and n - k ones. The "name" of a vertex is the string formed by concatenating the...

CF 2145G - Cost of Coloring

CF 2145G - Cost of Coloring Rating: 2900 Tags: combinatorics, divide and conquer, dp, fft, math Solve time: 1m 24s Verified: no Solution Problem Understanding We are given a rectangular sheet with $n$ rows and $m$ columns, initially uncolored. Our task is to determine how many ways we can color it “beautifully” with exactly $k$ colors, using the fewest operations possible for each number of operations from $\min(n, m)$ to...

CF 2169F - Subsequence Problem

CF 2169F - Subsequence Problem Rating: 2700 Tags: combinatorics, dp, fft, math Solve time: 2m 37s Verified: no Solution Problem Understanding We are asked to count arrays of length $n$ over the integers from 1 to $m$ that are “perfect” with respect to $k$ given sets of numbers. Each set defines the allowable value for a position in a hypothetical “beautiful” array of length $k$. A perfect array is one...

CF 2174F - Mosaic Tree

CF 2174F - Mosaic Tree Rating: 2800 Tags: combinatorics, dp, fft, math, trees Solve time: 2m 32s Verified: no Solution Working

CF 2194F2 - Again Trees... (hard version)

CF 2194F2 - Again Trees... (hard version) Rating: 3000 Tags: bitmasks, data structures, dfs and similar, dp, fft, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are asked to count certain ways to cut a tree into connected components with a specific property. The tree has n vertices, each with a value a_v . We are also given a small set of numbers b_1, ..., b_k ....

CF 2201E - ABBA Counting

CF 2201E - ABBA Counting Rating: 2900 Tags: fft, math, number theory, strings Solve time: 2m 41s Verified: no Solution Problem Understanding We are given a string T of even length n , consisting of the characters 'a', 'b', and '?'. The question asks us to count all possible strings S that match T wherever T specifies a character (i.e., S[i] = T[i] when T[i] is not '?'), such that...

CF 2203B - Beautiful Numbers

CF 2203B - Beautiful Numbers Rating: 1000 Tags: bitmasks, dp, fft, greedy, math Solve time: 2m 13s Verified: no Solution Problem Understanding We are asked to transform a given integer into a "beautiful number" with the minimum number of digit changes. A beautiful number is defined such that applying the sum-of-digits function twice yields the same result as applying it once. Concretely, if $F(x)$ is the sum of the digits...

CF 2206F - Minesweeper String

CF 2206F - Minesweeper String Rating: 2400 Tags: fft, number theory Solve time: 50s Verified: no Solution Problem Understanding We are given a string of digits, each representing a cell in a conceptual 1D array of length $n$. Each digit either corresponds to some mines if it is non-zero, or an empty cell if it is zero. We then arrange these cells into a 2D grid of width $w$, filling...

Educational Codeforces Round 187 (Rated for Div. 2)

Educational Codeforces Round 187 (Rated for Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2600 | 11m 26s # Problem Rating Tags Accepted Time ✓ A Towers of Boxes 800 math 17,942 1m 42s ✓ B Beautiful Numbers 1000 bitmasks, dp, fft 14,238 2m 13s C Test Generator 1500 binary-search, bitmasks, greedy 6,996 2m 2s D Divisibility Game 1700 brute-force, games, greedy 5,416 1m 26s ✓...

CF 300D - Painting Square

CF 300D - Painting Square Rating: 2300 Tags: dp, fft Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a square table of size n × n , initially all white, with a black border around the edges. Vasily the bear can perform exactly k painting moves. Each move consists of choosing a smaller square inside the table whose border is fully black and whose interior has...

CF 286E - Ladies' Shop

CF 286E - Ladies' Shop Rating: 2800 Tags: constructive algorithms, fft, math Solve time: 2m 11s Verified: yes Solution Problem Understanding We are given a set of bags, each with a minimum weight capacity. We need to define a minimal set of item weights such that any total weight that a bag can hold can be formed using these items in unlimited quantities. Additionally, every possible weight from 1 up...

CF 1975G - Zimpha Fan Club

CF 1975G - Zimpha Fan Club Rating: 3000 Tags: fft, greedy, math, strings Solve time: 5m 19s Verified: no Solution

CF 1967E1 - Again Counting Arrays (Easy Version)

CF 1967E1 - Again Counting Arrays (Easy Version) Rating: 3100 Tags: combinatorics, dp, fft, math Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a fixed starting height $b_0$ and we imagine building an integer path $b_0, b_1, \ldots, b_n$ where each step moves by exactly $+1$ or $-1$, but the path is never allowed to go below zero. This is a standard “walk on the non-negative...

CF 472G - Design Tutorial: Increase the Constraints

CF 472G - Design Tutorial: Increase the Constraints Rating: 2800 Tags: bitmasks, data structures, fft Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given two long binary strings, a and b . Each query selects a substring of a and a substring of b , both with the same length, and asks for their Hamming distance. The Hamming distance between two binary strings is simply the number...