1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Hossam and Friends
Contest: Codeforces Round 837 (Div. 2)
Difficulty rating: 1400
Tags: binary search, constructive algorithms, dp, two pointers

Hossam makes a big party, and he will invite his friends to the party.

He has $$$n$$$ friends numbered from $$$1$$$ to $$$n$$$. They will be arranged in a queue as follows: $$$1, 2, 3, \ldots, n$$$.

Hossam has a list of $$$m$$$ pairs of his friends that don't know each other. Any pair not present in this list are friends.

A subsegment of the queue starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is $$$[a, a + 1, a + 2, \ldots, b]$$$. A subsegment of the queue is called good when all pairs of that segment are friends.

Hossam wants to know how many pairs $$$(a, b)$$$ there are ($$$1 \le a \le b \le n$$$), such that the subsegment starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is good.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$), the number of test cases. Description of the test cases follows.

The first line of each test case contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$) representing the number of friends and the number of pairs, respectively.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$) representing a pair of Hossam's friends that don't know each other.

Note that pairs can be repeated.

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

Output format:
For each test case print an integer — the number of good subsegments.

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

Note:
In the first example, the answer is $$$4$$$.

The good subsegments are:

[1]

[2]

[3]

[1, 2]

In the second example, the answer is $$$5$$$.

The good subsegments are:

[1]

[2]

[3]

[4]

[3, 4]

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

Example output:
4
5

Editorial:
Just $$$a_i < b_i$$$ in non-friends pairs. Let's calculate $$$r_i = $$$ minimum non-friend for all people. So, we can't start subsegment in $$$a_i$$$ and finish it righter $$$r_i$$$.
Let's process people from right to left and calculate the rightmost positions there subsegment can end. Initially, $$$R = n-1$$$. Then we go to $$$a_i$$$ just do $$$R = \min(R, r_i)$$$ and add $$$R - i + 1$$$ to answer.
Hossam and Trainees
Contest: Codeforces Round 837 (Div. 2)
Difficulty rating: 1600
Tags: greedy, math, number theory

Hossam has $$$n$$$ trainees. He assigned a number $$$a_i$$$ for the $$$i$$$-th trainee.

A pair of the $$$i$$$-th and $$$j$$$-th ($$$i \neq j$$$) trainees is called successful if there is an integer $$$x$$$ ($$$x \geq 2$$$), such that $$$x$$$ divides $$$a_i$$$, and $$$x$$$ divides $$$a_j$$$.

Hossam wants to know if there is a successful pair of trainees.

Hossam is very tired now, so he asks you for your help!

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

The first line of each test case contains an integer number $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers, the number of each trainee $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output format:
Print the answer — "YES" (without quotes) if there is a successful pair of trainees and "NO" otherwise. You can print each letter in any case.

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

Note:
In the first example, the first trainee and the second trainee make up a successful pair:

$$$a_1 = 32, a_2 = 48$$$, you can choose $$$x = 4$$$.

Example input:
2
3
32 48 7
3
14 5 9

Example output:
YES
NO

Editorial:
If exists $$$x \geq 2$$$ such that $$$a_i$$$ divides $$$x$$$ and $$$a_j$$$ divides $$$x$$$ then exists prime number $$$p$$$ such that $$$a_i$$$ and $$$a_j$$$ divides $$$p$$$. We can choose $$$p = $$$ any prime divisor of $$$x$$$.
So, let's factorize all numbers and check, if two of them divides one prime number. We can use default factorization, and it will be $$$O(n \cdot \sqrt{A})$$$. It's too long, so just calculate prime numbers $$$\leq \sqrt{A}$$$ and check if $$$a_i$$$ divides this numbers. It will be $$$O(n \cdot \frac{\sqrt{A}}{\log{A}})$$$ - fast enouth.
Split it!
Contest: Codeforces Round 706 (Div. 2)
Difficulty rating: 900
Tags: brute force, constructive algorithms, greedy, strings

Kawashiro Nitori is a girl who loves competitive programming.

One day she found a string and an integer. As an advanced problem setter, she quickly thought of a problem.

Given a string $$$s$$$ and a parameter $$$k$$$, you need to check if there exist $$$k+1$$$ non-empty strings $$$a_1,a_2...,a_{k+1}$$$, such that $$$$$$s=a_1+a_2+\ldots +a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\ldots+R(a_{1}).$$$$$$

Here $$$+$$$ represents concatenation. We define $$$R(x)$$$ as a reversed string $$$x$$$. For example $$$R(abcd) = dcba$$$. Note that in the formula above the part $$$R(a_{k+1})$$$ is intentionally skipped.

