1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Common Divisors
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 1300
Tags: implementation, math

You are given an array $$$a$$$ consisting of $$$n$$$ integers.

Your task is to say the number of such positive integers $$$x$$$ such that $$$x$$$ divides each number from the array. In other words, you have to find the number of common divisors of all elements in the array.

For example, if the array $$$a$$$ will be $$$[2, 4, 6, 2, 10]$$$, then $$$1$$$ and $$$2$$$ divide each number from the array (so the answer for this test is $$$2$$$).

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

Output format:
Print one integer — the number of such positive integers $$$x$$$ such that $$$x$$$ divides each number from the given array (in other words, the answer is the number of common divisors of all elements in the array).

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

Example input:
5
1 2 3 4 5

Example output:
1

Example input:
6
6 90 12 18 30 18

Example output:
4

Editorial:
Let $$$g = gcd(a_1, a_2, \dots, a_n)$$$ is the greatest common divisor of all elements of the array. You can find it by Euclidean algorithm or some standard library functions. Then the answer is just the number of divisors of $$$g$$$. You can find this value in $$$\sqrt{g}$$$.
Remove the Substring (easy version)
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 1600
Tags: greedy, implementation

The only difference between easy and hard versions is the length of the string.

You are given a string $$$s$$$ and a string $$$t$$$, both consisting only of lowercase Latin letters. It is guaranteed that $$$t$$$ can be obtained from $$$s$$$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $$$s$$$ without changing order of remaining characters (in other words, it is guaranteed that $$$t$$$ is a subsequence of $$$s$$$).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from $$$s$$$ of maximum possible length such that after removing this substring $$$t$$$ will remain a subsequence of $$$s$$$.

If you want to remove the substring $$$s[l;r]$$$ then the string $$$s$$$ will be transformed to $$$s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$$$ (where $$$|s|$$$ is the length of $$$s$$$).

Your task is to find the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

Input format:
The first line of the input contains one string $$$s$$$ consisting of at least $$$1$$$ and at most $$$200$$$ lowercase Latin letters.

The second line of the input contains one string $$$t$$$ consisting of at least $$$1$$$ and at most $$$200$$$ lowercase Latin letters.

It is guaranteed that $$$t$$$ is a subsequence of $$$s$$$.

Output format:
Print one integer — the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

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

Example input:
bbaba
bb

Example output:
3

Example input:
baaba
ab

Example output:
2

Editorial:
In this problem we can just iterate over all possible substrings and try to remove each of them. After removing the substring we can check if $$$t$$$ remains the subsequence of $$$s$$$ in linear time.
Let we remove the substring $$$s[l; r]$$$. Let's maintain a pointer $$$pos$$$ (the initial value of the pointer is $$$1$$$) and iterate over all possible $$$i$$$ from $$$1$$$ to $$$|s|$$$. If $$$pos \le |t|$$$ and $$$s_i = t_{pos}$$$ let's increase $$$pos$$$ by one. If after all iterations $$$pos = |t| + 1$$$ then let's update the answer with the length of the current substring.
Remove the Substring (hard version)
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 1700
Tags: binary search, greedy, implementation, two pointers

The only difference between easy and hard versions is the length of the string.

You are given a string $$$s$$$ and a string $$$t$$$, both consisting only of lowercase Latin letters. It is guaranteed that $$$t$$$ can be obtained from $$$s$$$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $$$s$$$ without changing order of remaining characters (in other words, it is guaranteed that $$$t$$$ is a subsequence of $$$s$$$).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from $$$s$$$ of maximum possible length such that after removing this substring $$$t$$$ will remain a subsequence of $$$s$$$.

If you want to remove the substring $$$s[l;r]$$$ then the string $$$s$$$ will be transformed to $$$s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$$$ (where $$$|s|$$$ is the length of $$$s$$$).

Your task is to find the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

Input format:
The first line of the input contains one string $$$s$$$ consisting of at least $$$1$$$ and at most $$$2 \cdot 10^5$$$ lowercase Latin letters.

