yl-9/probench huggingface dataset:
# Game with Doors

## Problem Description

There are $ 100 $ rooms arranged in a row and $ 99 $ doors between them; the $ i $ -th door connects rooms $ i $ and $ i+1 $ . Each door can be either locked or unlocked. Initially, all doors are unlocked.

We say that room $ x $ is reachable from room $ y $ if all doors between them are unlocked.

You know that:

- Alice is in some room from the segment $ [l, r] $ ;
- Bob is in some room from the segment $ [L, R] $ ;
- Alice and Bob are in different rooms.

However, you don't know the exact rooms they are in.

You don't want Alice and Bob to be able to reach each other, so you are going to lock some doors to prevent that. What's the smallest number of doors you have to lock so that Alice and Bob cannot meet, regardless of their starting positions inside the given segments?

## 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 two integers $ l $ and $ r $ ( $ 1 \le l < r \le 100 $ ) — the bounds of the segment of rooms where Alice is located.

The second line of each test case contains two integers $ L $ and $ R $ ( $ 1 \le L < R \le 100 $ ) — the bounds of the segment of rooms where Bob is located.

## Output Format

For each test case, print a single integer — the smallest number of doors you have to lock so that Alice and Bob cannot meet, regardless of their starting positions inside the given segments.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
1
3
2
3
```

## Hint

In the first test case, it is sufficient to lock the door between rooms $ 2 $ and $ 3 $ .

In the second test case, the following doors have to be locked: $ (2,3) $ , $ (3,4) $ , $ (4,5) $ .

In the third test case, the following doors have to be locked: $ (5, 6) $ and $ (6,7) $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, greedy
Difficulty: 1000
# Closest Point

## Problem Description

Consider a set of points on a line. The distance between two points $ i $ and $ j $ is $ |i - j| $ .

The point $ i $ from the set is the closest to the point $ j $ from the set, if there is no other point $ k $ in the set such that the distance from $ j $ to $ k $ is strictly less than the distance from $ j $ to $ i $ . In other words, all other points from the set have distance to $ j $ greater or equal to $ |i - j| $ .

For example, consider a set of points $ \{1, 3, 5, 8\} $ :

- for the point $ 1 $ , the closest point is $ 3 $ (other points have distance greater than $ |1-3| = 2 $ );
- for the point $ 3 $ , there are two closest points: $ 1 $ and $ 5 $ ;
- for the point $ 5 $ , the closest point is $ 3 $ (but not $ 8 $ , since its distance is greater than $ |3-5| $ );
- for the point $ 8 $ , the closest point is $ 5 $ .

You are given a set of points. You have to add an integer point into this set in such a way that it is different from every existing point in the set, and it becomes the closest point to every point in the set. Is it possible?

## Input Format

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

Each test case consists of two lines:

- the first line contains one integer $ n $ ( $ 2 \le n \le 40 $ ) — the number of points in the set;
- the second line contains $ n $ integers $ x_1, x_2, \dots, x_n $ ( $ 1 \le x_1 < x_2 < \dots < x_n \le 100 $ ) — the points from the set.

## Output Format

For each test case, print YES if it is possible to add a new point according to the conditions from the statement. Otherwise, print NO.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
YES
NO
NO
```

## Hint

In the first example, the point $ 7 $ will be the closest to both $ 3 $ and $ 8 $ .

In the second example, it is impossible to add an integer point so that it becomes the closest to both $ 5 $ and $ 6 $ , and is different from both of them.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: implementation, math
Difficulty: 800
# Turtle and Three Sequences

## Problem Description

Piggy gives Turtle three sequences $ a_1, a_2, \ldots, a_n $ , $ b_1, b_2, \ldots, b_n $ , and $ c_1, c_2, \ldots, c_n $ .

Turtle will choose a subsequence of $ 1, 2, \ldots, n $ of length $ m $ , let it be $ p_1, p_2, \ldots, p_m $ . The subsequence should satisfy the following conditions:

- $ a_{p_1} \le a_{p_2} \le \cdots \le a_{p_m} $ ;
- All $ b_{p_i} $ for all indices $ i $ are pairwise distinct, i.e., there don't exist two different indices $ i $ , $ j $ such that $ b_{p_i} = b_{p_j} $ .

