1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Suffix Subgroup
Contest: Friday the 13th, Programmers Day
Difficulty rating: 2200
Tags: *special, strings

You are given a group of n strings: s1, s2, ..., sn.

You should find a subgroup si1, si2, ..., sik (1 ≤ i1 < i2 < ... < ik ≤ n) of the group. The following two conditions must hold:

- there exists a string t such, that each string from found subgroup is its suffix;
- the number of strings in the found subgroup is as large as possible.

Your task is to print the number of strings in the found subgroup.

Input format:
The first line contains an integer n (1 ≤ n ≤ 105) — the number of strings in the group. Each of the next n lines contains a string. The i-th line contains non-empty string si.

Each string consists only from lowercase Latin letters. The sum of all strings si doesn't exceed 105.

Output format:
Output a single integer — the number of strings in the found subgroup.

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

Note:
Look at the test sample. The required subgroup is s1, s2, s3.

Example input:
6
bb
bb
b
aaa
aa
z

Example output:
3

Editorial:
Little Elephant and Function
Contest: Codeforces Round 136 (Div. 2)
Difficulty rating: 1000
Tags: implementation, math

The Little Elephant enjoys recursive functions.

This time he enjoys the sorting function. Let a is a permutation of an integers from 1 to n, inclusive, and ai denotes the i-th element of the permutation. The Little Elephant's recursive function f(x), that sorts the first x permutation's elements, works as follows:

- If x = 1, exit the function.
- Otherwise, call f(x - 1), and then make swap(ax - 1, ax) (swap the x-th and (x - 1)-th elements of a).

The Little Elephant's teacher believes that this function does not work correctly. But that-be do not get an F, the Little Elephant wants to show the performance of its function. Help him, find a permutation of numbers from 1 to n, such that after performing the Little Elephant's function (that is call f(n)), the permutation will be sorted in ascending order.

Input format:
A single line contains integer n (1 ≤ n ≤ 1000) — the size of permutation.

Output format:
In a single line print n distinct integers from 1 to n — the required permutation. Numbers in a line should be separated by spaces.

It is guaranteed that the answer exists.

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

Example input:
1

Example output:
1

Example input:
2

Example output:
2 1

Editorial:
Little Elephant and Numbers
Contest: Codeforces Round 136 (Div. 2)
Difficulty rating: 1300
Tags: implementation

The Little Elephant loves numbers.

He has a positive integer x. The Little Elephant wants to find the number of positive integers d, such that d is the divisor of x, and x and d have at least one common (the same) digit in their decimal representations.

Help the Little Elephant to find the described number.

Input format:
A single line contains a single integer x (1 ≤ x ≤ 109).

Output format:
In a single line print an integer — the answer to the problem.

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

Example input:
1

Example output:
1

Example input:
10

Example output:
2

Editorial:
Balance the Bits
Contest: Codeforces Round 712 (Div. 1)
Difficulty rating: 1600
Tags: constructive algorithms, greedy

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.

You are given a binary string $$$s$$$ of length $$$n$$$. Construct two balanced bracket sequences $$$a$$$ and $$$b$$$ of length $$$n$$$ such that for all $$$1\le i\le n$$$:

- if $$$s_i=1$$$, then $$$a_i=b_i$$$
- if $$$s_i=0$$$, then $$$a_i\ne b_i$$$

If it is impossible, you should report about it.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$n$$$ is even).

The next line contains a string $$$s$$$ of length $$$n$$$, consisting of characters 0 and 1.

The sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
If such two balanced bracked sequences exist, output "YES" on the first line, otherwise output "NO". You can print each letter in any case (upper or lower).

If the answer is "YES", output the balanced bracket sequences $$$a$$$ and $$$b$$$ satisfying the conditions on the next two lines.

If there are multiple solutions, you may print any.

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

Note:
In the first test case, $$$a=$$$"()()()" and $$$b=$$$"((()))". The characters are equal in positions $$$1$$$, $$$3$$$, $$$4$$$, and $$$6$$$, which are the exact same positions where $$$s_i=1$$$.

In the second test case, $$$a=$$$"()()((()))" and $$$b=$$$"(())()()()". The characters are equal in positions $$$1$$$, $$$4$$$, $$$5$$$, $$$7$$$, $$$8$$$, $$$10$$$, which are the exact same positions where $$$s_i=1$$$.

In the third test case, there is no solution.

Example input:
3
6
101101
10
1001101101
4
1100

Example output:
YES
()()()
((()))
YES
()()((()))
(())()()()
NO

