yl-9/probench huggingface dataset:
# Delicate Anti-monotonous Operations

## Problem Description

I shall be looking for you who would be out of Existence.

— HyuN, [Disorder](https://soundcloud.com/k-sounds-studio/g2r2018-hyun-disorder-feat-yuri)



There are always many repetitive tasks in life. Iris always dislikes them, so she refuses to repeat them. However, time cannot be turned back; we only have to move forward.

Formally, Iris has an integer sequence $ a_1, a_2, \ldots, a_n $ , where each number in the sequence is between $ 1 $ and $ w $ , inclusive. It is guaranteed that $ w \geq 2 $ .

Iris defines an operation as selecting two numbers $ a_i, a_{i+1} $ satisfying $ a_i = a_{i+1} $ , and then changing them to two arbitrary integers within the range $ [1, w] $ . Iris does not like equality, so she must guarantee that $ a_i \neq a_{i+1} $ after the operation. Two identical pairs $ a_i, a_{i+1} $ can be selected multiple times.

Iris wants to know the maximum possible sum of all elements of $ a $ after several (possible, zero) operations, as well as the minimum number of operations required to achieve this maximum value.

## Input Format

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ w $ ( $ 1 \leq n \leq 2\cdot 10^5 $ , $ 2 \leq w \leq 10^8 $ ) — the length of the array, and the maximum allowed value of the elements.

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

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

## Output Format

For each test case, output two integers — the maximum possible sum of all elements of $ a $ and the minimum number of operations required, respectively.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
15 0
34 6
```

## Hint

In the first test case, no operation can be performed so the answers are $ \sum a_i = 15 $ and $ 0 $ , respectively.

In the second test case, the operations can be performed as follows:

 $ $$$[3, 1, 2, 3, 4, \underline{1, 1}] \rightarrow [3, 1, 2, 3, \underline{4, 4}, 5] \rightarrow [3, 1, 2, \underline{3, 3}, 5, 5] \rightarrow [3, 1, \underline{2, 2}, 5, 5, 5] \rightarrow [3, \underline{1, 1}, 5, 5, 5, 5] \rightarrow [\underline{3, 3}, 5, 5, 5, 5, 5] \rightarrow [4, 5, 5, 5, 5, 5, 5] $ $ </p><p>It can be shown this is optimal, so we should output  $ \\sum a\_i = 34 $  and the number of <span class="tex-font-style-it">operations</span>,  $ 6$$$, respectively.

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: constructive algorithms, implementation
# Bewitching Stargazer

## Problem Description

I'm praying for owning a transparent heart; as well as eyes with tears more than enough...

— Escape Plan, [Brightest Star in the Dark](https://www.youtube.com/watch?v=GPnymcrXgX0)



Iris looked at the stars and a beautiful problem emerged in her mind. She is inviting you to solve it so that a meteor shower is believed to form.

There are $ n $ stars in the sky, arranged in a row. Iris has a telescope, which she uses to look at the stars.

Initially, Iris observes stars in the segment $ [1, n] $ , and she has a lucky value of $ 0 $ . Iris wants to look for the star in the middle position for each segment $ [l, r] $ that she observes. So the following recursive procedure is used:

- First, she will calculate $ m = \left\lfloor \frac{l+r}{2} \right\rfloor $ .
- If the length of the segment (i.e. $ r - l + 1 $ ) is even, Iris will divide it into two equally long segments $ [l, m] $ and $ [m+1, r] $ for further observation.
- Otherwise, Iris will aim the telescope at star $ m $ , and her lucky value will increase by $ m $ ; subsequently, if $ l \neq r $ , Iris will continue to observe two segments $ [l, m-1] $ and $ [m+1, r] $ .

Iris is a bit lazy. She defines her laziness by an integer $ k $ : as the observation progresses, she will not continue to observe any segment $ [l, r] $ with a length strictly less than $ k $ . In this case, please predict her final lucky value.

## Input Format

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

The only line of each test case contains two integers $ n $ and $ k $ ( $ 1 \leq k \leq n \leq 2\cdot 10^9 $ ).

## Output Format

For each test case, output a single integer — the final lucky value.

## Sample #1

### Sample Input #1

```
6
7 2
11 3
55 13
5801 6
8919 64
8765432 1
```

### Sample Output #1

```
12
18
196
1975581
958900
38416403456028
```

## Hint

In the first test case, at the beginning, Iris observes $ [1, 7] $ . Since $ [1, 7] $ has an odd length, she aims at star $ 4 $ and therefore increases her lucky value by $ 4 $ . Then it is split into $ 2 $ new segments: $ [1, 3] $ and $ [5, 7] $ . The segment $ [1, 3] $ again has an odd length, so Iris aims at star $ 2 $ and increases her lucky value by $ 2 $ . Then it is split into $ 2 $ new segments: $ [1, 1] $ and $ [3, 3] $ , both having a length less than $ 2 $ , so no further observation is conducted. For range $ [5, 7] $ , the progress is similar and the lucky value eventually increases by $ 6 $ . Therefore, the final lucky value is $ 4 + 2 + 6 = 12 $ .

In the last test case, Iris finally observes all the stars and the final lucky value is $ 1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, divide and conquer, dp, math
# Outstanding Impressionist

## Problem Description

If it was so, then let's make it a deal...

— MayDay, [Gentleness](https://www.youtube.com/watch?v=mtAc_bMYBsM&list=PLj6NQzHFCvkHKIm0Vnk9LH3odqTIBRZ1Q&index=15)



Even after copying the paintings from famous artists for ten years, unfortunately, Eric is still unable to become a skillful impressionist painter. He wants to forget something, but the white bear phenomenon just keeps hanging over him.

Eric still remembers $ n $ pieces of impressions in the form of an integer array. He records them as $ w_1, w_2, \ldots, w_n $ . However, he has a poor memory of the impressions. For each $ 1 \leq i \leq n $ , he can only remember that $ l_i \leq w_i \leq r_i $ .

Eric believes that impression $ i $ is unique if and only if there exists a possible array $ w_1, w_2, \ldots, w_n $ such that $ w_i \neq w_j $ holds for all $ 1 \leq j \leq n $ with $ j \neq i $ .

Please help Eric determine whether impression $ i $ is unique for every $ 1 \leq i \leq n $ , independently for each $ i $ . Perhaps your judgment can help rewrite the final story.

## Input Format

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

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

Then $ n $ lines follow, the $ i $ -th containing two integers $ l_i $ and $ r_i $ ( $ 1 \leq l_i \leq r_i \leq 2\cdot n $ ) — the minimum possible value and the maximum possible value of $ w_i $ .

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 binary string $ s $ of length $ n $ : for each $ 1 \leq i \leq n $ , if impression $ i $ is unique, $ s_i=\texttt{1} $ ; otherwise, $ s_i=\texttt{0} $ . Do not output spaces.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
00
1111
100110
1001111
011
```

## Hint

In the first test case, the only possible array $ w $ is $ [1, 1] $ , making neither impression $ 1 $ nor $ 2 $ unique (since $ w_1 = w_2 $ ).

In the second test case, all impressions can be made unique:

- For $ i = 1 $ , we can set $ w $ to $ [1, 3, 2, 3] $ , in which $ w_1 \neq w_2 $ , $ w_1 \neq w_3 $ , and $ w_1 \neq w_4 $ ;
- For $ i = 2 $ , we can set $ w $ to $ [2, 3, 1, 2] $ , in which $ w_2 \neq w_1 $ , $ w_2 \neq w_3 $ , and $ w_2 \neq w_4 $ ;
- For $ i = 3 $ , we can set $ w $ to $ [1, 1, 3, 1] $ ;
- For $ i = 4 $ , we can set $ w $ to $ [2, 3, 3, 1] $ .

In the third test case, for $ i = 4 $ , we can set $ w $ to $ [3, 2, 2, 1, 3, 2] $ . Thus, impression $ 4 $ is unique.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: binary search, brute force, data structures, greedy
# Judicious Watching

## Problem Description

Jill loves having good grades in university, so she never misses deadlines for her homework assignments. But even more, she loves watching the series and discussing it with her best friend Johnny. And unfortunately, today she needs to choose between these two activities!

Jill needs to complete $ n $ homework tasks. The $ i $ -th task would require $ a_i $ minutes to complete and needs to be submitted to the teacher at most $ d_i $ minutes from now. Also, there are $ m $ new episodes of the series that Johnny and Jill want to discuss. The $ j $ -th episode lasts $ l_j $ minutes. Jill can complete tasks in any order, but she needs to watch the episodes in the order they come. Neither completing a homework task nor watching an episode can be interrupted after starting.

Johnny and Jill need to agree on a time $ t_k $ when they would have a call to discuss the series. They are not sure yet which time to choose. For each possible time, compute the maximum number of episodes Jill could watch before that time while still being able to complete all $ n $ homework tasks in time.

Note that for the purpose of this problem we assume that discussing the series with Johnny at time $ t_k $ does not consume significant time from Jill and can happen even if she is in the middle of completing any of her homework tasks.

## Input Format

There are several test cases in the input. The input begins with the number of test cases $ T $ ( $ 1 \le T \le 1\,000 $ ).

Each test case starts with a line with three integers $ n $ ( $ 1 \le n \le 200\,000 $ ) — the number of homework tasks, $ m $ ( $ 1 \le m \le 200\,000 $ ) — the number of episodes, and $ q $ ( $ 1 \le q \le 200\,000 $ ) — the number of possible times for the call with Jill.

The second line contains $ n $ integers $ a_i $ ( $ 1 \le a_i \le 10^9 $ ) — the number of minutes it takes to complete the task. The next line contains $ n $ integers $ d_i $ ( $ 1 \le d_i \le 10^{15} $ ) — the deadline before which this task must be completed. The next line contains $ m $ integers $ l_j $ ( $ 1 \le l_j \le 10^9 $ ) — the length of episodes in the order they need to be watched. The next line contains $ q $ integers $ t_k $ ( $ 1 \le t_k \le 10^{15} $ ) — the possible times of call with Jill.

It is possible to complete all tasks within their respective deadlines.

The sum of each of $ n $ , $ m $ , $ q $ over all test cases in input doesn't exceed $ 200\,000 $ .

## Output Format

For each test case output a single line with $ q $ integers — for each possible time $ t_k $ the maximum number of episodes Jill can watch.

## Sample #1

### Sample Input #1

```
2
1 2 3
10
15
5 5
5 15 20
3 4 5
8 100 8
10 150 20
2 32 1 1
9 200 51 50 10
```

### Sample Output #1

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

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: binary search, greedy, sortings
Difficulty: 2000
# Geometric Balance

## Problem Description

Peter's little brother Ivan likes to play with a turtle. The turtle is a special toy that lives on the plane and can execute three commands:

- Rotate $ a $ degrees counterclockwise.
- Draw $ d $ units in the direction it is facing while dispensing ink. No segment of the plane will be covered by ink more than once.
- Move $ d $ units in the direction it is facing without drawing.

Ivan just learned about the compass, so he will only rotate his turtle so it faces one of eight cardinal or ordinal directions (angles $ a $ in rotate commands are always divisible by 45). Also, he will perform at least one draw command.

Peter has noted all the commands Ivan has given to his turtle. He thinks that the image drawn by the turtle is adorable. Now Peter wonders about the smallest positive angle $ b $ such that he can perform the following operations: move the turtle to a point of his choosing, rotate it by $ b $ degrees, and execute all the commands in the same order. These operations should produce the same image as the original one. Can you help Peter?

Note, two images are considered the same if the sets of points covered by ink on the plane are the same in both of the images.

## Input Format

The first line of the input contains a single integer $ n\;(1 \le n \le 50000) $ — the number of commands Ivan has given.

The next $ n $ lines contain commands. Each command is one of:

- "rotate $ a $ " ( $ 45 \le a \le 360 $ ) where $ a $ is divisible by $ 45 $ ;
- "draw $ d $ " ( $ 1 \le d \le 10^9 $ );
- "move $ d $ " ( $ 1 \le d \le 10^9 $ ).

At least one and at most 2000 of the commands are draw. It is guaranteed that no segment of the plane will be covered by ink more than once.

## Output Format

Output a single number, the answer to the question. The answer always exists.

## Sample #1

### Sample Input #1

```
1
draw 10
```

### Sample Output #1

```
180
```

## Sample #2

### Sample Input #2

```
7
draw 1
rotate 90
draw 1
rotate 90
draw 1
rotate 90
draw 1
```

### Sample Output #2

```
90
```

## Sample #3

### Sample Input #3

```
3
draw 1
move 1
draw 2
```

### Sample Output #3

```
360
```

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: data structures, geometry, implementation
Difficulty: 2800
# Fix Flooded Floor

## Problem Description

Archimedes conducted his famous experiments on buoyancy. But not everyone knows that while he was taking a bath, he was too focused and didn't notice the moment when the water overflowed over the edge of the bath and flooded the floor near the wall. His expensive parquet was irreversibly damaged!

Archimedes noticed that not all was lost, and there were still several undamaged parquet pieces. The parquet near the wall had the shape of a long narrow stripe of $ 2\times n $ cells. Archimedes had an unlimited supply of $ 1\times 2 $ parquet pieces that could be placed parallel or perpendicular to the wall. Archimedes didn't want to cut the parquet pieces. As a great scientist, he figured out that there was exactly one way to restore the parquet by filling the damaged area of the parquet with the non-overlapping $ 1\times 2 $ cell shaped pieces.

Help historians to check Archimedes' calculations. For the given configuration of the $ 2\times n $ parquet floor, determine whether there is exactly one way to fill the damaged parquet cells with the $ 1\times 2 $ cell parquet pieces. If Archimedes was wrong, find out whether there are multiple ways to restore the parquet, or there are no ways at all.

## Input Format

The first line contains a single integer $ T $ ( $ 1 \le T \le 10^4 $ ) — the number of test cases to solve.

Then the description of test cases follows.

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

The following two lines contain exactly $ n $ characters each and describe the parquet, where '.' denotes a damaged cell and '\#' denotes an undamaged cell.

The total sum of $ n $ in all $ T $ test cases doesn't exceed $ 2\cdot 10^5 $ .

## Output Format

For each test case, print "Unique" if there is exactly one way to restore the parquet, "Multiple" if there are multiple ways to do so, or "None" if it is impossible to restore the parquet.

## Sample #1

### Sample Input #1

```
4
10
#.......##
##..#.##..
6
...#..
..#...
8
........
........
3
###
###
```

### Sample Output #1

```
Unique
None
Multiple
Unique
```

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: constructive algorithms, dp, graphs
Difficulty: 1700
# Expression Correction

## Problem Description

Eve is studying mathematics in school. They've already learned how to perform addition and subtraction of decimal numbers and are practicing it by solving fun puzzles. The specific type of the puzzle they are solving is described below. They are given an equality with addition and subtraction which may or may not be a correct one. They have to verify the equality, and if it is not a correct one, then they have to tell if it is possible to turn it into a correct one by moving one digit to a different place in the equality.

Let us formally define the equality in this puzzle:

- Number is a string of at least one and at most 10 decimal digits ('0' to '9') that has no extra leading zeroes (the only number that is allowed to start with the zero digit is "0").
- Expression is a string composed of one or more numbers, as defined above, that are separated with addition ('+') or subtraction ('-') operators.
- Equality is a string composed of an expression, as defined above, followed by an equals sign ('='), followed by another expression.
- Correct equality is an equality where both expressions on the left and right hand sides of the equals sign evaluate to the same decimal number according to the standard arithmetic. Note that while all the numbers in the expression are positive, the evaluated number can be negative. Also, the evaluated number can be longer than 10 digits.
- Moving a digit in an equality means removing a digit from any position in the string and inserting it into another position so that the resulting string is again an equality.

The puzzle is pretty straightforward once you know how to add and subtract decimal numbers, but it is tenuous. It is easy to get distracted and make a mistake while performing computation. Your task is to write a program that solves the expression correction puzzle to help Eve.

## Input Format

The input file consists of a single line — an equality as defined in the problem statement. The total length of the input string does not exceed 100 characters.

## Output Format

Write a single line to the output. If the input contains a correct equality, output a single word "Correct". Otherwise, if the input equality can be turned into a correct one by moving one digit, output the resulting correct equality. If there are multiple possible correct equalities after moving one digit, you may output any one of them. Otherwise, output a single word "Impossible".

## Sample #1

### Sample Input #1

```
2+2=4
```

### Sample Output #1

```
Correct
```

## Sample #2

### Sample Input #2

```
123456789+9876543210=111111110+11-1
```

### Sample Output #2

```
123456789+987654321=1111111100+11-1
```

## Sample #3

### Sample Input #3

```
10+9=10
```

### Sample Output #3

```
Impossible
```

## Sample #4

### Sample Input #4

```
24=55-13
```

### Sample Output #4

```
42=55-13
```

## Sample #5

### Sample Input #5

```
1000000000-10=9999999999
```

### Sample Output #5

```
Impossible
```

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: brute force, expression parsing, strings
Difficulty: 1900
# DAG Serialization

## Problem Description

Consider a simple single-bit boolean register that supports two operations:

- set — sets the register to true if it was false, and returns true; otherwise, it returns false;
- unset — sets the register to false if it was true, and returns true; otherwise, it returns false.

The initial state of the register is false. Suppose there were $ n $ operations $ op_i $ (for $ 1 \le i \le n $ ) where at most two operations returned true. Also, we are given the partial order of operations as a directed acyclic graph (DAG): an edge $ i \rightarrow j $ means that $ op_i $ happened before $ op_j $ . You are asked whether it is possible to put these operations in some linear sequential order that satisfies the given partial order and such that if operations are applied to the register in that order, their results are the same as given.

## Input Format

In the first line, you are given an integer $ n $ — the number of operations ( $ 1 \le n \le 10^5 $ ). In the following $ n $ lines, you are given operations in the format "type result", where type is either "set" or "unset" and result is either "true" or "false". It is guaranteed that at most two operations have "true" results.

In the next line, you are given an integer $ m $ — the number of arcs of the DAG ( $ 0 \le m \le 10^5 $ ). In the following $ m $ lines, you are given arcs — pairs of integers $ a $ and $ b $ ( $ 1 \leq a, b \leq n $ ; $ a \neq b $ ). Each arc indicates that operation $ op_a $ happened before operation $ op_b $ .

## Output Format

Print any linear order of operations that satisfies the DAG constraints and ensures the results of the operations match the ones given in the input. If a correct operation order does not exist, print $ -1 $ .

## Sample #1

### Sample Input #1

```
5
set true
unset true
set false
unset false
unset false
2
1 4
5 2
```

### Sample Output #1

```
5 1 3 2 4
```

## Sample #2

### Sample Input #2

```
3
unset true
unset false
set true
0
```

### Sample Output #2

```
2 3 1
```

## Sample #3

### Sample Input #3

```
2
unset false
set true
1
2 1
```

### Sample Output #3

```
-1
```

## Sample #4

### Sample Input #4

```
2
unset false
set false
0
```

### Sample Output #4

```
-1
```

## Limit



Time Limit
3.00s

Memory Limit
1000.00MB

Tags: brute force, graphs
Difficulty: 2100