Help him find the maximum value of $ \sum\limits_{i = 1}^m c_{p_i} $ , or tell him that it is impossible to choose a subsequence of length $ m $ that satisfies the conditions above.

Recall that a sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements.

## Input Format

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 3000 $ , $ 1 \le m \le 5 $ ) — the lengths of the three sequences and the required length of the subsequence.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of the sequence $ a $ .

The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le n $ ) — the elements of the sequence $ b $ .

The fourth line contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \le c_i \le 10^4 $ ) — the elements of the sequence $ c $ .

## Output Format

Output a single integer — the maximum value of $ \sum\limits_{i = 1}^m c_{p_i} $ . If it is impossible to choose a subsequence of length $ m $ that satisfies the conditions above, output $ -1 $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
5
```

## Sample #2

### Sample Input #2

```
7 3
1 4 5 2 3 6 7
1 2 2 1 1 3 2
1 5 6 7 3 2 4
```

### Sample Output #2

```
13
```

## Sample #3

### Sample Input #3

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

### Sample Output #3

```
-1
```

## Hint

In the first example, we can choose $ p = [1, 2] $ , then $ c_{p_1} + c_{p_2} = 1 + 4 = 5 $ . We can't choose $ p = [2, 4] $ since $ a_2 > a_4 $ , violating the first condition. We can't choose $ p = [2, 3] $ either since $ b_2 = b_3 $ , violating the second condition. We can choose $ p = [1, 4] $ , but $ c_1 + c_4 = 4 $ , which isn't maximum.

In the second example, we can choose $ p = [4, 6, 7] $ .

In the third example, it is impossible to choose a subsequence of length $ 3 $ that satisfies both of the conditions.

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: brute force, data structures, dp, greedy, math, probabilities, two pointers
Difficulty: 2800
# Turtle and Inversions (Hard Version)

## Problem Description

This is a hard version of this problem. The differences between the versions are the constraint on $ m $ and $ r_i < l_{i + 1} $ holds for each $ i $ from $ 1 $ to $ m - 1 $ in the easy version. You can make hacks only if both versions of the problem are solved.

Turtle gives you $ m $ intervals $ [l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m] $ . He thinks that a permutation $ p $ is interesting if there exists an integer $ k_i $ for every interval ( $ l_i \le k_i < r_i $ ), and if he lets $ a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i} p_j $ for every integer $ i $ from $ 1 $ to $ m $ , the following condition holds:

 $ $$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i $ $ </p><p>Turtle wants you to calculate the maximum number of inversions of all interesting permutations of length  $ n $ , or tell him if there is no interesting permutation.</p><p>An inversion of a permutation  $ p $  is a pair of integers  $ (i, j) $  ( $ 1 \\le i &lt; j \\le n $ ) such that  $ p\_i &gt; p\_j$$$.

## Input Format

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

The first line of each test case contains two integers $ n, m $ ( $ 2 \le n \le 5 \cdot 10^3, 0 \le m \le 5 \cdot 10^3 $ ) — the length of the permutation and the number of intervals.

The $ i $ -th of the following $ m $ lines contains two integers $ l_i, r_i $ ( $ 1 \le l_i < r_i \le n $ ) — the $ i $ -th interval. Note that there may exist identical intervals (i.e., there may exist two different indices $ i, j $ such that $ l_i = l_j $ and $ r_i = r_j $ ).

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

## Output Format

For each test case, if there is no interesting permutation, output a single integer $ -1 $ .

Otherwise, output a single integer — the maximum number of inversions.

## Sample #1

### Sample Input #1

```
8
2 0
2 1
1 2
5 1
2 4
8 3
1 4
2 5
7 8
7 2
1 4
4 7
7 3
1 2
1 7
3 7
7 4
1 3
4 7
1 3
4 7
7 3
1 2
3 4
5 6
```

### Sample Output #1

```
1
0
8
18
-1
-1
15
15
```

## Hint

In the third test case, the interesting permutation with the maximum number of inversions is $ [5, 2, 4, 3, 1] $ .

In the fourth test case, the interesting permutation with the maximum number of inversions is $ [4, 3, 8, 7, 6, 2, 1, 5] $ . In this case, we can let $ [k_1, k_2, k_3] = [2, 2, 7] $ .

In the fifth and the sixth test case, it can be proven that there is no interesting permutation.

In the seventh test case, the interesting permutation with the maximum number of inversions is $ [4, 7, 6, 3, 2, 1, 5] $ . In this case, we can let $ [k_1, k_2, k_3, k_4] = [1, 6, 1, 6] $ .

In the eighth test case, the interesting permutation with the maximum number of inversions is $ [4, 7, 3, 6, 2, 5, 1] $ .

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, data structures, divide and conquer, dp, greedy, math, two pointers
Difficulty: 2700
# Turtle and Inversions (Easy Version)

## Problem Description

This is an easy version of this problem. The differences between the versions are the constraint on $ m $ and $ r_i < l_{i + 1} $ holds for each $ i $ from $ 1 $ to $ m - 1 $ in the easy version. You can make hacks only if both versions of the problem are solved.

Turtle gives you $ m $ intervals $ [l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m] $ . He thinks that a permutation $ p $ is interesting if there exists an integer $ k_i $ for every interval ( $ l_i \le k_i < r_i $ ), and if he lets $ a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i} p_j $ for every integer $ i $ from $ 1 $ to $ m $ , the following condition holds:

 $ $$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i $ $ </p><p>Turtle wants you to calculate the maximum number of inversions of all interesting permutations of length  $ n $ , or tell him if there is no interesting permutation.</p><p>An inversion of a permutation  $ p $  is a pair of integers  $ (i, j) $  ( $ 1 \\le i &lt; j \\le n $ ) such that  $ p\_i &gt; p\_j$$$.

## Input Format

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

The first line of each test case contains two integers $ n, m $ ( $ 2 \le n \le 5 \cdot 10^3, 0 \le m \le \frac{n}{2} $ ) — the length of the permutation and the number of intervals.

The $ i $ -th of the following $ m $ lines contains two integers $ l_i, r_i $ ( $ 1 \le l_i < r_i \le n $ ) — the $ i $ -th interval.

Additional constraint on the input in this version: $ r_i < l_{i + 1} $ holds for each $ i $ from $ 1 $ to $ m - 1 $ .

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

## Output Format

For each test case, if there is no interesting permutation, output a single integer $ -1 $ .

Otherwise, output a single integer — the maximum number of inversions.

## Sample #1

### Sample Input #1

```
6
2 0
2 1
1 2
5 1
2 4
8 2
1 4
6 8
7 2
1 3
4 7
7 3
1 2
3 4
5 6
```

### Sample Output #1

```
1
0
8
21
15
15
```

## Hint

In the third test case, the interesting permutation with the maximum number of inversions is $ [5, 2, 4, 3, 1] $ .

In the fourth test case, the interesting permutation with the maximum number of inversions is $ [4, 8, 7, 6, 3, 2, 1, 5] $ . In this case, we can let $ [k_1, k_2] = [1, 7] $ .

In the fifth test case, the interesting permutation with the maximum number of inversions is $ [4, 7, 6, 3, 2, 1, 5] $ .

In the sixth test case, the interesting permutation with the maximum number of inversions is $ [4, 7, 3, 6, 2, 5, 1] $ .

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, divide and conquer, dp, greedy, math
Difficulty: 2600
# Turtle and Good Pairs

## Problem Description

Turtle gives you a string $ s $ , consisting of lowercase Latin letters.

Turtle considers a pair of integers $ (i, j) $ ( $ 1 \le i < j \le n $ ) to be a pleasant pair if and only if there exists an integer $ k $ such that $ i \le k < j $ and both of the following two conditions hold:

- $ s_k \ne s_{k + 1} $ ;
- $ s_k \ne s_i $ or $ s_{k + 1} \ne s_j $ .

Besides, Turtle considers a pair of integers $ (i, j) $ ( $ 1 \le i < j \le n $ ) to be a good pair if and only if $ s_i = s_j $ or $ (i, j) $ is a pleasant pair.

Turtle wants to reorder the string $ s $ so that the number of good pairs is maximized. Please help him!

## Input Format

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

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

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

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 the string $ s $ after reordering so that the number of good pairs is maximized. If there are multiple answers, print any of them.

## Sample #1

### Sample Input #1

```
5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces
```

### Sample Output #1

```
acb
ddedf
urtlet
pppppppp
codeforces
```

## Hint

In the first test case, $ (1, 3) $ is a good pair in the reordered string. It can be seen that we can't reorder the string so that the number of good pairs is greater than $ 1 $ . bac and cab can also be the answer.

In the second test case, $ (1, 2) $ , $ (1, 4) $ , $ (1, 5) $ , $ (2, 4) $ , $ (2, 5) $ , $ (3, 5) $ are good pairs in the reordered string. efddd can also be the answer.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, sortings, strings
Difficulty: 1200
# Turtle and Good Strings

## Problem Description

Turtle thinks a string $ s $ is a good string if there exists a sequence of strings $ t_1, t_2, \ldots, t_k $ ( $ k $ is an arbitrary integer) such that:

- $ k \ge 2 $ .
- $ s = t_1 + t_2 + \ldots + t_k $ , where $ + $ represents the concatenation operation. For example, $ \texttt{abc} = \texttt{a} + \texttt{bc} $ .
- For all $ 1 \le i < j \le k $ , the first character of $ t_i $ isn't equal to the last character of $ t_j $ .

Turtle is given a string $ s $ consisting of lowercase Latin letters. Please tell him whether the string $ s $ is a good string!

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.

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

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

## Output Format

For each test case, output "YES" if the string $ s $ is a good string, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

```
4
2
aa
3
aba
4
abcb
12
abcabcabcabc
```

### Sample Output #1

```
No
nO
Yes
YES
```

## Hint

In the first test case, the sequence of strings $ \texttt{a}, \texttt{a} $ satisfies the condition $ s = t_1 + t_2 + \ldots + t_k $ , but the first character of $ t_1 $ is equal to the last character of $ t_2 $ . It can be seen that there doesn't exist any sequence of strings which satisfies all of the conditions, so the answer is "NO".

In the third test case, the sequence of strings $ \texttt{ab}, \texttt{cb} $ satisfies all of the conditions.

In the fourth test case, the sequence of strings $ \texttt{abca}, \texttt{bcab}, \texttt{cabc} $ satisfies all of the conditions.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, strings
Difficulty: 800
# Counting 101

## Problem Description

It's been a long summer's day, with the constant chirping of cicadas and the heat which never seemed to end. Finally, it has drawn to a close. The showdown has passed, the gates are open, and only a gentle breeze is left behind.

Your predecessors had taken their final bow; it's your turn to take the stage.

Sorting through some notes that were left behind, you found a curious statement named Problem 101:

- Given a positive integer sequence $ a_1,a_2,\ldots,a_n $ , you can operate on it any number of times. In an operation, you choose three consecutive elements $ a_i,a_{i+1},a_{i+2} $ , and merge them into one element $ \max(a_i+1,a_{i+1},a_{i+2}+1) $ . Please calculate the maximum number of operations you can do without creating an element greater than $ m $ .

After some thought, you decided to propose the following problem, named Counting 101:

- Given $ n $ and $ m $ . For each $ k=0,1,\ldots,\left\lfloor\frac{n-1}{2}\right\rfloor $ , please find the number of integer sequences $ a_1,a_2,\ldots,a_n $ with elements in $ [1, m] $ , such that when used as input for Problem 101, the answer is $ k $ . As the answer can be very large, please print it modulo $ 10^9+7 $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le10^3 $ ). The description of the test cases follows.

The only line of each test case contains two integers $ n $ , $ m $ ( $ 1\le n\le 130 $ , $ 1\le m\le 30 $ ).

## Output Format

For each test case, output $ \left\lfloor\frac{n+1}{2}\right\rfloor $ numbers. The $ i $ -th number is the number of valid sequences such that when used as input for Problem 101, the answer is $ i-1 $ , modulo $ 10^9+7 $ .

## Sample #1

### Sample Input #1

```
2
3 2
10 10
```

### Sample Output #1

```
6 2 
1590121 23399118 382293180 213020758 379696760
```

## Hint

In the first test case, there are $ 2^3=8 $ candidate sequences. Among them, you can operate on $ [1,2,1] $ and $ [1,1,1] $ once; you cannot operate on the other $ 6 $ sequences.

## Limit



Time Limit
10.10s

Memory Limit
986.33MB

Tags: greedy
Difficulty: 3500
# Lattice Optimizing

## Problem Description

Consider a grid graph with $ n $ rows and $ n $ columns. Let the cell in row $ x $ and column $ y $ be $ (x,y) $ . There exists a directed edge from $ (x,y) $ to $ (x+1,y) $ , with non-negative integer value $ d_{x,y} $ , for all $ 1\le x < n, 1\le y \le n $ , and there also exists a directed edge from $ (x,y) $ to $ (x,y+1) $ , with non-negative integer value $ r_{x,y} $ , for all $ 1\le x \le n, 1\le y < n $ .

Initially, you are at $ (1,1) $ , with an empty set $ S $ . You need to walk along the edges and eventually reach $ (n,n) $ . Whenever you pass an edge, its value will be inserted into $ S $ . Please maximize the MEX $ ^{\text{∗}} $ of $ S $ when you reach $ (n,n) $ .

 $ ^{\text{∗}} $ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

- The MEX of $ [2,2,1] $ is $ 0 $ , because $ 0 $ does not belong to the array.
- The MEX of $ [3,1,0,1] $ is $ 2 $ , because $ 0 $ and $ 1 $ belong to the array, but $ 2 $ does not.
- The MEX of $ [0,3,1,2] $ is $ 4 $ , because $ 0, 1, 2 $ , and $ 3 $ belong to the array, but $ 4 $ does not.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le100 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2\le n\le20 $ ) — the number of rows and columns.

Each of the next $ n-1 $ lines contains $ n $ integers separated by single spaces — the matrix $ d $ ( $ 0\le d_{x,y}\le 2n-2 $ ).

Each of the next $ n $ lines contains $ n-1 $ integers separated by single spaces — the matrix $ r $ ( $ 0\le r_{x,y}\le 2n-2 $ ).

It is guaranteed that the sum of all $ n^3 $ does not exceed $ 8000 $ .

## Output Format

For each test case, print a single integer — the maximum MEX of $ S $ when you reach $ (n,n) $ .

## Sample #1

### Sample Input #1

```
2
3
1 0 2
0 1 3
2 1
0 3
3 0
3
1 2 0
0 1 2
2 0
1 2
0 1
```

### Sample Output #1

```
3
2
```

## Sample #2

### Sample Input #2

```
1
10
16 7 3 15 9 17 1 15 9 0
4 3 1 12 13 10 10 14 6 12
3 1 3 9 5 16 0 12 7 12
11 4 8 7 13 7 15 13 9 2
2 3 9 9 4 12 17 7 10 15
10 6 15 17 13 6 15 9 4 9
13 3 3 14 1 2 10 10 12 16
8 2 9 13 18 7 1 6 2 6
15 12 2 6 0 0 13 3 7 17
7 3 17 17 10 15 12 14 15
4 3 3 17 3 13 11 16 6
16 17 7 7 12 5 2 4 10
18 9 9 3 5 9 1 16 7
1 0 4 2 10 10 12 2 1
4 14 15 16 15 5 8 4 18
7 18 10 11 2 0 14 8 18
2 17 6 0 9 6 13 5 11
5 15 7 11 6 3 17 14 5
1 3 16 16 13 1 0 13 11
```

### Sample Output #2

```
14
```

## Hint

In the first test case, the grid graph and one of the optimal paths are as follows:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2002G/39bbb57cab4add33784d285946add739d65301a5.png)In the second test case, the grid graph and one of the optimal paths are as follows:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2002G/58ad0efca54b4bc955c226e6f4d3531e48728c01.png)

## Limit



Time Limit
7.00s

Memory Limit
1000.00MB

Tags: bitmasks, brute force, hashing, meet-in-the-middle
Difficulty: 3400