The second line of the input contains one string $$$t$$$ consisting of at least $$$1$$$ and at most $$$2 \cdot 10^5$$$ lowercase Latin letters.

It is guaranteed that $$$t$$$ is a subsequence of $$$s$$$.

Output format:
Print one integer — the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

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

Example input:
bbaba
bb

Example output:
3

Example input:
baaba
ab

Example output:
2

Editorial:
Let $$$rg_i$$$ be such rightmost position $$$x$$$ in $$$s$$$ that the substring $$$t[i;|t|]$$$ is the subsequence of $$$s[x;|s|]$$$. We need values $$$rg_i$$$ for all $$$i$$$ from $$$1$$$ to $$$|t|$$$. We can calculate it just iterating from right to left over all characters of $$$s$$$ and maintaining the pointer to the string $$$t$$$ as in easy version.
Then let's iterate over all positions $$$i$$$ from $$$1$$$ to $$$|s|$$$ and maintain the pointer $$$pos$$$ as in the easy version which tells us the maximum length of the prefix of $$$t$$$ we can obtain using only the substring $$$s[1;i)$$$ (exclusively!). Suppose we want to remove the substring of $$$s$$$ starting from $$$i$$$. Then if $$$pos \le |t|$$$ then let $$$rpos$$$ be $$$rg_{pos} - 1$$$, otherwise let $$$rpos$$$ be $$$|s|$$$. $$$rpos$$$ tells us the farthest rightmost character of the substring we can remove. So we can update the answer with the value $$$rpos - i + 1$$$ and go to the next position (and don't forget to increase $$$pos$$$ if needed).
Boxers
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 1500
Tags: greedy, sortings

There are $$$n$$$ boxers, the weight of the $$$i$$$-th boxer is $$$a_i$$$. Each of them can change the weight by no more than $$$1$$$ before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.

It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers' weights in the team are different (i.e. unique).

Write a program that for given current values ​$$$a_i$$$ will find the maximum possible number of boxers in a team.

It is possible that after some change the weight of some boxer is $$$150001$$$ (but no more).

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 150000$$$) — the number of boxers. The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ ($$$1 \le a_i \le 150000$$$) is the weight of the $$$i$$$-th boxer.

Output format:
Print a single integer — the maximum possible number of people in a team.

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

Note:
In the first example, boxers should not change their weights — you can just make a team out of all of them.

In the second example, one boxer with a weight of $$$1$$$ can be increased by one (get the weight of $$$2$$$), one boxer with a weight of $$$4$$$ can be reduced by one, and the other can be increased by one (resulting the boxers with a weight of $$$3$$$ and $$$5$$$, respectively). Thus, you can get a team consisting of boxers with weights of $$$5, 4, 3, 2, 1$$$.

Example input:
4
3 2 4 1

Example output:
4

Example input:
6
1 1 1 4 4 4

Example output:
5

Editorial:
Let $$$lst$$$ be the last weight of the boxer taken into the team. Initially $$$lst = \infty$$$. Let's sort all boxers in order of non-increasing their weights and iterate over all boxers in order from left to right. If the current boxer has the weight $$$w$$$ then let's try to take him with weight $$$w+1$$$ (we can do it if $$$w+1<lst$$$). If we cannot do it, let's try to take him with weight $$$w$$$. And in case of fault let's try to take him with weight $$$w-1$$$. If we cannot take him even with weight $$$w-1$$$ then let's skip him. And if we take him let's replace $$$lst$$$ with him weight. The answer is the number of boxers we took.
Complete the Projects (easy version)
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 2100
Tags: greedy

The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $$$r$$$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $$$i$$$-th project, Polycarp needs to have at least $$$a_i$$$ units of rating; after he completes this project, his rating will change by $$$b_i$$$ (his rating will increase or decrease by $$$b_i$$$) ($$$b_i$$$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Is it possible to complete all the projects? Formally, write a program to check if such an order of the projects exists, that Polycarp has enough rating before starting each project, and he has non-negative rating after completing each project.

In other words, you have to check that there exists such an order of projects in which Polycarp will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$r$$$ ($$$1 \le n \le 100, 1 \le r \le 30000$$$) — the number of projects and the initial rating of Polycarp, respectively.

The next $$$n$$$ lines contain projects, one per line. The $$$i$$$-th project is represented as a pair of integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 30000$$$, $$$-300 \le b_i \le 300$$$) — the rating required to complete the $$$i$$$-th project and the rating change after the project completion.

Output format:
Print "YES" or "NO".

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

Note:
In the first example, the possible order is: $$$1, 2, 3$$$.

In the second example, the possible order is: $$$2, 3, 1$$$.

In the third example, the possible order is: $$$3, 1, 4, 2$$$.

Example input:
3 4
4 6
10 -2
8 -1

Example output:
YES

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

Example output:
YES

Editorial:
Firstly, let's divide all projects into two sets: all projects giving us non-negative rating changes (let this set be $$$pos$$$) and all projects giving up negative rating changes (let this set be $$$neg$$$). Firstly let's take all projects from the set $$$pos$$$. How do we do that? Let's sort them by $$$a_i$$$ in non-decreasing order because each project we take cannot make our rating less and we need to consider them in order of their requirements. If we can take the current project $$$i$$$ ($$$r \ge a_i$$$), set $$$r := r + b_i$$$ and go further, otherwise print "NO" and terminate the program.
Okay, what do we do with the projects that has negative $$$b_i$$$? Firstly, let's set $$$a_i := max(a_i, -b_i)$$$. This means the tighter requirement of this project, obviously. Then let's sort all projects in order of $$$a_i + b_i$$$ in non-increasing order and go from left to right and take all of them. If we cannot take at least one project, the answer is "NO". Otherwise the answer is "YES".
Complete the Projects (hard version)
Contest: Codeforces Round 579 (Div. 3)
Difficulty rating: 2300
Tags: dp, greedy

The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $$$r$$$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $$$i$$$-th project, Polycarp needs to have at least $$$a_i$$$ units of rating; after he completes this project, his rating will change by $$$b_i$$$ (his rating will increase or decrease by $$$b_i$$$) ($$$b_i$$$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Polycarp can choose the order in which he completes projects. Furthermore, he can even skip some projects altogether.

To gain more experience (and money, of course) Polycarp wants to choose the subset of projects having maximum possible size and the order in which he will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Your task is to calculate the maximum possible size of such subset of projects.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$r$$$ ($$$1 \le n \le 100, 1 \le r \le 30000$$$) — the number of projects and the initial rating of Polycarp, respectively.

The next $$$n$$$ lines contain projects, one per line. The $$$i$$$-th project is represented as a pair of integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 30000$$$, $$$-300 \le b_i \le 300$$$) — the rating required to complete the $$$i$$$-th project and the rating change after the project completion.

Output format:
Print one integer — the size of the maximum possible subset (possibly, empty) of projects Polycarp can choose.

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

Example input:
3 4
4 6
10 -2
8 -1

Example output:
3

Example input:
5 20
45 -6
34 -15
10 34
1 27
40 -45

Example output:
5

Editorial:
To view the main idea of the problem, read the editorial of easy version. The only difference is that for non-negative $$$b_i$$$ we don't need to print "NO" if we cannot take the project, we just need to skip it because we cannot take it at all. And for negative $$$b_i$$$ we need to write the knapsack dynamic programming to take the maximum possible number of projects (we need to consider them in order of their sorting). Dynamic programming is pretty easy: $$$dp_{i, j}$$$ means that we consider $$$i$$$ projects and our current rating is $$$j$$$ and the value of dp is the maximum number of negative projects we can take. If the current project is the $$$i$$$-th negative project in order of sorting, we can do two transitions: $$$dp_{i + 1, j} = max(dp_{i + 1, j}, dp_{i, j})$$$ and if $$$r + b_i \ge 0$$$ then we can make the transition $$$dp_{i + 1, j + b_i} = max(dp_{i + 1, j + b_i}, dp_{i, j} + 1)$$$. And then we just need to find the maximum value among all values of dp and add the number of positive projects we take to find the answer.
Short Substrings
Contest: Codeforces Round 650 (Div. 3)
Difficulty rating: 800
Tags: implementation, strings

