1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Load Testing
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest, qualification stage (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1600
Tags: greedy

Polycarp plans to conduct a load testing of its new project Fakebook. He already agreed with his friends that at certain points in time they will send requests to Fakebook. The load testing will last n minutes and in the i-th minute friends will send ai requests.

Polycarp plans to test Fakebook under a special kind of load. In case the information about Fakebook gets into the mass media, Polycarp hopes for a monotone increase of the load, followed by a monotone decrease of the interest to the service. Polycarp wants to test this form of load.

Your task is to determine how many requests Polycarp must add so that before some moment the load on the server strictly increases and after that moment strictly decreases. Both the increasing part and the decreasing part can be empty (i. e. absent). The decrease should immediately follow the increase. In particular, the load with two equal neigbouring values is unacceptable.

For example, if the load is described with one of the arrays [1, 2, 8, 4, 3], [1, 3, 5] or [10], then such load satisfies Polycarp (in each of the cases there is an increasing part, immediately followed with a decreasing part). If the load is described with one of the arrays [1, 2, 2, 1], [2, 1, 2] or [10, 10], then such load does not satisfy Polycarp.

Help Polycarp to make the minimum number of additional requests, so that the resulting load satisfies Polycarp. He can make any number of additional requests at any minute from 1 to n.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 100 000) — the duration of the load testing.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the number of requests from friends in the i-th minute of the load testing.

Output format:
Print the minimum number of additional requests from Polycarp that would make the load strictly increasing in the beginning and then strictly decreasing afterwards.

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

Note:
In the first example Polycarp must make two additional requests in the third minute and four additional requests in the fourth minute. So the resulting load will look like: [1, 4, 5, 6, 5]. In total, Polycarp will make 6 additional requests.

In the second example it is enough to make one additional request in the third minute, so the answer is 1.

In the third example the load already satisfies all conditions described in the statement, so the answer is 0.

Example input:
5
1 4 3 2 5

Example output:
6

Example input:
5
1 2 2 2 1

Example output:
1

Editorial:
Weather Tomorrow
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest, qualification stage (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1000
Tags: implementation, math

Vasya came up with his own weather forecasting method. He knows the information about the average air temperature for each of the last n days. Assume that the average air temperature for each day is integral.

Vasya believes that if the average temperatures over the last n days form an arithmetic progression, where the first term equals to the average temperature on the first day, the second term equals to the average temperature on the second day and so on, then the average temperature of the next (n + 1)-th day will be equal to the next term of the arithmetic progression. Otherwise, according to Vasya's method, the temperature of the (n + 1)-th day will be equal to the temperature of the n-th day.

Your task is to help Vasya predict the average temperature for tomorrow, i. e. for the (n + 1)-th day.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 100) — the number of days for which the average air temperature is known.

The second line contains a sequence of integers t1, t2, ..., tn ( - 1000 ≤ ti ≤ 1000) — where ti is the average temperature in the i-th day.

Output format:
Print the average air temperature in the (n + 1)-th day, which Vasya predicts according to his method. Note that the absolute value of the predicted temperature can exceed 1000.

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

Note:
In the first example the sequence of the average temperatures is an arithmetic progression where the first term is 10 and each following terms decreases by 5. So the predicted average temperature for the sixth day is  - 10 - 5 =  - 15.

In the second example the sequence of the average temperatures is an arithmetic progression where the first term is 1 and each following terms equals to the previous one. So the predicted average temperature in the fifth day is 1.

In the third example the average temperatures do not form an arithmetic progression, so the average temperature of the fourth day equals to the temperature of the third day and equals to  - 5.

In the fourth example the sequence of the average temperatures is an arithmetic progression where the first term is 900 and each the following terms increase by 100. So predicted average temperature in the third day is 1000 + 100 = 1100.

Example input:
5
10 5 0 -5 -10

Example output:
-15

Example input:
4
1 1 1 1

Example output:
1

Editorial:
Contest for Robots
Contest: Технокубок 2020 - Финал
Tags: math

Polycarp is preparing the first programming contest for robots. There are $$$n$$$ problems in it, and a lot of robots are going to participate in it. Each robot solving the problem $$$i$$$ gets $$$p_i$$$ points, and the score of each robot in the competition is calculated as the sum of $$$p_i$$$ over all problems $$$i$$$ solved by it. For each problem, $$$p_i$$$ is an integer not less than $$$1$$$.

Two corporations specializing in problem-solving robot manufacturing, "Robo-Coder Inc." and "BionicSolver Industries", are going to register two robots (one for each corporation) for participation as well. Polycarp knows the advantages and flaws of robots produced by these companies, so, for each problem, he knows precisely whether each robot will solve it during the competition. Knowing this, he can try predicting the results — or manipulating them.

For some reason (which absolutely cannot involve bribing), Polycarp wants the "Robo-Coder Inc." robot to outperform the "BionicSolver Industries" robot in the competition. Polycarp wants to set the values of $$$p_i$$$ in such a way that the "Robo-Coder Inc." robot gets strictly more points than the "BionicSolver Industries" robot. However, if the values of $$$p_i$$$ will be large, it may look very suspicious — so Polycarp wants to minimize the maximum value of $$$p_i$$$ over all problems. Can you help Polycarp to determine the minimum possible upper bound on the number of points given for solving the problems?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of problems.

The second line contains $$$n$$$ integers $$$r_1$$$, $$$r_2$$$, ..., $$$r_n$$$ ($$$0 \le r_i \le 1$$$). $$$r_i = 1$$$ means that the "Robo-Coder Inc." robot will solve the $$$i$$$-th problem, $$$r_i = 0$$$ means that it won't solve the $$$i$$$-th problem.

The third line contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ ($$$0 \le b_i \le 1$$$). $$$b_i = 1$$$ means that the "BionicSolver Industries" robot will solve the $$$i$$$-th problem, $$$b_i = 0$$$ means that it won't solve the $$$i$$$-th problem.

Output format:
If "Robo-Coder Inc." robot cannot outperform the "BionicSolver Industries" robot by any means, print one integer $$$-1$$$.

Otherwise, print the minimum possible value of $$$\max \limits_{i = 1}^{n} p_i$$$, if all values of $$$p_i$$$ are set in such a way that the "Robo-Coder Inc." robot gets strictly more points than the "BionicSolver Industries" robot.

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

Note:
In the first example, one of the valid score assignments is $$$p = [3, 1, 3, 1, 1]$$$. Then the "Robo-Coder" gets $$$7$$$ points, the "BionicSolver" — $$$6$$$ points.

In the second example, both robots get $$$0$$$ points, and the score distribution does not matter.

In the third example, both robots solve all problems, so their points are equal.

Example input:
5
1 1 1 0 0
0 1 1 1 1

Example output:
3

Example input:
3
0 0 0
0 0 0

Example output:
-1

Editorial:
Journey Planning
Contest: Технокубок 2020 - Финал
Difficulty rating: 1400
Tags: data structures, dp, greedy, math, sortings

Tanya wants to go on a journey across the cities of Berland. There are $$$n$$$ cities situated along the main railroad line of Berland, and these cities are numbered from $$$1$$$ to $$$n$$$.

Tanya plans her journey as follows. First of all, she will choose some city $$$c_1$$$ to start her journey. She will visit it, and after that go to some other city $$$c_2 > c_1$$$, then to some other city $$$c_3 > c_2$$$, and so on, until she chooses to end her journey in some city $$$c_k > c_{k - 1}$$$. So, the sequence of visited cities $$$[c_1, c_2, \dots, c_k]$$$ should be strictly increasing.

There are some additional constraints on the sequence of cities Tanya visits. Each city $$$i$$$ has a beauty value $$$b_i$$$ associated with it. If there is only one city in Tanya's journey, these beauty values imply no additional constraints. But if there are multiple cities in the sequence, then for any pair of adjacent cities $$$c_i$$$ and $$$c_{i + 1}$$$, the condition $$$c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}$$$ must hold.

For example, if $$$n = 8$$$ and $$$b = [3, 4, 4, 6, 6, 7, 8, 9]$$$, there are several three possible ways to plan a journey:

- $$$c = [1, 2, 4]$$$;
- $$$c = [3, 5, 6, 8]$$$;
- $$$c = [7]$$$ (a journey consisting of one city is also valid).

There are some additional ways to plan a journey that are not listed above.

Tanya wants her journey to be as beautiful as possible. The beauty value of the whole journey is the sum of beauty values over all visited cities. Can you help her to choose the optimal plan, that is, to maximize the beauty value of the journey?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of cities in Berland.

The second line contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ ($$$1 \le b_i \le 4 \cdot 10^5$$$), where $$$b_i$$$ is the beauty value of the $$$i$$$-th city.

Output format:
Print one integer — the maximum beauty of a journey Tanya can choose.

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

Note:
The optimal journey plan in the first example is $$$c = [2, 4, 5]$$$.

The optimal journey plan in the second example is $$$c = [1]$$$.

The optimal journey plan in the third example is $$$c = [3, 6]$$$.

Example input:
6
10 7 1 9 10 15

Example output:
26

Example input:
1
400000

Example output:
400000

Editorial:
Let's rewrite the equality given in the statement as $$$c_{i + 1} - b_{c_{i + 1}} = c_i - b_{c_i}$$$. It means that all cities in our path will have the same value of $$$i - b_i$$$; furthermore, all cities with the same such value can always be visited in ascending order.
So we may group cities by $$$i - b_i$$$, compute the sum in each group and find the maximum over all groups. For example, this can be done by storing the sum for each $$$i - b_i$$$ in an array (be careful with negative values of $$$i - b_i$$$, though!)
Remove Adjacent
Contest: Технокубок 2020 - Финал
Tags: greedy, strings

You are given a string $$$s$$$ consisting of lowercase Latin letters. Let the length of $$$s$$$ be $$$|s|$$$. You may perform several operations on this string.

In one operation, you can choose some index $$$i$$$ and remove the $$$i$$$-th character of $$$s$$$ ($$$s_i$$$) if at least one of its adjacent characters is the previous letter in the Latin alphabet for $$$s_i$$$. For example, the previous letter for b is a, the previous letter for s is r, the letter a has no previous letters. Note that after each removal the length of the string decreases by one. So, the index $$$i$$$ should satisfy the condition $$$1 \le i \le |s|$$$ during each operation.

For the character $$$s_i$$$ adjacent characters are $$$s_{i-1}$$$ and $$$s_{i+1}$$$. The first and the last characters of $$$s$$$ both have only one adjacent character (unless $$$|s| = 1$$$).

Consider the following example. Let $$$s=$$$ bacabcab.

1. During the first move, you can remove the first character $$$s_1=$$$ b because $$$s_2=$$$ a. Then the string becomes $$$s=$$$ acabcab.
2. During the second move, you can remove the fifth character $$$s_5=$$$ c because $$$s_4=$$$ b. Then the string becomes $$$s=$$$ acabab.
3. During the third move, you can remove the sixth character $$$s_6=$$$'b' because $$$s_5=$$$ a. Then the string becomes $$$s=$$$ acaba.
4. During the fourth move, the only character you can remove is $$$s_4=$$$ b, because $$$s_3=$$$ a (or $$$s_5=$$$ a). The string becomes $$$s=$$$ acaa and you cannot do anything with it.

Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.

Input format:
The only line of the input contains one integer $$$|s|$$$ ($$$1 \le |s| \le 100$$$) — the length of $$$s$$$.

The second line of the input contains one string $$$s$$$ consisting of $$$|s|$$$ lowercase Latin letters.

Output format:
Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.

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

Note:
The first example is described in the problem statement. Note that the sequence of moves provided in the statement is not the only, but it can be shown that the maximum possible answer to this test is $$$4$$$.

In the second example, you can remove all but one character of $$$s$$$. The only possible answer follows.

1. During the first move, remove the third character $$$s_3=$$$ d, $$$s$$$ becomes bca.
2. During the second move, remove the second character $$$s_2=$$$ c, $$$s$$$ becomes ba.
3. And during the third move, remove the first character $$$s_1=$$$ b, $$$s$$$ becomes a.

Example input:
8
bacabcab

Example output:
4

Example input:
4
bcda

Example output:
3

Editorial:
Primal Sport
Contest: VK Cup 2018 - Round 1
Difficulty rating: 1700
Tags: math, number theory

Alice and Bob begin their day with a quick game. They first choose a starting number X0 ≥ 3 and try to reach one million by the process described below.

Alice goes first and then they take alternating turns. In the i-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime p < Xi - 1 and then finds the minimum Xi ≥ Xi - 1 such that p divides Xi. Note that if the selected prime p already divides Xi - 1, then the number does not change.

Eve has witnessed the state of the game after two turns. Given X2, help her determine what is the smallest possible starting number X0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

Input format:
The input contains a single integer X2 (4 ≤ X2 ≤ 106). It is guaranteed that the integer X2 is composite, that is, is not prime.

Output format:
Output a single integer — the minimum possible X0.

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

Note:
In the first test, the smallest possible starting number is X0 = 6. One possible course of the game is as follows:

- Alice picks prime 5 and announces X1 = 10
- Bob picks prime 7 and announces X2 = 14.

In the second case, let X0 = 15.

- Alice picks prime 2 and announces X1 = 16
- Bob picks prime 5 and announces X2 = 20.

Example input:
14

Example output:
6

Example input:
20

Example output:
15

Editorial:
Let P(N) be the largest prime factor of N. Clearly, we can obtain N from any number in interval [N - P(N) + 1, N] by picking P(N) as the prime, and we cannot obtain N from any other number. By factorizing X2, we can find the range for X1. By factorizing all numbers from the range of X1, we can find intervals for X0. The answer is the minimum of their union. The solution works in $${\mathcal {O}}(N{\sqrt {N}})$$, which is fast in practice.
Bonus: Solve it for Q queries of XK in $${\mathcal {O}}(N\log N+Q\log K)$$.
Twin Permutations
Contest: Codeforces Round 875 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms

You are given a permutation$$$^\dagger$$$ $$$a$$$ of length $$$n$$$.

Find any permutation $$$b$$$ of length $$$n$$$ such that $$$a_1+b_1 \le a_2+b_2 \le a_3+b_3 \le \ldots \le a_n+b_n$$$.

It can be proven that a permutation $$$b$$$ that satisfies the condition above always exists.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of permutations $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of permutation $$$a$$$. All elements of $$$a$$$ are distinct.

Note that there is no bound on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output any permutation $$$b$$$ which satisfies the constraints mentioned in the statement. It can be proven that a permutation $$$b$$$ that satisfies the condition above always exists.

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

Note:
In the first test case $$$a=[1, 2, 4, 5, 3]$$$. Then the permutation $$$b=[1, 2, 4, 3, 5]$$$ satisfies the condition because $$$1 + 1 \le 2 + 2 \le 4 + 4 \le 5 + 3 \le 3 + 5$$$.

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

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

Editorial:
Let's try to simplify the condition and try to solve the new problem. What if instead of finding a permutation $$$b$$$ that satisfies $$$a_1+b_1 \le a_2+b_2 \le a_3+b_3 \le \ldots \le a_n+b_n$$$, we instead find a permutation for which all sums would be equal, in other words, satisfy the condition: $$$a_1+b_1 = a_2+b_2 = a_3+b_3 = \ldots = a_n+b_n$$$. Since in a permutation, all numbers are distinct integers from $$$1$$$ to $$$n$$$, it's easy to see we can make all sums equal to $$$n + 1$$$ and all the integers in $$$b$$$ would still be distinct integers from $$$1$$$ to $$$n$$$.
So, the permutation $$$b$$$ we are forming will be constructed in the following way: $$$b_i = n + 1 - a_i$$$.
Array merging
Contest: Codeforces Round 875 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, greedy

You are given two arrays $$$a$$$ and $$$b$$$ both of length $$$n$$$.

You will merge$$$^\dagger$$$ these arrays forming another array $$$c$$$ of length $$$2 \cdot n$$$. You have to find the maximum length of a subarray consisting of equal values across all arrays $$$c$$$ that could be obtained.

$$$^\dagger$$$ A merge of two arrays results in an array $$$c$$$ composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of $$$c$$$. We repeat this operation as long as we can (i.e. at least one array is nonempty).

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2 \cdot n$$$) — the elements of array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le 2 \cdot n$$$) — the elements of array $$$b$$$.

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

Output format:
For each test case, output the maximum length of a subarray consisting of equal values across all merges.

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

Note:
In the first test case, we can only make $$$c=[2,2]$$$, thus the answer is $$$2$$$.

In the second test case, since all values are distinct, the answer must be $$$1$$$.

In the third test case, the arrays $$$c$$$ we can make are $$$[1,2,1,2]$$$, $$$[1,2,2,1]$$$, $$$[2,1,1,2]$$$, $$$[2,1,2,1]$$$. We can see that the answer is $$$2$$$ when we choose $$$c=[1,2,2,1]$$$.

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

Example output:
2
1
2
5

Editorial:
Eshag Loves Big Arrays
Contest: Codeforces Round 722 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, math

Eshag has an array $$$a$$$ consisting of $$$n$$$ integers.

Eshag can perform the following operation any number of times: choose some subsequence of $$$a$$$ and delete every element from it which is strictly larger than $$$AVG$$$, where $$$AVG$$$ is the average of the numbers in the chosen subsequence.

For example, if $$$a = [1 , 4 , 3 , 2 , 4]$$$ and Eshag applies the operation to the subsequence containing $$$a_1$$$, $$$a_2$$$, $$$a_4$$$ and $$$a_5$$$, then he will delete those of these $$$4$$$ elements which are larger than $$$\frac{a_1+a_2+a_4+a_5}{4} = \frac{11}{4}$$$, so after the operation, the array $$$a$$$ will become $$$a = [1 , 3 , 2]$$$.

Your task is to find the maximum number of elements Eshag can delete from the array $$$a$$$ by applying the operation described above some number (maybe, zero) times.

A sequence $$$b$$$ is a subsequence of an array $$$c$$$ if $$$b$$$ can be obtained from $$$c$$$ by deletion of several (possibly, zero or all) elements.

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

The first line of each test case contains an integer $$$n$$$ $$$(1\le n\le 100)$$$ — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1\le a_i \le 100)$$$ — the elements of the array $$$a$$$.

Output format:
For each test case print a single integer — the maximum number of elements Eshag can delete from the array $$$a$$$.

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

Note:
Consider the first test case.

Initially $$$a = [1, 1, 1, 2, 2, 3]$$$.

In the first operation, Eshag can choose the subsequence containing $$$a_1$$$, $$$a_5$$$ and $$$a_6$$$, their average is equal to $$$\frac{a_1 + a_5 + a_6}{3} = \frac{6}{3} = 2$$$. So $$$a_6$$$ will be deleted.

After this $$$a = [1, 1, 1, 2, 2]$$$.

In the second operation, Eshag can choose the subsequence containing the whole array $$$a$$$, the average of all its elements is equal to $$$\frac{7}{5}$$$. So $$$a_4$$$ and $$$a_5$$$ will be deleted.

After this $$$a = [1, 1, 1]$$$.

In the second test case, Eshag can't delete any element.

Example input:
3
6
1 1 1 2 2 3
6
9 9 9 9 9 9
6
6 4 1 1 4 1

Example output:
3
0
3

Editorial:
We state that every element except for the elements with the smallest value can be deleted.
Proof: denote $$$MN$$$ as the minimum element (s) of the array $$$a$$$, in each operation pick $$$MN$$$ and some other element, say $$$X$$$, which is bigger than $$$MN$$$, since $$$AVG = \frac{X + MN}{2} < X$$$, then $$$X$$$ will be deleted.
Doing this for every $$$X > MN$$$ will result in the deletion of every element except for the elements with the smallest value. So the answer to the problem is $$$n - cntMN$$$, where $$$cntMN$$$ is the number of times $$$MN$$$ appeared in $$$a$$$.
complexity: $$$\mathcal{O}(n)$$$