yl-9/probench huggingface dataset:
# Digits

## Problem Description

Artem wrote the digit $ d $ on the board exactly $ n! $ times in a row. So, he got the number $ dddddd \dots ddd $ (exactly $ n! $ digits).

Now he is curious about which odd digits from $ 1 $ to $ 9 $ divide the number written on the board.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The next $ t $ test cases follow.

Each test case consists of a single line containing two integers $ n $ and $ d $ ( $ 2 \le n \le 10^9 $ , $ 1 \le d \le 9 $ ).

## Output Format

For each test case, output the odd digits in ascending order that divide the number written on the board.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
1 3 
1 3 7 9 
1 3 5 7 9
```

## Hint

The factorial of a positive integer $ n $ ( $ n! $ ) is the product of all integers from $ 1 $ to $ n $ . For example, the factorial of $ 5 $ is $ 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: math, number theory
# Coin Transformation

## Problem Description

Initially, you have a coin with value $ n $ . You can perform the following operation any number of times (possibly zero):

- transform one coin with value $ x $ , where $ x $ is greater than $ 3 $  ( $ x>3 $ ), into two coins with value $ \lfloor \frac{x}{4} \rfloor $ .

What is the maximum number of coins you can have after performing this operation any number of times?

## Input Format

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

Each test case consists of one line containing one integer $ n $ ( $ 1 \le n \le 10^{18} $ ).

## Output Format

For each test case, print one integer — the maximum number of coins you can have after performing the operation any number of times.

## Sample #1

### Sample Input #1

```
4
1
5
16
1000000000000000000
```

### Sample Output #1

```
1
2
4
536870912
```

## Hint

In the first example, you have a coin of value $ 1 $ , and you can't do anything with it. So, the answer is $ 1 $ .

In the second example, you can transform a coin of value $ 5 $ into two coins with value $ 1 $ .

In the third example, you can transform a coin of value $ 16 $ into two coins with value $ 4 $ . Each of the resulting coins can be transformed into two coins with value $ 1 $ .

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: brute force, math
# Two Subarrays

## Problem Description

You are given two integer arrays $ a $ and $ b $ , both of size $ n $ .

Let's define the cost of the subarray $ [l, r] $ as $ a_l + a_{l + 1} + \cdots + a_{r - 1} + a_r + b_l + b_r $ . If $ l=r $ , then the cost of the subarray is $ a_l + 2 \cdot b_l $ .

You have to perform queries of three types:

- " $ 1 $ $ p $ $ x $ " — assign $ a_{p} := x $ ;
- " $ 2 $ $ p $ $ x $ " — assign $ b_{p} := x $ ;
- " $ 3 $ $ l $ $ r $ " — find two non-empty non-overlapping subarrays within the segment $ [l, r] $ with the maximum total cost and print their total cost.

## Input Format

The first line contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ).

The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ -10^9 \le b_i \le 10^9 $ ).

The fourth line contains a single integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ).

The next $ q $ lines contain the queries: one per line. Each query is of one of three types:

- " $ 1 $ $ p $ $ x $ " ( $ 1 \le p \le n $ ; $ -10^9 \le x \le 10^9 $ );
- " $ 2 $ $ p $ $ x $ " ( $ 1 \le p \le n $ ; $ -10^9 \le x \le 10^9 $ );
- " $ 3 $ $ l $ $ r $ " ( $ 1 \le l < r \le n $ ).

It is guaranteed that there is at least one query of the third type.

## Output Format

For each query of the third type, print the maximum possible total cost of two non-empty non-overlapping subarrays within the segment $ [l, r] $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
18
7
16
```

## Sample #2

### Sample Input #2

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

### Sample Output #2

```
23
28
28
-17
27
-22
```

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: data structures, dp, implementation, matrices
Difficulty: 2600
# Vertex Pairs

## Problem Description

You are given a tree consisting of $ 2n $ vertices. Recall that a tree is a connected undirected graph with no cycles. Each vertex has an integer from $ 1 $ to $ n $ written on it. Each value from $ 1 $ to $ n $ is written on exactly two different vertices. Each vertex also has a cost —vertex $ i $ costs $ 2^i $ .

You need to choose a subset of vertices of the tree such that:

- the subset is connected; that is, from each vertex in the subset, you can reach every other vertex in the subset by passing only through the vertices in the subset;
- each value from $ 1 $ to $ n $ is written on at least one vertex in the subset.

Among all such subsets, you need to find the one with the smallest total cost of the vertices in it. Note that you are not required to minimize the number of vertices in the subset.

## Input Format

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ).

The second line contains $ 2n $ integers $ a_1, a_2, \dots, a_{2n} $ ( $ 1 \le a_i \le n $ ). Each value from $ 1 $ to $ n $ appears exactly twice.

Each of the next $ 2n-1 $ lines contains two integers $ v $ and $ u $ ( $ 1 \le v, u \le 2n $ ) — the edges of the tree. These edges form a valid tree.

## Output Format

In the first line, print a single integer $ k $ — the number of vertices in the subset.

In the second line, print $ k $ distinct integers from $ 1 $ to $ 2n $ — the indices of the vertices in the chosen subset. The vertices can be printed in an arbitrary order.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
3
2 4 5
```

## Sample #2

### Sample Input #2

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

### Sample Output #2

```
4
1 3 4 6
```

## Sample #3

### Sample Input #3

```
6
5 2 3 4 6 4 2 5 6 1 1 3
10 8
2 10
12 7
4 10
5 9
6 2
1 9
3 4
12 6
11 5
4 5
```

### Sample Output #3

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

## Hint

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2042E/678d793458e0891cd605e59af036c54639284d60.png)The images show the answers to the first two examples. The numbers in parentheses are the values written on the vertices.

In the first example, there are valid subsets such as: $ [2, 4, 5] $ (with a cost of $ 2^2 + 2^4 + 2^5 = 52 $ ), $ [2, 4, 5, 6] $ (with a cost of $ 116 $ ), $ [1, 6, 3] $ (with a cost of $ 74 $ ), $ [2, 6, 3] $ (with a cost of $ 76 $ ), and many others.

In the second example, the cost of the subset $ [4, 6, 3, 1] $ is $ 90 $ .

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: binary search, brute force, data structures, dfs and similar, divide and conquer, greedy, implementation, trees
Difficulty: 2900
# Recommendations

## Problem Description

Suppose you are working in some audio streaming service. The service has $ n $ active users and $ 10^9 $ tracks users can listen to. Users can like tracks and, based on likes, the service should recommend them new tracks.

Tracks are numbered from $ 1 $ to $ 10^9 $ . It turned out that tracks the $ i $ -th user likes form a segment $ [l_i, r_i] $ .

Let's say that the user $ j $ is a predictor for user $ i $ ( $ j \neq i $ ) if user $ j $ likes all tracks the $ i $ -th user likes (and, possibly, some other tracks too).

Also, let's say that a track is strongly recommended for user $ i $ if the track is not liked by the $ i $ -th user yet, but it is liked by every predictor for the $ i $ -th user.

Calculate the number of strongly recommended tracks for each user $ i $ . If a user doesn't have any predictors, then print $ 0 $ for that user.

## Input Format

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

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

The next $ n $ lines contain two integers $ l_i $ and $ r_i $ per line ( $ 1 \le l_i \le r_i \le 10^9 $ ) — the segment of tracks the $ i $ -th user likes.

Additional constraint on the input: the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, print $ n $ integers, where the $ i $ -th integer is the number of strongly recommended tracks for the $ i $ -th user (or $ 0 $ , if that user doesn't have any predictors).

## Sample #1

### Sample Input #1

```
4
3
3 8
2 5
4 5
2
42 42
1 1000000000
3
42 42
1 1000000000
42 42
6
1 10
3 10
3 7
5 7
4 4
1 2
```

### Sample Output #1

```
0
0
1
999999999
0
0
0
0
0
2
3
2
4
8
```

## Hint

In the first test case:

- the first user has no predictors;
- the second user has no predictors;
- the third user has two predictors: users $ 1 $ and $ 2 $ ; only track $ 3 $ is liked by both of them and not liked by the third user.

In the second test case, the second user is a predictor for the first user. Therefore, all tracks, except $ 42 $ , are strongly recommended for the first user.

In the third test case, the first user has two predictors: users $ 2 $ and $ 3 $ , but there is no track that is liked by them and not liked by the first user himself.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: data structures, implementation, sortings, two pointers
Difficulty: 1900
# Competitive Fishing

## Problem Description

Alice and Bob participate in a fishing contest! In total, they caught $ n $ fishes, numbered from $ 1 $ to $ n $ (the bigger the fish, the greater its index). Some of these fishes were caught by Alice, others — by Bob.

Their performance will be evaluated as follows. First, an integer $ m $ will be chosen, and all fish will be split into $ m $ non-empty groups. The first group should contain several (at least one) smallest fishes, the second group — several (at least one) next smallest fishes, and so on. Each fish should belong to exactly one group, and each group should be a contiguous subsegment of fishes. Note that the groups are numbered in exactly that order; for example, the fishes from the second group cannot be smaller than the fishes from the first group, since the first group contains the smallest fishes.

Then, each fish will be assigned a value according to its group index: each fish in the first group gets value equal to $ 0 $ , each fish in the second group gets value equal to $ 1 $ , and so on. So, each fish in the $ i $ -th group gets value equal to $ (i-1) $ .

The score of each contestant is simply the total value of all fishes that contestant caught.

You want Bob's score to exceed Alice's score by at least $ k $ points. What is the minimum number of groups ( $ m $ ) you have to split the fishes into? If it is impossible, you should report that.

## 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 $ n $ and $ k $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ 1 \le k \le 10^9 $ ).

The second line contains a string, consisting of exactly $ n $ characters. The $ i $ -th character is either 0 (denoting that the $ i $ -th fish was caught by Alice) or 1 (denoting that the $ i $ -th fish was caught by Bob).

Additional constraint on the input: the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, print a single integer — the minimum number of groups you have to split the fishes into; or -1 if it's impossible.

## Sample #1

### Sample Input #1

```
7
4 1
1001
4 1
1010
4 1
0110
4 2
0110
6 3
001110
10 20
1111111111
5 11
11111
```

### Sample Output #1

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

## Hint

In the first test case of the example, you can split the fishes into groups as follows: the first three fishes form the $ 1 $ -st group, the last fish forms the $ 2 $ -nd group. Then, Bob's score will be $ 1 $ , and Alice's score will be $ 0 $ .

In the third test case of the example, you can split the fishes into groups as follows: the first fish forms the $ 1 $ -st group, the last three fishes form the $ 2 $ -nd group. Then, Bob's score will be $ 2 $ , and Alice's score will be $ 1 $ .

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: greedy
Difficulty: 1800
# Game with Colored Marbles

## Problem Description

Alice and Bob play a game. There are $ n $ marbles, the $ i $ -th of them has color $ c_i $ . The players take turns; Alice goes first, then Bob, then Alice again, then Bob again, and so on.

During their turn, a player must take one of the remaining marbles and remove it from the game. If there are no marbles left (all $ n $ marbles have been taken), the game ends.

Alice's score at the end of the game is calculated as follows:

- she receives $ 1 $ point for every color $ x $ such that she has taken at least one marble of that color;
- additionally, she receives $ 1 $ point for every color $ x $ such that she has taken all marbles of that color (of course, only colors present in the game are considered).

For example, suppose there are $ 5 $ marbles, their colors are $ [1, 3, 1, 3, 4] $ , and the game goes as follows: Alice takes the $ 1 $ -st marble, then Bob takes the $ 3 $ -rd marble, then Alice takes the $ 5 $ -th marble, then Bob takes the $ 2 $ -nd marble, and finally, Alice takes the $ 4 $ -th marble. Then, Alice receives $ 4 $ points: $ 3 $ points for having at least one marble for colors $ 1 $ , $ 3 $ and $ 4 $ , and $ 1 $ point for having all marbles of color $ 4 $ . Note that this strategy is not necessarily optimal for both players.

Alice wants to maximize her score at the end of the game. Bob wants to minimize it. Both players play optimally (i. e. Alice chooses a strategy which allows her to get as many points as possible, and Bob chooses a strategy which minimizes the amount of points Alice can get).

Calculate Alice's score at the end of the game.

## 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 $ ( $ 1 \le n \le 1000 $ ) — the number of marbles;
- the second line contains $ n $ integers $ c_1, c_2, \dots, c_n $ ( $ 1 \le c_i \le n $ ) — the colors of the marbles.

Additional constraint on the input: the sum of $ n $ over all test cases does not exceed $ 1000 $ .

## Output Format

For each test case, print one integer — Alice's score at the end of the game, assuming that both players play optimally.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
4
4
1
```

## Hint

In the second test case of the example, the colors of all marbles are distinct, so, no matter how the players act, Alice receives $ 4 $ points for having all marbles of two colors, and no marbles of the third color.

In the third test case of the example, the colors of all marbles are the same, so, no matter how the players act, Alice receives $ 1 $ point for having at least one (but not all) marble of color $ 4 $ .

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: games, greedy
Difficulty: 900
# Greedy Monocarp

## Problem Description

There are $ n $ chests; the $ i $ -th chest initially contains $ a_i $ coins. For each chest, you can choose any non-negative ( $ 0 $ or greater) number of coins to add to that chest, with one constraint: the total number of coins in all chests must become at least $ k $ .

After you've finished adding coins to the chests, greedy Monocarp comes, who wants the coins. He will take the chests one by one, and since he is greedy, he will always choose the chest with the maximum number of coins. Monocarp will stop as soon as the total number of coins in chests he takes is at least $ k $ .

You want Monocarp to take as few coins as possible, so you have to add coins to the chests in such a way that, when Monocarp stops taking chests, he will have exactly $ k $  coins. Calculate the minimum number of coins you have to add.

## 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 two integers $ n $ and $ k $ ( $ 1 \le n \le 50 $ ; $ 1 \le k \le 10^7 $ );
- the second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le k $ ).

## Output Format

For each test case, print one integer — the minimum number of coins you have to add so that, when Monocarp stops taking the chests, he has exactly $ k $  coins. It can be shown that under the constraints of the problem, it is always possible.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
0
1
8
2
```

## Hint

In the first test case of the example, you don't have to add any coins. When Monocarp arrives, he will take the chest with $ 4 $ coins, so he will have exactly $ 4 $ coins.

In the second test case of the example, you can add $ 1 $ coin to the $ 4 $ -th chest, so, when Monocarp arrives, he will take a chest with $ 4 $ coins, then another chest with $ 4 $ coins, and a chest with $ 2 $ coins.

In the third test case of the example, you can add $ 3 $ coins to the $ 1 $ -st chest and $ 5 $ coins to the $ 2 $ -nd chest.

In the fourth test case of the example, you can add $ 1 $ coin to the $ 1 $ -st chest and $ 1 $ coin to the $ 3 $ -rd chest.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: greedy, sortings
Difficulty: 800
# Selection Sort

## Problem Description

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041M/d5dc69f2c95d765850bbfc6e16bfc04c742abf70.png)Every student enrolled in the algorithms course is required to submit an assignment this week. The task is to implement an $ O(n^2) $ -time algorithm to sort $ n $ given integers in non-decreasing order. Alice has already completed her assignment, and her implementation is shown below.

```
<pre class="lstlisting">```
int alice_sort(int *s, int n){<br></br>  for(int i = 0; i < n; ++i){<br></br>    for(int j = i + 1; j < n; ++j){<br></br>      if(s[i] > s[j]){<br></br>        int swap = s[i];<br></br>        s[i] = s[j];<br></br>        s[j] = swap;<br></br>      }<br></br>    }<br></br>  }<br></br>  return 0;<br></br>}<br></br>
```
```

While you have access to Alice's code, you prefer not to simply copy it. Instead, you want to use Alice's sorting function as a building block for your own solution. There are two ways as listed below you can utilize her function, but each of them can be applied at most once. The order in which these two operations are invoked can be arbitrary.

- Prefix sort: choose a length $ i \in \{1, 2, \ldots, n\} $ and call $ \texttt{alicesort(}s, i\texttt{)} $ . This sorts the first $ i $ elements in the array $ s $ .
- Suffix sort: choose a length $ i \in \{1, 2, \ldots, n\} $ and call $ \texttt{alicesort(}s+n-i, i\texttt{)} $ . This sorts the last $ i $ elements in the array $ s $ .

Due to the time complexity of the sorting algorithm, the cost of performing either a prefix or suffix sort is $ i^2 $ , where $ i $ is the length of the chosen subarray. Your goal is to determine the minimum cost to sort the input array $ s $ of $ n $ integers in non-decreasing order using Alice's function, following the rules mentioned above.

For example, Let $ s=[3,2,5,5,4,1] $ . We can first perform a suffix sort of length $ 4 $ , and the array becomes $ [3,2,1,4,5,5] $ . Then, we perform a prefix sort of length $ 3 $ , and the array becomes $ [1,2,3,4,5,5] $ , which is a sorted array. The cost is $ 4^2+3^2=25 $ . Here is another example, let $ s=[4,3,2,1] $ . We can complete the sorting by performing only a prefix sort of length $ 4 $ , and the cost is $ 4^2=16 $ .

## Input Format

The first line contains exactly one integer $ n $ which indicates the number of integers in the array $ s $ . The second line contains the $ n $ integers in $ s=[s_0, s_1, \ldots, s_{n-1}] $ .

- $ 1 \le n \le 10^6 $
- For all $ i $ ( $ 0\le i < n $ ), $ 0\le s_i < 2^{31}-1 $ .

## Output Format

Output an integer on a line, indicating the minimum cost to sort the input array $ s $ of $ n $ integers in non-decreasing order using Alice's function, following the rules mentioned above.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
25
```

## Sample #2

### Sample Input #2

```
4
4 3 2 1
```

### Sample Output #2

```
16
```

## Limit



Time Limit
2.00s

Memory Limit
1000.00MB

Tags: binary search, data structures, greedy, two pointers
Difficulty: 2000
# Sheet Music

## Problem Description

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2041H/b6dd52e9533263fc8e6069a510bb15c19ed436d6.png) Image generated by ChatGPT 4o.Alice likes singing. As a singing enthusiast, Alice has listened to countless songs and has tried singing them many times. However, occasionally, some songs make Alice feel bored. After some research, Alice believes that this is because even though the songs she chose are all different, due to her instinctive preference, they all turn out to be musically similar to one another.

To thoroughly analyze this, Alice decided to study the sheet music of the songs. For convenience, Alice represented a song of length $ n $ as an integer sequence $ a_1, a_2, \ldots, a_n $ , where $ a_i $ is the pitch of the $ i $ -th note. Then she defined the musical equivalence between songs. Two songs $ a_1, a_2, \ldots, a_n $ and $ b_1, b_2, \ldots, b_n $ of length $ n $ are musically equivalent if for all $ 1\leq i<n $ , both $ a_i, a_{i+1} $ and $ b_{i}, b_{i+1} $ have the same pitch relationship. More specifically, $ a_i, a_{i+1} $ and $ b_i, b_{i+1} $ have the same pitch relationship if either

- $ a_i < a_{i + 1} $ and $ b_i < b_{i + 1} $ ,
- $ a_i = a_{i + 1} $ and $ b_i = b_{i + 1} $ , or
- $ a_i > a_{i + 1} $ and $ b_i > b_{i + 1} $ .

 For example, $ 1, 2, 3, 3, 2 $ and $ 5, 9, 13, 13, 1 $ are musically equivalent, while $ 1, 2, 3, 2, 1 $ and $ 1, 2, 2, 2, 1 $ are not. Having practiced consistently for a long time, Alice is able to sing any note in the range of $ [1, k] $ . She wants to know how many different songs of length $ n $ within her range there are, if we treat musically equivalent songs as the same one. Can you help her calculate the number?

Since the answer might be large, print the answer modulo $ 998244353 $ .

## Input Format

The only line contains two integers $ n, k $ .

- $ 1\leq n\leq 10^6 $
- $ 1\leq k \leq 10^9 $

## Output Format

Output the number of different songs modulo $ 998244353 $ .

## Sample #1

### Sample Input #1

```
3 2
```

### Sample Output #1

```
7
```

## Sample #2

### Sample Input #2

```
5 3
```

### Sample Output #2

```
67
```

## Limit



Time Limit
1.00s

Memory Limit
1000.00MB

Tags: combinatorics, dp, math
Difficulty: 2300