1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Space Harbour
Contest: Codeforces Round 921 (Div. 1)
Difficulty rating: 2100
Tags: data structures, implementation, math, sortings

There are $$$n$$$ points numbered $$$1$$$ to $$$n$$$ on a straight line. Initially, there are $$$m$$$ harbours. The $$$i$$$-th harbour is at point $$$X_i$$$ and has a value $$$V_i$$$. It is guaranteed that there are harbours at the points $$$1$$$ and $$$n$$$. There is exactly one ship on each of the $$$n$$$ points. The cost of moving a ship from its current location to the next harbour is the product of the value of the nearest harbour to its left and the distance from the nearest harbour to its right. Specifically, if a ship is already at a harbour, the cost of moving it to the next harbour is $$$0$$$.

Additionally, there are $$$q$$$ queries, each of which is either of the following $$$2$$$ types:

- $$$1$$$ $$$x$$$ $$$v$$$ — Add a harbour at point $$$x$$$ with value $$$v$$$. It is guaranteed that before adding the harbour, there is no harbour at point $$$x$$$.
- $$$2$$$ $$$l$$$ $$$r$$$ — Print the sum of the cost of moving all ships at points from $$$l$$$ to $$$r$$$ to their next harbours. Note that you just need to calculate the cost of moving the ships but not actually move them.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le m \le n \le 3 \cdot 10^5$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — the number of points, harbours, and queries, respectively.

The second line contains $$$m$$$ distinct integers $$$X_1, X_2, \ldots, X_m(1 \le X_i \le n)$$$ — the position at which the $$$i$$$-th harbour is located.

The third line contains $$$m$$$ integers $$$V_1, V_2, \ldots, V_m(1 \le V_i \le 10^7)$$$ — the value of the $$$i$$$-th harbour.

Each of the next $$$q$$$ lines contains three integers. The first integer is $$$t$$$ ($$$1\le t \le 2$$$) — type of query. If $$$t=1$$$, then the next two integers are $$$x$$$ and $$$v$$$ ($$$2 \le x \le n - 1$$$, $$$1 \le v \le 10^7$$$) — first-type query. If $$$t=2$$$, then the next two integers are $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — second-type query.

It is guaranteed that there is at least one second-type query.

Output format:
For every second-type query, print one integer in a new line — answer to this query.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first type $$$2$$$ query, the cost for ships at positions $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ are $$$3(3 \times 1)$$$, $$$0$$$, $$$96(24 \times 4)$$$ and $$$72(24 \times 3)$$$ respectively.

For the second type $$$2$$$ query, since the ship at position $$$5$$$ is already at a harbour, so the cost is $$$0$$$.

For the third type $$$2$$$ query, the cost for ships at position $$$7$$$ and $$$8$$$ are $$$15(15 \times 1)$$$ and $$$0$$$ respectively.

Example input:
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8

Example output:
171
0
15

Editorial:
Fractal Origami
Contest: Codeforces Round 921 (Div. 1)
Difficulty rating: 2400
Tags: geometry, math, matrices

You have a square piece of paper with a side length equal to $$$1$$$ unit. In one operation, you fold each corner of the square to the center of the paper, thus forming another square with a side length equal to $$$\dfrac{1}{\sqrt{2}}$$$ units. By taking this square as a new square, you do the operation again and repeat this process a total of $$$N$$$ times.

Performing operations for $$$N = 2$$$.

After performing the set of operations, you open the paper with the same side up you started with and see some crease lines on it. Every crease line is one of two types: a mountain or a valley. A mountain is when the paper folds outward, and a valley is when the paper folds inward.

You calculate the sum of the length of all mountain crease lines on the paper and call it $$$M$$$. Similarly, you calculate for valley crease lines and call it $$$V$$$. You want to find the value of $$$\dfrac{M}{V}$$$.

It can be proved that this value can be represented in the form of $$$A + B\sqrt{2}$$$, where $$$A$$$ and $$$B$$$ are rational numbers. Let this $$$B$$$ be represented as an irreducible fraction $$$\dfrac{p}{q}$$$, your task is to print $$$p*inv(q)$$$ modulo $$$999\,999\,893$$$ (note the unusual modulo), where $$$inv(q)$$$ is the modular inverse of $$$q$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.

The only line of each test case contains an integer $$$N$$$ ($$$1 \leq N \leq 10^9$$$), the number of operations you perform on the square paper.

Output format:
For each test case, print on a new line the required answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The blue lines in the given figures represent mountain crease lines, and the green lines represent valley crease lines.

Crease lines after $$$1$$$ operation $$$(\dfrac{M}{V} = 0)$$$.Crease lines after $$$2$$$ operations $$$(\dfrac{M}{V} = \sqrt{2} - 1)$$$.

Example input:
3
1
2
3

Example output:
0
1
714285638

Editorial:
Balanced Subsequences
Contest: Codeforces Round 921 (Div. 1)
Difficulty rating: 2700
Tags: combinatorics, dp, math

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

You are given three integers $$$n$$$, $$$m$$$ and $$$k$$$. Find the number of sequences consisting of $$$n$$$ '(' and $$$m$$$ ')', such that the longest balanced subsequence is of length $$$2 \cdot k$$$. Since the answer can be large calculate it modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^3$$$). Description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^3$$$)

Output format:
For each test case, print one integer — the answer to the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case "()()", "(())" are the $$$2$$$ sequences

For the second test case no sequence is possible.

For the third test case ")((()", ")(()(", ")()((", "())((" are the $$$4$$$ sequences.

Example input:
3
2 2 2
3 2 3
3 2 1

Example output:
2
0
4

Editorial:
Paper Cutting Again
Contest: Codeforces Round 921 (Div. 1)
Difficulty rating: 3100
Tags: combinatorics, probabilities

There is a rectangular sheet of paper with initial height $$$n$$$ and width $$$m$$$. Let the current height and width be $$$h$$$ and $$$w$$$ respectively. We introduce a $$$xy$$$-coordinate system so that the four corners of the sheet are $$$(0, 0), (w, 0), (0, h)$$$, and $$$(w, h)$$$. The sheet can then be cut along the lines $$$x = 1,2,\ldots,w-1$$$ and the lines $$$y = 1,2,\ldots,h-1$$$. In each step, the paper is cut randomly along any one of these $$$h+w-2$$$ lines. After each vertical and horizontal cut, the right and bottom piece of paper respectively are discarded.

Find the expected number of steps required to make the area of the sheet of paper strictly less than $$$k$$$. It can be shown that this answer can always be expressed as a fraction $$$\dfrac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Calculate $$$p\cdot q^{-1} \bmod (10^9+7)$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 57000$$$). Description of the test cases follows.

The first line of each test case contains 3 integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 10^6$$$, $$$2 \le k \le 10^{12}$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$10^6$$$.

Output format:
For each test case, print one integer — the answer to the problem.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first test case, the area is already less than $$$10$$$ so no cuts are required.

For the second test case, the area is exactly $$$8$$$ so any one of the $$$4$$$ possible cuts would make the area strictly less than $$$8$$$.

For the third test case, the final answer is $$$\frac{17}{6} = 833\,333\,342\bmod (10^9+7)$$$.

For the fourth test case, the final answer is $$$\frac{5}{4} = 250\,000\,003\bmod (10^9+7)$$$.

Example input:
4
2 4 10
2 4 8
2 4 2
2 4 6

Example output:
0
1
833333342
250000003

Editorial:
Vasya and Digital Root
Contest: Codeforces Round 206 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, implementation

Vasya has recently found out what a digital root of a number is and he decided to share his knowledge with you.

Let's assume that S(n) is the sum of digits of number n, for example, S(4098) = 4 + 0 + 9 + 8 = 21. Then the digital root of number n equals to:

1. dr(n) = S(n), if S(n) < 10;
2. dr(n) = dr( S(n) ), if S(n) ≥ 10.

For example, dr(4098)  =  dr(21)  =  3.

Vasya is afraid of large numbers, so the numbers he works with are at most 101000. For all such numbers, he has proved that dr(n)  =  S( S( S( S(n) ) ) ) (n ≤ 101000).

Now Vasya wants to quickly find numbers with the given digital root. The problem is, he hasn't learned how to do that and he asked you to help him. You task is, given numbers k and d, find the number consisting of exactly k digits (the leading zeroes are not allowed), with digital root equal to d, or else state that such number does not exist.

Input format:
The first line contains two integers k and d (1 ≤ k ≤ 1000; 0 ≤ d ≤ 9).

Output format:
In a single line print either any number that meets the requirements (without the leading zeroes) or "No solution" (without the quotes), if the corresponding number does not exist.

The chosen number must consist of exactly k digits. We assume that number 0 doesn't contain any leading zeroes.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test sample dr(5881)  =  dr(22)  =  4.

For the second test sample dr(36172)  =  dr(19)  =  dr(10)  =  1.

Example input:
4 4

Example output:
5881

Example input:
5 1

Example output:
36172

Editorial:
Vasya and Public Transport
Contest: Codeforces Round 206 (Div. 2)
Difficulty rating: 1100
Tags: greedy, implementation

Vasya often uses public transport. The transport in the city is of two types: trolleys and buses. The city has n buses and m trolleys, the buses are numbered by integers from 1 to n, the trolleys are numbered by integers from 1 to m.

Public transport is not free. There are 4 types of tickets:

1. A ticket for one ride on some bus or trolley. It costs c1 burles;
2. A ticket for an unlimited number of rides on some bus or on some trolley. It costs c2 burles;
3. A ticket for an unlimited number of rides on all buses or all trolleys. It costs c3 burles;
4. A ticket for an unlimited number of rides on all buses and trolleys. It costs c4 burles.

Vasya knows for sure the number of rides he is going to make and the transport he is going to use. He asked you for help to find the minimum sum of burles he will have to spend on the tickets.

Input format:
The first line contains four integers c1, c2, c3, c4 (1 ≤ c1, c2, c3, c4 ≤ 1000) — the costs of the tickets.

The second line contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of buses and trolleys Vasya is going to use.

The third line contains n integers ai (0 ≤ ai ≤ 1000) — the number of times Vasya is going to use the bus number i.

The fourth line contains m integers bi (0 ≤ bi ≤ 1000) — the number of times Vasya is going to use the trolley number i.

Output format:
Print a single number — the minimum sum of burles Vasya will have to spend on the tickets.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample the profitable strategy is to buy two tickets of the first type (for the first bus), one ticket of the second type (for the second bus) and one ticket of the third type (for all trolleys). It totals to (2·1) + 3 + 7 = 12 burles.

In the second sample the profitable strategy is to buy one ticket of the fourth type.

In the third sample the profitable strategy is to buy two tickets of the third type: for all buses and for all trolleys.

Example input:
1 3 7 19
2 3
2 5
4 4 4

Example output:
12

Example input:
4 3 2 1
1 3
798
1 2 3

Example output:
1

Editorial:
Nezzar and Board
Contest: Codeforces Round 698 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms, math, number theory

$$$n$$$ distinct integers $$$x_1,x_2,\ldots,x_n$$$ are written on the board. Nezzar can perform the following operation multiple times.

- Select two integers $$$x,y$$$ (not necessarily distinct) on the board, and write down $$$2x-y$$$. Note that you don't remove selected numbers.

Now, Nezzar wonders if it is possible to have his favorite number $$$k$$$ on the board after applying above operation multiple times.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n,k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$-10^{18} \le k \le 10^{18}$$$).

The second line of each test case contains $$$n$$$ distinct integers $$$x_1,x_2,\ldots,x_n$$$ ($$$-10^{18} \le x_i \le 10^{18}$$$).

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print "YES" on a single line if it is possible to have $$$k$$$ on the board. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the number $$$1$$$ is already on the board.

In the second test case, Nezzar could perform the following operations to write down $$$k=0$$$ on the board:

- Select $$$x=3$$$ and $$$y=2$$$ and write down $$$4$$$ on the board.
- Select $$$x=4$$$ and $$$y=7$$$ and write down $$$1$$$ on the board.
- Select $$$x=1$$$ and $$$y=2$$$ and write down $$$0$$$ on the board.

In the third test case, it is impossible to have the number $$$k = -1$$$ on the board.

Example input:
6
2 1
1 2
3 0
2 3 7
2 -1
31415926 27182818
2 1000000000000000000
1 1000000000000000000
2 -1000000000000000000
-1000000000000000000 123
6 80
-5 -20 13 -14 -2 -11

Example output:
YES
YES
NO
YES
YES
NO

Editorial:
Let's first assume that $$$x_1=0$$$ (Otherwise, we could subtract $$$x_1$$$ for $$$x_1,x_2,\ldots,x_n$$$ and $$$k$$$). We will now prove that the answer is "YES" if and only if $$$k$$$ can be divided by $$$g=\gcd(x_2,x_3,\ldots,x_n)$$$.
One direction is straightforward. Note that any number written on the board should be divisible by $$$g$$$, which follows from the fact that $$$g|x, g|y \implies g|2x-y$$$. It only remains to prove that for any $$$x$$$ divisible by $$$g$$$, we could write down $$$x$$$ on the board. We will prove it by induction on $$$n$$$.
Base case ($$$n=2$$$) is obvious. Let $$$g_0=\gcd(x_2,x_3,\ldots,x_{n-1})$$$. By Bézout's Theorem, there exists integers $$$s,t$$$ such that $$$g_0 s-x_n t = g$$$. By induction, we could write down $$$g_0$$$ on the board, and trivially $$$x_n t$$$ can be written on the board. Therefore, we could write down $$$g$$$ applying operation recursively.
Nezzar and Nice Beatmap
Contest: Codeforces Round 698 (Div. 1)
Difficulty rating: 2200
Tags: constructive algorithms, geometry, greedy, math, sortings

Nezzar loves the game osu!.

osu! is played on beatmaps, which can be seen as an array consisting of distinct points on a plane. A beatmap is called nice if for any three consecutive points $$$A,B,C$$$ listed in order, the angle between these three points, centered at $$$B$$$, is strictly less than $$$90$$$ degrees.

Points $$$A,B,C$$$ on the left have angle less than $$$90$$$ degrees, so they can be three consecutive points of a nice beatmap; Points $$$A',B',C'$$$ on the right have angle greater or equal to $$$90$$$ degrees, so they cannot be three consecutive points of a nice beatmap.

Now Nezzar has a beatmap of $$$n$$$ distinct points $$$A_1,A_2,\ldots,A_n$$$. Nezzar would like to reorder these $$$n$$$ points so that the resulting beatmap is nice.

Formally, you are required to find a permutation $$$p_1,p_2,\ldots,p_n$$$ of integers from $$$1$$$ to $$$n$$$, such that beatmap $$$A_{p_1},A_{p_2},\ldots,A_{p_n}$$$ is nice. If it is impossible, you should determine it.

Input format:
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 5000$$$).

Then $$$n$$$ lines follow, $$$i$$$-th of them contains two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — coordinates of point $$$A_i$$$.

It is guaranteed that all points are distinct.

Output format:
If there is no solution, print $$$-1$$$.

Otherwise, print $$$n$$$ integers, representing a valid permutation $$$p$$$.

If there are multiple possible answers, you can print any.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Here is the illustration for the first test:

Please note that the angle between $$$A_1$$$, $$$A_2$$$ and $$$A_5$$$, centered at $$$A_2$$$, is treated as $$$0$$$ degrees. However, angle between $$$A_1$$$, $$$A_5$$$ and $$$A_2$$$, centered at $$$A_5$$$, is treated as $$$180$$$ degrees.

Example input:
5
0 0
5 0
4 2
2 1
3 0

Example output:
1 2 5 3 4

Editorial:
There are two different approaches to solve this task.
Furthest Points
Pick an arbitrary point, and in each iteration, select the furthest point from previously chosen point among all available points. Indeed, we can prove the correctness by contradiction.
Insertion Sorting
Notice that in any triangle (possibly degenerate), there exists at most one obtuse angle or right angle in this triangle. Therefore, we may build our permutation using modified version of insertion sort (it suffices to substitute comparing operator).
We believe that time complexity for the latter approach is better than $$$O(n^2)$$$. However, we fail to find a proof or counterexample for it. It would be grateful if someone could figure it out and inform us about it!
Array and Peaks
Contest: Divide by Zero 2021 and Codeforces Round 714 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, implementation

A sequence of $$$n$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once.

Given two integers $$$n$$$ and $$$k$$$, construct a permutation $$$a$$$ of numbers from $$$1$$$ to $$$n$$$ which has exactly $$$k$$$ peaks. An index $$$i$$$ of an array $$$a$$$ of size $$$n$$$ is said to be a peak if $$$1 < i < n$$$ and $$$a_i \gt a_{i-1}$$$ and $$$a_i \gt a_{i+1}$$$. If such permutation is not possible, then print $$$-1$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

Then $$$t$$$ lines follow, each containing two space-separated integers $$$n$$$ ($$$1 \leq n \leq 100$$$) and $$$k$$$ ($$$0 \leq k \leq n$$$) — the length of an array and the required number of peaks.

Output format:
Output $$$t$$$ lines. For each test case, if there is no permutation with given length and number of peaks, then print $$$-1$$$. Otherwise print a line containing $$$n$$$ space-separated integers which forms a permutation of numbers from $$$1$$$ to $$$n$$$ and contains exactly $$$k$$$ peaks.

If there are multiple answers, print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the second test case of the example, we have array $$$a = [2,4,1,5,3]$$$. Here, indices $$$i=2$$$ and $$$i=4$$$ are the peaks of the array. This is because $$$(a_{2} \gt a_{1} $$$, $$$a_{2} \gt a_{3})$$$ and $$$(a_{4} \gt a_{3}$$$, $$$a_{4} \gt a_{5})$$$.

Example input:
5
1 0
5 2
6 6
2 1
6 1

Example output:
1 
2 4 1 5 3 
-1
-1
1 3 6 5 4 2

Editorial:
There are many ways to solve this problem. The key idea is we try to use the first $$$k$$$ largest elements from $$$n$$$ to $$$n-k+1$$$ to construct the $$$k$$$ peaks. So try constructing the array like this: $$$1, n, 2, n-1, 3, n-2,..., n-k+1, k+1, k+2,..., n-k$$$. For this answer to be possible $$$n-k+1 \gt k+1$$$ which means $$$2 \cdot k \lt n$$$. If this is not the case we output $$$-1$$$.
Add One
Contest: Divide by Zero 2021 and Codeforces Round 714 (Div. 2)
Difficulty rating: 1600
Tags: dp, matrices

You are given an integer $$$n$$$. You have to apply $$$m$$$ operations to it.

In a single operation, you must replace every digit $$$d$$$ of the number with the decimal representation of integer $$$d + 1$$$. For example, $$$1912$$$ becomes $$$21023$$$ after applying the operation once.

You have to find the length of $$$n$$$ after applying $$$m$$$ operations. Since the answer can be very large, print it modulo $$$10^9+7$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

The only line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the initial number and the number of operations.

Output format:
For each test case output the length of the resulting number modulo $$$10^9+7$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test, $$$1912$$$ becomes $$$21023$$$ after $$$1$$$ operation which is of length $$$5$$$.

For the second test, $$$5$$$ becomes $$$21$$$ after $$$6$$$ operations which is of length $$$2$$$.

For the third test, $$$999$$$ becomes $$$101010$$$ after $$$1$$$ operation which is of length $$$6$$$.

For the fourth test, $$$88$$$ becomes $$$1010$$$ after $$$2$$$ operations which is of length $$$4$$$.

Example input:
5
1912 1
5 6
999 1
88 2
12 100

Example output:
5
2
6
4
2115

Editorial:
We can solve this problem using 1D dp.
Let $$$dp_i$$$ be defined as the length of the string after applying operation $$$i$$$-times to the number $$$10$$$. Then,
• $$$dp_i =2$$$, $$$\forall$$$ $$$i$$$ in $$$[0,8]$$$
• $$$dp_i =3$$$, if $$$i=9$$$ (The final number after applying $$$9$$$ operations to the number $$$10$$$ is $$$109$$$.)
• $$$dp_i =dp_{i-9}+dp_{i-10}$$$, Otherwise.(length would be the sum of $$$i-9$$$ operations and $$$i-10$$$ operations.)
Now for each test case, the final answer is:
$$$ans=\sum_{i=1}^{|s|}\Bigl( \bigr(m+(int)(s[i]-'0')<10 \bigr) ? 1 : dp_{m-10+(int)(s[i]-'0')} \Bigr)$$$, where $$$s$$$ is $$$n$$$ (in form of string).
Time Complexity O($$$m$$$+$$$t \cdot $$$|$$$s$$$|), where |$$$s$$$| is the number of digits in $$$n$$$.