Alice guesses the strings that Bob made for her.

At first, Bob came up with the secret string $$$a$$$ consisting of lowercase English letters. The string $$$a$$$ has a length of $$$2$$$ or more characters. Then, from string $$$a$$$ he builds a new string $$$b$$$ and offers Alice the string $$$b$$$ so that she can guess the string $$$a$$$.

Bob builds $$$b$$$ from $$$a$$$ as follows: he writes all the substrings of length $$$2$$$ of the string $$$a$$$ in the order from left to right, and then joins them in the same order into the string $$$b$$$.

For example, if Bob came up with the string $$$a$$$="abac", then all the substrings of length $$$2$$$ of the string $$$a$$$ are: "ab", "ba", "ac". Therefore, the string $$$b$$$="abbaac".

You are given the string $$$b$$$. Help Alice to guess the string $$$a$$$ that Bob came up with. It is guaranteed that $$$b$$$ was built according to the algorithm given above. It can be proved that the answer to the problem is unique.

Input format:
The first line contains a single positive integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

Each test case consists of one line in which the string $$$b$$$ is written, consisting of lowercase English letters ($$$2 \le |b| \le 100$$$) — the string Bob came up with, where $$$|b|$$$ is the length of the string $$$b$$$. It is guaranteed that $$$b$$$ was built according to the algorithm given above.

Output format:
Output $$$t$$$ answers to test cases. Each answer is the secret string $$$a$$$, consisting of lowercase English letters, that Bob came up with.

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

Note:
The first test case is explained in the statement.

In the second test case, Bob came up with the string $$$a$$$="ac", the string $$$a$$$ has a length $$$2$$$, so the string $$$b$$$ is equal to the string $$$a$$$.

In the third test case, Bob came up with the string $$$a$$$="bcdaf", substrings of length $$$2$$$ of string $$$a$$$ are: "bc", "cd", "da", "af", so the string $$$b$$$="bccddaaf".

Example input:
4
abbaac
ac
bccddaaf
zzzzzzzzzz

Example output:
abac
ac
bcdaf
zzzzzz

Editorial:
Note that the first two characters of $$$a$$$ match the first two characters of $$$b$$$. The third character of the string $$$b$$$ again matches the second character of $$$a$$$ (since it is the first character in the second substring, which contains the second and the third character of $$$a$$$). The fourth character $$$b$$$ matches with the third character of $$$a$$$.
It is easy to notice that such a pattern continues further. That is, the string $$$a$$$ consists of the first character $$$b$$$ and all characters at even positions in $$$b$$$.
Even Array
Contest: Codeforces Round 650 (Div. 3)
Difficulty rating: 800
Tags: greedy, math

You are given an array $$$a[0 \ldots n-1]$$$ of length $$$n$$$ which consists of non-negative integers. Note that array indices start from zero.

An array is called good if the parity of each index matches the parity of the element at that index. More formally, an array is good if for all $$$i$$$ ($$$0 \le i \le n - 1$$$) the equality $$$i \bmod 2 = a[i] \bmod 2$$$ holds, where $$$x \bmod 2$$$ is the remainder of dividing $$$x$$$ by 2.

For example, the arrays [$$$0, 5, 2, 1$$$] and [$$$0, 17, 0, 3$$$] are good, and the array [$$$2, 4, 6, 7$$$] is bad, because for $$$i=1$$$, the parities of $$$i$$$ and $$$a[i]$$$ are different: $$$i \bmod 2 = 1 \bmod 2 = 1$$$, but $$$a[i] \bmod 2 = 4 \bmod 2 = 0$$$.