Editorial:
Any balanced bracket sequence must begin with '(' and end with ')'. Therefore, $$$a$$$ and $$$b$$$ must agree in the first and last positions, so we require $$$s_1=s_n=1$$$ or a solution doesn't exist.
The total number of open brackets in $$$a$$$ and $$$b$$$ must be $$$n$$$, which is even. Each $$$1$$$ bit in $$$s$$$ creates an even number of open brackets and each $$$0$$$ bit creates an odd number of open brackets. Therefore, there must be an even number of $$$0$$$ bits, or a solution doesn't exist. Note that the number of $$$1$$$ bits also must be even.
Assuming these conditions hold, let's construct a solution. Suppose there are $$$k$$$ positions where $$$s_i=1$$$. We will make the first $$$\frac k2$$$ positions open in both $$$a$$$ and $$$b$$$, and we will make the last $$$\frac k2$$$ positions closed in both $$$a$$$ and $$$b$$$. Then, the $$$0$$$ bits in $$$s$$$ will alternate between which string gets the open bracket.
To My Critics
Contest: Codeforces Round 886 (Div. 4)
Difficulty rating: 800
Tags: implementation, sortings

Suneet has three digits $$$a$$$, $$$b$$$, and $$$c$$$.

Since math isn't his strongest point, he asks you to determine if you can choose any two digits to make a sum greater or equal to $$$10$$$.

Output "YES" if there is such a pair, and "NO" otherwise.

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

The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a, b, c \leq 9$$$).

Output format:
For each test case, output "YES" if such a pair exists, and "NO" otherwise.

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

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

Note:
For the first test case, by choosing the digits $$$8$$$ and $$$2$$$ we can obtain a sum of $$$8 + 2 = 10$$$ which satisfies the condition, thus the output should be "YES".

For the second test case, any combination of chosen digits won't be at least $$$10$$$, thus the output should be "NO" (note that we can not choose the digit on the same position twice).

For the third test case, any combination of chosen digits will have a sum equal to $$$18$$$, thus the output should be "YES".

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

Example output:
YES
NO
YES
NO
YES

Editorial:
One way to solve the problem is to check if $$$a + b + c - min(a, b, c) \geq 10$$$ using an if statement.
Ten Words of Wisdom
Contest: Codeforces Round 886 (Div. 4)
Difficulty rating: 800
Tags: implementation, sortings

In the game show "Ten Words of Wisdom", there are $$$n$$$ participants numbered from $$$1$$$ to $$$n$$$, each of whom submits one response. The $$$i$$$-th response is $$$a_i$$$ words long and has quality $$$b_i$$$. No two responses have the same quality, and at least one response has length at most $$$10$$$.

The winner of the show is the response which has the highest quality out of all responses that are not longer than $$$10$$$ words. Which response is the winner?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the number of responses.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 50$$$) — the number of words and the quality of the $$$i$$$-th response, respectively.

Additional constraints on the input: in each test case, at least one value of $$$i$$$ satisfies $$$a_i \leq 10$$$, and all values of $$$b_i$$$ are distinct.

Output format:
For each test case, output a single line containing one integer $$$x$$$ ($$$1 \leq x \leq n$$$) — the winner of the show, according to the rules given in the statement.

It can be shown that, according to the constraints in the statement, exactly one winner exists for each test case.

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

Note:
In the first test case, the responses provided are as follows:

- Response 1: $$$7$$$ words, quality $$$2$$$
- Response 2: $$$12$$$ words, quality $$$5$$$
- Response 3: $$$9$$$ words, quality $$$3$$$
- Response 4: $$$9$$$ words, quality $$$4$$$
- Response 5: $$$10$$$ words, quality $$$1$$$

We can see that the responses with indices $$$1$$$, $$$3$$$, $$$4$$$, and $$$5$$$ have lengths not exceeding $$$10$$$ words. Out of these responses, the winner is the one with the highest quality.

Comparing the qualities, we find that:

- Response 1 has quality $$$2$$$.
- Response 3 has quality $$$3$$$.
- Response 4 has quality $$$4$$$.
- Response 5 has quality $$$1$$$.

Among these responses, Response 4 has the highest quality.

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

Example output:
4
3
1

Editorial:
Let's iterate through all responses: if it has $$$> 10$$$ words, ignore it. Otherwise, keep track of the maximum quality and its index, and update it as we go along. Then output the index with maximum quality. The time complexity is $$$\mathcal{O}(n)$$$.
Word on the Paper
Contest: Codeforces Round 886 (Div. 4)
Difficulty rating: 800
Tags: implementation, strings

On an $$$8 \times 8$$$ grid of dots, a word consisting of lowercase Latin letters is written vertically in one column, from top to bottom. What is it?

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

Each test case consists of $$$8$$$ lines, each containing $$$8$$$ characters. Each character in the grid is either $$$\texttt{.}$$$ (representing a dot) or a lowercase Latin letter ($$$\texttt{a}$$$–$$$\texttt{z}$$$).

The word lies entirely in a single column and is continuous from the beginning to the ending (without gaps). See the sample input for better understanding.

Output format:
For each test case, output a single line containing the word made up of lowercase Latin letters ($$$\texttt{a}$$$–$$$\texttt{z}$$$) that is written vertically in one column from top to bottom.

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

Example input:
5
........
........
........
........
...i....
........
........
........
........
.l......
.o......
.s......
.t......
........
........
........
........
........
........
........
......t.
......h.
......e.
........
........
........
........
........
.......g
.......a
.......m
.......e
a.......
a.......
a.......
a.......
a.......
a.......
a.......
a.......

Example output:
i
lost
the
game
aaaaaaaa

Editorial:
You can iterate through the grid and then once you find a letter, iterate downwards until you get the whole word.
However there is an approach that is even faster to code: just input each character, and output it if it is not a dot. This works because we will input the characters in the same order from top to bottom. The complexity is $$$\mathcal{O}(1)$$$ regardless.
Balanced Round
Contest: Codeforces Round 886 (Div. 4)
Difficulty rating: 900
Tags: brute force, greedy, implementation, sortings

You are the author of a Codeforces round and have prepared $$$n$$$ problems you are going to set, problem $$$i$$$ having difficulty $$$a_i$$$. You will do the following process:

- remove some (possibly zero) problems from the list;
- rearrange the remaining problems in any order you wish.

A round is considered balanced if and only if the absolute difference between the difficulty of any two consecutive problems is at most $$$k$$$ (less or equal than $$$k$$$).

What is the minimum number of problems you have to remove so that an arrangement of problems is balanced?

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

The first line of each test case contains two positive integers $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) and $$$k$$$ ($$$1 \leq k \leq 10^9$$$) — the number of problems, and the maximum allowed absolute difference between consecutive problems.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the difficulty of each problem.

Note that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of problems you have to remove so that an arrangement of problems is balanced.

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

Note:
For the first test case, we can remove the first $$$2$$$ problems and construct a set using problems with the difficulties $$$[4, 5, 6]$$$, with difficulties between adjacent problems equal to $$$|5 - 4| = 1 \leq 1$$$ and $$$|6 - 5| = 1 \leq 1$$$.

For the second test case, we can take the single problem and compose a round using the problem with difficulty $$$10$$$.

Example input:
7
5 1
1 2 4 5 6
1 2
10
8 3
17 3 1 20 12 5 17 12
4 2
2 4 6 8
5 3
2 3 19 10 8
3 4
1 10 5
8 1
8 3 1 4 5 10 7 3

Example output:
2
0
5
0
3
1
4

Editorial:
Let's calculate the maximum number of problems we can take, and the answer will be $$$n$$$ subtracted by that count.
An arrangement that always minimizes the absolute difference between adjacent pairs is the array in sorted order. What we notice, is that if the array is sorted, we will always take a subarray (all taken elements will be consecutive).
So, the problem converts to finding the largest subarray for which $$$a_i - a_{i-1} \leq k$$$. It's easy to see that all the subarrays are totally different (don't share any intersection of elements), thus, we can maintain a count variable of the current number of elements in the current subarray, and iterate through array elements from left to right. If we currently are at $$$i$$$ and $$$a_i - a_{i-1} > k$$$ then we just set the count to $$$1$$$ since we know a new subarray starts, otherwise, we just increase our count by $$$1$$$. The answer will be $$$n$$$ subtracted by the largest value that our count has achieved.
We Were Both Children
Contest: Codeforces Round 886 (Div. 4)
Difficulty rating: 1300
Tags: brute force, implementation, math, number theory

Mihai and Slavic were looking at a group of $$$n$$$ frogs, numbered from $$$1$$$ to $$$n$$$, all initially located at point $$$0$$$. Frog $$$i$$$ has a hop length of $$$a_i$$$.

Each second, frog $$$i$$$ hops $$$a_i$$$ units forward. Before any frogs start hopping, Slavic and Mihai can place exactly one trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate.

However, the children can't go far away from their home so they can only place a trap in the first $$$n$$$ points (that is, in a point with a coordinate between $$$1$$$ and $$$n$$$) and the children can't place a trap in point $$$0$$$ since they are scared of frogs.

Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap?

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the lengths of the hops of the corresponding frogs.

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 maximum number of frogs Slavic and Mihai can catch using a trap.

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

Note:
In the first test case, the frogs will hop as follows:

- Frog 1: $$$0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$$$
- Frog 2: $$$0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$$$
- Frog 3: $$$0 \to 3 \to 6 \to 9 \to 12 \to \cdots$$$
- Frog 4: $$$0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$$$
- Frog 5: $$$0 \to 5 \to 10 \to 15 \to 20 \to \cdots$$$

In the second test case, Slavic and Mihai can put a trap at coordinate $$$2$$$ and catch all three frogs instantly.

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

Example output:
3
3
3
5
0
4
4

Editorial:
We disregard any $$$a_i$$$ larger than $$$n$$$ since we can't catch them anyway. We keep in $$$cnt_i$$$ how many frogs we have for each hop distance. We go through each $$$i$$$ from $$$1$$$ to $$$n$$$ and add $$$cnt_i$$$ to every multiple of $$$i$$$ smaller or equal to $$$n$$$. This action is a harmonic series and takes $$$O(nlogn)$$$ time. We go through all from $$$1$$$ to $$$n$$$ and take the maximum.
Integers Have Friends
Contest: Codeforces Round 736 (Div. 1)
Difficulty rating: 1800
Tags: binary search, data structures, divide and conquer, math, number theory, two pointers

British mathematician John Littlewood once said about Indian mathematician Srinivasa Ramanujan that "every positive integer was one of his personal friends."

It turns out that positive integers can also be friends with each other! You are given an array $$$a$$$ of distinct positive integers.

Define a subarray $$$a_i, a_{i+1}, \ldots, a_j$$$ to be a friend group if and only if there exists an integer $$$m \ge 2$$$ such that $$$a_i \bmod m = a_{i+1} \bmod m = \ldots = a_j \bmod m$$$, where $$$x \bmod y$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$.

Your friend Gregor wants to know the size of the largest friend group in $$$a$$$.

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

Each test case begins with a line containing the integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the size of the array $$$a$$$.

The next line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le {10}^{18}$$$), representing the contents of the array $$$a$$$. It is guaranteed that all the numbers in $$$a$$$ are distinct.

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

Output format:
Your output should consist of $$$t$$$ lines. Each line should consist of a single integer, the size of the largest friend group in $$$a$$$.

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

Note:
In the first test case, the array is $$$[1,5,2,4,6]$$$. The largest friend group is $$$[2,4,6]$$$, since all those numbers are congruent to $$$0$$$ modulo $$$2$$$, so $$$m=2$$$.

In the second test case, the array is $$$[8,2,5,10]$$$. The largest friend group is $$$[8,2,5]$$$, since all those numbers are congruent to $$$2$$$ modulo $$$3$$$, so $$$m=3$$$.

In the third case, the largest friend group is $$$[1000,2000]$$$. There are clearly many possible values of $$$m$$$ that work.

Example input:
4
5
1 5 2 4 6
4
8 2 5 10
2
1000 2000
8
465 55 3 54 234 12 45 78

Example output:
3
3
2
6

Editorial:
The key observation is to construct the difference array $$$d$$$ of size $$$N-1$$$, where $$$d[i]=A[i+1]-A[i]$$$. If a given subarray is a friend group, then every difference is a multiple of some $$$m$$$. Since every element of $$$A$$$ is distinct, the case when $$$d[i]=0$$$ can be ignored.
The other key observation is to then convert this into a GCD (greatest common divisor) problem. It follows that $$$A[i\dots j]$$$ is a friend group if and only if $$$\gcd{(d[i\dots j-1])} > 1$$$. Indeed, the value $$$m$$$ that we want is equal to this GCD.
To solve the problem, we can use a sparse table or a segment tree to find the largest possible subarray beginning at $$$i$$$, and then max over all subarray answers to get the final answer.
Time Complexity: $$$\mathcal{O}(N\log{N}\log{10^9})$$$. The first log is for the sparse table, the second is for computing GCDs.
Too Min Too Max
Contest: Codeforces Round 931 (Div. 2)
Difficulty rating: 800
Tags: greedy, math

Given an array $$$a$$$ of $$$n$$$ elements, find the maximum value of the expression:

$$$$$$|a_i - a_j| + |a_j - a_k| + |a_k - a_l| + |a_l - a_i|$$$$$$

where $$$i$$$, $$$j$$$, $$$k$$$, and $$$l$$$ are four distinct indices of the array $$$a$$$, with $$$1 \le i, j, k, l \le n$$$.

Here $$$|x|$$$ denotes the absolute value of $$$x$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$).

Output format:
For each test case, print a single integer — the maximum value.

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

Note:
In the first test case, for any selection of $$$i$$$, $$$j$$$, $$$k$$$, $$$l$$$, the answer will be $$$0$$$. For example, $$$|a_1 - a_2| + |a_2 - a_3| + |a_3 - a_4| + |a_4 - a_1| = |1 - 1| + |1 - 1| + |1 - 1| + |1 - 1| = 0 + 0 + 0 + 0 = 0$$$.

In the second test case, for $$$i = 1$$$, $$$j = 3$$$, $$$k = 2$$$, and $$$l = 5$$$, the answer will be $$$6$$$. $$$|a_1 - a_3| + |a_3 - a_2| + |a_2 - a_5| + |a_5 - a_1| = |1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| = 1 + 1 + 2 + 2 = 6$$$.

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

Example output:
0
6
38
8
8

Editorial: