yl-9/probench huggingface dataset:
# Penchick and Satay Sticks

## Problem Description

Penchick and his friend Kohane are touring Indonesia, and their next stop is in Surabaya!

In the bustling food stalls of Surabaya, Kohane bought $ n $ satay sticks and arranged them in a line, with the $ i $ -th satay stick having length $ p_i $ . It is given that $ p $ is a permutation $ ^{\text{∗}} $ of length $ n $ .

Penchick wants to sort the satay sticks in increasing order of length, so that $ p_i=i $ for each $ 1\le i\le n $ . For fun, they created a rule: they can only swap neighboring satay sticks whose lengths differ by exactly $ 1 $ . Formally, they can perform the following operation any number of times (including zero):

- Select an index $ i $ ( $ 1\le i\le n-1 $ ) such that $ |p_{i+1}-p_i|=1 $ ;
- Swap $ p_i $ and $ p_{i+1} $ .

Determine whether it is possible to sort the permutation $ p $ , thus the satay sticks, by performing the above operation.

 $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

## 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^5 $ ). The description of the test cases follows.

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

The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ) — the permutation $ p $ representing the length of the satay sticks.

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 "YES" if it is possible to sort permutation $ p $ by performing the operation. Otherwise, output "NO".

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

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

### Sample Output #1

```
YES
NO
```

## Hint

In the first test case, we can sort permutation $ p = [2, 1, 3, 4] $ by performing an operation on index $ 1 $ ( $ |p_2 - p_1| = |1 - 2| = 1 $ ), resulting in $ p = [1, 2, 3, 4] $ .

In the second test case, it can be proven that it is impossible to sort permutation $ p = [4, 2, 3, 1] $ by performing the operation. Here is an example of a sequence of operations that can be performed on the permutation:

- Select $ i = 2 $ ( $ |p_3 - p_2| = |3 - 2| = 1 $ ). This results in $ p = [4, 3, 2, 1] $ .
- Select $ i = 1 $ ( $ |p_2 - p_1| = |3 - 4| = 1 $ ). This results in $ p = [3, 4, 2, 1] $ .
- Select $ i = 3 $ ( $ |p_4 - p_3| = |1 - 2| = 1 $ ). This results in $ p = [3, 4, 1, 2] $ .

Unfortunately, permutation $ p $ remains unsorted after performing the operations.

## Limit



Time Limit
1.50s

Memory Limit
250.00MB

Tags: brute force, greedy, sortings
Difficulty: 900
# Penchick and Modern Monument

## Problem Description

Amidst skyscrapers in the bustling metropolis of Metro Manila, the newest Noiph mall in the Philippines has just been completed! The construction manager, Penchick, ordered a state-of-the-art monument to be built with $ n $ pillars.

The heights of the monument's pillars can be represented as an array $ h $ of $ n $ positive integers, where $ h_i $ represents the height of the $ i $ -th pillar for all $ i $ between $ 1 $ and $ n $ .

Penchick wants the heights of the pillars to be in non-decreasing order, i.e. $ h_i \le h_{i + 1} $ for all $ i $ between $ 1 $ and $ n - 1 $ . However, due to confusion, the monument was built such that the heights of the pillars are in non-increasing order instead, i.e. $ h_i \ge h_{i + 1} $ for all $ i $ between $ 1 $ and $ n - 1 $ .

Luckily, Penchick can modify the monument and do the following operation on the pillars as many times as necessary:

- Modify the height of a pillar to any positive integer. Formally, choose an index $ 1\le i\le n $ and a positive integer $ x $ . Then, assign $ h_i := x $ .

Help Penchick determine the minimum number of operations needed to make the heights of the monument's pillars non-decreasing.

## Input Format

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

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

The second line of each test case contains $ n $ integers $ h_1, h_2, \ldots, h_n $ ( $ 1 \le h_i \le n $ and $ h_i\ge h_{i+1} $ ) — the height of the pillars.

Please take note that the given array $ h $ is non-increasing.

Note that there are no constraints on the sum of $ n $ over all test cases.

## Output Format

For each test case, output a single integer representing the minimum number of operations needed to make the heights of the pillars non-decreasing.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
4
1
0
```

## Hint

In the first test case, the initial heights of pillars are $ h = [5, 4, 3, 2, 1] $ .

- In the first operation, Penchick changes the height of pillar $ 1 $ to $ h_1 := 2 $ .
- In the second operation, he changes the height of pillar $ 2 $ to $ h_2 := 2 $ .
- In the third operation, he changes the height of pillar $ 4 $ to $ h_4 := 4 $ .
- In the fourth operation, he changes the height of pillar $ 5 $ to $ h_5 := 4 $ .

After the operation, the heights of the pillars are $ h = [2, 2, 3, 4, 4] $ , which is non-decreasing. It can be proven that it is not possible for Penchick to make the heights of the pillars non-decreasing in fewer than $ 4 $ operations.

In the second test case, Penchick can make the heights of the pillars non-decreasing by modifying the height of pillar $ 3 $ to $ h_3 := 2 $ .

In the third test case, the heights of pillars are already non-decreasing, so no operations are required.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, dp, greedy, math
Difficulty: 800
# Orangutan Approved Subarrays

## Problem Description

Suppose you have an array $ b $ . Initially, you also have a set $ S $ that contains all distinct elements of $ b $ . The array $ b $ is called orangutan-approved if it can be emptied by repeatedly performing the following operation:

- In one operation, select indices $ l $ and $ r $ ( $ 1 \leq l \leq r \leq |b| $ ) such that $ v = b_l = b_{l+1} = \ldots = b_r $ and $ v $ is present in $ S $ . Remove $ v $ from $ S $ , and simultaneously remove all $ b_i $ such that $ l \leq i \leq r $ . Then, reindex the elements $ b_{r+1}, b_{r+2}, \ldots $ as $ b_l, b_{l+1}, \ldots $ accordingly.

You are given an array $ a $ of length $ n $ and $ q $ queries.

Each query consists of two indices $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ), and you need to determine whether or not the subarray $ a_{l}, a_{l+1}, \ldots, a_r $ is orangutan-approved.

## Input Format

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

The first line of each test case contains integers $ n $ and $ q $ ( $ 1 \leq n,q \leq 2 \cdot 10^5 $ ) — the size of $ a $ and the number of queries, respectively.

The following line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array $ a $ .

The following $ q $ lines contain two integers $ l $ and $ r $ — the endpoints of the subarray for each query ( $ 1 \leq l \leq r \leq n $ ).

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

## Output Format

For each query, output "YES" (without quotes) if the subarray from $ l $ to $ r $ is orangutan-approved, and "NO" (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

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

### Sample Output #1

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

## Hint

In the first query of the first testcase, the answer is YES.

- Initially, $ S=\{1,2\} $ and $ b=[1,2,2,1] $
- Select $ l=2 $ and $ r=3 $ . Since $ b_2=b_3=2 $ is in $ S $ , we may erase $ b_2 $ and $ b_3 $ from the array, as well as erasing $ 2 $ from $ S $ . The set $ S $ becomes $ \{1\} $ and the array becomes $ [1,1] $ .
- Select $ l=1 $ and $ r=2 $ . Since $ b_1=b_2=1 $ is in $ S $ , we may erase $ b_1 $ and $ b_2 $ from the array, as well as erasing $ 1 $ from $ S $ . The set $ S $ becomes $ \{\} $ and the array becomes $ [] $ .
- Since the array is now empty, we can say the original array is orangutan-approved.

In the first query of the second testcase, the answer is NO, because it can be shown that the subarray $ [2,1,2,1] $ cannot become empty through any sequence of valid operations.

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: binary search, data structures, dp, greedy, implementation, two pointers
Difficulty: 2400
# MEXimize the Score

## Problem Description

Suppose we partition the elements of an array $ b $ into any number $ k $ of non-empty multisets $ S_1, S_2, \ldots, S_k $ , where $ k $ is an arbitrary positive integer. Define the score of $ b $ as the maximum value of $ \operatorname{MEX}(S_1) $ $ ^{\text{∗}} $ $  + \operatorname{MEX}(S_2) + \ldots + \operatorname{MEX}(S_k) $ over all possible partitions of $ b $ for any integer $ k $ .

Envy is given an array $ a $ of size $ n $ . Since he knows that calculating the score of $ a $ is too easy for you, he instead asks you to calculate the sum of scores of all $ 2^n - 1 $ non-empty subsequences of $ a $ . $ ^{\text{†}} $ Since this answer may be large, please output it modulo $ 998\,244\,353 $ .

 $ ^{\text{∗}} $ $ \operatorname{MEX} $ of a collection of integers $ c_1, c_2, \ldots, c_k $ is defined as the smallest non-negative integer $ x $ that does not occur in the collection $ c $ . For example, $ \operatorname{MEX}([0,1,2,2]) = 3 $ and $ \operatorname{MEX}([1,2,2]) = 0 $

 $ ^{\text{†}} $ A sequence $ x $ is a subsequence of a sequence $ y $ if $ x $ can be obtained from $ y $ by deleting several (possibly, zero or all) elements.

## Input Format

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

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

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i < n $ ) — the elements of the array $ a $ .

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 answer, modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
11
26
53
0
```

## Hint

In the first testcase, we must consider seven subsequences:

- $ [0] $ : The score is $ 1 $ .
- $ [0] $ : The score is $ 1 $ .
- $ [1] $ : The score is $ 0 $ .
- $ [0,0] $ : The score is $ 2 $ .
- $ [0,1] $ : The score is $ 2 $ .
- $ [0,1] $ : The score is $ 2 $ .
- $ [0,0,1] $ : The score is $ 3 $ .

 The answer for the first testcase is $ 1+1+2+2+2+3=11 $ .In the last testcase, all subsequences have a score of $ 0 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: combinatorics, data structures, dp, greedy, implementation, math
Difficulty: 2200
# A TRUE Battle

## Problem Description

Alice and Bob are playing a game. There is a list of $ n $ booleans, each of which is either true or false, given as a binary string $ ^{\text{∗}} $ of length $ n $ (where $ \texttt{1} $ represents true, and $ \texttt{0} $ represents false). Initially, there are no operators between the booleans.

Alice and Bob will take alternate turns placing and or or between the booleans, with Alice going first. Thus, the game will consist of $ n-1 $ turns since there are $ n $ booleans. Alice aims for the final statement to evaluate to true, while Bob aims for it to evaluate to false. Given the list of boolean values, determine whether Alice will win if both players play optimally.

To evaluate the final expression, repeatedly perform the following steps until the statement consists of a single true or false:

- If the statement contains an and operator, choose any one and replace the subexpression surrounding it with its evaluation.
- Otherwise, the statement contains an or operator. Choose any one and replace the subexpression surrounding the or with its evaluation.

 For example, the expression true or false and false is evaluated as true or (false and false) $ = $ true or false $ = $ true. It can be shown that the result of any compound statement is unique. $ ^{\text{∗}} $ A binary string is a string that only consists of characters $ \texttt{0} $ and $ \texttt{1} $

## Input Format

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

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

The second line contains a binary string of length $ n $ , consisting of characters $ \texttt{0} $ and $ \texttt{1} $ — the list of boolean values.

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

## Output Format

For each testcase, output "YES" (without quotes) if Alice wins, and "NO" (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

```
5
2
11
3
010
12
101111111100
10
0111111011
8
01000010
```

### Sample Output #1

```
YES
NO
YES
YES
NO
```

## Hint

In the first testcase, Alice can place and between the two booleans. The game ends as there are no other places to place operators, and Alice wins because true and true is true.

In the second testcase, Alice can place or between the middle true and the left false. Bob can place and between the middle true and the right false. The statement false or true and false is false.

Note that these examples may not be the best strategies for either Alice or Bob.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, games, greedy
Difficulty: 1100
# Minimise Oneness

## Problem Description

For an arbitrary binary string $ t $ $ ^{\text{∗}} $ , let $ f(t) $ be the number of non-empty subsequences $ ^{\text{†}} $ of $ t $ that contain only $ \mathtt{0} $ , and let $ g(t) $ be the number of non-empty subsequences of $ t $ that contain at least one $ \mathtt{1} $ .

Note that for $ f(t) $ and for $ g(t) $ , each subsequence is counted as many times as it appears in $ t $ . E.g., $ f(\mathtt{000}) = 7, g(\mathtt{100}) = 4 $ .

We define the oneness of the binary string $ t $ to be $ |f(t)-g(t)| $ , where for an arbitrary integer $ z $ , $ |z| $ represents the absolute value of $ z $ .

You are given a positive integer $ n $ . Find a binary string $ s $ of length $ n $ such that its oneness is as small as possible. If there are multiple strings, you can print any of them.

 $ ^{\text{∗}} $ A binary string is a string that only consists of characters $ \texttt{0} $ and $ \texttt{1} $ .

 $ ^{\text{†}} $ 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. For example, subsequences of $ \mathtt{1011101} $ are $ \mathtt{0} $ , $ \mathtt{1} $ , $ \mathtt{11111} $ , $ \mathtt{0111} $ , but not $ \mathtt{000} $ nor $ \mathtt{11100} $ .

## 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 an integer $ n $ ( $ 1 \leq n \leq 2\cdot10^5 $ ) — the length of $ s $ .

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

## Output Format

For each test case, output $ s $ on a new line. If multiple answers exist, output any.

## Sample #1

### Sample Input #1

```
3
1
2
3
```

### Sample Output #1

```
0
01
010
```

## Hint

In the first test case, for the example output, $ f(t)=1 $ because there is one subsequence that contains only $ \mathtt{0} $ ( $ \mathtt{0} $ ), and $ g(t)=0 $ because there are no subsequences that contain at least one $ 1 $ . The oneness is $ |1-0|=1 $ . The output $ \mathtt{1} $ is correct as well because its oneness is $ |0-1|=1 $ .

For the example output of the second test case, $ f(t)=1 $ because there is one non-empty subsequence that contains only $ \mathtt{0} $ , and $ g(t)=2 $ because there are two non-empty subsequences that contain at least one $ \mathtt{1} $ ( $ \mathtt{01} $ and $ \mathtt{1} $ ). The oneness is thus $ |1-2|=1 $ . It can be shown that $ 1 $ is the minimum possible value of its oneness over all possible binary strings of size $ 2 $ .

## Limit



Time Limit
1.50s

Memory Limit
250.00MB

Tags: combinatorics, constructive algorithms, games, math
Difficulty: 800
# A Gift From Orangutan

## Problem Description

While exploring the jungle, you have bumped into a rare orangutan with a bow tie! You shake hands with the orangutan and offer him some food and water. In return...

The orangutan has gifted you an array $ a $ of length $ n $ . Using $ a $ , you will construct two arrays $ b $ and $ c $ , both containing $ n $ elements, in the following manner:

- $ b_i = \min(a_1, a_2, \ldots, a_i) $ for each $ 1 \leq i \leq n $ .
- $ c_i = \max(a_1, a_2, \ldots, a_i) $ for each $ 1 \leq i \leq n $ .

Define the score of $ a $ as $ \sum_{i=1}^n c_i - b_i $ (i.e. the sum of $ c_i - b_i $ over all $ 1 \leq i \leq n $ ). Before you calculate the score, you can shuffle the elements of $ a $ however you want.

Find the maximum score that you can get if you shuffle the elements of $ a $ optimally.

## Input Format

The first line contains $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 1000 $ ) — the number of elements in $ a $ .

The following line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 1000 $ ) — the elements of the array $ a $ .

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

## Output Format

For each test case, output the maximum score that you can get.

## Sample #1

### Sample Input #1

```
3
1
69
3
7 6 5
5
1 1 1 2 2
```

### Sample Output #1

```
0
4
4
```

## Hint

In the first test case, there is no other way to rearrange $ a $ . So, $ b = [69] $ and $ c = [69] $ . The only possible score is $ 69 - 69 = 0 $ .

In the second test case, you can rearrange $ a $ as $ [7, 5, 6] $ . Here, $ b = [7, 5, 5] $ and $ c = [7, 7, 7] $ . The score in this case is $ (7 - 7) + (7 - 5) + (7 - 5) = 4 $ . It can be shown this is the maximum possible score.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math, sortings
Difficulty: 800
# Palindrome Everywhere

## Problem Description

You are given a cycle with $ n $ vertices numbered from $ 0 $ to $ n-1 $ . For each $ 0\le i\le n-1 $ , there is an undirected edge between vertex $ i $ and vertex $ ((i+1)\bmod n) $ with the color $ c_i $ ( $ c_i=\texttt{R} $ or $ \texttt{B} $ ).

Determine whether the following condition holds for every pair of vertices $ (i,j) $ ( $ 0\le i<j\le n-1 $ ):

- There exists a palindrome route between vertex $ i $ and vertex $ j $ . Note that the route may not be simple. Formally, there must exist a sequence $ p=[p_0,p_1,p_2,\ldots,p_m] $ such that:
  - $ p_0=i $ , $ p_m=j $ ;
  - For each $ 0\leq x\le m-1 $ , either $ p_{x+1}=(p_x+1)\bmod n $ or $ p_{x+1}=(p_{x}-1)\bmod n $ ;
  - For each $ 0\le x\le y\le m-1 $ satisfying $ x+y=m-1 $ , the edge between $ p_x $ and $ p_{x+1} $ has the same color as the edge between $ p_y $ and $ p_{y+1} $ .

## 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 number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $ n $ ( $ 3\leq n\leq10^6 $ ) — the number of vertices in the cycle.

The second line contains a string $ c $ of length $ n $ ( $ c_i=\texttt{R} $ or $ \texttt{B} $ ) — the color of each edge.

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

## Output Format

For each test case, print "YES" (without quotes) if there is a palindrome route between any pair of nodes, and "NO" (without quotes) 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

```
7
5
RRRRR
5
RRRRB
5
RBBRB
6
RBRBRB
6
RRBBRB
5
RBRBR
12
RRBRRBRRBRRB
```

### Sample Output #1

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

## Hint

In the first test case, it is easy to show that there is a palindrome route between any two vertices.

In the second test case, for any two vertices, there exists a palindrome route with only red edges.

In the third test case, the cycle is as follows: $ 0\color{red}{\overset{\texttt{R}}{\longleftrightarrow}}1\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}2\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}3\color{red}{\overset{\texttt{R}}{\longleftrightarrow}}4\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}0 $ . Take $ (i,j)=(0,3) $ as an example, then $ 0\color{red}{\overset{\texttt{R}}{\longrightarrow}}1\color{blue}{\overset{\texttt{B}}{\longrightarrow}}2\color{blue}{\overset{\texttt{B}}{\longrightarrow}}3\color{red}{\overset{\texttt{R}}{\longrightarrow}}4\color{blue}{\overset{\texttt{B}}{\longrightarrow}}0\color{blue}{\overset{\texttt{B}}{\longrightarrow}}4\color{red}{\overset{\texttt{R}}{\longrightarrow}}3 $ is a palindrome route. Thus, the condition holds for $ (i,j)=(0,3) $ .

In the fourth test case, when $ (i,j)=(0,2) $ , there does not exist a palindrome route.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: constructive algorithms, graphs, greedy
Difficulty: 2500