Input format:
The input consists of multiple test cases. The first line contains a single 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 description contains two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 100$$$, $$$0\le k\le \lfloor \frac{n}{2} \rfloor$$$)  — the length of the string $$$s$$$ and the parameter $$$k$$$.

The second line of each test case description contains a single string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

Output format:
For each test case, print "YES" (without quotes), if it is possible to find $$$a_1,a_2,\ldots,a_{k+1}$$$, and "NO" (without quotes) otherwise.

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

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

Note:
In the first test case, one possible solution is $$$a_1=qw$$$ and $$$a_2=q$$$.

In the third test case, one possible solution is $$$a_1=i$$$ and $$$a_2=o$$$.

In the fifth test case, one possible solution is $$$a_1=dokidokiliteratureclub$$$.

Example input:
7
5 1
qwqwq
2 1
ab
3 1
ioi
4 2
icpc
22 0
dokidokiliteratureclub
19 8
imteamshanghaialice
6 3
aaaaaa

Example output:
YES
NO
YES
NO
YES
NO
NO

Editorial:
If $$$k=0$$$ or $$$s[1,k]+s[n-k+1,n]$$$ is a palindrome, the answer is yes.
Otherwise, the answer is no.
Note that when $$$2k=n$$$, the answer is no, too.
The time complexity is $$$O(n+k)$$$ for each test case.
Max and Mex
Contest: Codeforces Round 706 (Div. 2)
Difficulty rating: 1100
Tags: math

You are given a multiset $$$S$$$ initially consisting of $$$n$$$ distinct non-negative integers. A multiset is a set, that can contain some elements multiple times.

You will perform the following operation $$$k$$$ times:

- Add the element $$$\lceil\frac{a+b}{2}\rceil$$$ (rounded up) into $$$S$$$, where $$$a = \operatorname{mex}(S)$$$ and $$$b = \max(S)$$$. If this number is already in the set, it is added again.

Here $$$\operatorname{max}$$$ of a multiset denotes the maximum integer in the multiset, and $$$\operatorname{mex}$$$ of a multiset denotes the smallest non-negative integer that is not present in the multiset. For example:

- $$$\operatorname{mex}(\{1,4,0,2\})=3$$$;
- $$$\operatorname{mex}(\{2,5,1\})=0$$$.

Your task is to calculate the number of distinct elements in $$$S$$$ after $$$k$$$ operations will be done.

Input format:
The input consists of multiple test cases. The first line contains a single 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 two integers $$$n$$$, $$$k$$$ ($$$1\le n\le 10^5$$$, $$$0\le k\le 10^9$$$) — the initial size of the multiset $$$S$$$ and how many operations you need to perform.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le 10^9$$$) — the numbers in the initial multiset.

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

Output format:
For each test case, print the number of distinct elements in $$$S$$$ after $$$k$$$ operations will be done.

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

Note:
In the first test case, $$$S=\{0,1,3,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. So $$$3$$$ is added into $$$S$$$, and $$$S$$$ becomes $$$\{0,1,3,3,4\}$$$. The answer is $$$4$$$.

In the second test case, $$$S=\{0,1,4\}$$$, $$$a=\operatorname{mex}(S)=2$$$, $$$b=\max(S)=4$$$, $$$\lceil\frac{a+b}{2}\rceil=3$$$. So $$$3$$$ is added into $$$S$$$, and $$$S$$$ becomes $$$\{0,1,3,4\}$$$. The answer is $$$4$$$.

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

Example output:
4
4
3
5
3

Editorial:
Let $$$a=\max(S),b=\operatorname{mex}(S)$$$.
When $$$k=0$$$, the answer is $$$n$$$.
Otherwise if $$$b>a$$$, then $$$b=a+1$$$ , so $$$\lceil\frac{a+b}{2}\rceil=b$$$ . It's not hard to find out that $$$\max(S\cup\{b\})=b,\operatorname{mex}(S\cup\{b\})=b+1$$$, so the set $$$S$$$ always satisfies $$$\max(S)+1=\operatorname{mex}(S)$$$. So the answer is $$$n+k$$$ when $$$b=a+1$$$.
Otherwise $$$b<a$$$. So $$$b<a \Rightarrow 2b<a+b\Rightarrow \frac{a+b}{2}>b\Rightarrow\lceil\frac{a+b}{2}\rceil>b$$$. In that case $$$\operatorname{mex}(S)=b$$$ is always true. So the element we add in all operations is always $$$\lceil\frac{a+b}{2}\rceil$$$. Just check whether it is in $$$S$$$ at first.
The time complexity is $$$O(n)$$$ or $$$O(n \log n)$$$ for each test case depending on your implementation.