1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Penchick and Desert Rabbit
Contest: Codeforces Round 987 (Div. 2)
Difficulty rating: 1700
Tags: binary search, data structures, dfs and similar, dp, dsu, greedy, implementation, two pointers

Dedicated to pushing himself to his limits, Penchick challenged himself to survive the midday sun in the Arabian Desert!

While trekking along a linear oasis, Penchick spots a desert rabbit preparing to jump along a line of palm trees. There are $$$n$$$ trees, each with a height denoted by $$$a_i$$$.

The rabbit can jump from the $$$i$$$-th tree to the $$$j$$$-th tree if exactly one of the following conditions is true:

- $$$j < i$$$ and $$$a_j > a_i$$$: the rabbit can jump backward to a taller tree.
- $$$j > i$$$ and $$$a_j < a_i$$$: the rabbit can jump forward to a shorter tree.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, determine the maximum height among all trees that the rabbit can reach if it starts from the $$$i$$$-th tree.

Input format:
The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the number of trees.

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

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

Output format:
For each test case, output $$$n$$$ integers. The $$$i$$$-th integer should contain the maximum height among all trees that the rabbit can reach if it starts from the $$$i$$$-th tree.

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

Note:
In the first test case, the initial heights of trees are $$$a = [2, 3, 1, 4]$$$.

- If the rabbit starts from the first tree, it can jump to the third tree as $$$3 > 1$$$ and $$$1 < 2$$$. Then, the rabbit can jump to the second tree as $$$2 < 3$$$ and $$$3 > 1$$$. It can be proved that the rabbit cannot reach the fourth tree; hence, the maximum height of the tree that the rabbit can reach is $$$a_2 = 3$$$.
- If the rabbit starts from the fourth tree, it does not need to jump anywhere as it is already at the highest tree.

In the second test case, the rabbit can jump to the first tree regardless of which tree it starts from.

In the fifth test case, if the rabbit starts from the fifth tree, it can jump to the fourth tree. Then the rabbit can jump to the seventh tree and finally reach the sixth tree. Therefore, the maximum height of the tree that the rabbit can reach is $$$8$$$.

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

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

Editorial:
Penchick and Chloe's Trees
Contest: Codeforces Round 987 (Div. 2)
Difficulty rating: 2100
Tags: data structures, dfs and similar, dp, greedy, implementation, math, sortings, trees

With just a few hours left until Penchick and Chloe leave for Singapore, they could hardly wait to see the towering trees at the Singapore Botanic Gardens! Attempting to contain their excitement, Penchick crafted a rooted tree to keep Chloe and himself busy.

Penchick has a rooted tree$$$^{\text{∗}}$$$ consisting of $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$, with vertex $$$1$$$ as the root, and Chloe can select a non-negative integer $$$d$$$ to create a perfect binary tree$$$^{\text{†}}$$$ of depth $$$d$$$.

Since Penchick and Chloe are good friends, Chloe wants her tree to be isomorphic$$$^{\text{‡}}$$$ to Penchick's tree. To meet this condition, Chloe can perform the following operation on her own tree any number of times:

- Select an edge $$$(u,v)$$$, where $$$u$$$ is the parent of $$$v$$$.
- Remove vertex $$$v$$$ and all the edges connected to $$$v$$$, then connect all of $$$v$$$'s previous children directly to $$$u$$$.

In particular, doing an operation on an edge $$$(u, v)$$$ where $$$v$$$ is a leaf will delete vertex $$$v$$$ without adding any new edges.

Since constructing a perfect binary tree can be time-consuming, Chloe wants to choose the minimum $$$d$$$ such that a perfect binary tree of depth $$$d$$$ can be made isomorphic to Penchick's tree using the above operation. Note that she can't change the roots of the trees.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the number of vertices in Penchick's tree.

The second line of each test case contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq i-1$$$) — the parent of vertex $$$i$$$.

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

Output format:
For each test case, output a single integer on each line: the minimum depth of Chloe's perfect binary tree.

Constraints:
Time limit: 3.5 s
Memory limit: 512.0 MB

Note:
For the first test case, create a perfect binary tree with depth $$$2$$$.

Consider carrying out the operation on edge $$$AC$$$. Then the edges $$$AC$$$, $$$CF$$$, and $$$CG$$$ are removed, and edges $$$AF$$$ and $$$AG$$$ are added.

The resulting tree is isomorphic to the tree given in the input. It can be proven that no sequence of operations carried out on a binary tree of depth less than $$$2$$$ can lead to a tree isomorphic to the tree given in the input.

In the second test case, the tree is already isomorphic to a perfect binary tree of depth $$$3$$$.

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

Example output:
2
3
3
3
3

Editorial:
A+B Again?
Contest: Codeforces Round 964 (Div. 4)
Difficulty rating: 800
Tags: implementation, math

Given a two-digit positive integer $$$n$$$, find the sum of its digits.

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

The only line of each test case contains a single two-digit positive integer $$$n$$$ ($$$10 \leq n \leq 99$$$).

Output format:
For each test case, output a single integer — the sum of the digits of $$$n$$$.

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

Example input:
8
77
21
40
34
19
84
10
99

Example output:
14
3
4
7
10
12
1
18

Editorial:
You can take the input as a string and output the sum of the two characters in the string.
There is also a formula: $$$\lfloor \frac{n}{10} \rfloor + n \bmod 10$$$. The first term is the tens digit, the second term — the ones digit.
Card Game
Contest: Codeforces Round 964 (Div. 4)
Difficulty rating: 1000
Tags: brute force, constructive algorithms, implementation

Suneet and Slavic play a card game. The rules of the game are as follows:

- Each card has an integer value between $$$1$$$ and $$$10$$$.
- Each player receives $$$2$$$ cards which are face-down (so a player doesn't know their cards).
- The game is turn-based and consists exactly of two turns. In a round, both players pick a random unflipped card and flip it. The player who flipped a card with a strictly greater number wins the round. In case of equality, no one wins the round.
- A player wins a game if he wins the most number of rounds (i.e. strictly greater than the other player). In case of equality, no one wins the game.

Since Suneet and Slavic aren't best friends, you need to calculate the number of ways the game could happen that Suneet would end up as the winner.

For a better understanding, please check the notes section.

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

The first and only line of each test case contains $$$4$$$ integers $$$a_1$$$, $$$a_2$$$, $$$b_1$$$, $$$b_2$$$ ($$$1 \leq a_1, a_2, b_1, b_2 \leq 10$$$) where $$$a_1$$$ and $$$a_2$$$ represent the cards Suneet has, and $$$b_1$$$ and $$$b_2$$$ represent the cards Slavic has, respectively.

Output format:
For each test case, output a single integer — the number of games Suneet would win considering all possible games.

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

Note:
Consider the first test case when Slavic starts with the cards that have the values $$$2$$$ and $$$6$$$, and Suneet starts with cards that have the values $$$3$$$ and $$$8$$$. The game could happen in $$$4$$$ different ways:

- Suneet flips $$$3$$$ and Slavic flips $$$2$$$. Suneet wins the first round. Then, Suneet flips $$$8$$$ and Slavic flips $$$6$$$. Suneet wins the second round as well. Since Suneet won $$$2$$$ rounds, he wins the game.
- Suneet flips $$$3$$$ and Slavic flips $$$6$$$. Slavic wins the first round. Then, Suneet flips $$$8$$$ and Slavic flips $$$2$$$. Suneet wins the second round. Nobody wins since both players won an equal amount of rounds.
- Suneet flips $$$8$$$ and Slavic flips $$$6$$$. Suneet wins the first round. Then, Suneet flips $$$3$$$ and Slavic flips $$$2$$$. Suneet wins the second round as well. Since Suneet won $$$2$$$ rounds, he wins the game.
- Suneet flips $$$8$$$ and Slavic flips $$$2$$$. Suneet wins the first round. Then, Suneet flips $$$3$$$ and Slavic flips $$$6$$$. Slavic wins the round. Nobody wins since both players won an equal amount of rounds.

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

Example output:
2
0
4
0
2

Editorial:
For each test case, we can brute force through all possible games (there are only four of them) and calculate who is the winner of the game by simulating the game.
Showering
Contest: Codeforces Round 964 (Div. 4)
Difficulty rating: 800
Tags: greedy, implementation

As a computer science student, Alex faces a hard challenge — showering. He tries to shower daily, but despite his best efforts there are always challenges. He takes $$$s$$$ minutes to shower and a day only has $$$m$$$ minutes!

He already has $$$n$$$ tasks planned for the day. Task $$$i$$$ is represented as an interval $$$(l_i$$$, $$$r_i)$$$, which means that Alex is busy and can not take a shower in that time interval (at any point in time strictly between $$$l_i$$$ and $$$r_i$$$). No two tasks overlap.

Given all $$$n$$$ time intervals, will Alex be able to shower that day? In other words, will Alex have a free time interval of length at least $$$s$$$?

In the first test case, Alex can shower for the first $$$3$$$ minutes of the day and not miss any of the tasks.

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

The first line of each test case contains three integers $$$n$$$, $$$s$$$, and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq s, m \leq 10^9$$$) — the number of time intervals Alex already has planned, the amount of time Alex takes to take a shower, and the amount of minutes a day has.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i < r_i \leq m$$$) — the time interval of the $$$i$$$-th task. No two tasks overlap.

Additional constraint on the input: $$$l_i > r_{i-1}$$$ for every $$$i > 1$$$.

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

Output format:
For each test case output "YES" (without quotes) if Alex can take a shower for that given test case, and "NO" (also without quotes) otherwise.

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

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

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

Example output:
YES
YES
NO
YES

Editorial:
We just need to find the lengths of the gaps between intervals. Note that from the additional constraint on the input, the intervals are in sorted order. So you need to find if for any $$$i > 1$$$, $$$l_i - r_{i - 1} \geq s$$$, and also if $$$l_1 \geq s$$$ (the initial interval), or if $$$m - r_{n} \geq s$$$ (the final interval).
Slavic's Exam
Contest: Codeforces Round 964 (Div. 4)
Difficulty rating: 1100
Tags: greedy, implementation, strings

Slavic has a very tough exam and needs your help in order to pass it. Here is the question he is struggling with:

There exists a string $$$s$$$, which consists of lowercase English letters and possibly zero or more "?".

Slavic is asked to change each "?" to a lowercase English letter such that string $$$t$$$ becomes a subsequence (not necessarily continuous) of the string $$$s$$$.

Output any such string, or say that it is impossible in case no string that respects the conditions exists.

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

The first line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$, and $$$s$$$ consists only of lowercase English letters and "?"-s)  – the original string you have.

The second line of each test case contains a single string $$$t$$$ ($$$1 \leq |t| \leq |s|$$$, and $$$t$$$ consists only of lowercase English letters)  – the string that should be a subsequence of string $$$s$$$.

The sum of $$$|s|$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$, where $$$|x|$$$ denotes the length of the string $$$x$$$.

Output format:
For each test case, if no such string exists as described in the statement, output "NO" (without quotes).

Otherwise, output "YES" (without quotes). Then, output one line — the string that respects all conditions.

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

If multiple answers are possible, you can output any of them.

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

Example input:
5
?????
xbx
ab??e
abcde
ayy?x
a
ab??e
dac
paiu
mom

Example output:
YES
xabax
YES
abcde
YES
ayyyx
NO
NO

Editorial:
Let's use a greedy strategy with two pointers, one at the start of $$$s$$$ (called $$$i$$$) and one at the start of $$$t$$$ (called $$$j$$$). At each step, advance $$$i$$$ by $$$1$$$. If $$$s_i = \texttt{?}$$$, then we set it to $$$t_j$$$ and increment $$$j$$$. If $$$s_i = t_j$$$ then we also increment $$$j$$$ (because there is a match).
It works because if there is ever a question mark, it never makes it worse to match the current character in $$$t$$$ earlier than later. The complexity is $$$\mathcal{O}(n)$$$.
Expected Median
Contest: Codeforces Round 964 (Div. 4)
Difficulty rating: 1500
Tags: combinatorics, math

Arul has a binary array$$$^{\text{∗}}$$$ $$$a$$$ of length $$$n$$$.

He will take all subsequences$$$^{\text{†}}$$$ of length $$$k$$$ ($$$k$$$ is odd) of this array and find their median.$$$^{\text{‡}}$$$

What is the sum of all these values?

As this sum can be very large, output it modulo $$$10^9 + 7$$$. In other words, print the remainder of this sum when divided by $$$10^9 + 7$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$k$$$ is odd) — the length of the array and the length of the subsequence, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.

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

Output format:
For each test case, print the sum modulo $$$10^9 + 7$$$.

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

Note:
In the first test case, there are four subsequences of $$$[1,0,0,1]$$$ with length $$$k=3$$$:

- $$$[1,0,0]$$$: median $$$= 0$$$.
- $$$[1,0,1]$$$: median $$$= 1$$$.
- $$$[1,0,1]$$$: median $$$= 1$$$.
- $$$[0,0,1]$$$: median $$$= 0$$$.

In the second test case, all subsequences of length $$$1$$$ have median $$$1$$$, so the answer is $$$5$$$.

Example input:
8
4 3
1 0 0 1
5 1
1 1 1 1 1
5 5
0 1 0 1 0
6 3
1 0 1 0 1 1
4 3
1 0 1 1
5 3
1 0 1 1 0
2 1
0 0
34 17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Example output:
2
5
0
16
4
7
0
333606206

Editorial:
Say the array has $$$x$$$ ones and $$$y$$$ zeroes.
If the median of a subsequence of length $$$k$$$ is $$$1$$$, then there are at least $$$\lfloor \frac{k}{2} \rfloor + 1$$$ ones in the array.
Let's iterate over the number of ones in the subsequence from $$$\lfloor \frac{k}{2} \rfloor + 1$$$ to $$$x$$$. Suppose there are $$$i$$$ ones. Then there are $$$k - i$$$ zeroes. The number of ways to choose $$$i$$$ ones from $$$x$$$ is $$$\binom{x}{i}$$$, that is, $$$x$$$ choose $$$i$$$ (this is the so-called binomial coefficient). Similarly, the number of ways to choose $$$k-i$$$ zeroes from $$$y$$$ of them is $$$\binom{y}{k-i}$$$.
Therefore the answer is the sum of $$$\binom{x}{i}\binom{y}{k-i}$$$ over all $$$i$$$ from $$$\lfloor \frac{k}{2} \rfloor + 1$$$ to $$$x$$$. You can compute binomial coefficients in many ways, for example precomputing all factorials and then using the formula $$$\binom{n}{k} = \frac{n!}{(n-k)!k!}$$$. Depending on your implementation, it can take $$$\mathcal{O}(n \log \mathrm{MOD})$$$ or $$$\mathcal{O}(n + \log \mathrm{MOD})$$$ time.
If you don't know how to do that, we recommend you read the article.
Primary Task
Contest: Codeforces Round 966 (Div. 3)
Difficulty rating: 800
Tags: implementation, math, strings

Dmitry wrote down $$$t$$$ integers on the board, and that is good. He is sure that he lost an important integer $$$n$$$ among them, and that is bad.

The integer $$$n$$$ had the form $$$\text{10^x}$$$ ($$$x \ge 2$$$), where the symbol '$$$\text{^}$$$' denotes exponentiation.. Something went wrong, and Dmitry missed the symbol '$$$\text{^}$$$' when writing the important integer. For example, instead of the integer $$$10^5$$$, he would have written $$$105$$$, and instead of $$$10^{19}$$$, he would have written $$$1019$$$.

Dmitry wants to understand which of the integers on the board could have been the important integer and which could not.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of integers on the board.

The next $$$t$$$ lines each contain an integer $$$a$$$ ($$$1 \le a \le 10000$$$) — the next integer from the board.

Output format:
For each integer on the board, output "YES" if it could have been the important integer and "NO" otherwise.

You may output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

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

Example input:
7
100
1010
101
105
2033
1019
1002

Example output:
NO
YES
NO
YES
NO
YES
NO

Editorial:
You need to check that the number has the form '$$$\text{10x}$$$', where $$$x$$$ is an integer without leading zeros. This means it must start with '10'; if the length of the number is $$$3$$$, then the third digit must be at least $$$2$$$; if the length is greater, then the third digit must be at least $$$1$$$ (all such numbers $$$x$$$ are at least $$$10$$$).
Additionally, under these constraints, you can simply check that for the given number $$$a$$$, either $$$102 \le a \le 109$$$ or $$$1010 \le a \le 1099$$$ holds true.
Seating in a Bus
Contest: Codeforces Round 966 (Div. 3)
Difficulty rating: 800
Tags: two pointers

In Berland, a bus consists of a row of $$$n$$$ seats numbered from $$$1$$$ to $$$n$$$. Passengers are advised to always board the bus following these rules:

- If there are no occupied seats in the bus, a passenger can sit in any free seat;
- Otherwise, a passenger should sit in any free seat that has at least one occupied neighboring seat. In other words, a passenger can sit in a seat with index $$$i$$$ ($$$1 \le i \le n$$$) only if at least one of the seats with indices $$$i-1$$$ or $$$i+1$$$ is occupied.

Today, $$$n$$$ passengers boarded the bus. The array $$$a$$$ chronologically records the seat numbers they occupied. That is, $$$a_1$$$ contains the seat number where the first passenger sat, $$$a_2$$$ — the seat number where the second passenger sat, and so on.

You know the contents of the array $$$a$$$. Determine whether all passengers followed the recommendations.

For example, if $$$n = 5$$$, and $$$a$$$ = [$$$5, 4, 2, 1, 3$$$], then the recommendations were not followed, as the $$$3$$$-rd passenger sat in seat number $$$2$$$, while the neighboring seats with numbers $$$1$$$ and $$$3$$$ were free.

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

The following describes the input test cases.

The first line of each test case contains exactly one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of seats in the bus and the number of passengers who boarded the bus.

The second line of each test case contains $$$n$$$ distinct integers $$$a_i$$$ ($$$1 \le a_i \le n$$$) — the seats that the passengers occupied in chronological order.

It is guaranteed that the sum of $$$n$$$ values across all test cases does not exceed $$$2 \cdot 10^5$$$, and that no passenger sits in an already occupied seat.

Output format:
For each test case, output on a separate line:

- "YES", if all passengers followed the recommendations;
- "NO" otherwise.

You may 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: 2.0 s
Memory limit: 256.0 MB

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

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

Example output:
NO
YES
YES
NO

Editorial:
To solve the problem, it is enough to use an array $$$used$$$ of size $$$2 \cdot 10^5 + 1$$$ (maximal value $$$n + 1$$$) consisting of boolean variables.
When a passenger gets on the bus to seat $$$a_i$$$, we will replace the value of $$$used[a_i]$$$ with true. Then, for all passengers, starting from the second one, we should check that at least one of the existing elements $$$used[a_i - 1]$$$ or $$$used[a_i + 1]$$$ has the value true.
If this condition is not satisfied, the answer to the problem is "NO". If at least $$$1$$$ occupied neighbouring seat always existed for all passengers at the moment they took their seat — the answer is "YES".