#number-theory
CF 1725E - Electrical Efficiency
CF 1725E - Electrical Efficiency Rating: 2500 Tags: combinatorics, data structures, dp, math, number theory, trees Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a tree of $N$ factories. Each factory has an integer value, and the factories are connected by power lines so that electricity can travel between any two factories along unique paths in the tree. For any triple of distinct factories $(x, y,...
CF 963C - Cutting Rectangle
CF 963C - Cutting Rectangle Rating: 2600 Tags: brute force, math, number theory Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a final collection of axis-aligned rectangles that come from cutting an unknown larger rectangle using only straight cuts parallel to its sides. Every cut is either horizontal or vertical, so the original rectangle is partitioned into a grid. If there are $p$ horizontal cuts and...
CF 1025D - Recovering BST
CF 1025D - Recovering BST Rating: 2100 Tags: brute force, dp, math, number theory, trees Solve time: 3m 32s Verified: yes Solution Problem Understanding We are given a sorted list of distinct integers, and we want to build a binary search tree using exactly these values as node keys. The in-order traversal of any valid BST with these keys is fixed and already matches the given order, so the only...
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 1561D1 - Up the Strip (simplified version)
CF 1561D1 - Up the Strip (simplified version) Rating: 1700 Tags: brute force, data structures, dp, math, number theory Solve time: 5m 59s Verified: no Solution Problem Understanding We are standing on a vertical strip of numbered cells from 1 at the top down to n at the bottom. A token starts at cell n, and we repeatedly move it upward until it reaches cell 1. Each move is a...
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 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 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 1070A - Find a Number
CF 1070A - Find a Number Rating: 2200 Tags: dp, graphs, number theory, shortest paths Solve time: 5m 57s Verified: yes Solution Problem Understanding We are looking for a positive integer that satisfies two simultaneous constraints. First, it must be divisible by a given integer $d$. Second, when written in decimal form, the sum of its digits must equal a given value $s$. Among all such integers, we want the...
CF 1654D - Potion Brewing Class
CF 1654D - Potion Brewing Class Rating: 2100 Tags: dfs and similar, math, number theory, trees Solve time: 9m 14s Verified: yes Solution Problem Understanding We are given a set of ingredients, each of which must appear in some positive integer quantity in a final mixture. The professor does not provide absolute amounts, but instead gives exactly $n-1$ constraints. Each constraint relates two ingredients and fixes their ratio: if ingredient...
CF 1553A - Digits Sum
CF 1553A - Digits Sum Rating: 800 Tags: math, number theory Solve time: 4m 41s Verified: yes Solution Problem Understanding We are given several independent queries. Each query provides a positive integer $n$, and we must count how many integers $x$ in the range from 1 to $n$ have a special property. For a number $x$, we compare the sum of its digits before and after adding one. If the...
CF 1209B - Koala and Lights
CF 1209B - Koala and Lights Rating: 1300 Tags: implementation, math, number theory Solve time: 11m 21s Verified: yes Solution Problem Understanding Each light in this problem behaves like a binary switch that flips its state over time. You are given an initial configuration where each light is either on or off. After that, every light follows its own periodic rule: it starts toggling at a specific time offset and...
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 914D - Bash and a Tough Math Puzzle
CF 914D - Bash and a Tough Math Puzzle Rating: 1900 Tags: data structures, number theory Solve time: 4m Verified: yes Solution Problem Understanding We maintain an array that supports two kinds of operations. The first operation asks about a segment [l, r] and a value x . We want to know whether it is possible to modify at most one element inside that segment so that the gcd of...
CF 906D - Power Tower
CF 906D - Power Tower Rating: 2700 Tags: chinese remainder theorem, math, number theory Solve time: 14m 47s Verified: yes Solution Problem Understanding We are asked to compute a "power tower" modulo a given number. Conceptually, imagine a sequence of rocks, each with a positive integer power. To construct the tower from rocks numbered l through r , we start from the top rock r and work down to l...
CF 1184A1 - Heidi Learns Hashing (Easy)
CF 1184A1 - Heidi Learns Hashing (Easy) Rating: 1200 Tags: brute force, math, number theory Solve time: 3m 46s Verified: yes Solution Problem Understanding The problem gives us a function $H(x, y) = x^2 + 2xy + x + 1$, and a positive integer $r$. We need to determine whether there exists a pair of positive integers $(x, y)$ such that $H(x, y) = r$. If multiple pairs exist, we...
CF 1184A2 - Heidi Learns Hashing (Medium)
CF 1184A2 - Heidi Learns Hashing (Medium) Rating: 2100 Tags: brute force, number theory Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a binary string y of length n . We want to count how many cyclic shift amounts k produce a situation where we can reconstruct some binary string x such that if we take x and XOR it with a circular right shift of...
CF 1210C - Kamil and Making a Stream
CF 1210C - Kamil and Making a Stream Rating: 2000 Tags: math, number theory, trees Solve time: 2m 30s Verified: yes Solution Problem Understanding We have a rooted tree with root at vertex 1 . Every vertex stores a value x[v] . For any ancestor-descendant pair (u, v) , we look at the path from u down to v and compute the gcd of all values on that path. The...
CF 1322C - Instant Noodles
CF 1322C - Instant Noodles Rating: 2300 Tags: graphs, hashing, math, number theory Solve time: 2m 42s 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 ones in the...
CF 1468L - Prime Divisors Selection
CF 1468L - Prime Divisors Selection Rating: 2700 Tags: binary search, greedy, math, number theory Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a set of up to 1000 distinct large integers, and we must pick exactly k of them. After picking, each chosen number must be assigned a prime divisor, one prime per number. The assignment is considered valid if every chosen number is divisible...
CF 1468F - Full Turn
CF 1468F - Full Turn Rating: 1700 Tags: geometry, hashing, number theory Solve time: 2m 1s Verified: yes Solution Problem Understanding We have a set of points on a plane, each representing a person, with each person initially looking at another point. Everyone rotates clockwise continuously, completing a full turn, and we are asked to count the number of distinct pairs of people who ever make “eye contact.” Eye contact...
CF 1500B - Two chandeliers
CF 1500B - Two chandeliers Rating: 2200 Tags: binary search, brute force, chinese remainder theorem, math, number theory Solve time: 1m 3s Verified: no Solution Problem Understanding We have two cyclic sequences of colors. The first chandelier repeats an array a of length n , and the second chandelier repeats an array b of length m . On day d , the first chandelier shows position (d - 1) mod...
CF 1510D - Digits
CF 1510D - Digits Rating: 2100 Tags: dp, math, number theory Solve time: 23m 14s Verified: no Solution Problem Understanding We have n cards. Each card contains a positive integer. We may choose any non-empty subset of cards and multiply all chosen numbers. The goal is not merely to obtain a product whose last decimal digit equals d . Among all such subsets, we want the subset whose product value...
CF 1558B - Up the Strip
CF 1558B - Up the Strip Rating: 1900 Tags: brute force, dp, math, number theory, two pointers Solve time: 6m 35s Verified: yes Solution Problem Understanding We are given a token placed at position $n$ on a vertical line of cells labeled from $1$ at the top to $n$ at the bottom. The goal is to count how many distinct sequences of moves can bring the token from $n$ down...
CF 1575G - GCD Festival
CF 1575G - GCD Festival Rating: 2200 Tags: math, number theory Solve time: 2m 13s Verified: no Solution Problem Understanding We are given an array of integers a with length n . The goal is to compute a sum over all pairs (i, j) where i and j are indices of the array, and for each pair we multiply two quantities: the GCD of the array elements a[i] and a[j]...
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 1609C - Complex Market Analysis
CF 1609C - Complex Market Analysis Rating: 1400 Tags: binary search, dp, implementation, number theory, schedules, two pointers Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given an array of integers and a step size e . For each starting index i , we can form a subsequence by taking every e -th element: a[i], a[i+e], a[i+2e], ... up to the point where the index does not...
CF 1609A - Divide and Multiply
CF 1609A - Divide and Multiply Rating: 900 Tags: greedy, implementation, math, number theory Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given several independent test cases. Each test case consists of a small array of integers, and we are allowed to repeatedly redistribute factors of two between elements. One operation chooses two positions, divides one chosen value by two (only if it is even), and doubles...
CF 1765M - Minimum LCM
CF 1765M - Minimum LCM Rating: 1000 Tags: math, number theory Solve time: 1m 26s Verified: yes Solution Problem Understanding We are asked to split a given integer n into two positive parts a and b so that their sum stays fixed at n . Among all such splits, we want the pair that makes the least common multiple of a and b as small as possible. So the input...
CF 2216D - RReeppeettiittiioonn
CF 2216D - RReeppeettiittiioonn Rating: 2000 Tags: brute force, implementation, number theory Solve time: 1m Verified: no Solution The value $V = 7\frac{1}{16}$ corresponds to the chi-square statistic computed from $k = 11$ categories, as in Eq. (5). The number of degrees of freedom is therefore $\nu = k - 1 = 10$. To determine whether $V$ is improbably high, one consults the line of Table 1 corresponding to $\nu...
CF 1877C - Joyboard
CF 1877C - Joyboard Rating: 1200 Tags: math, number theory Solve time: 2m 1s Verified: yes Solution Problem Understanding We choose a value $a_{n+1}$ between $0$ and $m$. After that, every earlier position is determined uniquely by $$a_i = a_{i+1} \bmod i$$ for $i=n,n-1,\dots,1$. The entire array is generated from a single starting value. We must count how many choices of $a_{n+1}$ produce exactly $k$ distinct numbers among all $n+1$...
CF 1877D - Effects of Anti Pimples
CF 1877D - Effects of Anti Pimples Rating: 1500 Tags: combinatorics, number theory, sortings Solve time: 1m 57s Verified: no Solution Problem Understanding We are given an array indexed from 1 to n. We repeatedly choose a non-empty subset of indices and mark them as special. Those chosen indices are colored black. After that, any still-unselected index becomes green if it is a multiple of at least one black index....
CF 1866B - Battling with Numbers
CF 1866B - Battling with Numbers Rating: 1400 Tags: combinatorics, math, number theory Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given two integers, but instead of being written in decimal form, they are described by their prime factorizations. One number, call it $X$, is fully determined by a list of primes and their exponents. The other number $Y$ is described the same way. The task is...
CF 1876B - Effects of Anti Pimples
CF 1876B - Effects of Anti Pimples Rating: 1500 Tags: combinatorics, number theory, sortings Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given an array of integers representing values at different positions. Chaneka can select one or more indices to color black. After that, every element at a position that is a multiple of a black index turns green. The score of a particular selection is the...
CF 1906G - Grid Game 2
CF 1906G - Grid Game 2 Rating: 2900 Tags: games, number theory Solve time: 2m 21s Verified: yes Solution Problem Understanding We are asked to analyze a two-player game played on an enormous grid of size $10^9 \times 10^9$. Each cell can be either black or white. Initially, only $N$ specific cells are black, and all others are white. Players take turns choosing a black cell. When a cell $(r,...
CF 2002F2 - Court Blue (Hard Version)
CF 2002F2 - Court Blue (Hard Version) Rating: 2800 Tags: brute force, dp, math, number theory Solve time: 2m 14s Verified: no Solution Problem Understanding We are constructing a sequence of rounds where exactly one of two players gains a point in each round. After each round we maintain two counters, one for each player, and the process is only valid if at every prefix the greatest common divisor of...
CF 2002F1 - Court Blue (Easy Version)
CF 2002F1 - Court Blue (Easy Version) Rating: 2600 Tags: brute force, dfs and similar, dp, math, number theory Solve time: 2m 57s Verified: no Solution Problem Understanding We are asked to plan a match between two performers, Lelle and Flamm, where each round produces a winner. The goal is to maximize the total score, which is computed as l * W_L + f * W_F , where W_L and...
CF 2021B - Maximize Mex
CF 2021B - Maximize Mex Rating: 1200 Tags: brute force, greedy, math, number theory Solve time: 39s Verified: no Solution Problem Understanding We start with an array of non-negative integers. The only operation allowed is to pick an element and add x to it. We may repeat this operation any number of times on any element. Adding x repeatedly has a very specific effect. An element can only move through...
CF 2034H - Rayan vs. Rayaneh
CF 2034H - Rayan vs. Rayaneh Rating: 3300 Tags: brute force, dfs and similar, dp, number theory Solve time: 2m 31s Verified: no Solution Problem Understanding We are given a set of distinct positive integers. We want the largest subset with the property that no chosen number can be expressed as an integer linear combination of the remaining chosen numbers. For integers, the subgroup generated by a collection of numbers...
CF 2034A - King Keykhosrow's Mystery
CF 2034A - King Keykhosrow's Mystery Rating: 800 Tags: brute force, chinese remainder theorem, math, number theory Solve time: 1m 20s Verified: yes Solution Problem Understanding The problem asks us to find a number that satisfies two properties relative to two given numbers, $a$ and $b$. Specifically, we want the smallest integer $m$ such that $m$ is at least as large as one of the two numbers and the remainder...
CF 2038K - Grid Walk
CF 2038K - Grid Walk Rating: 2100 Tags: brute force, dp, greedy, math, number theory Solve time: 1m 4s Verified: yes Solution Problem Understanding We are asked to move through an $n \times n$ grid from the top-left corner to the bottom-right corner, only stepping right or down. Every cell $(i, j)$ contributes a cost that depends only on its row index and column index through greatest common divisors: $\gcd(i,...
CF 2041F - Segmentation Folds
CF 2041F - Segmentation Folds Rating: 2400 Tags: brute force, dfs and similar, number theory Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a segment on the number line defined by two integers $\ell$ and $r$, and Peter can fold this segment in two specific ways: from left to right ( LTR ) and from right to left ( RTL ). Each fold is only possible...
CF 2045B - ICPC Square
CF 2045B - ICPC Square Rating: 2000 Tags: math, number theory Solve time: 2m 33s Verified: no Solution Problem Understanding We are given a hotel with $N$ floors and an unusual elevator. From floor $x$, the elevator allows a jump to any floor $y$ such that $y$ is a multiple of $x$ and the difference $y - x$ does not exceed $D$. We start at floor $S$ and want to...
CF 2124C - Subset Multiplication
CF 2124C - Subset Multiplication Rating: 1300 Tags: constructive algorithms, greedy, math, number theory Solve time: 1m 41s Verified: no Solution Problem Understanding We are given an array b that was generated from an unknown “beautiful” array a , where each element divides the next. Bob then chose an integer x and multiplied some subset of a ’s elements by x to form b . Our task is to recover...
CF 2181H - Honey Cake
CF 2181H - Honey Cake Rating: 1200 Tags: brute force, math, number theory Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a rectangular cake with dimensions $w \times h \times d$. The goal is to divide this solid into exactly $n$ smaller rectangular pieces, all identical in size. The only allowed operations are cuts that are parallel to the faces of the cake. Each dimension is...
CF 2206I - Growth Factor
CF 2206I - Growth Factor Rating: 2900 Tags: combinatorics, dp, math, number theory Solve time: 1m 10s Verified: yes Solution Problem Understanding We are counting how many ways we can build a sequence of integers when each position has an upper limit, and each element must divide the next one. More concretely, at position i we choose a value b_i that cannot exceed a_i . After choosing it, the next...
CF 2206H - Reflect Sort
CF 2206H - Reflect Sort Rating: 1800 Tags: number theory Solve time: 1m 42s Verified: no Solution Problem Understanding We are given an integer array and a somewhat unusual operation that allows us to “reflect” values around a chosen pivot element. Picking an index $i$ turns either the whole prefix or the whole suffix into mirrored values with respect to $a_i$, since each affected element $a_j$ becomes $2a_i - a_j$....
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...
CF 2215B - RReeppeettiittiioonn
CF 2215B - RReeppeettiittiioonn Rating: 2000 Tags: binary search, brute force, implementation, math, number theory Solve time: 2m 5s Verified: no Solution Problem Understanding The problem asks us to count the number of ways a given positive integer $n$ can be represented in a "repetitive" form across all numeral bases. More precisely, for a base $b \ge 2$ and a repetition length $p \ge 2$, $n$ is considered $(b, p)$-tidy...