yl-9/probench huggingface dataset:
# Kevin and Matrices

## Problem Description

Kevin has been transported to Sacred Heart Hospital, which contains all the $  n \times m  $ matrices with integer values in the range $  [1,v]  $ .

Now, Kevin wants to befriend some matrices, but he is willing to befriend a matrix $  a  $ if and only if the following condition is satisfied:

 $ $$$ \min_{1\le i\le n}\left(\max_{1\le j\le m}a_{i,j}\right)\le\max_{1\le j\le m}\left(\min_{1\le i\le n}a_{i,j}\right).  $ $ </p><p>Please count how many matrices in Sacred Heart Hospital can be friends with Kevin.</p><p>Since Kevin is very friendly, there could be many matrices that meet this condition. Therefore, you only need to output the result modulo  $ 998\\,244\\,353$$$.

## Input Format

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

The only line of each test case contains three integers $ n $ , $ m $ , $ v $ ( $  1 \le n, v, n \cdot v \leq 10^6 $ , $ 1 \le m \le 10^9  $ ).

It is guaranteed that the sum of $  n \cdot v  $ over all test cases doesn't exceed $  10^6  $ .

## Output Format

For each test case, output one integer — the number of matrices that can be friends with Kevin modulo $ 998\,244\,353 $ .

## Sample #1

### Sample Input #1

```
3
2 2 2
2 3 4
11 45 14
```

### Sample Output #1

```
14
2824
883799966
```

## Hint

In the first test case, besides the matrices $  a=\begin{bmatrix}1&2\\2&1\end{bmatrix}  $ and $  a=\begin{bmatrix}2&1\\1&2\end{bmatrix}  $ , which do not satisfy the condition, the remaining $  2^{2 \cdot 2} - 2 = 14  $ matrices can all be friends with Kevin.

## Limit



Time Limit
6.00s

Memory Limit
250.00MB

Tags: brute force, combinatorics, dp, math
Difficulty: 2800
# Kevin and Math Class

## Problem Description

Kevin is a student from Eversleeping Town, currently attending a math class where the teacher is giving him division exercises.

On the board, there are two rows of positive integers written, each containing $  n  $ numbers. The first row is $  a_1, a_2, \ldots, a_n  $ , and the second row is $  b_1, b_2, \ldots, b_n  $ .

For each division exercise, Kevin can choose any segment $  [l, r]  $ and find the smallest value $  x  $ among $  b_l, b_{l+1}, \ldots, b_r  $ . He will then modify each $  a_i  $ for $  l \leq i \leq r  $ to be the ceiling of $  a_i  $ divided by $  x  $ .

Formally, he selects two integers $  1 \leq l \leq r \leq n  $ , sets $  x = \min_{l \leq i \leq r} b_i  $ , and changes all $  a_i  $ for $  l \leq i \leq r  $ to $  \lceil \frac{a_i}{x} \rceil  $ .

Kevin can leave class and go home when all $  a_i  $ become $  1  $ . He is eager to leave and wants to know the minimum number of division exercises required to achieve this.

## 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 first line of each test case contains an integer $  n  $ ( $  1 \le n \leq 2 \cdot 10^5  $ ) — the length of the sequence $  a  $ and $  b  $ .

The second line of each test case contains $  n  $ integers $  a_1, a_2, \ldots, a_n  $ ( $  1 \le a_i \le 10^{18}  $ ) — the first row of integers on the board.

The third line of each test case contains $  n  $ integers $  b_1, b_2, \ldots, b_n  $ ( $  2 \le b_i \le 10^{18}  $ ) — the second row of integers on the board.

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

## Output Format

For each test case, output one integer — the minimum number of division exercises required to leave class.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
2
3
3
```

## Hint

For the first test case: $  [{\color{red}{5,4}},2]\xrightarrow[\min(b_1,b_2)=3]{\text{operate segment }[1,2]}[{\color{red}{2,2,2}}]\xrightarrow[\min(b_1,b_2,b_3)=2]{\text{operate segment }[1,3]}[1,1,1]  $ .

For the second test case: $  [{\color{red}{3,6,1}},3,2]\xrightarrow[\min(b_1,b_2,b_3)=3]{\text{operate segment }[1,3]}[1,{\color{red}{2,1,3}},2]\xrightarrow[\min(b_2,b_3,b_4)=2]{\text{operate segment }[2,4]}[1,1,1,{\color{red}{2,2}}]\xrightarrow[\min(b_4,b_5)=2]{\text{operate segment }[4,5]}[1,1,1,1,1]  $ .

## Limit



Time Limit
2.00s

Memory Limit
1000.00MB

Tags: brute force, data structures, divide and conquer, dp, implementation, math, trees
Difficulty: 2500
# Kevin and Bipartite Graph

## Problem Description

The Arms Factory needs a poster design pattern and finds Kevin for help.

A poster design pattern is a bipartite graph with $  2n  $ vertices in the left part and $  m  $ vertices in the right part, where there is an edge between each vertex in the left part and each vertex in the right part, resulting in a total of $  2nm  $ edges.

Kevin must color each edge with a positive integer in the range $  [1, n]  $ . A poster design pattern is good if there are no monochromatic cycles $ ^{\text{∗}} $ in the bipartite graph.

Kevin needs your assistance in constructing a good bipartite graph or informing him if it is impossible.

 $ ^{\text{∗}} $ A monochromatic cycle refers to a simple cycle in which all the edges are colored with the same color.

## Input Format

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

The only line of each test case contains two integers $  n  $ and $  m  $ ( $  1 \le n, m \leq 10^3  $ ) — the bipartite graph has $  2n  $ vertices in the left part and $  m  $ vertices in the right part.

It is guaranteed that both the sum of $  n  $ and the sum of $  m  $ over all test cases do not exceed $  10^3  $ .

## Output Format

For each test case, if there is no solution, then output No.

Otherwise, output Yes, and then output $  2n  $ lines, with each line containing $  m  $ positive integers. The $  i  $ -th line's $  j  $ -th integer represents the color of the edge between the $  i  $ -th vertex in the left part and the $  j  $ -th vertex in the right part.

If there are multiple answers, you can print any of them.

You can output each letter 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
2 2
3 7
5 4
```

### Sample Output #1

```
YES
1 2
2 1
2 2
2 1
NO
YES
1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
```

## Hint

For the first test case, the graph is shown as follows:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2048E/e4da0903a1b5d9ddcce4814e073d00bff46bc1e3.png)For the second test case, it can be proven that there is no valid solution.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, graphs, greedy
Difficulty: 2000
# Kevin and Binary Strings

## Problem Description

Kevin discovered a binary string $ s $ that starts with 1 in the river at Moonlit River Park and handed it over to you. Your task is to select two non-empty substrings $ ^{\text{∗}} $ of $ s $ (which can be overlapped) to maximize the XOR value of these two substrings.

The XOR of two binary strings $ a $ and $ b $ is defined as the result of the $ \oplus $ operation applied to the two numbers obtained by interpreting $ a $ and $ b $ as binary numbers, with the leftmost bit representing the highest value. Here, $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

The strings you choose may have leading zeros.

 $ ^{\text{∗}} $ A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

## 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 only line of each test case contains a binary string $ s $ that starts with 1 ( $ 1\le\lvert s\rvert\le 5000 $ ).

It is guaranteed that the sum of $ \lvert s\rvert $ over all test cases doesn't exceed $ 5000 $ .

## Output Format

For each test case, output four integers $ l_1, r_1, l_2, r_2 $ ( $ 1 \le l_1 \le r_1 \le |s| $ , $ 1 \le l_2 \le r_2 \le |s| $ ) — in the case the two substrings you selected are $ s_{l_1} s_{l_1 + 1} \ldots s_{r_1} $ and $ s_{l_2} s_{l_2 + 1} \ldots s_{r_2} $ .

If there are multiple solutions, print any of them.

## Sample #1

### Sample Input #1

```
5
111
1000
10111
11101
1100010001101
```

### Sample Output #1

```
2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11
```

## Hint

In the first test case, we can choose $  s_2=\texttt{1}  $ and $  s_1 s_2 s_3=\texttt{111}  $ , and $  \texttt{1}\oplus\texttt{111}=\texttt{110}  $ . It can be proven that it is impossible to obtain a larger result. Additionally, $  l_1=3 $ , $ r_1=3 $ , $ l_2=1 $ , $ r_2=3  $ is also a valid solution.

In the second test case, $  s_1 s_2 s_3=\texttt{100}  $ , $  s_1 s_2 s_3 s_4=\texttt{1000}  $ , the result is $  \texttt{100}\oplus\texttt{1000}=\texttt{1100}  $ , which is the maximum.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, brute force, greedy, implementation, strings
Difficulty: 1200
# Kevin and Permutation

## Problem Description

Kevin is a master of permutation-related problems. You are taking a walk with Kevin in Darkwoods, and during your leisure time, he wants to ask you the following question.

Given two positive integers $  n  $ and $  k  $ , construct a permutation $ ^{\text{∗}} $ $  p  $ of length $  n  $ to minimize the sum of the minimum values of all subarrays $ ^{\text{†}} $ of length $  k  $ . Formally, you need to minimize

 $ $$$ \sum_{i=1}^{n-k+1}\left( \min_{j=i}^{i+k-1} p_j\right).  $ $ </p><div class="statement-footnote"><p> $ ^{\\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). </p><p> $ ^{\\text{†}} $ An array  $ a $  is a subarray of an array  $ b $  if  $ a $  can be obtained from  $ b$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Two subarrays are considered different if the sets of positions of the deleted elements are different.

## Input Format

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

The only line of each test case contains two integers $  n  $ and $  k  $ ( $  1\le k\le n\le 10^5  $ ).

It is guaranteed that the sum of $  n  $ over all test cases doesn't exceed $  10^5  $ .

## Output Format

For each test case, output $  n  $ integers on a single line — the permutation $  p  $ you constructed.

If there are multiple answers, you can print any of them.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Hint

In the first test case, with $  k=2  $ , consider all subarrays of length $  2  $ : the minimum value of $  p_1,p_2  $ is $  1  $ , the minimum value of $  p_2,p_3  $ is $  1  $ , and the minimum value of $  p_3,p_4  $ is $  2  $ . The sum $  1+1+2=4  $ is the smallest among all possible permutations.

In the second test case, all subarrays of length $  1  $ have minimum values of $  5, 2, 1, 6, 4, 3  $ , and the sum $  5+2+1+6+4+3=21  $ is proven to be the smallest.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy
Difficulty: 900
# Kevin and Combination Lock

## Problem Description

Kevin is trapped in Lakeside Village by Grace. At the exit of the village, there is a combination lock that can only be unlocked if Kevin solves it.

The combination lock starts with an integer $  x  $ . Kevin can perform one of the following two operations zero or more times:

1. If $  x \neq 33  $ , he can select two consecutive digits $  3  $ from $  x  $ and remove them simultaneously. For example, if $  x = 13\,323  $ , he can remove the second and third $  3  $ , changing $  x  $ to $  123  $ .
2. If $  x \geq 33  $ , he can change $  x  $ to $  x - 33  $ . For example, if $  x = 99  $ , he can choose this operation to change $  x  $ to $  99 - 33 = 66  $ .

When the value of $  x  $ on the combination lock becomes $  0  $ , Kevin can unlock the lock and escape from Lakeside Village. Please determine whether it is possible for Kevin to unlock the combination lock and escape.

## 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 only line of each test case contains a positive integer $ x $ ( $ 1\leq x\leq 10^9 $ ).

## Output Format

For each test case, output "YES" or "NO" (without quotes) in one line, representing whether Kevin can unlock the combination lock and escape. 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

```
5
165
6369
666
114514
133333332
```

### Sample Output #1

```
YES
YES
NO
NO
YES
```

## Hint

For the first test case, $ 165\xrightarrow{-33}132\xrightarrow{-33}99\xrightarrow{-33}66\xrightarrow{-33}33\xrightarrow{-33}0 $ .

For the second test case, $ 6369\xrightarrow{-33}6{\color{red}{33}}6\xrightarrow{\text{remove "33"}}66\xrightarrow{-33}33\xrightarrow{-33}0 $ .

For the third test case, it can be proven that, regardless of the operations performed, $ 666 $ cannot be transformed into $ 0 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, greedy, implementation, math, number theory
Difficulty: 800
# Replace Character

## Problem Description

You're given a string $ s $ of length $ n $ , consisting of only lowercase English letters.

You must do the following operation exactly once:

- Choose any two indices $ i $ and $ j $ ( $ 1 \le i, j \le n $ ). You can choose $ i = j $ .
- Set $ s_i := s_j $ .

You need to minimize the number of distinct permutations $ ^\dagger $ of $ s $ . Output any string with the smallest number of distinct permutations after performing exactly one operation.

 $ ^\dagger $ A permutation of the string is an arrangement of its characters into any order. For example, "bac" is a permutation of "abc" but "bcc" is not.

## 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 $ n $ ( $ 1 \le n \le 10 $ ) — the length of string $ s $ .

The second line of each test case contains $ s $ of length $ n $ . The string contains only lowercase English letters.

## Output Format

For each test case, output the required $ s $ after applying exactly one operation. If there are multiple solutions, print any of them.

## Sample #1

### Sample Input #1

```
6
3
abc
4
xyyx
8
alphabet
1
k
10
aabbccddee
6
ttbddq
```

### Sample Output #1

```
cbc
yyyx
alphaaet
k
eabbccddee
tttddq
```

## Hint

In the first test case, we can obtain the following strings in one operation: "abc", "bbc", "cbc", "aac", "acc", "aba", and "abb".

The string "abc" has $ 6 $ distinct permutations: "abc", "acb", "bac", "bca", "cab", and "cba".

The string "cbc" has $ 3 $ distinct permutations: "bcc", "cbc", and "ccb", which is the lowest of all the obtainable strings. In fact, all obtainable strings except "abc" have $ 3 $ permutations, so any of them would be accepted.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, combinatorics, greedy, strings
Difficulty: 900
# Alyona and a Square Jigsaw Puzzle

## Problem Description

Alyona assembles an unusual square Jigsaw Puzzle. She does so in $ n $ days in the following manner:

- On the first day, she starts by placing the central piece in the center of the table.
- On each day after the first one, she places a certain number of pieces around the central piece in clockwise order, always finishing each square layer completely before starting a new one.

For example, she places the first $ 14 $ pieces in the following order:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2047A/79d4bc6fb70315d8b0bc2f84e7e9b7aaaaa1456d.png) The colors denote the layers. The third layer is still unfinished.Alyona is happy if at the end of the day the assembled part of the puzzle does not have any started but unfinished layers. Given the number of pieces she assembles on each day, find the number of days Alyona is happy on.

## 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 contains a single integer $ n $ ( $ 1 \le n \le 100 $ ), the number of days.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 100 $ , $ a_1 = 1 $ ), where $ a_i $ is the number of pieces Alyona assembles on the $ i $ -th day.

It is guaranteed in each test case that at the end of the $ n $ days, there are no unfinished layers.

## Output Format

For each test case, print a single integer: the number of days when Alyona is happy.

## Sample #1

### Sample Input #1

```
5
1
1
2
1 8
5
1 3 2 1 2
7
1 2 1 10 2 7 2
14
1 10 10 100 1 1 10 1 10 2 10 2 10 1
```

### Sample Output #1

```
1
2
2
2
3
```

## Hint

In the first test case, in the only day Alyona finishes the only layer.

In the second test case, on the first day, Alyona finishes the first layer, and on the second day, she finishes the second layer.

In the third test case, she finishes the second layer in a few days.

In the fourth test case, she finishes the second layer and immediately starts the next one on the same day, therefore, she is not happy on that day. She is only happy on the first and last days.

In the fifth test case, Alyona is happy on the first, fourth, and last days.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: implementation, math
Difficulty: 800
# Yandex Cuneiform (Easy Version)

## Problem Description

This is the easy version of the problem. The difference between the versions is that in this version, there are no question marks. You can hack only if you solved all versions of this problem.

For a long time, no one could decipher Sumerian cuneiform. However, it has finally succumbed to pressure! Today, you have the chance to decipher Yandex cuneiform.

Yandex cuneiform is defined by the following rules:

1. An empty string is a Yandex cuneiform.
2. If you insert exactly one copy of each of the three letters 'Y', 'D', and 'X' into a Yandex cuneiform in such a way that no two adjacent letters become equal after the operation, you obtain a Yandex cuneiform.
3. If a string can't be obtained using the above rules, it is not a Yandex cuneiform.

You are given a template. A template is a string consisting of the characters 'Y', 'D', 'X', and '?'.

You need to check whether there exists a way to replace each question mark with 'Y', 'D', or 'X' to obtain a Yandex cuneiform, and if it exists, output any of the matching options, as well as a sequence of insertion operations to obtain the resulting cuneiform.

In this version of the problem, there are no question marks in the template.

## Input Format

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

Each test case consists of a single line containing a template of length $ n $ ( $ 3 \leq n < 2 \cdot 10^5 $ , $ n \bmod 3 = 0 $ ), consisting only of characters 'Y', 'D', 'X'.

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 a single line containing 'NO' if it is not possible to obtain a cuneiform from the given template.

Otherwise, output 'YES' on the first line, and on the second line, any obtainable cuneiform. After that, you need to output the sequence of operations that leads to the cuneiform you printed.

A sequence of operations is described by $ \frac{n}{3} $ triples of pairs. A pair has the form c p, where $ c $ is one of the letters 'Y', 'D', or 'X', and $ p $ is the position at which the letter $ c $ should be inserted. The insertion position is the number of letters to skip from the beginning of the string for the insertion. For example, after inserting the character 'D' into the string "YDX" with $ p=3 $ , the result is "YDXD", and with $ p=0 $ , it is "DYDX". Note that the index cannot exceed the current length of the string.

The operations are applied from top to bottom, left to right. After inserting each triple to the string, there should be no two adjacent identical characters.

## Sample #1

### Sample Input #1

```
4
YDX
YDXDYX
YDX
DYYDXYXYX
```

### Sample Output #1

```
YES
YDX
X 0 D 0 Y 0 
YES
YDXDYX
X 0 Y 0 D 1
X 2 D 3 Y 4
YES
YDX
Y 0 D 1 X 2
NO
```

## Hint

In the second example, the string is transformed like this: $ "" \to \mathtt{YDX} \to \mathtt{YDXDYX} $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, data structures, greedy
Difficulty: 3300
# For the Emperor!

## Problem Description

In Ancient Rome, a plan to defeat the barbarians was developed, but for its implementation, each city must be informed about it.

The northern part of the Roman Empire consists of $ n $ cities connected by $ m $ one-way roads. Initially, the $ i $ -th city has $ a_i $ messengers, and each messenger can freely move between cities following the existing roads. A messenger can carry a copy of the plan with him and inform the cities he visits, and can make unlimited copies for other messengers in the city he is currently in.

At the start, you will produce some number of plans and deliver them to messengers of your choice. Your goal is to make sure that every city is visited by a messenger with a plan. Find the smallest number of the plans you need to produce originally, so that the messengers will deliver them to every city, or determine that it is impossible to do so at all.

## Input Format

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

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 200 $ , $ 1 \le m \le 800 $ ) — the number of cities and roads.

The second line contains $ n $ non-negative integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_{i} \le n $ ) — the initial number of messengers in each city.

Each of the following $ m $ lines contains two integers $ u $ and $ v $ ( $ 1 \le u,v \le n, u \ne v $ ), indicating that there is a one-way road from city $ u $ to city $ v $ . The roads may repeat.

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

## Output Format

Output a single line containing a single integer — the smallest number of messengers you need to give a copy of the plan in the beginning, or $ -1 $ if it is not possible to inform all cities.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
2
2
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: flows, graphs
Difficulty: 3100