In one move, you can take any two elements of the array and swap them (these elements are not necessarily adjacent).

Find the minimum number of moves in which you can make the array $$$a$$$ good, or say that this is not possible.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

Each test case starts with a line containing an integer $$$n$$$ ($$$1 \le n \le 40$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$0 \le a_i \le 1000$$$) — the initial array.

Output format:
For each test case, output a single integer — the minimum number of moves to make the given array $$$a$$$ good, or -1 if this is not possible.

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

Note:
In the first test case, in the first move, you can swap the elements with indices $$$0$$$ and $$$1$$$, and in the second move, you can swap the elements with indices $$$2$$$ and $$$3$$$.

In the second test case, in the first move, you need to swap the elements with indices $$$0$$$ and $$$1$$$.

In the third test case, you cannot make the array good.

Example input:
4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0

Example output:
2
1
-1
0

Editorial:
We split all the positions in which the parity of the index does not match with the parity of the element into two arrays. If there is an odd number in the even index, add this index to the $$$e$$$ array. Otherwise, if there is an even number in the odd index, add this index to the $$$o$$$ array. Note that if the sizes of the $$$o$$$ and $$$e$$$ arrays are not equal, then there is no answer. Otherwise, the array $$$a$$$ can be made good by doing exactly $$$|o|$$$ operations by simply swapping all the elements in the $$$o$$$ and $$$e$$$ arrays.
Flying Sort (Easy Version)
Contest: Codeforces Round 650 (Div. 3)
Difficulty rating: 2100
Tags: dp, greedy, two pointers

This is an easy version of the problem. In this version, all numbers in the given array are distinct and the constraints on $$$n$$$ are less than in the hard version of the problem.

You are given an array $$$a$$$ of $$$n$$$ integers (there are no equals elements in the array). You can perform the following operations on array elements:

1. choose any index $$$i$$$ ($$$1 \le i \le n$$$) and move the element $$$a[i]$$$ to the begin of the array;
2. choose any index $$$i$$$ ($$$1 \le i \le n$$$) and move the element $$$a[i]$$$ to the end of the array.

For example, if $$$n = 5$$$, $$$a = [4, 7, 2, 3, 9]$$$, then the following sequence of operations can be performed:

- after performing the operation of the first type to the second element, the array $$$a$$$ will become $$$[7, 4, 2, 3, 9]$$$;
- after performing the operation of the second type to the second element, the array $$$a$$$ will become $$$[7, 2, 3, 9, 4]$$$.

You can perform operations of any type any number of times in any order.

Find the minimum total number of operations of the first and second type that will make the $$$a$$$ array sorted in non-decreasing order. In other words, what is the minimum number of operations that must be performed so the array satisfies the inequalities $$$a[1] \le a[2] \le \ldots \le a[n]$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.

Each test case starts with a line containing an integer $$$n$$$ ($$$1 \le n \le 3000$$$) — length of the array $$$a$$$.

Then follow $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — an array that needs to be sorted by the given operations. All numbers in the given array are distinct.

The sum of $$$n$$$ for all test cases in one test does not exceed $$$3000$$$.

Output format:
For each test case output one integer — the minimum total number of operations of the first and second type, which will make the array sorted in non-decreasing order.

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

Note:
In the first test case, you first need to move 3, and then 2 to the beginning of the array. Therefore, the desired sequence of operations: $$$[4, 7, 2, 3, 9] \rightarrow [3, 4, 7, 2, 9] \rightarrow [2, 3, 4, 7, 9]$$$.

In the second test case, you need to move the 1 to the beginning of the array, and the 8 — to the end. Therefore, the desired sequence of operations: $$$[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$$$.

In the third test case, the array is already sorted.

Example input:
4
5
4 7 2 3 9
5
3 5 8 1 7
5
1 4 5 7 12
4
0 2 1 3

Example output:
2
2
0
2

Editorial: