yl-9/probench huggingface dataset:
# Photoshoot for Gorillas

## Problem Description

You really love gorillas, so you decided to organize a photoshoot for them. Gorillas live in the jungle. The jungle is represented as a grid of $ n $ rows and $ m $ columns. $ w $ gorillas agreed to participate in the photoshoot, and the gorilla with index $ i $ ( $ 1 \le i \le w $ ) has a height of $ a_i $ . You want to place all the gorillas in the cells of the grid such that there is no more than one gorilla in each cell.

The spectacle of the arrangement is equal to the sum of the spectacles of all sub-squares of the grid with a side length of $ k $ .

The spectacle of a sub-square is equal to the sum of the heights of the gorillas in it.

From all suitable arrangements, choose the arrangement with the maximum spectacle.

## Input Format

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

The descriptions of the test cases follow.

The first line contains integers $ n $ , $ m $ , $ k $ ( $ 1 \le n, m \le 2 \cdot 10^5 $ , $ 1 \le n \cdot m \le 2 \cdot 10^5 $ , $ 1 \le k \le \min(n, m) $ ) — the dimensions of the grid and the side length of the square.

The second line contains an integer $ w $ ( $ 1 \le w \le n \cdot m $ ) — the number of gorillas.

The third line contains $ w $ integers $ a_1, a_2, \ldots, a_w $ ( $ 1 \le a_i \le 10^9 $ ) — the heights of the gorillas.

It is guaranteed that the sum of $ n \cdot m $ across all test cases does not exceed $ 2 \cdot 10^5 $ . The same guarantee applies to $ w $ .

## Output Format

For each test case, output a single integer — the maximum spectacle of a suitable arrangement.

## Sample #1

### Sample Input #1

```
5
3 4 2
9
1 1 1 1 1 1 1 1 1
2 1 1
2
5 7
20 15 7
9
4 1 4 5 6 1 1000000000 898 777
1984 1 1
4
5 4 1499 2004
9 5 5
6
6 7 14 16 16 6
```

### Sample Output #1

```
21
12
49000083104
3512
319
```

## Hint

In the first test case of the first input set, the spectacle of the following sub-squares is summed:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2000E/b97739f14b46eed8bd7b574f0209e05c71109d45.png) Yellow color corresponds to the sub-squares, green — to the rest of the grid squares.The picture shows the optimal arrangement of the gorillas. The spectacle of the arrangement is $ 4 + 4 + 3 + 3 + 4 + 3 = 21 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, data structures, greedy, math
Difficulty: 1400
# Right Left Wrong

## Problem Description

Vlad found a strip of $ n $ cells, numbered from left to right from $ 1 $ to $ n $ . In the $ i $ -th cell, there is a positive integer $ a_i $ and a letter $ s_i $ , where all $ s_i $ are either 'L' or 'R'.

Vlad invites you to try to score the maximum possible points by performing any (possibly zero) number of operations.

In one operation, you can choose two indices $ l $ and $ r $ ( $ 1 \le l < r \le n $ ) such that $ s_l $ = 'L' and $ s_r $ = 'R' and do the following:

- add $ a_l + a_{l + 1} + \dots + a_{r - 1} + a_r $ points to the current score;
- replace $ s_i $ with '.' for all $ l \le i \le r $ , meaning you can no longer choose these indices.

For example, consider the following strip:

  $ 3 $  $ 5 $  $ 1 $  $ 4 $  $ 3 $  $ 2 $ LRLLLRYou can first choose $ l = 1 $ , $ r = 2 $ and add $ 3 + 5 = 8 $ to your score.

  $ 3 $  $ 5 $  $ 1 $  $ 4 $  $ 3 $  $ 2 $ ..LLLRThen choose $ l = 3 $ , $ r = 6 $ and add $ 1 + 4 + 3 + 2 = 10 $ to your score.

  $ 3 $  $ 5 $  $ 1 $  $ 4 $  $ 3 $  $ 2 $ ......As a result, it is impossible to perform another operation, and the final score is $ 18 $ .

What is the maximum score that can be achieved?

## Input Format

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

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

The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^5 $ ) — the numbers written on the strip.

The third line of each test case contains a string $ s $ of $ n $ characters 'L' and 'R'.

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

## Output Format

For each test case, output one integer — the maximum possible number of points that can be scored.

## Sample #1

### Sample Input #1

```
4
6
3 5 1 4 3 2
LRLLLR
2
2 8
LR
2
3 9
RL
5
1 2 3 4 5
LRLRR
```

### Sample Output #1

```
18
10
0
22
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, implementation, two pointers
Difficulty: 1200
# Numeric String Template

## Problem Description

Kristina has an array $ a $ , called a template, consisting of $ n $ integers. She also has $ m $ strings, each consisting only of lowercase Latin letters. The strings are numbered from $ 1 $ to $ m $ . She wants to check which strings match the template.

A string $ s $ is considered to match the template if all of the following conditions are simultaneously satisfied:

- The length of the string $ s $ is equal to the number of elements in the array $ a $ .
- The same numbers from $ a $ correspond to the same symbols from $ s $ . So, if $ a_i = a_j $ , then $ s_i = s_j $ for ( $ 1 \le i, j \le n $ ).
- The same symbols from $ s $ correspond to the same numbers from $ a $ . So, if $ s_i = s_j $ , then $ a_i = a_j $ for ( $ 1 \le i, j \le n $ ).

 In other words, there must be a one-to-one correspondence between the characters of the string and the elements of the array.For example, if $ a $ = \[ $ 3, 5, 2, 1, 3 $ \], then the string "abfda" matches the template, while the string "afbfa" does not, since the character "f" corresponds to both numbers $ 1 $ and $ 5 $ .

## 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 descriptions are for the test cases.

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

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

The third line of each test case contains a single integer $ m $ ( $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of strings to check for template matching.

Following are $ m $ strings, each containing a non-empty string $ s_j $ ( $ 1 \le |s_j| \le 2 \cdot 10^5 $ ), consisting of lowercase Latin letters.

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ , and that the sum of the lengths of all strings does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output $ m $ lines. On the $ i $ -th line ( $ 1 \le i \le m $ ) output:

- "YES", if the string with index $ i $ matches the template;
- "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).

## Sample #1

### Sample Input #1

```
3
5
3 5 2 1 3
2
abfda
afbfa
2
1 2
3
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb
```

### Sample Output #1

```
YES
NO
YES
NO
NO
NO
YES
NO
YES
```

## Hint

The first test case is explained in the problem statement.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, strings
Difficulty: 1000
# Seating in a Bus

## Problem Description

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).

## Sample #1

### Sample Input #1

```
4
5
5 4 2 1 3
3
2 3 1
4
2 3 1 4
5
1 2 3 5 4
```

### Sample Output #1

```
NO
YES
YES
NO
```

## Hint

The first test case is explained in the problem statement.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: two pointers
Difficulty: 800
# Primary Task

## Problem Description

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.

## Sample #1

### Sample Input #1

```
7
100
1010
101
105
2033
1019
1002
```

### Sample Output #1

```
NO
YES
NO
YES
NO
YES
NO
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation, math, strings
Difficulty: 800
# Expected Median

## Problem Description

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 $ .

 $ ^{\text{∗}} $ A binary array is an array consisting only of zeros and ones.

 $ ^{\text{†}} $ An array $ b $ is a subsequence of an array $ a $ if $ b $ can be obtained from $ a $ by the deletion of several (possibly, zero or all) elements. Subsequences don't have to be contiguous.

 $ ^{\text{‡}} $ The median of an array of odd length $ k $ is the $ \frac{k+1}{2} $ -th element when sorted.

## 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 $ .

## Sample #1

### Sample Input #1

```
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
```

### Sample Output #1

```
2
5
0
16
4
7
0
333606206
```

## Hint

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 $ .

 The sum of the results is $ 0+1+1+0=2 $ .In the second test case, all subsequences of length $ 1 $ have median $ 1 $ , so the answer is $ 5 $ .

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: combinatorics, math
Difficulty: 1500
# Triple Operations

## Problem Description

On the board Ivy wrote down all integers from $ l $ to $ r $ , inclusive.

In an operation, she does the following:

- pick two numbers $ x $ and $ y $ on the board, erase them, and in their place write the numbers $ 3x $ and $ \lfloor \frac{y}{3} \rfloor $ . (Here $ \lfloor \bullet \rfloor $ denotes rounding down to the nearest integer).

What is the minimum number of operations Ivy needs to make all numbers on the board equal $ 0 $ ? We have a proof that this is always possible.

## Input Format

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

The only line of each test case contains two integers $ l $ and $ r $ ( $ 1 \leq l < r \leq 2 \cdot 10^5 $ ).

## Output Format

For each test case, output a single integer — the minimum number of operations needed to make all numbers on the board equal $ 0 $ .

## Sample #1

### Sample Input #1

```
4
1 3
2 4
199999 200000
19 84
```

### Sample Output #1

```
5
6
36
263
```

## Hint

In the first test case, we can perform $ 5 $ operations as follows: $ $$$ 1,2,3 \xrightarrow[x=1,\,y=2]{} 3,0,3 \xrightarrow[x=0,\,y=3]{} 1,0,3 \xrightarrow[x=0,\,y=3]{} 1,0,1 \xrightarrow[x=0,\,y=1]{} 0,0,1 \xrightarrow[x=0,\,y=1]{} 0,0,0 . $ $$$

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: dp, implementation, math
Difficulty: 1300
# Slavic's Exam

## Problem Description

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.

## Sample #1

### Sample Input #1

```
5
?????
xbx
ab??e
abcde
ayy?x
a
ab??e
dac
paiu
mom
```

### Sample Output #1

```
YES
xabax
YES
abcde
YES
ayyyx
NO
NO
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, implementation, strings
Difficulty: 1100
# Showering

## Problem Description

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 $ ?

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1999C/f37c16ccee56dc0e812638d809cb1411cb80cf1b.png)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).

## Sample #1

### Sample Input #1

```
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
```

### Sample Output #1

```
YES
YES
NO
YES
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Card Game

## Problem Description

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.

## Sample #1

### Sample Input #1

```
5
3 8 2 6
1 1 1 1
10 10 2 2
1 1 10 10
3 8 7 2
```

### Sample Output #1

```
2
0
4
0
2
```

## Hint

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.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, implementation
Difficulty: 1000
# A+B Again?

## Problem Description

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 $ .

## Sample #1

### Sample Input #1

```
8
77
21
40
34
19
84
10
99
```

### Sample Output #1

```
14
3
4
7
10
12
1
18
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation, math
Difficulty: 800