yl-9/probench huggingface dataset:
# New Game

## Problem Description

There's a new game Monocarp wants to play. The game uses a deck of $ n $ cards, where the $ i $ -th card has exactly one integer $ a_i $ written on it.

At the beginning of the game, on the first turn, Monocarp can take any card from the deck. During each subsequent turn, Monocarp can take exactly one card that has either the same number as on the card taken on the previous turn or a number that is one greater than the number on the card taken on the previous turn.

In other words, if on the previous turn Monocarp took a card with the number $ x $ , then on the current turn he can take either a card with the number $ x $ or a card with the number $ x + 1 $ . Monocarp can take any card which meets that condition, regardless of its position in the deck.

After Monocarp takes a card on the current turn, it is removed from the deck.

According to the rules of the game, the number of distinct numbers written on the cards that Monocarp has taken must not exceed $ k $ .

If, after a turn, Monocarp cannot take a card without violating the described rules, the game ends.

Your task is to determine the maximum number of cards that Monocarp can take from the deck during the game, given that on the first turn he can take any card from the deck.

## 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 $ ( $ 1 \le k \le n \le 200\,000 $ ) — the number of cards in the deck and the maximum number of distinct numbers that can be written on the cards that Monocarp takes.

The second line contains a sequence of integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{9} $ ), where $ a_i $ is the number written on the $ i $ -th card.

Additional constraint of the input: the sum of $ n $ over all test cases doesn't exceed $ 200\,000 $ .

## Output Format

For each test case, print the maximum number of cards that Monocarp can take from the deck during the game, given that on the first turn he can take any card from the deck.

## Sample #1

### Sample Input #1

```
4
10 2
5 2 4 3 4 3 4 5 3 2
5 1
10 11 10 11 10
9 3
4 5 4 4 6 5 4 4 6
3 2
1 3 1
```

### Sample Output #1

```
6
3
9
2
```

## Hint

In the first example, Monocarp needs to take any of the cards with the number $ 3 $ . On the next two turns, he needs to take the two remaining cards with the number $ 3 $ . On the next three turns, he needs to take three cards with the number $ 4 $ . After that, Monocarp will not be able to take any more cards from the deck, and he will have $ 6 $ cards.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: binary search, brute force, greedy, implementation, sortings, two pointers
Difficulty: 1300
# Binomial Coefficients, Kind Of

## Problem Description

Recently, akshiM met a task that needed binomial coefficients to solve. He wrote a code he usually does that looked like this:

```
<pre class="verbatim">    for (int n = 0; n < N; n++) { // loop over n from 0 to N-1 (inclusive)<br></br>        C[n][0] = 1;<br></br>        C[n][n] = 1;<br></br>        for (int k = 1; k < n; k++) // loop over k from 1 to n-1 (inclusive)<br></br>            C[n][k] = C[n][k - 1] + C[n - 1][k - 1];<br></br>    }<br></br>
```

Unfortunately, he made an error, since the right formula is the following:

```
<pre class="verbatim">            C[n][k] = C[n - 1][k] + C[n - 1][k - 1]<br></br>
```

But his team member keblidA is interested in values that were produced using the wrong formula. Please help him to calculate these coefficients for $ t $ various pairs $ (n_i, k_i) $ . Note that they should be calculated according to the first (wrong) formula.

Since values $ C[n_i][k_i] $ may be too large, print them modulo $ 10^9 + 7 $ .

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of pairs. Next, $ t $ pairs are written in two lines.

The second line contains $ t $ integers $ n_1, n_2, \dots, n_t $ ( $ 2 \le n_i \le 10^5 $ ).

The third line contains $ t $ integers $ k_1, k_2, \dots, k_t $ ( $ 1 \le k_i < n_i $ ).

## Output Format

Print $ t $ integers $ C[n_i][k_i] $ modulo $ 10^9 + 7 $ .

## Sample #1

### Sample Input #1

```
7
2 5 5 100000 100000 100000 100000
1 2 3 1 33333 66666 99999
```

### Sample Output #1

```
2
4
8
2
326186014
984426998
303861760
```

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: combinatorics, dp, math
Difficulty: 1100
# Two Screens

## Problem Description

There are two screens which can display sequences of uppercase Latin letters. Initially, both screens display nothing.

In one second, you can do one of the following two actions:

- choose a screen and an uppercase Latin letter, and append that letter to the end of the sequence displayed on that screen;
- choose a screen and copy the sequence from it to the other screen, overwriting the sequence that was displayed on the other screen.

You have to calculate the minimum number of seconds you have to spend so that the first screen displays the sequence $ s $ , and the second screen displays the sequence $ t $ .

## Input Format

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

Each test case consists of two lines. The first line contains the string $ s $ , and the second line contains the string $ t $ ( $ 1 \le |s|, |t| \le 100 $ ). Both strings consist of uppercase Latin letters.

## Output Format

For each test case, print one integer — the minimum possible number of seconds you have to spend so that the first screen displays the sequence $ s $ , and the second screen displays the sequence $ t $ .

## Sample #1

### Sample Input #1

```
3
GARAGE
GARAGEFORSALE
ABCDE
AABCD
TRAINING
DRAINING
```

### Sample Output #1

```
14
10
16
```

## Hint

In the first test case, the following sequence of actions is possible:

- spend $ 6 $ seconds to write the sequence GARAGE on the first screen;
- copy the sequence from the first screen to the second screen;
- spend $ 7 $ seconds to complete the sequence on the second screen by writing FORSALE.

In the second test case, the following sequence of actions is possible:

- spend $ 1 $ second to write the sequence A on the second screen;
- copy the sequence from the second screen to the first screen;
- spend $ 4 $ seconds to complete the sequence on the first screen by writing BCDE;
- spend $ 4 $ seconds to complete the sequence on the second screen by writing ABCD.

In the third test case, the fastest way to display the sequences is to type both of them character by character without copying, and this requires $ 16 $ seconds.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: binary search, greedy, strings, two pointers
Difficulty: 800
# Profitable Interest Rate

## Problem Description

Alice has $ a $ coins. She can open a bank deposit called "Profitable", but the minimum amount required to open this deposit is $ b $ coins.

There is also a deposit called "Unprofitable", which can be opened with any amount of coins. Alice noticed that if she opens the "Unprofitable" deposit with $ x $ coins, the minimum amount required to open the "Profitable" deposit decreases by $ 2x $ coins. However, these coins cannot later be deposited into the "Profitable" deposit.

Help Alice determine the maximum number of coins she can deposit into the "Profitable" deposit if she first deposits some amount of coins (possibly $ 0 $ ) into the "Unprofitable" deposit. If Alice can never open the "Profitable" deposit, output $ 0 $ .

## Input Format

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

A single line of each test case contains two integers $ a $ and $ b $ ( $ 1 \le a, b \le 10^9 $ ) — the number of coins Alice has and the initial minimum amount required to open the "Profitable" deposit.

## Output Format

For each test case, output a single integer — the maximum number of coins that Alice can deposit into the "Profitable" deposit. If Alice can never open the "Profitable" deposit, output $ 0 $ .

## Sample #1

### Sample Input #1

```
5
10 5
7 9
5 100
1 1
1 2
```

### Sample Output #1

```
10
5
0
1
0
```

## Hint

In the first test case, $ a \ge b $ , so Alice can immediately open the "Profitable" deposit with all $ 10 $ coins.

In the second test case, Alice can open the "Unprofitable" deposit with $ 2 $ coins. Then she will have $ 5 $ coins left, but the minimum amount required to open the "Profitable" deposit will decrease by $ 4 $ coins, making it equal to $ 5 $ coins. Thus, Alice will be able to open the "Profitable" deposit with $ 5 $ coins.

In the third test case, Alice will not be able to open the "Profitable" deposit.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, math
Difficulty: 800
# Concatenation of Arrays

## Problem Description

You are given $ n $ arrays $ a_1 $ , $ \ldots $ , $ a_n $ . The length of each array is two. Thus, $ a_i = [a_{i, 1}, a_{i, 2}] $ . You need to concatenate the arrays into a single array of length $ 2n $ such that the number of inversions $ ^{\dagger} $ in the resulting array is minimized. Note that you do not need to count the actual number of inversions.

More formally, you need to choose a permutation $ ^{\ddagger} $ $ p $ of length $ n $ , so that the array $ b = [a_{p_1,1}, a_{p_1,2}, a_{p_2, 1}, a_{p_2, 2}, \ldots, a_{p_n,1}, a_{p_n,2}] $ contains as few inversions as possible.

 $ ^{\dagger} $ The number of inversions in an array $ c $ is the number of pairs of indices $ i $ and $ j $ such that $ i < j $ and $ c_i > c_j $ .

 $ ^{\ddagger} $ 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 consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.

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

Each of the following $ n $ lines contains two integers $ a_{i,1} $ and $ a_{i,2} $ ( $ 1 \le a_{i,j} \le 10^9 $ ) — the elements of the $ i $ -th array.

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

## Output Format

For each test case, output $ 2n $ integers — the elements of the array you obtained. If there are multiple solutions, output any of them.

## Sample #1

### Sample Input #1

```
4
2
1 4
2 3
3
3 2
4 3
2 1
5
5 10
2 3
9 6
4 1
8 7
1
10 20
```

### Sample Output #1

```
2 3 1 4
2 1 3 2 4 3
4 1 2 3 5 10 8 7 9 6
10 20
```

## Hint

In the first test case, we concatenated the arrays in the order $ 2, 1 $ . Let's consider the inversions in the resulting array $ b = [2, 3, 1, 4] $ :

- $ i = 1 $ , $ j = 3 $ , since $ b_1 = 2 > 1 = b_3 $ ;
- $ i = 2 $ , $ j = 3 $ , since $ b_2 = 3 > 1 = b_3 $ .

Thus, the number of inversions is $ 2 $ . It can be proven that this is the minimum possible number of inversions.

In the second test case, we concatenated the arrays in the order $ 3, 1, 2 $ . Let's consider the inversions in the resulting array $ b = [2, 1, 3, 2, 4, 3] $ :

- $ i = 1 $ , $ j = 2 $ , since $ b_1 = 2 > 1 = b_2 $ ;
- $ i = 3 $ , $ j = 4 $ , since $ b_3 = 3 > 2 = b_4 $ ;
- $ i = 5 $ , $ j = 6 $ , since $ b_5 = 4 > 3 = b_6 $ .

Thus, the number of inversions is $ 3 $ . It can be proven that this is the minimum possible number of inversions.

In the third test case, we concatenated the arrays in the order $ 4, 2, 1, 5, 3 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, math, sortings
Difficulty: 1300
# Gerrymandering

## Problem Description

We all steal a little bit. But I have only one hand, while my adversaries have two.

Álvaro Obregón



Álvaro and José are the only candidates running for the presidency of Tepito, a rectangular grid of $ 2 $ rows and $ n $ columns, where each cell represents a house. It is guaranteed that $ n $ is a multiple of $ 3 $ .

Under the voting system of Tepito, the grid will be split into districts, which consist of any $ 3 $ houses that are connected $ ^{\text{∗}} $ . Each house will belong to exactly one district.

Each district will cast a single vote. The district will vote for Álvaro or José respectively if at least $ 2 $ houses in that district select them. Therefore, a total of $ \frac{2n}{3} $ votes will be cast.

As Álvaro is the current president, he knows exactly which candidate each house will select. If Álvaro divides the houses into districts optimally, determine the maximum number of votes he can get.

 $ ^{\text{∗}} $ A set of cells is connected if there is a path between any $ 2 $ cells that requires moving only up, down, left and right through cells in the set.

## 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 one integer $ n $ ( $ 3 \le n \le 10^5 $ ; $ n $ is a multiple of $ 3 $ ) — the number of columns of Tepito.

The following two lines each contain a string of length $ n $ . The $ i $ -th line contains the string $ s_i $ , consisting of the characters $ \texttt{A} $ and $ \texttt{J} $ . If $ s_{i,j}=\texttt{A} $ , the house in the $ i $ -th row and $ j $ -th column will select Álvaro. Otherwise if $ s_{i,j}=\texttt{J} $ , the house will select José.

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

## Output Format

For each test case, output a single integer — the maximum number of districts Álvaro can win by optimally dividing the houses into districts.

## Sample #1

### Sample Input #1

```
4
3
AAA
AJJ
6
JAJAJJ
JJAJAJ
6
AJJJAJ
AJJAAA
9
AJJJJAJAJ
JAAJJJJJA
```

### Sample Output #1

```
2
2
3
2
```

## Hint

The image below showcases the optimal arrangement of districts Álvaro can use for each test case in the example.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2022C/df820ffc2e1ad6e016254b57c0ce9fb7f735735d.png)

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dp, implementation
Difficulty: 1800
# Kar Salesman

## Problem Description

Karel is a salesman in a car dealership. The dealership has $ n $ different models of cars. There are $ a_i $ cars of the $ i $ -th model. Karel is an excellent salesperson and can convince customers to buy up to $ x $ cars (of Karel's choice), as long as the cars are from different models.

Determine the minimum number of customers Karel has to bring in to sell all the cars.

## 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 two integers $ n $ and $ x $ ( $ 1 \le n \le 5 \cdot 10^5 $ ; $ 1 \le x \le 10 $ ) — the number of different models of cars and the maximum number of cars Karel can convince a customer to buy.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the number of cars of each model.

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

## Output Format

For each test case, output the minimum possible number of customers needed to sell all the cars.

## Sample #1

### Sample Input #1

```
4
3 2
3 1 2
3 3
2 1 3
5 3
2 2 1 9 2
7 4
2 5 3 3 5 2 5
```

### Sample Output #1

```
3
3
9
7
```

## Hint

For the first case, Karel only needs to lure in $ 3 $ customers. He will convince the customers to buy the following models of cars:

- Customer $ 1 $ buys $ 2 $ cars with model $ 1 $ and $ 3 $ .
- Customer $ 2 $ buys $ 2 $ cars with model $ 1 $ and $ 2 $ .
- Customer $ 3 $ buys $ 2 $ cars with model $ 1 $ and $ 3 $ .

For the second case, Karel only needs to lure in $ 3 $ customers. He will convince the customers to buy the following models of cars:

- Customer $ 1 $ buys $ 2 $ cars with model $ 1 $ and $ 3 $ .
- Customer $ 2 $ buys $ 3 $ cars with model $ 1 $ , $ 2 $ and $ 3 $ .
- Customer $ 3 $ buys $ 1 $ car with model $ 3 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: binary search, greedy, math
Difficulty: 1300
# Bus to Pénjamo

## Problem Description

Ya vamos llegando a Péeeenjamoo ♫♫♫ 





There are $ n $ families travelling to Pénjamo to witness Mexico's largest-ever "walking a chicken on a leash" marathon. The $ i $ -th family has $ a_i $ family members. All families will travel using a single bus consisting of $ r $ rows with $ 2 $ seats each.

A person is considered happy if:

- Another family member is seated in the same row as them, or
- They are sitting alone in their row (with an empty seat next to them).

Determine the maximum number of happy people in an optimal seating arrangement. Note that everyone must be seated in the bus.

It is guaranteed that all family members will fit on the bus. Formally, it is guaranteed that $ \displaystyle\sum_{i=1}^{n}a_i \le 2r $ .

## 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 two integers $ n $ and $ r $ ( $ 1 \le n \le 100 $ ; $ 1 \le r \le 500 $ ) — the number of families and the number of rows in the bus.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10 $ ) — the number of family members in each family.

## Output Format

For each test case, output the maximum number of happy people in an optimal seating arrangement.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
4
6
6
6
```

## Hint

In the first test case, the two members of the first family can sit together in the first row, while the two members of the second family can sit together in the second row. The remaining member of the second family can sit in the third row along with a member of the third family. This seating arrangement is shown below, where the $ 4 $ happy people are colored green.

  $ \color{green}{1} $  $ \color{green}{1} $  $ \color{green}{2} $  $ \color{green}{2} $  $ 2 $  $ 3 $ In the second test case, a possible seating arrangement with $ 6 $ happy people is shown below.

  $ \color{green}{3} $  $ \color{green}{3} $  $ \color{green}{1} $  $ \color{green}{1} $  $ \color{green}{2} $  $ \color{green}{2} $ In the third test case, a possible seating arrangement with $ 6 $ happy people is shown below.

  $ \color{green}{4} $  $ \color{green}{4} $  $ \color{green}{} $  $ \color{green}{2} $  $ \color{green}{3} $  $ \color{green}{3} $  $ \color{green}{1} $  $ \color{green}{} $  $ \color{green}{} $  $ \color{green}{} $

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, greedy, implementation, math
Difficulty: 800
# Digital Village (Extreme Version)

## Problem Description

This is the extreme version of the problem. In the three versions, the constraints on $ n $ and $ m $ are different. You can make hacks only if all the versions of the problem are solved.

Pak Chanek is setting up internet connections for the village of Khuntien. The village can be represented as a connected simple graph with $ n $ houses and $ m $ internet cables connecting house $ u_i $ and house $ v_i $ , each with a latency of $ w_i $ .

There are $ p $ houses that require internet. Pak Chanek can install servers in at most $ k $ of the houses. The houses that need internet will then be connected to one of the servers. However, since each cable has its latency, the latency experienced by house $ s_i $ requiring internet will be the maximum latency of the cables between that house and the server it is connected to.

For each $ k = 1,2,\ldots,n $ , help Pak Chanek determine the minimum total latency that can be achieved for all the houses requiring internet.

## 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 3 integers $ n $ , $ m $ , $ p $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ n-1 \le m \le 2 \cdot 10^5 $ ; $ 1 \le p \le n $ ) — the number of houses, the number of cables, and the number of houses that need internet.

The second line of each test case contains $ p $ integers $ s_1, s_2, \ldots, s_p $ ( $ 1 \le s_i \le n $ ) — the houses that need internet. It is guaranteed that all elements of $ s $ are distinct.

The $ i $ -th of the next $ m $ lines of each test case contains three integers $ u_i $ , $ v_i $ , and $ w_i $ ( $ 1 \le u_i < v_i \le n $ ; $ 1 \le w_i \le 10^9 $ ) — the internet cable connecting house $ u_i $ and house $ v_i $ with latency of $ w_i $ . It is guaranteed that the given edges form a connected simple graph.

It is guaranteed that the sum of $ n $ and the sum of $ m $ do not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output $ n $ integers: the minimum total latency that can be achieved for all the houses requiring internet for each $ k = 1,2,\ldots,n $ .

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
34 19 9 4 0 0 0 0 0
2 0 0
```

## Hint

In the first test case for $ k=3 $ , a possible optimal solution is to install servers at vertices $ 2 $ , $ 6 $ and $ 8 $ and obtain the following latency:

- $ \text{latency}(2) = 0 $
- $ \text{latency}(5) = \max(3, 5) = 5 $
- $ \text{latency}(6) = 0 $
- $ \text{latency}(8) = 0 $
- $ \text{latency}(9) = \max(2, 4) = 4 $

So the total latency is $ 9 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, dfs and similar, dp, dsu, graphs, greedy, math, trees
Difficulty: 2800