1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Don't Try to Count
Contest: Codeforces Round 903 (Div. 3)
Difficulty rating: 800
Tags: brute force, strings

Given a string $$$x$$$ of length $$$n$$$ and a string $$$s$$$ of length $$$m$$$ ($$$n \cdot m \le 25$$$), consisting of lowercase Latin letters, you can apply any number of operations to the string $$$x$$$.

In one operation, you append the current value of $$$x$$$ to the end of the string $$$x$$$. Note that the value of $$$x$$$ will change after this.

For example, if $$$x =$$$"aba", then after applying operations, $$$x$$$ will change as follows: "aba" $$$\rightarrow$$$ "abaaba" $$$\rightarrow$$$ "abaabaabaaba".

After what minimum number of operations $$$s$$$ will appear in $$$x$$$ as a substring? A substring of a string is defined as a contiguous segment of it.

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

The first line of each test case contains two numbers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 25$$$) — the lengths of strings $$$x$$$ and $$$s$$$, respectively.

The second line of each test case contains the string $$$x$$$ of length $$$n$$$.

The third line of each test case contains the string $$$s$$$ of length $$$m$$$.

Output format:
For each test case, output a single number — the minimum number of operations after which $$$s$$$ will appear in $$$x$$$ as a substring. If this is not possible, output $$$-1$$$.

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

Note:
In the first test case of the example, after $$$2$$$ operations, the string will become "aaaa", and after $$$3$$$ operations, it will become "aaaaaaaa", so the answer is $$$3$$$.

In the second test case of the example, after applying $$$1$$$ operation, the string will become "$$$\text{e}\color{red}{\text{force}}\text{forc}$$$", where the substring is highlighted in red.

In the fourth test case of the example, it can be shown that it is impossible to obtain the desired string as a substring.

Example input:
12
1 5
a
aaaaa
5 5
eforc
force
2 5
ab
ababa
3 5
aba
ababa
4 3
babb
bbb
5 1
aaaaa
a
4 2
aabb
ba
2 8
bk
kbkbkbkb
12 2
fjdgmujlcont
tf
2 2
aa
aa
3 5
abb
babba
1 19
m
mmmmmmmmmmmmmmmmmmm

Example output:
3
1
2
-1
1
0
1
3
1
0
2
5

Editorial:
Note that the answer is always not greater than $$$5$$$. When $$$n=1$$$, $$$m=25$$$, the answer is either $$$5$$$ or $$$-1$$$, it is easy to see that the answer cannot be greater.
This allows us to simply iterate over the number of operations, each time checking if $$$s$$$ occurs in $$$x$$$. The time complexity of this solution is $$$O(2^5\cdot n \cdot m)$$$.
Three Threadlets
Contest: Codeforces Round 903 (Div. 3)
Difficulty rating: 900
Tags: math

Once upon a time, bartender Decim found three threadlets and a pair of scissors.

In one operation, Decim chooses any threadlet and cuts it into two threadlets, whose lengths are positive integers and their sum is equal to the length of the threadlet being cut.

For example, he can cut a threadlet of length $$$5$$$ into threadlets of lengths $$$2$$$ and $$$3$$$, but he cannot cut it into threadlets of lengths $$$2.5$$$ and $$$2.5$$$, or lengths $$$0$$$ and $$$5$$$, or lengths $$$3$$$ and $$$4$$$.

Decim can perform at most three operations. He is allowed to cut the threadlets obtained from previous cuts. Will he be able to make all the threadlets of equal length?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of each test case.

In a single line of each test case, there are three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a, b, c \le 10^9$$$) — the lengths of the threadlets.

Output format:
For each test case, output "YES" if it is possible to make all the threadlets of equal length by performing at most three operations, otherwise output "NO".

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

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

Note:
Let's consider some testcases of the first test.

In the first testcase, you can apply following operations:

$$$1, 3, 2 \to 1, 2, 1, 2 \to 1, 1, 1, 1, 2 \to 1, 1, 1, 1, 1, 1$$$.

In the second testcase, you can do nothing, the threadlets are already of equal length.

In the third testcase, it isn't possible to make threadlets of equal length.

Example input:
15
1 3 2
5 5 5
6 36 12
7 8 7
6 3 3
4 4 12
12 6 8
1000000000 1000000000 1000000000
3 7 1
9 9 1
9 3 6
2 8 2
5 3 10
8 4 8
2 8 4

Example output:
YES
YES
NO
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
NO

Editorial:
If the lengths of the threadlets are equal, the answer is "YES".
Otherwise, let's denote the length of the minimum threadlet as $$$a$$$. If we cut it, we will have only two operations, which is not enough.
Therefore, the desired length should be equal to $$$a$$$. If $$$b$$$ or $$$c$$$ are not divisible by $$$a$$$, the answer is "NO". Otherwise, we will check if $$$\frac{b}{a} - 1 + \frac{c}{a} - 1 \le 3$$$.
Perfect Square
Contest: Codeforces Round 903 (Div. 3)
Difficulty rating: 1200
Tags: brute force, implementation

Kristina has a matrix of size $$$n$$$ by $$$n$$$, filled with lowercase Latin letters. The value of $$$n$$$ is even.

She wants to change some characters so that her matrix becomes a perfect square. A matrix is called a perfect square if it remains unchanged when rotated $$$90^\circ$$$ clockwise once.

Here is an example of rotating a matrix by $$$90^\circ$$$:

In one operation, Kristina can choose any cell and replace its value with the next character in the alphabet. If the character is equal to "z", its value does not change.

Find the minimum number of operations required to make the matrix a perfect square.

For example, if the $$$4$$$ by $$$4$$$ matrix looks like this:

$$$$$$\matrix{ a & b & b & a \cr b & c & \textbf{b} & b \cr b & c & c & b\cr a & b & b & a \cr }$$$$$$

then it is enough to apply $$$1$$$ operation to the letter b, highlighted in bold.

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

Then follows the description of each test case.

The first line of each test case contains a single even integer $$$n$$$ ($$$2 \le n \le 10^3$$$) — the number of rows and columns in the matrix.

Then follows $$$n$$$ lines, each containing exactly $$$n$$$ lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output format:
For each test case, output a single number on a separate line: the minimum number of operations required for Kristina to obtain a perfect square.

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

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

Example input:
5
4
abba
bcbb
bccb
abba
2
ab
ba
6
codefo
rcesco
deforc
escode
forces
codefo
4
baaa
abba
baba
baab
4
bbaa
abba
aaba
abba

Example output:
1
2
181
5
9

Editorial:
When rotating a matrix of size $$$n$$$ by $$$n$$$ by $$$90$$$ degrees:
• element $$$a[i][j]$$$ takes the position of element $$$a[j][n - 1 - i]$$$;
• element $$$a[n - 1 - j][i]$$$ takes the position of element $$$a[i][j]$$$;
• element $$$a[n - 1 - i][n - 1 - j]$$$ takes the position of element $$$a[n - 1 - j][i]$$$.
In order for the matrix to be a perfect square, the symbols at all of these positions must be equal. Since we can only maximize a symbol, we do the following:
1. Among these 4 symbols, let's find the lexicographically maximal one, that is, the one that is in the alphabet not before all the others;
2. For all characters that are not equal to the maximum, calculate the number of operations that must be applied to them to make them equal to the maximum character. This number of operations is equal to the difference of positions of symbols in the alphabet.
Divide and Equalize
Contest: Codeforces Round 903 (Div. 3)
Difficulty rating: 1300
Tags: math, number theory

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. You can perform the following operation on it:

1. Choose a pair of elements $$$a_i$$$ and $$$a_j$$$ ($$$1 \le i, j \le n$$$ and $$$i \neq j$$$);
2. Choose one of the divisors of the integer $$$a_i$$$, i.e., an integer $$$x$$$ such that $$$a_i \bmod x = 0$$$;
3. Replace $$$a_i$$$ with $$$\frac{a_i}{x}$$$ and $$$a_j$$$ with $$$a_j \cdot x$$$.

For example, let's consider the array $$$a$$$ = [$$$100, 2, 50, 10, 1$$$] with $$$5$$$ elements. Perform two operations on it:

1. Choose $$$a_3 = 50$$$ and $$$a_2 = 2$$$, $$$x = 5$$$. Replace $$$a_3$$$ with $$$\frac{a_3}{x} = \frac{50}{5} = 10$$$, and $$$a_2$$$ with $$$a_2 \cdot x = 2 \cdot 5 = 10$$$. The resulting array is $$$a$$$ = [$$$100, 10, 10, 10, 1$$$];
2. Choose $$$a_1 = 100$$$ and $$$a_5 = 1$$$, $$$x = 10$$$. Replace $$$a_1$$$ with $$$\frac{a_1}{x} = \frac{100}{10} = 10$$$, and $$$a_5$$$ with $$$a_5 \cdot x = 1 \cdot 10 = 10$$$. The resulting array is $$$a$$$ = [$$$10, 10, 10, 10, 10$$$].

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

Then follows the description of each test case.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the number of elements in the array $$$a$$$.

The second line of each test case contains exactly $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output format:
For each test case, output a single line:

- "YES" if it is possible to make all elements in the array equal by applying the operation a certain (possibly zero) number of times;
- "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer).

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

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

Example input:
7
5
100 2 50 10 1
3
1 1 1
4
8 2 4 2
4
30 50 27 20
2
75 40
2
4 4
3
2 3 1

Example output:
YES
YES
NO
YES
NO
YES
NO

Editorial:
To solve the problem, we need to decompose all numbers in the array into prime divisors. After that, let's calculate the number of each divisor, summarizing the decompositions of all numbers.
If each divisor enters $$$k\cdot n$$$ times, where $$$k$$$ is a natural number, then we can equalize all the numbers in the array: we will sequentially apply the operation so that each number consists of the same set of prime divisors.
If some divisor enters a different number of times, then it will not be possible to equalize the numbers in the array.
Block Sequence
Contest: Codeforces Round 903 (Div. 3)
Difficulty rating: 1500
Tags: dp

Given a sequence of integers $$$a$$$ of length $$$n$$$.

A sequence is called beautiful if it has the form of a series of blocks, each starting with its length, i.e., first comes the length of the block, and then its elements. For example, the sequences [$$$\color{red}{3},\ \color{red}{3},\ \color{red}{4},\ \color{red}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$$$] and [$$$\color{red}{1},\ \color{red}{8},\ \color{green}{4},\ \color{green}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$$$] are beautiful (different blocks are colored differently), while [$$$1$$$], [$$$1,\ 4,\ 3$$$], [$$$3,\ 2,\ 1$$$] are not.

In one operation, you can remove any element from the sequence. What is the minimum number of operations required to make the given sequence beautiful?

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the sequence $$$a$$$.

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

Output format:
For each test case, output a single number — the minimum number of deletions required to make the sequence $$$a$$$ beautiful.

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

Note:
In the first test case of the example, the given sequence is already beautiful, as shown in the statement.

In the second test case of the example, the sequence can only be made beautiful by removing all elements from it.

In the fifth test case of the example, the sequence can be made beautiful by removing the first and last elements. Then the sequence will become [$$$2,\ 3,\ 4$$$].

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

Example output:
0
4
1
1
2
1
0

Editorial:
Let's use the dynamic programming approach: let $$$dp[i]$$$ be the number of operations required to make the segment from $$$i$$$ to $$$n$$$ beautiful. There are two possible ways to achieve this:
• Remove the element at position $$$i$$$ and make the segment from $$$i + 1$$$ to $$$n$$$ beautiful, then $$$dp[i] = dp[i+1] + 1$$$;
• Make the segment from $$$i + a_i + 1$$$ to $$$n$$$ beautiful, then $$$dp[i] = dp[i + a_i + 1]$$$ (cases where $$$i + a_i + 1 > n$$$ need to be handled separately).
Minimum Maximum Distance
Contest: Codeforces Round 903 (Div. 3)
Difficulty rating: 1700
Tags: dfs and similar, dp, graphs, shortest paths, trees

You have a tree with $$$n$$$ vertices, some of which are marked. A tree is a connected undirected graph without cycles.

Let $$$f_i$$$ denote the maximum distance from vertex $$$i$$$ to any of the marked vertices.

Your task is to find the minimum value of $$$f_i$$$ among all vertices.

For example, in the tree shown in the example, vertices $$$2$$$, $$$6$$$, and $$$7$$$ are marked. Then the array $$$f(i) = [2, 3, 2, 4, 4, 3, 3]$$$. The minimum $$$f_i$$$ is for vertices $$$1$$$ and $$$3$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree and the number of marked vertices, respectively.

The second line of each test case contains $$$k$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n, a_{i-1} < a_i$$$) — the indices of the marked vertices.

The next $$$n - 1$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$ — the indices of vertices connected by the $$$i$$$-th edge.

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

Output format:
For each test case, output a single integer — the minimum value of $$$f_i$$$ among all vertices.

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

Example input:
6
7 3
2 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 4
1 2 3 4
1 2
2 3
3 4
5 1
1
1 2
1 3
1 4
1 5
5 2
4 5
1 2
2 3
1 4
4 5
10 8
1 2 3 4 5 8 9 10
2 10
10 5
5 3
3 1
1 7
7 4
4 9
8 9
6 1
10 9
1 2 4 5 6 7 8 9 10
1 3
3 9
9 4
4 10
10 6
6 7
7 2
2 5
5 8

Example output:
2
2
0
1
4
5

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

Example output:
0
2
0

Editorial:
Let's run a breadth-first traversal from any labeled vertex $$$v_1$$$ and find the farthest other labeled vertex $$$v_2$$$ from it. Then we run a traversal from $$$v_2$$$ and find the farthest labeled vertex $$$v_3$$$ from it (it may coincide with $$$v_1$$$). Then the answer is $$$\lceil \frac{d}{2} \rceil$$$, where $$$d$$$ is the distance between $$$v_2$$$ and $$$v_3$$$. It is worth considering separately the case when there is only one labeled vertex in the tree. Then the answer is $$$0$$$.
The Check of the Point
Contest: Surprise Language Round 8
Difficulty rating: 1200
Tags: *special, geometry

On the coordinate plane there is a square with sides parallel to the coordinate axes. The length of the square side is equal to a. The lower left corner of the square coincides with the point (0, 0) (the point of the origin). The upper right corner of the square has positive coordinates.

You are given a point with coordinates (x, y). Your task is to determine whether this point is located strictly inside the square, on its side, or strictly outside the square.

Input format:
The first line contains three integers a, x and y (1 ≤ a ≤ 1000,  - 1000 ≤ x, y ≤ 1000) — the length of the square side and the coordinates of the point which should be checked.

Output format:
Print one integer:

- 0, if the point is located strictly inside the square;
- 1, if the point is located on the side of the square;
- 2, if the point is located strictly outside the square.

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

Example input:
2 1 1

Example output:
0

Example input:
4 4 4

Example output:
1

Editorial:
The Teacher of Physical Education
Contest: Surprise Language Round 8
Difficulty rating: 1600
Tags: *special

n pupils came to Physical Education lesson. We know the name and the height of each pupil.

Your task is to help the teacher of Physical Education to line up all pupils in non-decreasing order of their heights.

Input format:
The first line contains the positive integer n (1 ≤ n ≤ 5000) — the number of pupils.

The next n lines contain the pupils' description. In the i-th line there is pupil's name namei (a non-empty string which consists of uppercase and lowercase Latin letters, the length does not exceed five) and pupil's height xi (130 ≤ xi ≤ 215). Some pupils can have the same name. Uppercase and lowercase letters of the alphabet should be considered different.

Output format:
Print n lines — pupils' names in the non-decreasing order of their heights. Each line must contain exactly one name.

If there are several answers, print any of them. Uppercase and lowercase letters of the alphabet should be considered different.

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

Example input:
4
Ivan 150
Igor 215
Dasha 158
Katya 150

Example output:
Ivan
Katya
Dasha
Igor

Example input:
2
SASHA 180
SASHA 170

Example output:
SASHA
SASHA

Editorial:
Symmetric Difference
Contest: Surprise Language Round 8
Difficulty rating: 1600
Tags: *special

You are given two sets of numbers. Your task is to print all numbers from the sets, that both sets don't contain simultaneously.

Input format:
The first line contains the description of the first set, the second line contains the description of the second set. Each description begins with the number of elements in this set. All elements of the set follow in the arbitrary order. In each set all elements are distinct and both sets are not empty. The number of elements in each set doesn't exceed 1000. All elements of the sets are integers from -1000 to 1000.

Output format:
Print the number of the required numbers and then the numbers themselves separated by a space.

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

Example input:
3 1 2 3
3 2 3 4

Example output:
2 1 4

Example input:
5 1 4 8 9 10
4 1 2 8 10

Example output:
3 2 4 9

Editorial:
Chocolate Bar
Contest: Surprise Language Round 8
Difficulty rating: 1400
Tags: *special, math

A chocolate bar has a rectangular shape and consists of n × m slices. In other words, a bar consists of n rows with m slices of chocolate in each row.

Each slice of chocolate is known to weigh 1 gram. Your task is to determine for each of the q chocolate bars whether it is possible to obtain a piece weighing p grams by breaking the bar several (possibly zero) times. The final piece of the chocolate bar should be whole, and breaks are made along the line of slices' section for the whole length of the current piece.

Input format:
The first line contains the positive integer q (1 ≤ q ≤ 100) — the number of chocolate bars.

Each of the following q lines contains three positive integers n, m and p (1 ≤ n, m, p ≤ 1000) — the size of the chocolate bar, and the weight of the piece which should be obtained.

Output format:
The output should contain q lines and the i-th line must contain "Yes" (without the quotes), if it is possible to perform the task for i-th chocolate bar, or "No" otherwise.

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

Example input:
2
3 3 4
4 4 7

Example output:
Yes
No

Editorial:
Hammer throwing
Contest: Surprise Language Round 8
Difficulty rating: 1800
Tags: *special

n athletes take part in the hammer throw. Each of them has his own unique identifier — the integer from 1 to n (all athletes have distinct identifiers). After the draw, the order in which the athletes will throw the hammer has been determined (they will do it one by one).

Unfortunately, a not very attentive judge lost the list with the order of athletes, but each of the athletes has remembered how many competitors with identifiers larger than his own will throw the hammer before him.

Your task is to help the organizers as quickly as possible to restore the order of the athletes.

Input format:
The first line contains the positive integer n (1 ≤ n ≤ 1000) — the number of athletes.

The next line contains the sequence of integers a1, a2, ..., an (0 ≤ ai < n), where ai is equal to the number of the athletes with identifiers larger than i, who should throw the hammer before the athlete with identifier i.

Output format:
Print n distinct numbers — the sequence of athletes' identifiers in the order in which they will throw the hammer. If there are several answers it is allowed to print any of them.

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

Example input:
4
2 0 1 0

Example output:
2 4 1 3

Example input:
6
2 2 0 1 1 0

Example output:
3 6 1 2 4 5

Editorial:
Reformat the String
Contest: Surprise Language Round 8
Difficulty rating: 1800
Tags: *special

In this problem you are given a string s consisting of uppercase and lowercase Latin letters, spaces, dots and commas. Your task is to correct the formatting of this string by removing and inserting spaces, as well as changing the case of the letters.

After formatting, the resulting string must meet the following requirements:

- the string must not start with a space;
- there should be exactly one space between any two consecutive words;
- there should be a Latin letter immediately before a dot or a comma, and there should be a space immediately after a dot or a comma in the case that there is a word after that dot or comma, otherwise that dot or comma must be the last character in the string;
- all letters must be lowercase, except all first letters in the first words of the sentences, they must be capitalized. The first word of a sentence is a word that is either the first word of the string or a word after a dot.

It is guaranteed that there is at least one letter in the given string between any two punctuation marks (commas and dots are punctuation marks). There is at least one letter before the leftmost punctuation mark.

Input format:
The first line contains a non-empty string s, consisting of uppercase and lowercase Latin letters, spaces, dots and commas. The length of the given string does not exceed 255. The string is guaranteed to have at least one character other than the space.

Output format:
Output the corrected string which meets all the requirements described in the statement.

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

Example input:
hello ,i AM veRy GooD.Boris

Example output:
Hello, i am very good. Boris

Example input:
a. b,   C  .

Example output:
A. B, c.

Editorial: