# First Round SOI 2022/2023

## Overview

Welcome to the first round of the Swiss Olympiad in Informatics! You will find below an overview of what you’ve done so far as well as a few things that you should know before getting started.

Contest ends at 2022-11-30T23:59:59+01:00

Junior onlyparagliding‒/100‒/15‒/15‒/15‒/25‒/30
Junior onlyrubiksknob‒/100‒/17‒/16‒/23‒/44
Bothboulders‒/100‒/10‒/25‒/30‒/35
Bothcardgame‒/100‒/20‒/20‒/20‒/20‒/20
Bothpalatinalcrypt‒/100‒/15‒/10‒/25‒/50
Regular onlythermalsprings‒/100‒/20‒/20‒/20‒/40
Regular onlytrees‒/100‒/10‒/15‒/75

## Tips

You may use any programming language to solve the tasks of the first round. To solve a practical task, you have to design a program, download an input file, run the program on the data in that file, write the results in another file and upload it along with the source code to the website, which will grade your submission and display the number of points that you’ve earned as well as an explanation if you did not get all the possible points. In order to read the data in the input file, make sure that your program either reads directly in that file or redirect the standard input to it (in a terminal running on Linux, Windows or OS X, you can do that by using the command ‘yourprogram < inputfile’, replacing ‘yourprogram’ and ‘inputfile’ by the paths to the actual program and input file). There are also theoretical tasks and a creativity task, about which you will get more information on the dedicated pages. More elaborate explanations about how to solve the tasks of the first round await you on our wiki and our training page. Note that in case you get stuck on the tasks, you can move to next task and try again later: no need to solve them in order.

You should also hear about our workshops! In October and November, we offer workshops in two parts about programming and algorithmics. It’s a great opportunity to learn all you need for the first round and to meet other like-minded participants. Whether you’re a beginner or an experienced programmer, it’s worth it to come. More info and registration here.

## Rules and Prizes

The first round has two categories: Junior and Regular. You can participate in the Junior category if you are eligible to participate in this year’s edition of SOI as well as the two next ones. If you are eligible as a junior, you can choose to participate in the Junior or in the Regular category or in both.

The top 8 juniors will qualify for our training camp in Sarnen. The second round will be open to the top 20 of the Junior category.

The 16 best regular participants qualify for our camp in Sarnen. The top 40 of the regular round will advance to the second round.

The 3 best juniors and 3 best regular participants shall be rewarded with prizes during the SOI Day in January (if someone is among the 3 best juniors and 3 best regular participants, they win both prizes). Also, we will give the Rainbow Award to the participant who has solved the first round in the Regular category using the most programming languages. The last submission with a nonzero score for each subtask counts.

We wish you good luck, hope you will enjoy solving our tasks and look forward to meeting you at our workshops or at SOI Day.

## Paragliding

Mouse Binna has recently become interested in paragliding. She is already planning her next trip and is examining different locations where she could go paragliding. Currently, she is looking at a place range. On a map, she marked various points of interests: places where she could start or land, like peaks, cliffs, valleys etc.

The region Binna is currently looking at can be described as a sequence of $N$ places on a line, numbered from $0$ to $N - 1$ from left to right. The $i$-th place is located at position $x_i$ and its height is $h_i$ meters. Binna can fly from place $i$ to place $j$ if place $i$ is higher than place $j$ and also all places in between. Note that place $j$ can lie before or after place $i$.

For each place $i$, Mouse Binna would like to know the maximal distance she could fly starting from $i$. The distance between two places $i$ and $j$ is defined as the absolute difference between their positions: $|x_i - x_j|$. If, for some place, Binna can not fly to any other place, the maximal distance for this place is $0$.

Can you help Binna to calculate for each place the maximal distance she could fly starting from there?

### Subtask 1: The Uetliberg (15 points)

As Mouse Binna is not yet very experienced, she would like to start at the Uetliberg, which is a small hill next to Zurich. There is only one starting place and as unexperienced as Binna is, she would like to land on the beginner’s landing place directly below. Thus there are only two places to consider, so $N = 2$.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

• The first line contains a single integer $N$ denoting the number of places.
• The second line consists of $N$ integers $x_i$ denoting the position of the $i$-th place.
• The third line consist of $N$ integers $h_i$ denoting the height of the $i$-th place.

#### Output

For the $i$-th testcase, output a line containing “Case #i:” followed by $N$ integers, where the $j$-th integer is the maximum flight distance if Binna begins at place $j$.

#### Limits

• $T=100$.
• $N = 2$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i \neq h_j$ for $i \neq j$, the height of each place is distinct.

#### Example

Input:

2
2
3 5
10 20
2
0 639
732 554

Output:

Case #0: 0 2
Case #1: 639 0

Comment:

Case #0: We cannot glide from the first place to the second place since its height is lower, thus no trip is possible and the distance is $0$. Since the second place is higher than the first we can fly from the second place to the first place, the distance of this trip is $2$.

Case #1: Here since the first place is higher than the second we may fly from the first to the second with a distance of $639$ meters, flying over the steep face directly below the take-off site at the Uetliberg. However we cannot fly from the second to the first so the distance is $0$.

### Subtask 2: Paragliding at the Gornergrat (15 Points)

Mouse Binna is now already feeling better. As she was enjoying her view of the Matterhorn from the Gornergrat, a rocky ridge next to Zermatt, she had the idea to paraglide at the Gornergrat. On her way back down, she wrote down a list of possible paragliding places. She was walking only downwards, meaning that in this subtask, each place is lower than the place just before it. Can you compute for her for each place how far she could fly starting from this place?

#### Limits

• $T=100$.
• $2 \le N \le 3\,000$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i > h_j$ for $i < j$, the heights of the places are decreasing (this is a special restriction of this subtask).

### Input and Output

#### Example

Input:

2
5
1 3 6 8 9
8 6 5 2 1
6
0 1430 2870 5310 7590 9340
3089 2819 2582 2210 1770 1604

Output:

Case #0: 8 6 3 1 0
Case #1: 9340 7910 6470 4030 1750 0

Comment:

Case #0: From the first place, we can paraglide down everything until place 4 for a distance of 8 meters.

Case #1: It seems like Binna didn’t walk down the Gornergrat, but took the train instead and just wrote down the different train stations. What a lazy mouse.

### Subtask 3: Mount Kékes (15 Points)

The International Mouse Olympiad in Informatics 2023 will take place in Hungary, and Mouse Binna managed to qualify. She started looking at the different mountains of Hungary and figured out that for paragliding her best bet would be Mount Kékes. So she started looking at possible places for take-off and landing at Mount Kékes. Mount Kékes has what she calls the “standard mountain shape”. Thus for all cases in this subtask, the heights are first increasing and then decreasing. Formally, in every test case there is an index $k$ such that $h_{0}< {\dots} < h_{k - 1} < h_k > h_{k + 1} > {\dots} > h_{n - 1}$ (note that $k$ can be $0$ or $n - 1$).

#### Limits

• $T=100$.
• $2 \le N \le 3\,000$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• There is an index $k$ such that $h_{0}< {\dots} < h_{k - 1} < h_k > h_{k + 1} > {\dots} > h_{n - 1}$ (this is a special restriction of this subtask).

### Input and Output

Same as subtasks 1 and 2.

#### Example

Input:

2
6
1 2 6 7 8 9
1 4 5 7 6 2
8
0 957 1370 1981 2873 3001 3651 4781
675 836 949 1014 885 881 730 565

Output:

Case #0: 0 1 5 6 1 0
Case #1: 0 957 1370 2800 1908 1780 1130 0

Comment:

Case #0: From place number 3, all the places are reachable, however, the longest flight can be achieved by flying all to the left until place 0.

Case #1: Did you know that Mount Kékes is only 1014 metres high?

### Subtask 4: The Mátra Mountain Range (25 points)

Mouse Binna figured out that if she wants to find longer paraglides, she must take into account multiple mountains instead of only a single one. Thus she is now looking at the Mátra mountain range in Hungary. She already wrote down a lot of places to look at. However, this time, there is no real pattern. Can you still help Binna and compute for her how far she can fly from each possible starting point?

### Input and Output

Same as subtasks 1, 2 and 3.

#### Limits

• $T=100$.
• $2 \le N \le 3\,000$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i \neq h_j$ for $i \neq j$, the height of each place is distinct.

#### Example

Input:

2
5
1 2 3 4 5
5 3 1 2 4
5
1 3 6 8 9
2 1 3 5 4

Output:

Case #0: 4 2 0 1 3
Case #1: 2 0 5 7 0

Comment:

Case #0: The first place has height 5 so we can glide all the way to the last place with height 4, for a distance of 4. From the last place with height 4 we can glide to the second place, for a distance of 3. The other trips may also be shown to be maximal.

Case #1: Note that from the place with index 3 (position 8 and height 5) we may fly to the place with index 0 (position 1 and height 2) for a distance of 7, although a place between them exists with height 3. This is because only the starting height must be greater than all heights between the starting and ending place. The ending height may be lower than a place between the starting and ending place.

### Subtask 5: All of Hungary (30 points)

Back in Mouseland Binna has a lot of fans. They would love to accompany her on her trip to Hungary. To make it especially interesting, Binna thought that every one of her fans should start from a different location. She still wants to make sure they’re all having as much fun as possible, so each one of their fans should fly the longest possible route.

Can you help her to plan this trip? To keep it simple, she invites only as many fans as there are places to take off from in Hungary. Now she would like to know the total distance they can manage to paraglide through Hungary together. Calculate for each place the longest possible paraglide and tell Binna the combined distance they might achieve.

### Input

Same as subtasks 1, 2, 3 and 4.

### Output

Output a single number per test case, the combined distance paraglided by all of Binna’s fans.

#### Limits

• $T=100$.
• $2 \le N \le 10^{6}$.
• $1 \le x_i, h_i \le 10^{12}$. Note that these increased limits lead to large results.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i \neq h_j$ for $i \neq j$, the height of each place is distinct.

#### Example

Input:

3
5
1 2 3 4 5
5 3 1 2 4
5
1 3 6 8 9
2 1 3 5 4
2
0 384403739351
384403739351 0

Output:

Case #0: 10
Case #1: 14
Case #2: 384403739351


Comment:

Case #0: The sample is the same as the first sample from subtask four. The combined distance is calculated as: $4 + 2 + 0 + 1 + 3 = 10$.

Case #1: The sample is the same as the first sample from subtask four. The combined distance is calculated as: $2 + 0 + 5 + 7 + 0 = 14$.

Case #2: Binna’s first fan flies to the second place for a distance of 384403739351mm. Note that in this scenario, Binna’s first fan starts from the surface of the moon while the second fan is waiting in Hungary. Unfortunately, the second fan can’t get to the moon from Hungary, so the total distance remains 384403739351mm.

Note that all but at most $10$ test cases in this subtask also satisfy the limits of the previous subtask. Please be patient, generating the test data can take a while.

## Rubik's Knob

Ernő Rubik is a Hungarian inventor best known for his mechanical puzzles such as the Rubik’s Cube, Rubik’s Magic and Rubik’s Snake. Many of those puzzles have attracted a speed solving community that tries to solve the puzzles as fast as possible.

Mouse Stofl is interested in mastering a lesser known puzzle: the Rubik’s Knob.

The Knob is a round handle that can be rotated. It has an indicator that initially is pointing up. Inside the knob there is a spiral torsion spring that has a charge and tries to push the knob back to its initial position.

The knob can point to one of $M$ positions in total, numbered from $0$ to $M-1$. Initially, the indicator points to position $0$.

The spring starts with a charge of $0$. The knob can be rotated freely in both directions:

• right: from position $i$ to $i+1$ (for $0\le i\le M-2$) or from $M-1$ to $0$. This increases the charge by $1$.
• left: from position $i$ to $i-1$ (for $1\le i\le M-1$) or from $0$ to $M-1$. This decreases the charge by $1$.

We say a rotation is a wind-up step if it goes against the direction of the spring. Formally, this is the case if the absolute value of the charge increases (e.g. from $0$ to $1$, or from $-5$ to $-6$).

A puzzle for the Rubik’s Knob consists of a sequence $x_{0},x_{1},{\dots},x_{N-1}$. The goal is to rotate the knob first to position $x_{0}$, then to position $x_{1}$, etc., until position $x_{N-1}$.

### Subtask 1: Computing the number of wind-ups (17 Points)

By solving some puzzles by hand, Mouse Stofl learned that the time-consuming part are the wind-up steps.

A solution to puzzle $x_{0},x_{1},{\dots},x_{N-1}$ can be described as a sequence of $N$ instructions $d_{0},d_{1},{\dots},d_{N-1}$ where $d_i$ is either “L” or “R” and describes that $x_i$ should be reached by applying only left (“L”) or only right (“R”) rotations from the previous position.

Given such a solution, compute the number of wind-up steps.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow of the following format:

• The first line contains two integers $N$ and $M$, the length of the puzzle and the number of positions of the knob.
• The second line contains $N$ integers $x_{0}, x_{1}, {\dots}, x_{N-1}$, where $x_i$ is the $i$-th position the knob needs to be rotated to.
• The third line contains a string of length $N$, where the $i$-th character indicates $d_i$.

#### Output

For the $i$-th testcase, output a line containing “Case #i:” followed by a single integer: the total number of wind-up steps.

#### Limits

• $T=100$.
• $1 \le N \le 1\,000\,000$.
• $1 \le M \le 10^{12}$.
• $0 \le x_i < M$ for all $0\le i.
• $d_i=\mathtt{"L"}$ or $d_i=\mathtt{"R"}$ for all $0\le i.

#### Example

Input:

4
1 10
3
R
1 10
3
L
2 10
3 8
RL
5 1000000000000
0 1 1 9 5
RLRLR

Output:

Case #0: 3
Case #1: 7
Case #2: 5
Case #3: 1999999999991

Comment:

Case #0: All 3 right rotations $0\leadsto 1$, $1\leadsto 2$ and $2\leadsto 3$ are wind-ups.
Case #1: All 7 left rotations $0\leadsto 9$, $9\leadsto 8$, … , $4\leadsto 3$ are wind-ups.
Case #2: The first 3 right rotations are wind-ups, followed by 3 discharges to 0 and two more left rotations which are wind-ups again.
Case #3:
• from 0 to 0 (right): 0 wind-ups.
• from 0 to 1 (left): 999999999999 wind-ups.
• from 1 to 1 (right): 0 wind-ups.
• from 1 to 9 (left): 999999999992 wind-ups.
• from 9 to 5 (right) 0 wind-ups (all steps are discharging the spring)

### Subtask 2: Beginner Puzzles (16 Points)

Being equipped with a way to calculate the cost of solutions, Mouse Stofl now tries to find the optimal way to solve the puzzles.

First, he is starting on beginner puzzles: all positions are given in increasing order.

What is the minimal number of wind-ups required to solve the puzzle?

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow of the following format:

• The first line contains two integers $N$ and $M$, the length of the puzzle and the number of positions of the knob.
• The second line contains $N$ integers $x_{0}, x_{1}, {\dots}, x_{N-1}$, where $x_i$ is the $i$-th position the knob needs to be rotated to.

#### Output

For the $i$-th testcase, output a line containing “Case #i:” followed a single integer: the minimal total number of wind-up steps to solve this puzzle.

#### Limits

• $T=100$.
• $1 \le N \le 1\,000\,000$.
• $1 \le M \le 10^{12}$.
• $0 \le x_i \le M-1$ for all $0\le i.
• $0 \le x_{0}\le x_{1}\le x_{2}\le {\dots} \le x_{N-2} \le x_{N-1}$. This is the special restriction for this subtask.

#### Example

Input:

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

Output:

Case #0: 3
Case #1: 4
Case #2: 1

Comment:

The optimal sequences are “RRR”, “RRRL” and “L”.

The advanced puzzle pack contains puzzles with arbitrary positions, but only up to $100$.

Can you help Stofl compute the minimal number of wind-ups to solve those?

#### Limits

• $T=100$.
• $1 \le N \le 100$. This is the special restriction for this subtask.
• $1 \le M \le 10^{12}$.
• $0 \le x_i \le M-1$ for all $0\le i.

#### Example

Input:

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

Output:

Case #0: 7
Case #1: 6

### Subtask 4: Expert: Large Puzzles (44 Points)

Finally Stofl thinks he’s able to tackle the expert puzzles: Arbitrary positions and up to $5\,000\,000$ of them!

Can you help Stofl one more time?

#### Input and Output

Same as subtasks 2 and 3.

#### Limits

• $T=100$.
• $1 \le N \le 5\,000\,000$.
• $1 \le M \le 10^{12}$.
• $0 \le x_i < M$ for all $0\le i.

Note that all but at most 30 test cases in this subtask also satisfy $N \le 1000$.

## Boulders

While taking a stroll around Kékes, the tallest mountain in Hungary, Mouse Binna has found a nice slope. Unfortunately, there are no boulders on this slope. In order to rectify the situation, Mouse Binna would like to place some boulders in a nice pattern.

The slope is a grid with $N$ rows and $M$ columns. Immediately to the left of each row and on top of each column, there is an arbitrarily big supply of boulders. The slope is slanted such that Mouse Binna can easily push boulders to the right or downwards.

More precisely, Mouse Binna can place boulders by executing a sequence of steps. In each step, Mouse Binna can select either a row or a column:

• If Mouse Binna selects a row, a boulder starts rolling down that row from left to right. The boulder will roll until it reaches the right side of the grid or until it reaches a grid square whose right neighbour is occupied by another boulder.
• If Mouse Binna selects a column, a boulder starts rolling down that column from top to bottom. The boulder will roll until it reaches the bottom of the grid or until it reaches a grid square whose bottom neighbour is occupied by another boulder.

Note that boulders can never change their direction of movement. As soon as a boulder is moving, Mouse Binna will not be able to stop it until it hits the bottom of the slope or it touches another boulder. Furthermore, once a boulder has stopped rolling, Mouse Binna will not be able to move it again.

Given some nice boulder patterns, determine if Mouse Binna is able to place those patterns on the slope. If it is possible, you should also provide a valid way to place the boulders.

### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

• the first line contains $N$ and $M$, the number of rows and the number of columns respectively.
• each of the next $N$ lines contains a string of characters “.” and “#”, describing a nice pattern of boulders. A character “.” indicates an empty grid square, while a character “#” indicates that a boulder is to be placed on the respective grid square.

### Output

For the $i$-th test case (zero-based), print a line “Case #i:” followed by the string “No” if Mouse Binna cannot place the boulders in the given nice pattern or “Yes” if Mouse Binna can do it.

In case it is possible, further print a number of lines equal to the number of boulders in the grid. The $j$-th such line is either the character “R”, followed by a row index between $0$ and $N-1$ or the character “C”, followed by a column index between $0$ and $M-1$. Columns are numbered from left to right and rows are numbered from top to bottom. Pushing a boulder down the specified rows and columns in the order printed in the output must result in the given nice pattern.

Note that there can be multiple ways to obtain the given nice pattern, in such a case you can print any one of them.

### Limits

In all subtasks: - There are $T=100$ test cases. - In all but at most $10$ test cases, we have $1\le N\cdot M\le 100$. - In all but at most $20$ test cases, we have $1\le N\cdot M\le 1\,000$. - In all but at most $10$ test cases, we have $1\le N\cdot M\le 10\,000$. - In all testcases, we have $1\le N\cdot M\le 100\,000$.

In this subtask, we have the additional constraint that $N=1$. I.e., there is only a single row. Note that this additional constraint means that it is always possible for Mouse Binna to place the boulders in any given pattern. Therefore, you have to print “Yes” for all test cases.

From $N=1$, it follows that $1\le M\le 1'00\,000$.

#### Example

Input:

3
1 1
.
1 1
#
1 4
#.##

Output:

Case #0: Yes
Case #1: Yes
C 0
Case #2: Yes
C 3
R 0
C 0

Comment:

The first line with “3” indicates that there are three test cases.

Case #0: The grid has $1$ row and $1$ column and Mouse Binna does not have to place any boulders.

Case #1: The grid has $1$ row and $1$ column, and Mouse Binna has to place a boulder in the single grid square. She can do so by rolling a boulder down column $0$. Note that the only other correct output is R 0.
Case #2: The grid has $1$ row and $4$ columns and Mouse Binna has to place $3$ boulders. Note that there are many other correct outputs, for example (R 0, R 0, C 0) or (R 0, C 2, C 0).

### Interactive visualization

In this subtask, we have the additional constraint that $N=2$, i.e., there are exactly two rows. Note that for $N=2$, there are patterns that Mouse Binna cannot build. For such patterns, you should print “No”.

#### Example

Input:

3
2 2
.#
##
2 2
#.
..
2 4
#.##
##..

Output:

Case #0: Yes
C 1
C 1
R 1
Case #1: No
Case #2: Yes
R 0
R 0
C 0
C 0
C 1

Comment:

The first line with “3” indicates that there are three test cases.

Case #0: The grid has $2$ rows and $2$ column and Mouse Binna has to place three boulders. The solution first rolls a boulder down column $1$. The boulder stops at the bottom of the grid. It then rolls another boulder down column $1$. The boulder is stopped immediately by the other boulder and we fill up column $1$ entirely. Finally, Mouse Binna lets a boulder roll down row $1$, which is stopped immediately, also by the first boulder.

Case #1: The grid has $2$ rows and $2$ columns and Mouse Binna has to place one boulder. No matter how Mouse Binna lets a single boulder roll down a row or column, there is no way to place a boulder in the top left square (we could individually fill the three other squares, but not the top left square).
Case #2: The grid has $2$ rows and $4$ columns and Mouse Binna has to place $5$ boulders. She first handles the two boulders at the top right by letting two boulders roll down row $0$. Then she handles the leftmost boulders, by letting two boulders roll down column $0$. (Note that the order of operations is important, as the fourth boulder closes off row $0$.) Finally, she lets a boulder roll down column $1$, which handles the final boulder in the middle.

### Interactive visualization

Let $K$ be the number of boulders that we have to place. In this subtask, we have no further constraints on $N$ and $M$, but it is guaranteed that $0\le K\le 20$.

#### Example

Input:

3
3 3
.#.
###
...
3 4
##..
.##.
..##
4 5
##...
.####
..#.#
....#

Output:

Case #0: Yes
R 1
R 1
C 1
R 1
Case #1: Yes
R 2
R 2
C 2
R 1
C 1
R 0
Case #2: No

### Interactive visualization

In this subtask, there are no further constraints. I.e., we have $1\le N\cdot M\le 100\,000$ and $0\le K\le N\cdot M$, where $K$ is the number of boulders we have to place.

## Cardgame

You are playing a card game against Mouse Stofl. Initially, both of you have $N$ cards. Each card has a number between $0$ and $2 \cdot N - 1$ printed on it, and there is exactly one card of each number. The game has $N$ turns. In each turn, both players play one of their remaining cards, and the one who played the higher value wins the turn. You already know the order in which Mouse Stofl is going to play his cards.

In this subtask, you want to figure out whether you can win all turns, and if yes, in what order you can play your cards to achieve this. If you can’t win all turns, you don’t care how many turns you win.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to be play them. A third line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order.

#### Output

For the $i$-th test case, output a line “Case #i: M”, where M is “No” if you can’t win all turns, otherwise “Yes” followed by $N$ integers separated by spaces $c_{0}\ldots c_{N-1}$, the values of your cards in the order you’re going to play them.

#### Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 1\,000$.

#### Example

Input:

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

Output:

Case #0: Yes 5 1 4
Case #1: Yes 1
Case #2: No
Case #3: No

Comment:

Case #0: Stofl is going to play $2$ in the first turn, $0$ in the second turn, and $3$ in the third turn. You can win all turns by first playing $5$, then $1$ and then $4$, since $5>2$, $1>0$, and $4>3$. Note that you could also win by swapping the $5$ and the $4$ from this order. Any winning order is a valid output.
Case #3: There’s no way to play your $0$ and not lose that turn.

In this subtask, you want to lose as many turns as possible. Can you figure out the lowest number of turns you win if you play as badly as possible? Note that you don’t need to print the order you play the cards anymore.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

The first line of the test case contains a single integer: $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order.

#### Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the smallest possible number of turns that you can win.

#### Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 500\,000$.

Note that all but at most $10$ test cases in this subtask also satisfy $1 \le N \le 10\,000$.

#### Example

Input:

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

Output:

Case #0: 2
Case #1: 1
Case #2: 0

In this subtask, each of your own cards now also has a score attached. A score is a positive integer, and your total score at the end of the game is the sum of the scores of the cards that you played in the turns that you win. Note that Mouse Stofl’s cards don’t have scores in this subtask. Your goal is to maximize your total score.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order. A fourth line follows with $N$ integers $s_{0},\ldots,s_{N-1}$, the scores of your cards. (The $i$-th card has value $b_i$ and score $s_i$).

#### Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the largest possible total score that you can achieve.

#### Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 1\,000$. All scores are $1 \le s_i \le 100\,000$.

#### Example

Input:

2
3
2 0 3
1 5 4
3 2 1
3
1 3 4
0 2 5
11 3 7

Output:

Case #0: 6
Case #1: 10

Comment:

Case #0: As in the example in subtask 1 with the same card values, you can win all turns. This gives you a total score of $1+2+3=6$.
Case #1: There’s no way to play your $0$ and not lose that turn, so you can’t add those $11$ points in your total score. But you can win the other two turns, giving you a total score of $3+7=10$.

In this subtask, Mouse Stofl’s cards have scores, and your cards don’t. Your total score at the end of the game is the sum of the scores of the cards that Stofl played in the turns that you win. Your goal is still to maximize your total score.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $r_{0},\ldots,r_{N-1}$, the scores of Stofl’s cards. (The $i$-th card has value $a_i$ and score $r_i$). A fourth line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order.

#### Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the largest possible total score that you can achieve.

#### Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 500\,000$. All scores are $1 \le r_i \le 100\,000$.

Note that all but at most $10$ test cases in this subtask also satisfy $1 \le N \le 10\,000$.

#### Example

Input:

2
3
2 1 4
4 1 1
0 5 3
3
2 3 5
11 3 7
0 1 4

Output:

Case #0: 5
Case #1: 11

In this final subtask, all cards have scores. Your total score at the end of the game is the sum of the scores of the cards played by you and by Stofl in the turns that you win. Your goal is still to maximize your total score.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $r_{0},\ldots,r_{N-1}$, the scores of Stofl’s cards. (The $i$-th of Stofl’s cards has value $a_i$ and score $r_i$). A fourth line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order. A fifth line follows with $N$ integers $s_{0},\ldots,s_{N-1}$, the scores of your cards. (The $i$-th of your cards has value $b_i$ and score $s_i$).

#### Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the largest possible total score that you can achieve.

#### Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 500\,000$. All scores are $1 \le s_i, r_i \le 100\,000$.

Note that all but at most $10$ test cases in this subtask also satisfy $1 \le N \le 10\,000$.

#### Example

Input:

2
3
2 1 4
4 1 1
0 5 3
7 2 3
3
0 3 5
11 3 7
1 2 4
5 2 1

Output:

Case #0: 10
Case #1: 20

## Palatinal Crypt

Below Buda castle in Budapest lies the Palatinal Crypt, a burial place of several Archdukes and Archduchesses from the Habsburg dynasty.

The crypt consists of several rooms that are arranged in an $N\times M$ grid. When the crypt was constructed initially, the rooms were sealed off.

To celebrate the crypt’s 255th birthday, the Hungarian state wants to open up the crypt to the public. For that, some walls should be removed such that all rooms inside the crypt become connected. To preserve the crypt, this should be done by removing strictly less walls than there are rooms.

Furthermore, out of respect to the buried, no room should have all 4 walls removed.

The government has hired Stofl to come up with some plans to satisfy all those constraints. However Stofl can’t find a solution either so he needs your help.

### Subtask 1: Klotild Wing (15 points)

The government wants to try out this plan in one of the newer wings of the crypt, the Klotild wing.

Can you help Stofl find a valid solution?

#### Input

The first line contains a single integer $T$, the number of test cases.

$T$ lines follow, each with two integers $N$ and $M$: There are $N \times M$ rooms.

#### Output

For the $i$-th test case, print a line “Case #i:

This should be followed by an ASCII representation of the crypt with some walls removed. A description of such a representation follows, but it might be easier to look at the examples below.

There should be $2\cdot N - 1$ lines containing $2\cdot M - 1$ characters each.
Every second character of every second line, starting with the first character of the first line, should be the letter $o$ denoting a room of the crypt.
For every pair of rooms that you want to connect (by removing the wall between them), do the following:
• If the rooms are adjacent horizontally, place a minus sign (“-“) between the corresponding letters $o$.
• If the rooms are adjacent vertically, place a pipe character (“|”) between the corresponding letters $o$.
The remainder of the ASCII representation should consist of periods (“.”).
If there are multiple valid ways to satisfy all constraints, you may output any of them.

#### Limits

• $T=100$.
• $2 \le N \cdot M \le 1000$.

#### Examples

Input:

2
3 3
4 3

Output:

Case #0:
o.o.o
|.|.|
o-o-o
|...|
o-o.o
Case #1:
o-o-o
..|..
o-o.o
|...|
o-o-o
..|.|
o-o.o

The following is an example of invalid output

Input:

3
3 3
3 3
3 3

Output:

Case #0:
o-o-o
..|..
o-o-o
..|..
o-o-o
Case #1:
o-o-o
|...|
o.o-o
|...|
o-o-o
Case #2:
o-o.o
|...|
o.o.o
..|.|
o-o-o

Comment:

All of those outputs are incorrect. The following paragraphs explain why:

In Case #0, the room in the center of the grid has all four walls removed.

In Case #1, more walls are removed than allowed.

In Case #2, the network is not connected. For example, you can’t get from the top left room to the top right room.

#### Feedback

The following example should help you understand some of the automatic feedback you might receive. Click on the box below to see it.

Expand

Input:

3
2 2
2 2
3 4

Output:

Case #0:
o-o
..|
o!o
Case #1:
o-o

..|
o!o
Case #2:
o-o-o-o
....|..
o-o-o-o
....|..
o-o-o-o

Comment:

Feedback for Case #0: “Presentation Error in testcase Case #0': Invalid character on line 2: Expected -'/.' at the position marked with underscores: o_!_o”. Note that line zero is the first line containing output (not including Case #i)

Feedback for Case #1: “Presentation Error in testcase Case #1': Invalid character on line 2: Expected -'/.' at the position marked with underscores: o_!_o”. Note that blank lines are ignored and not counted, which explains why it says line 2 and not line 3.

Feedback for Case #2: “Wrong Answer in testcase Case #3': You removed 4 walls in the room at position (1, 2), you should have removed one of the following numbers of walls: [0, 1, 2, 3]”. If the grader can understand your ASCII representation but it isn’t a valid answer, it might tell you where the problem lies. The top left room has coordinates $(0, 0)$, the next one to the right has coordinates $(0, 1)$ etc.

After further investigation, the government also does not want to have rooms that have exactly 2 walls removed. This demotes the room into a passage which does not pay the proper respect for a burial site.

Stofl does not believe this is possible. Can you show him some examples where this is indeed possible?

#### Input

The first line of input is $T$, the number of crypt layouts you should output. This number is always 20.

This will be followed by $T$ lines containing the indices of the testcases, i.e. the first line contains the number $0$, the second line the number $1$ etc.

Note that your program doesn’t actually have to read any input since the input file will always be the same.

#### Output

Output twenty crypt layouts. For the $i$-th crypt, output Case #i: N M with some integers $N$ and $M$ of your choice: The height and width of the crypt. After that, output the crypt itself like in Subtask 1. It should have $N \times M$ rooms.

No two crypts may have the same width and the same height. It is, however, allowed to output any number of crypts with the same width or the same height.

#### Limits

• $T = 20$.
• $2 \le N \cdot M \le 1000$. Note that this isn’t a constraint on the input file, but on your output file.

#### Example

Input:

2
0
1

Output:

Case #0: 1 2
o-o
Case #1: 2 3
o-o-o
..|..
o-o-o

The following is an example of invalid output

Input:

3
0
1
2

Output:

Case #0: 3 3
o.o.o
|.|.|
o-o-o
|...|
o-o.o
Case #1: 1 2
o-o
Case #2: 1 2
o-o

Comment:

In Case #0, the bottom left room has exactly two walls removed. This is no longer allowed in this subtask, but would have been allowed in Subtask 1.

Case #1 and Case #2 would be OK by themselves, but they use the same width and height.

### Subtask 3: Esztergom Wing (25 points)

Since you’ve convinced Stofl that there are some crypt sizes where the constraints from Subtask 2 can be satisfied, he now wants you to do the same for some other sizes.

#### Output

For the $i$-th crypt, print a line “Case #i: Possible” or “Case #i: Impossible”, depending on whether it is possible to remove some walls from a $N \times M$ crypt in order to satisfy all constraints

If it is possible, output the ASCII representation as in Subtasks 1 and 2.

#### Example

Input:

3
1 2
2 2
2 3

Output:

Case #0: Possible
o-o
Case #1: Impossible
Case #2: Possible
o-o-o
..|..
o-o-o

#### Feedback

Note that the automatic grader will not tell you if you wrongly answer “Possible”. It will only point out why your output is not a solution. This can either mean there is a solution, but you did something wrong, or it can mean there is no solution.

### Subtask 4 (Theoretical): World Crypt Association (50 points)

Your designs got so much praise that other crypts around the world want to implement a similar scheme. Because Mouse Stofl does not have the time to respond to every request, he wants you to create a well-documented instruction manual so that everybody can figure out which walls to tear down by themselves.

This is a theoretical subtask. Describe an algorithm that can solve subtask 3 and prove its correctness.

Hand in a document (preferably PDF) that describes

• how your algorithm works. In particular, explain how your algorithm determines whether or not the task is possible and how it constructs a solution if it is possible.
• why your algorithm is correct. In particular, you should show that the solutions given by your algorithm satisfy all constraints, and that your algorithm only claims the task to be impossible when it actually is.
• how much time and memory it uses.

#### Limits

• $N$, $M$ are variables. You can assume that basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform and that storing one integer uses a single unit of memory.

## Thermal Springs

Hungary is home to a huge variety of thermal water springs, each with different water temperatures, mineral contents or smell. Some springs even come with some nice panorama. Mouse Binna plans to hike around in Hungary and bathe at many different springs. In order for her trip to end on a high note, she wants every spring to be strictly better than the previous: each thermal spring should have a higher water temperature, a higher mineral content, less sulfur smell and more scenery than the previous spring.

Binna has already asked the local wood mice about the various upsides and downsides of each spring. Can you help her plan her trip?

### Subtask 1: All the Springs (20 Points)

For her first trip, Binna wants to bathe at all the springs near Szeged, Hungary. Can you help her find a route to do so, or tell her this is not possible?

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow of the following format:

• The first line contains one integer $N$ – the number of springs.
• The second line contains $N$ integers $t_i$ – the temperature of the $i$-th spring ($0 \leq i < N$).
• The third line contains $N$ integers $m_i$ – the amount of minerals in the water of the $i$-th spring ($0 \leq i < N$).
• The fourth line contains $N$ integers $s_i$ – the intensity of the sulfur smell at the $i$-th spring ($0 \leq i < N$).
• The fifth line contains $N$ integers $p_i$ – the beauty of the panorama at the $i$-th spring ($0 \leq i < N$).

#### Output

For the $t$-th test case print a line “Case #t:” followed by “YES” or “NO”, depending on whether Binna can bathe at all the springs. If the answer was “YES”, then print a single line with $N$ integers – the order in which Binna can bathe at the springs. (Springs are numbered from $0$ to $N-1$.)

#### Limits

• $T=100$.
• $1 \le N \le 300$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

#### Example

Input:

4
2
2 1
2 1
1 2
2 1
2
1 2
1 2
1 2
1 2
3
9 4 7
8 2 3
12 44 13
5 1 4
3
1 1 1
2 2 2
3 3 3
4 4 4

Output:

Case #0: YES
1 0
Case #1: NO
Case #2: YES
1 2 0
Case #3: NO

Comment:

Case #1: If Binna bathes at spring $0$ first, the second bath will have too much sulfur smell. If she starts with spring $1$, then the second bath (at spring $0$) will be too cold.

### Subtask 2: As Many Springs as Possible (20 Points)

After realizing that she sometimes couldn’t bathe at all the springs, Binna was about to give up on her hike, but then she had an idea: what if she instead tried to bathe at as many springs as possible? Can you help her plan her trip?

#### Output

For the $t$-th test case print a line “Case #t:” followed by an integer $S$ – the maximum number of springs Binna can bathe at while ensuring that every spring is better then the previous. On the next line print $S$ integers – the springs Binna bathes at, in order. If there are multiple optimal solutions, you may print any one of them.

#### Limits

• $T=100$.
• $1 \le N \le 300$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

#### Example

Input:

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

Output:

Case #0: 2
1 0
Case #1: 1
0
Case #2: 1
1
Case #3: 2
1 2

Comment:

Note: In cases #1, #2 and #3, there are multiple optional solutions. You may print any of them.

### Subtask 3: Two Mice (20 Points)

Bathing at this many spring was a lot of fun, but Binna still has nagging thoughts about not having bathed at all the springs. She’s planning another trip to Hungary, but this time, she invited mouse Stofl to come with her. Stofl also likes to bathe and he too wants every spring to be better than the previous one.

The plan is to hike on different routes such that every spring will be bathed at by exactly one mouse. Can you help them plan their trip?

#### Output

For the $t$-th test case print a line “Case #t:” followed by “YES” or “NO”, depending on whether Binna and Stofl can find two routes such that every spring will be bathed at by exactly one mouse. If the answer was “YES, then print two more lines. The first line should contain the springs Binna bathes at, it order, and the second line should contain the springs Stofl bathes at, in order. (Springs are numbered from $0$ to $N-1$.)

#### Limits

• $T=100$.
• $1 \le N \le 1000$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

#### Example

Input:

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

Output:

Case #0: YES
1
0
Case #1: YES
1 0

Case #2: NO
Case #3: YES
0 2
1

Comment:

In Case #1, Stofl doesn’t bathe at all.

### Subtask 4: Big Plans (40 Points)

Together, Binna and Stofl bathed at every thermal spring near Szeged. Now, they have bigger plans: they want to bathe at every single thermal spring in Hungary. Those are a lot of springs, so you better help them find good routes!

#### Limits

• $T=100$.
• $1 \le N \le 100\,000$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

Note that all but at most $10$ test cases in this subtask also satisfy the limits of the previous subtask.

The famous Dada artist Mouse Stofl is making a new artwork right inside the famous “Budavári Labirintus” labyrinth in Budapest. The labyrinth has $N$ rooms connected with $N-1$ two-way passages in such a way that it is possible to get from any room to any other room. In other words, the rooms and passages form a tree. The rooms are numbered from $0$ to $N-1$, and the $j$-th passage connects rooms $u_j$ and $v_j$.

The artwork consists of $N$ paintings, one in each room. Mouse Stofl has already placed a big white canvas in each of the rooms.

Mouse Stofl has also bought $N$ buckets of paint of pairwise different colors numbered from $0$ to $N-1$ and placed them strategically: the bucket of paint with color $i$ is in the room $i$.

For each of the paintings, Mouse Stofl knows which colors need to be applied to it, but he does not care in particular in which order this will happen. More specifically, the painting in the $i$-th room needs $k_i$ different colors applied: $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$, in any order. It is possible that some paintings need to be left untouched ($k_i=0$), or that some colors are not needed on any painting.

Mouse Stofl can move between the rooms using the passages either empty-handed or carrying at most one bucket with paint, since those are quite heavy. In order to apply a color to the painting in a room, Stofl needs to bring the corresponding bucket there. Since the buckets are going to be part of the artwork as well, in the end each bucket needs to be brought back to the room where it was in the beginning: the bucket of paint with color $i$ needs to end up in room $i$.

Mouse Stofl does not like to carry heavy buckets around. Can you help him find the minimum number of times he needs to carry a bucket of paint along a passage in order to complete the artwork?

### Subtask 1: A single color (10 Points)

In this subtask all paintings either require no paint at all, or require only color $0$.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow of the following format:

• The first line contains one integer $N$, the number of rooms and colors.
• The $j$-th of the next $N-1$ lines describes the $j$-th passage and contains two integers: the numbers $u_j$ and $v_j$ of the rooms this passage connects.
• The $i$-th of the next $N$ lines describes the painting in the $i$-th room: the number $k_i$ of colors it needs, followed by $k_i$ distinct colors $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$.

#### Output

For the $t$-th test case, output a line containing “Case #t:”, followed by a space and an integer equal to the minimum number of times Stofl needs to carry a bucket of paint along a passage in order to apply all required colors to each painting and then bring each bucket to its original location.

#### Limits

• $T=100$.
• $2 \le N \le 1000$.
• $0 \le k_i \le 1$ for all $0\le i.
• $a_{i1} = 0$ for all $0\le i such that $k_i = 1$.

#### Example

Input:

1
3
0 1
1 2
1 0
1 0
0

Output:

Case #0: 2

Comment:

Mouse Stofl needs to carry the bucket from room $0$ to room $1$ and back.

### Subtask 2: Many colors (15 Points)

In this subtask the paintings may require an arbitrary number of colors.

#### Limits

• $T=100$.
• $2 \le N \le 1000$.
• $0 \le k_i \le N$ for all $0\le i.
• The sum $\sum k_i \le 1000$.

#### Example

Input:

1
3
0 1
0 2
0
2 2 1
2 2 0

Output:

Case #0: 6

Comment:

Mouse Stofl needs to carry the bucket with color $0$ from room $0$ to room $2$ and back, and the bucket with color $2$ from room $2$ through room $0$ to room $1$ and back.

### Subtask 3: Apprentices (20 Points)

In this subtask, $M$ apprentices will be helping Mouse Stofl complete the artwork. Since apprentices are not yet artists, Stofl can only give them a limited type of tasks.

More specifically, for each color $i$, Stofl will meet the apprentices in room $i$ where the bucket with this color is initially placed, and pour some paint of this color into smaller buckets. He will then give some (possibly none or all) apprentices one smaller bucket each, and send them through different passages going from this room. Each apprentice will visit all rooms that they can reach before going back to room $i$, and apply the color $i$ to the paintings in those rooms if necessary. But as soon as an apprentice gets back to room $i$, they pour the remaining contents of their small bucket back into the big bucket with color $i$, and they do not want to work with this color anymore.

This process is repeated for each color. Note that even though Mouse Stofl can carry the big buckets around, he will not move the bucket with color $i$ before the apprentices are done with color $i$, to avoid confusion. Therefore the apprentices carrying color $i$ are always sent out from room $i$.

Note that if the number of passages connected to room $i$ is greater than $M$, some rooms will not be visited by apprentices carrying color $i$, and therefore Stofl might still have to carry the big bucket there himself to apply this color to the painting. In that case he still needs to bring the bucket back to room $i$ at the end.

For each color $i$, Mouse Stofl is free to choose up to $M$ passages going from room $i$ that he will send apprentices through in any way. His goal is still to minimize the number of times he needs to carry a bucket through a passage himself.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow of the following format:

• The first line contains two integers $N$ and $M$, the number of rooms and colors, and the number of apprentices.
• The $j$-th of the next $N-1$ lines describes the $j$-th passage and contains two integers: the numbers $u_j$ and $v_j$ of the rooms this passage connects
• The $i$-th of the next $N$ lines describes the painting in the $i$-th room: the number $k_i$ of colors it needs, followed by $k_i$ distinct colors $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$.

#### Output

For the $t$-th test case, output a line containing “Case #t:”, followed by a space and an integer equal to the minimum number of times Stofl needs to carry a bucket of paint himself along a passage in order to apply all required colors to each painting and then bring each bucket to its original location.

#### Limits

• $T=100$.
• $2 \le N \le 1000$.
• $0 \le M \le 1000$.
• $0 \le k_i \le N$ for all $0\le i.
• The sum $\sum k_i \le 1000$.

#### Example

Input:

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

Output:

Case #0: 4

Comment:

For all colors except color $2$, the apprentices can do all work. For color $2$, Mouse Stofl can send one apprentice toward room $1$, and they will also visit rooms $0$ and $3$ before coming back to room $2$. The second apprentice can go toward room $4$, and they will also visit room $6$. Mouse Stofl will still need to carry the paint himself to rooms $5$ and $7$.

### Subtask 4: A Huge Artwork (15 Points)

#### Limits

• $T=100$.
• $2 \le N \le 3 \cdot 10^{5}$.
• $0 \le M \le 3 \cdot 10^{5}$.
• $0 \le k_i \le N$ for all $0\le i.
• The sum $\sum k_i \le 3 \cdot 10^{5}$.

Note that all but at most $10$ test cases in this subtask also satisfy the limits of the previous subtask.

### Subtask 5: Theoretical (40 Points)

You need to analyze how big the answer in this problem can be depending on the values of $N$ and $M$.

More specifically, we define $f(N,M)$ as the maximum possible number of times Mouse Stofl needs to carry a bucket along a passage for any possible input with $N$ rooms and $M$ apprentices. You need to provide an upper bound and a lower bound for $f(N,M)$, expressed as formulas with two variables $N$ and $M$, and prove those formulas.

You can consider that $N \ge 2$ and $M \ge 0$, but note that unlike all previous subtasks, there is no upper limit on $N$, $M$ or $\sum k_i$. Your formulas have to cover all possible options for paintings in $N$ rooms. The proof for the lower bound will typically involve demonstrating an example input achieving this lower bound for each given $N$ and $M$, while the proof for the upper bound needs to consider all possible inputs.

For both bounds, we do not care about a constant factor: for example the formulas $f(N,M)\le 2N^{10}$ and $f(N,M)\le 3N^{10}$, or any two formulas such that their fraction is bounded by some constant from above and by some positive constant from below, will get the same number of points. In other words you can use the big-O notation for the upper bound and the big-Omega notation for the lower bound. You can read more about those notations in https://soi.ch/wiki/algorithms-intro/.

For example, $f(N,M)\le 2N^{10}(M+1)^{7}$ and $f(N,M)\ge 1$ would be a valid answer to this subtask (which you would still need to prove, even if it is not very hard), but it will not give you any points as these are not very tight bounds. $f(N,M)=\mathcal{O}(N^{10}(M+1)^{7})$ and $f(N,M)=\mathcal\Omega(1)$ would be another valid way to write this using the big-O and big-Omega notations.

You are free to write down your formulas in any way you like, for example you can also write things like $f(N,M)\le 2N^{10}M^{7}$ if $M>0$, or $2N^{10}$ if $M=0$.

Hand in a document (preferably PDF) that contains

• the upper bound on the number of times Mouse Stofl needs to carry a bucket, as a formula with two variables $N$ and $M$.
• a proof why the answer will never exceed that value.
• the lower bound on the number of times Stofl needs to carry a bucket as a formula with two variables $N$ and $M$.
• a proof why the answer can reach that value (would typically include an example for each pair of $N$ and $M$ and an explanation why Mouse Stofl needs to carry a bucket at least this many times in this example).

If your proofs are correct, we will give you the points based on how close are the values computed using your formulas to the real value of $f(N,M)$. The smaller the upper bound is (notwithstanding a constant factor), and the bigger the lower bound is (again notwithstanding a constant factor), the more points you will get.

10 points will be allocated to the lower bound, and 30 points will be allocated to the upper bound.

## Trees

Mouseland got a new subway system thanks to you! One of the subway lines leads out of the city into a newly created nature reserve. Mouse Binna and mouse Stofl were tasked with reforestation of the area to make it more pleasurable for the mice to spend time there.

Unfortunately, Binna and Stofl can’t agree on which type of forest they should plant. While Binna is convinced that the population of Mouseland would prefer oak trees, Stofl thinks they should plant pine trees. As they did not reach a conclusion after hours of discussion, they decided to turn it into a game. Help one of them to win and establish either oak trees or pine trees as the dominant tree in the nature reserve.

### Game

The nature reserve is split into multiple points of interest with bidirectional trails between them. Each node $i$ has some fertility $f_i$ and some attractiveness $a_i$. Initially, there are no trees in the nature reserve.

At the start of the game, the two players are assigned a starting node each. They both plant their type of tree on this node. Once there is some type of tree on a node, the player who is planting this type of tree owns the node. A node will never change the type of tree growing on it once some type of tree grew on it.

Afterwards, the game proceeds in rounds. In each round, a player gets some number of saplings equivalent to the sum of fertility of all the nodes the player owns. Each player can then distribute some or all of its saplings onto empty nodes. Unused saplings can be saved up for future rounds. After the saplings were placed, each node is evaluated in parallel as follows:

1. The saplings need to be transported from an already owned node but some of them are lost on the way. Specifically, for a certain tree type, let $d$ be the shortest number of trails which need to be traversed to reach a node where this type already grows. Then, the number of planted saplings is divided by $d^{2}$ and rounded down to the nearest integer. This is then the number of saplings actually arriving at this node.
2. If there are saplings from both types of trees present on the node, the type with more saplings prevails and displaces the saplings of the other type. The displaced saplings are removed from the node. If there is an equal number of saplings from both types on the node, all saplings are removed.
3. If there still some saplings on the node, this type of tree will now grow on this node and the player planting this type will own the node.

The game ends once all nodes have trees on them or after 2’000 rounds. The player with the higher sum of attractiveness of their nodes wins.

### Protocol

The communication between program and server is handled using Stdin / Stdout.

One line with $n$ $m$ $e_{1}$ $e_{2}$, the number of nodes $n$, the number of paths $m$, your starting node $e_{1}$, and the starting node $e_{2}$ of your opponent. On the next line there are $n$ space separated integers $f_i$, the fertility of the $i$-th node. On the next line there are $n$ space separated integers $a_i$, the attractiveness of the $i$-th node. $m$ lines follow with two space separated integers $b$ $c$ each, denoting a path between node $b$ and $c$.

Now the game starts. For each round you first get two space separated integers $u_{1}$ $u_{2}$, the number of saplings $u_{1}$ you have available and the number of saplings $u_{2}$ your opponent has available in this round. Then you have to print one line with $n$ space separated integers $s_i$, the number of saplings you want to plant on node $i$. You will then receive $n$ lines with two integers $t_i$ $o_i$, the number of saplings $t_i$ your opponent placed on the $i$-th node in this round, and the owner $o_i$ of the $i$-th node: $-1$ for your opponent, $0$ for no owner, and $1$ if you are the owner.

After the last round you will receive a final line with $-1$ $-1$ (i.e. $-1$ for both $u_{1}$ and $u_{2}$). Your program should exit.

### Limits

These limits apply for all maps and are therefore very general. Take a look at the maps section to get a better idea of the kind of maps you can expect.

• $3 \le n \le 1000$
• $n-1 \le m \le n*(n-1)$
• $0 \le e1, e2, b, c < n$
• $e_{1}\neq e_{2}$
• $0 \le f_i \le 20$
• $0 \le a_i \le 1000$
• $0 \le u_{1}, u_{2}, t_i \le 10^{9}$
• $-1 \le o_i \le 1$

We aim for $n \le 500$, but due to some randomness in the map generation it is possible that there are a few more nodes.

It is guaranteed that there exists some sequence of trails to get from every node to every other node.

### Example

Open the example in the visualization

The map before the start of the game. Attractivity is displayed in yellow, fertility in green.

The moves of the first round. Both have planted the same number on the node in the middle right, so nobody gets it.

The map after the first round. Red has spent all saplings, blue still has one left.

The moves of the second round. Even tough red only put three saplings on the node in the middle right, and blue put 4, red gets the node, because for blue 3 are lost on the way.

The map at the end of the game. Red has the higher sum of attractiveness, and with that wins the game.

Here is the communication from the point of view of the red player. The input of the program is marked with “<”, and the output with “>”.

< 6 6 0 5
< 5 3 10 0 3 5
< 0 0 372 584 310 0
< 0 1
< 1 2
< 1 3
< 2 3
< 3 4
< 4 5
< 5 5
> 0 1 0 4 0 0
< 0 1
< 0 1
< 0 0
< 4 0
< 0 0
< 0 -1
< 8 6
> 0 0 3 3 0 0
< 0 1
< 0 1
< 0 1
< 4 1
< 1 -1
< 0 -1
< -1 -1
`

### Creativity platform

The creativity task will take place on the creativity platform. There you can create new bots, upload the source code for your bots, play games against other participants (or your own bots), view the results of tournaments, and see a ranking of all bots. If you have any questions about the platform do not hesitate to ask us.

A few notes about the platform:

• The idea is that you create a new bot for a completely new strategy. For small updates to your current strategy just upload a new version for the appropriate bot. There is no hard limit on the number of bots you can create, but we ask you to keep it to a reasonable number.
• You can not choose the name of your bots. This is to provide some anonymity and we hope that this encourages everyone to play games against each other more freely. If you are unhappy with the name of your bot you can randomize it again as long as you did not yet upload any code.
• By default, no one can play games against your bots. We think it is very helpful to already play some games before the tournaments and compare your bot with other bots. In order for there to be bots to compare against, some people need to allow others to play games against their bots. So please set your bots to accept games if you feel comfortable doing so. There is also the option where you have to confirm every game so you have better control over which bots you want to play against.
• If you have bots which require confirmation to play against, don’t forget to check from time to time whether you got any requests.
• Don’t forget to register your bots for the tournaments. If you abandon a bot please deregister it from the tournaments.
• The time limit for a bot is 2 minutes per game.
• If you submit a Java bot, your main class needs to be called $Bot$ and it may not be in any package.

### Subtask 1: Play by the rules (10 Points)

Write a bot that follows the rules and can beat the example bot. Just play and win any game against the random bot on the creativity platform. We have to manually update the scores, so it might take a few days until they show up on the round 1 ranking.

### Subtask 2: Play smart (15 Points)

Write a bot which is able to beat our smart bot. Play and win games on at least 5 different map layouts against the smart bot on the creativity platform. You may choose the other map parameters freely. We have to manually update the scores, so it might take a few days until they show up on the round 1 ranking.

### Subtask 3: Creativity tournament (75 Points)

You play against other participants of the SOI in multiple tournaments. Based on the rankings of these you will get points.

Each tournament is worth a certain amount of points and you will get a fraction of these based on your rank: 100% for rank 1, then 10% less for every following rank until rank 6 (50%), then 5% less for every following rank. We only include the best bot for each participant in the ranking. However, the creativity platform does not exclude multiple bots from the same person, so the points you receive might not match the displayed ranking.

In the end, your score for this subtask will be the maximal score you achieved during any tournament. There will be the following tournaments:

• 25.9.2022, 20:00: Early bird tournament, worth 20 points.
• 9.10.2022, 20:00: Getting started tournament, worth 30 points.
• 23.10.2022, 20:00: Midway tournament, worth 40 points.
• 6.11.2022, 20:00: Getting serious tournament, worth 50 points.
• 20.11.2022, 20:00: Final spurt tournament, worth 60 points.
• 1.12.2022, 10:00: Creativity tournament, worth 75 points. Ranking will be hidden.

We will update the scores on the round 1 ranking after every tournament, but as we do this manually it might take a few days.

On the creativity platform you can view additional details about the tournaments. A tournament consists of multiple map configurations. For each configuration you will play against every other bot. Each configuration has a score weight $s_i$ associated with it. For a win on a map you will get $3 \cdot s_i$, for a draw $1 \cdot s_i$ and for a loss $0$ score. The ranking will be according to the sum of these scores across all played games.

### Maps

There are a few different map configurations on which we will run the bots. A configuration consists of the following parameters:

• Map layout: the algorithm to generate the graph.
• random: Completely random graph
• line: A line graph
• star: A generalization of the line map, with a single center and multiple lines originating from there
• circle: A single circle
• tree: A random tree (i.e. a connected graph with no circles)
• wheel: A random graph with high girth (i.e. large cycles)
• cluster: A treemost graph where each node was replaced by a random graph and each edge by a line
• Start nodes: whether the two bots start very close or very far from each other.
• Map fertility: how to select nodes which have fertility.
• none: No additional fertility on any nodes
• low/high: Different probabilities for a node having additional fertility
• all: Every node has additional fertility
• cluster: Only for cluster map layout, each node in the treemost graph has a 50% probability of having additional fertility in the generated random graph
• Map attractiveness: how to select nodes which have attractiveness.
• all1: Every node has 1 attractiveness
• low/medium/high: Different probabilities for a node having positive attractiveness
• all: Every node has a random, positive attractiveness
• cluster: Only for cluster map layout, each node in the treemost graph has a 50% probability of having positive attractiveness in the generated random graph

### Hints

It is important for interactive tasks to flush the output buffer after every turn to make sure the server can see your output.

Use the following commands:

• C/C++: fflush(stdout);
• C++: cout << flush; (not necessary if you read afterwards)
• There are similar commands in other languages.

Furthermore it is important that you don’t wait for more characters than the server gives you as an input. For example spaces or line endings in C format strings are a common source for errors. For example if you read the last variable in the input with “scanf("%d ", &x);” it will wait for the next character that is not a space or a line break. You will receive such a character only after you printed your next turn. To solve this use “scanf("%d", &x);” instead (no non-printable characters after the “%d”).

If you want to run your bots locally you can download the judge and the visualization here. This also includes a sample C++ bot. The judge and the visualization both include a short explanation on how to run them. They are the exact same version which is used on the creativity platform, except for some additional sandboxing for the bots.