# First Round SOI 2021/2022

## 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.

This contest is over.
Junior onlypeaks‒/100‒/10‒/10‒/30‒/20‒/30
Junior onlyropeways‒/100‒/10‒/20‒/30‒/40
bothtshirts‒/100‒/5‒/10‒/20‒/25‒/40
bothclawsort‒/100‒/15‒/10‒/20‒/55
bothdancing‒/100‒/5‒/10‒/12‒/16‒/57
Regular onlyrerouting‒/100‒/10‒/20‒/30‒/40
Regular onlytinmining‒/100‒/15‒/15‒/15‒/15‒/40

## Peaks

The peaks of Eiger, Mönch and Jungfrau, overlooking the Oberland. Photo by Armin Kübelbeck / CC BY-SA.

Mouse Stofl will lead the Swiss delegation at the Mouse Olympiad in Informatics in Indonesia this year. According to tradition, he wants to hand out gifts related to Switzerland to participants from other countries. He has found a cheap type of presents: postcards! He wants to buy some with beautiful pictures of the Swiss mountains. The most beautiful pictures are those in which one can see many peaks. There are many available pictures and Stofl wants you to help him count how many peaks there are on some of them.

A picture can be described as a sequence of $N$ integers $h_{0},{\dots},h_{N-1}$. Each number $h_i$ represents the height of the mountains at the horizontal coordinate $i$ on the postcard. There is a peak at coordinate $i$ if and only if that coordinate has two neighbours that are lower than it. That means there is a peak at $i$ when $h_i>h_{i-1}$ and $h_i>h_{i+1}$. Note, in particular, that there is never a peak at coordinates $0$ and $N-1$, because those have only one neighbour.

### Subtask 1: Small Picture (10 Points)

Mouse Stofl starts by asking you to test your program on a very small picture with just $N=3$ mountains to see how the postcards look like without paying for huge ones. There are only three coordinates on the picture, and you should tell whether there is a peak on it.

#### 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 coordinates on the picture.
• On the second and last line, there are $N$ space-separated integers $h_{0},h_{1},{\dots},h_{N-1}$, the heights of the mountains at the coordinates $0$ to $N-1$.

#### Output

For the $i$-th test case, print a line “Case #i:” followed by “yes” if there is a peak on the picture or “no” if there is not.

#### Limits

• $T=100$.
• $N = 3$.
• $1 \le h_i \le 10^{9}$ for all $0\le i.

#### Example

Input:

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

Output:

Case #0: yes
Case #1: no
Case #2: no
Case #3: no

Comment:

The first line with “4” indicates that there are four test cases. The next two lines are “3” and “2 4 1” and describe the first (“Case #0”) of the four test cases. In this case, the three mountains have heights 2, 4, and 1. Below an explanation of the answers, see also the graphic after that:

Case #0: There is a peak at coordinate $1$.
Case #1: There is no peak, just a descent.
Case #2: There is no peak (inverted peaks do not count).
Case #3: There is no peak (the peak should be strictly larger than its neighbours).

### Subtask 2: Medium Picture (10 Points)

Mouse Stofl continues with a larger picture containing $N=5$ mountains. This time, you should not tell him if there is a peak, but tell him how many there are instead.

#### Output

For the $i$-th test case, print a line “Case #i:” followed by a single integer, the number of peaks in that picture.

#### Limits

• $T=100$.
• $N = 5$.
• $1 \le h_i \le 10^{9}$ for all $0\le i.

#### Example

Input:

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

Output:

Case #0: 2
Case #1: 0

Comment:

Case #0: There are peaks at coordinates $1$ and $3$.
Case #1: There is no peak.

### Subtask 3: Large Picture (30 Points)

Now, the picture is really large. You should once again tell Stofl how many peaks it displays.

#### Limits

• $T=100$.
• $3 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i.

#### Example

Input:

1
7
2 4 3 3 5 1 2

Output:

Case #0: 2

Comment:

Case #0: There are peaks at coordinates $1$ and $4$.

### Subtask 4: Cut a Picture (20 Points)

Those large postcards that Stofl showed you are made for humans, not for mice! He didn’t realise it at first, but he can’t pack them in his bags. Therefore, he wants to cut the picture so that it only contains $K$ coordinates. Tell him how many peaks he can keep on the picture if he cuts it optimally. Formally, you have to find the contiguous subsequence of length $K$ in the $N$ given integers that contains the largest amount of peaks.

#### 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 $K$, the number of coordinates on the picture and the number of coordinates that should be included on the picture after it is cut.
• On the second and last line, there are $N$ space-separated integers $h_{0},h_{1},{\dots},h_{N-1}$, the heights of the mountains at the coordinates $0$ to $N-1$.

#### Output

Print the maximum amount of peaks that one can fit on a contiguous part of the original picture of size $K$.

#### Limits

• $T=100$.
• $3 \le N \le 10\,000$
• $3 \le K \le 1000$
• $K \le N$
• $1 \le h_i \le 10^{9}$ for all $0\le i.

#### Example

Input:

1
12 6
3 6 4 2 1 2 1 5 3 2 6 3

Output:

Case #0: 2

Comment:

Case #0: It is possible to have two peaks by including coordinates $4$ to $9$. Note that it is not possible to reach three peaks by using coordinates $5$ to $10$: on the picture resulting from the cut, the mountains at coordinates $5$ and $10$ would not be peaks like in the original picture, because they would be at the edge of the new picture.

#### Interactive visualization

You can move the cutout with your mouse.

### Subtask 5: Cut a Large Picture (30 Points)

Stofl wants to use and cut even bigger postcards, so you need to be very smart to compute efficiently how many peaks he can get this time!

#### Limits

• $T=100$.
• $3 \le K \le N \le 1\,000\,000$
• $1 \le h_i \le 10^{9}$ for all $0\le i.

## Ropeways

A ropeway from Timang Beach to the island Pulau Timang in Yogyakarta, Indonesia. Photo by Pandora Voon, CC BY-SA.

Ropeways are used to transport people and goods across difficult terrain. A famous example of a ropeway is the gondola at Timang Beach. Originally built to ferry fisherman from the coast to a lobster nest on Pulau Timang, nowadays it is a popular tourist attraction.

As soon as she saw that there are more islands aligned on a line to the right of Pulau Timang, Mouse Binna had an idea for a new business opportunity: let’s build a system of ropeways that connects Pulau Timang with the right-most island.

Let’s number the islands from $0$ to $N-1$. Mouse Binna wants to connect island $0$ (Pulau Timang) with island $N-1$ using a set of ropeways.

Ropeways have a maximum length $K$ and can connect two islands that are up to $K$ apart. Formally, a ropeway can connect island $i$ with island $j$ if $i and $j-i\le K$ are satisfied.

You are given the heights $h_{0},h_{1},{\dots},h_{N-1}$ of islands on the shore. A ropeway from $i$ to $j$ is fun if $h_i>h_j$ (it goes down very fast) and is boring if $h_i\le h_j$ (it needs to be motor-powered which is slow).

Help Binna to decide which ropeways to build such that it is possible to go from $0$ to $N-1$ using the least amount of boring ropeways, for different values of $K$.

### Input/Output

All subtasks have the same input and output format.

#### 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 $Q$, the number of islands and the number of maximum lengths Binna wants to try out.
• On the second line there are $N$ numbers $h_{0},h_{1},{\dots},h_{N-1}$, the heights of the islands.
• The third line contains $Q$ numbers $k_{0},k_{1},{\dots},k_{Q-1}$, the different values of $K$ Binna is interested in.

#### Output

For the $i$-th test case print a line “Case #i:” followed by $Q$ numbers, where the $i$-th number is the minimum number of boring ropeways for a system where each ropeway has length at most $k_i$.

### Subtask 1: Long Ropeways to Pulau Ngondo (10 Points)

Mouse Binna has found a quality manufacturer that produces ropeways that have a maximum length of $N-2$ (thus it is one short to cover the whole range). Note that in this subtask $Q=1$ and $k_{0}=N-2$.

#### Limits

• $T=100$.
• $3 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i.
• $Q = 1$.
• $k_{0}=N-2$. This is the special restriction for subtask 1.

#### Example

Input:

3
3 1
3 1 4
1
4 1
1 3 3 7
2
5 1
999999999 1000000000 1 500000000 1
3

Output:

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

Comment:

Case #0: There is only one way to build the ropeways: $3-1$ and $1-4$. The second ride is boring.
Case #1: The two ropeways will be $1-3$ and $3-7$ which are both boring.
Case #2: There are the following options:
• $999999999\leadsto 1000000000\leadsto 1$: 1 boring ride
• $999999999\leadsto 1\leadsto 1$: 1 boring ride
• $999999999\leadsto 500000000\leadsto 1$: 0 boring rides
• $999999999\leadsto 1000000000\leadsto 1\leadsto 1$: 2 boring rides
• $999999999\leadsto 1000000000\leadsto 500000000\leadsto 1$: 1 boring ride
• $999999999\leadsto 1000000000\leadsto 1\leadsto 500000000\leadsto 1$: 2 boring rides

It is optimal to have exactly 0 boring rides.

### Subtask 2: Short Ropeways to Pulau Watubebek (20 Points)

This time Mouse Binna wants to go for cheaper ropeways that have a maximum length of either $1$ or $2$. Note that in this subtask $Q=2$ and $k_{0}=1$ and $k_{1}=2$.

#### Limits

• $T=100$.
• $2 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i.
• $Q = 2$.
• $k_{0}=1$ and $k_{1}=2$. This is the special restriction for subtask 2.

#### Example

Input:

2
3 2
11 22 33
1 2
15 2
3 1 2 1 4 5 4 4 3 3 9 4 7 5 5
1 2

Output:

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

### Subtask 3: Fast Track to Pulau Jungok (30 Points)

Mouse Binna has found a manufacturer that can produce ropeways of any quality. So she wants to know the answers for arbitrary values of $K$, but first on a segment with fewer islands. Note that in this subtask $N\le 5\,000$.

#### Limits

• $T=100$.
• $2 \le N \le 5\,000$. This is the special restriction for subtask 3.
• $1 \le h_i \le 10^{9}$ for all $0\le i.
• $1 \le Q \le 30$.
• $1 \le k_j < N$.

#### Example

Input:

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

Output:

Case #0: 7 25 12 2 6 2 2

### Subtask 4: Galactic System of Ropeways to Pulau Glatik (40 Points)

The last step is to build a large network of ropeways for arbitrary values of $K$. Everything is the same as in the previous subtask, except that $N$ and $Q$ can be much larger.

#### Limits

• $T=100$.
• $2 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i.
• $1 \le Q \le 100$.
• $1 \le k_j < N$.

## T-Shirts

The Mouse Olympiad in Informatics takes place in Indonesia this year and Mouse Binna is in charge of ordering the T-shirts. This turns out to be more difficult than anticipated because Java, where Yogyakarta is located, has four spoken languages. Javanese, the commonly spoken language in Yogyakarta, even uses their own numerals. This is very confusing and every time Binna orders T-shirts they arrive in all the wrong sizes! Help Binna to make the best out of the situation.

### Subtask 1: One Mouse (5 Points)

To check out the design, Binna ordered one T-shirt for herself. The T-shirt that arrived had size $s$. Binna can wear any T-shirt of size at least $l$ and at most $r$. Can she wear the T-shirt that arrived?

#### Input

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

• The first line contains an integer $l$, the minimal size a T-shirt must have so Binna can wear it.
• The second line contains an integer $r$, the maximal size a T-shirt can have so Binna can still wear it.
• The third line contains an integer $s$, the size of the T-shirt that arrived.

#### Output

For the $i$-th testcase, output a line containing “Case #i:” followed by “Yes” if the T-shirt fits, and “No” it does not.

#### Limits

• $T = 100$
• $1 \le l \le r \le 100$.
• $1 \le s \le 100$

#### Example

Input:

3
1
5
7
10
20
13
3
100
2

Output:

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

Comment:

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

Case #0: The next two lines are “1” and “5” and describe that Binna can wear a T-shirt of size at least $1$ and at most $5$. The next line is “7”, which means that the ordered T-shirt has size $7$. This T-shirt is too large for Binna, therefore the output for “Case #0” is “No”.

Case #1: Binna can wear T-shirts of size between $10$ and $20$ and the ordered T-shirt has size $13$. Thus she can wear it.
Case #2: No, a T-shirt of size $2$ is too small for Binna.

### Subtask 2: Same Size (10 Points)

Now Mouse Binna wants to order the T-shirts for the participants and she found a factory that produces T-shirts in only one size. But since she can’t predict what size arrives anyway, she thought that should be alright.

She noted down the sizes of the $N$ participants: participant $i$ can wear a T-shirt of size at least $l_i$ and at most $r_i$.

Finally Binna received the order and figured out she got $N$ T-shirts of size $S$. How many mice can wear a T-shirt?

#### 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 mice and T-shirts.
• The second line contains $N$ integers: $l_{0}, l_{1}, \ldots, l_{N-1}$, where $l_i$ is the minimal size a T-shirt can have such that the $i$-th participant could wear it.
• The third line contains $N$ integers: $r_{0}, r_{1}, \ldots, r_{N-1}$, where $r_i$ is the maximal size a T-shirt can have such that the $i$-th participant could wear it.
• The fourth line contains one integer $S$, the size of the T-shirts.

#### Output

For the $i$-th testcase, output a line containing “Case #i:” followed by a single integer, the number of T-shirts that can be assigned to mice satisfying the constraints described above.

#### Limits

• $T = 100$
• $1 \le N \le 100$
• $0 \le S \le 10^{9}$.
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.

#### Example

Input:

2
5
1 7 3 5 10
4 9 8 10 15
6
3
4 100 80
70 120 1000
73

Output:

Case #0: 2
Case #1: 0

Comment:

Case #0: The third and fourth participants can each wear a T-shirt of size $6$.
Case #1: None of the participants can wear a T-shirt of size $73$.

### Subtask 3: Rats (20 Points)

The Rat Olympiad in Informatics is also taking place in Indonesia this year. The organizers liked Binna’s T-shirt design so much that they stole all large T-shirts for their participants. The $M$ T-shirts that are left were too small for the rats and definitely can’t be too big for the mice. Therefore, in this subtask, Mouse Binna only needs to make sure the mice get a T-shirt that is bigger than their minimum size.

How many mice can get a T-shirt with a size that fits them, assuming we distribute the T-shirts optimally among them? Note that each T-shirt can only be assigned to at most one mouse.

#### 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 mice and the number of T-shirts.
• The second line contains $N$ integers: $l_{0}, l_{1}, \ldots, l_{N-1}$, where $l_i$ is the minimal size a T-shirt can have such that the $i$-th participant could wear it.
• The third line contains $N$ integers: $r_{0}, r_{1}, \ldots, r_{N-1}$, where $r_i$ is the maximal size a T-shirt can have such that the $i$-th participant could wear it.
• The fourth line contains $M$ integers: $s_{0}, s_{1}, \ldots, s_{M-1}$, describing the size of the T-shirts.

#### Output

For the $i$-th testcase, output a line containing “Case #i:” followed by a single integer, the number of T-shirts that can be assigned to mice satisfying the constraints described above.

#### Limits

• $T = 100$
• $1 \le N \le 10^{4}$
• $1 \le M \le 10^{4}$
• $s_j \le r_i$ for all $i$ and $j$. This is the special restriction for this subtask.
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.
• $0 \le s_j \le 10^{9}$ for all $j$.

#### Example

Input:

2
3 4
1 7 3
4 9 8
3 2 4 2
5 4
12 17 3 1 9
20 30 15 22 31
4 14 13 7

Output:

Case #0: 2
Case #1: 4

Comment:

Case #0: We can give the T-shirt of size 3 to mouse 0 (which can wear sizes from 1 to 4) and T-shirt of size 4 to mouse 2 (which can wear sizes from 3 to 8). There is no way we can give a T-shirt to mouse 1, since the T-shirts are too small.
Case #1: We can give away all the 4 T-shirts if we do so optimally.

### Subtask 4: Everything (25 Points)

Finally, the $M$ T-shirts have arrived. This time Binna also needs to consider the maximum size of the participants. Help Binna to find out how many mice can wear a T-shirt.

#### Limits

• $T = 100$
• $1 \le N \le 10^{4}$
• $1 \le M \le 10^{4}$
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.
• $0 \le s_j \le 10^{9}$ for all $j$.

#### Example

Input:

2
3 4
1 7 3
4 9 8
5 2 9 2
5 4
12 17 3 1 9
20 30 15 22 31
4 14 33 17

Output:

Case #0: 3
Case #1: 3

### Subtask 5: Many Participants (40 Points)

The Mouse Olympiad in Informatics is a large event with many mice, so there can be up to $10^{6}$ participants.

#### Limits

• $T = 100$
• $1 \le N \le 10^{6}$
• $1 \le M \le 10^{6}$
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.
• $0 \le s_j \le 10^{9}$ for all $j$.

## Claw Sort

Mouse Stofl has built a robot with a claw attached, which can pick up and put down objects. The robot also has wheels, and can move to the left or to the right.

The robot can be in one of $N$ positions, and it starts at position $0$. When it starts, its claw is empty. The robot can be controlled by giving it one of two possible commands:

• >”: exchange the currently held item with the item at the current position and move one to the right.
• <”: exchange the currently held item with the item at the current position and move one to the left.

The robot cannot move outside of the $N$ positions.

In order to test the robot, Stofl has placed a row of cards with numbers on them on the floor, but they are all jumbled up. He wants to use the robot to sort the numbers in increasing order. Can you help him?

### Subtask 1: Simulate the robot (15 Points)

Mouse Stofl has written a list of commands which he thinks will sort the cards, but he is not sure if it is correct. Simulate the robot and tell Stofl in what order the cards are afterwards.

#### 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 the number of cards $N$.
• The second line contains the $N$ numbers which are written on the cards from left to right. Every number between $0$ and $N-1$ appears exactly once.
• The third line contains the list of commands, which consists of $K$ characters “>” or “<”, terminated by a single “.”.

It is guaranteed that after executing all commands of a test case, the robot will end up with an empty claw.

#### Output

You should output $T$ lines, one for each test case. For the $i$-th test case, output “Case #i:” followed by $N$ numbers, the numbers on the cards from left to right after the robot has executed the commands.

#### Limits

• $T = 100$
• $2 \le N \le 200$
• $0 \le K \le 1000$

#### Example

Input:

2
2
1 0
><>.
3
2 0 1
>><><<>.

Output:

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

Comment:

Case #0: The robot picks up the $1$ and moves it to the right, exchanges it with the $0$, then moves back and puts the $0$ down, and moves to the right again with an empty claw.
Case #1: It looks like Stofl has made a mistake, because the resulting list is not correctly sorted. The $2$ is at the right place, but now $0$ and $1$ are in the wrong order.

### Subtask 2: Sort three cards (10 Points)

Evidently, Mouse Stofl is not very good at giving the robot commands for correctly sorting cards. Can you do it better?

#### 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 the number of cards $N$.
• The second line contains the $N$ numbers which are written on the cards from left to right. Every number between $0$ and $N-1$ appears exactly once.

#### Output

You should output $T$ lines, one for each test case. For the $i$-th test case, output “Case #i:” followed by a list of commands, which consists of $K$ characters “>” or “<”, followed by “.”.

#### Limits

• $T = 100$
• $N = 3$
• $K \le 100$ (you can send at most $100$ commands to the robot)

#### Example

Input:

2
3
2 0 1
3
0 1 2

Output:

Case #0: ><>><<.
Case #1: .

Comment:

Case #0: This is one way to correctly sort the list from subtask 1. Note that there are many possible solutions, you can output any one of them.
Case #1: The list is already sorted, so we don’t need any commands.

### Subtask 3: Reverse the cards (20 Points)

Mouse Stofl noticed that his cards are already sorted in decreasing order. That’s bad, because he wants to have them in increasing order. Can you help him reverse them?

#### Limits

• $T = 100$
• $1 \le N \le 101$
• $K \le 10\,000\,000$
• The $i$-th testcase has $N=i+1$.
• The numbers are sorted in decreasing order.

Note that every input file looks exactly the same.

#### Example

Input:

2
1
0
2
1 0

Output:

Case #0: .
Case #1: ><><><><>.

Comment:

Case #0: For $N=1$ there is no valid move except for stopping the robot.
Case #1: This is not the minimal way of reversing them, but it does the job.

### Subtask 4: Sort a lot of cards (55 Points)

Can you solve the final challenge and sort up to 300 cards with the robot? Sorting so many cards takes a lot of time and Stofl is in a hurry. Therefore he will pay you points depending on how fast your robot is. See scoring section for more details.

#### Input and Output

Same as subtasks 2 and 3.

#### Limits

• $T = 100$
• $K \le 400\,000$
• For limits on $N$ see below.

#### Scoring

You can get a variable amount of points for this subtask.

• 7 points if you only solve the first 30 test cases (0 to 29), where we have $2 \le N \le 7$.

• 20 points if you only solve the first 60 test cases (0 to 59), where we have $2 \le N \le 50$.

• 25–55 points if you solve all test cases. In all test cases, $2 \le N \le 300$. The score of a test case is calculated as follows.

Let $A$ be the number of operations you need in your solution.
Let $S$ be the number of operations of our master solution.
Then you get the following amount of points:
$25+\left\lfloor 10 \cdot \tan(\arctan(3) \cdot \max(0, \min\left(1, 1 - \frac{A - S}{400\,000 - S}\right)))\right\rfloor$

Your total score is the minimum score over all test cases.

Click below for some reference values for this function:

Expand
maximum A possible score
$68\,840$ 55
$68\,841$ 54
$80\,000$ 51
$90\,000$ 48
$100\,000$ 46
$200\,000$ 34
$300\,000$ 28
$400\,000$ 25

#### Example

Input:

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

Output:

Case #0: >>><<><<><>>.
Case #1: >><>>><<><<<>><<.
Case #2: >><<>>><>><>><<<<<.

#### Interactive visualization

Note: The upload limit is 10 MiB. If you exceed that you get an error “413 Request Entity Too Large”. Most likely this is because you exceed the $400\,000$ move limit. In that case, just upload the first 60 test cases (you won’t get more than 20 points anyways if you exceed the limit).

## Dancing Mice

Mouse Stofl is organizing a stage dance for $N$ mice. The $N$ mice will stand in a circle, and then during the dance the mice that stand next to each other in the circle can form pairs. During each moment, one mouse can belong to at most one pair, but the pairs can change during the dance. For example, for $N=5$ the mice can first form pairs as 0+1, 2 (dancing alone), 3+4, and then change to 1, 2, 3, 4+0 (remember that since they are standing in a circle mouse $N-1$ can form a pair with mouse 0), and so on.

For each pair of adjacent mice $i$ and $i+1$ (or $N-1$ and $0$ for $i=N-1$), Stofl has prepared a sequence of dance moves that they will perform as a pair, which lasts for $t_i$ seconds. These moves do not have to be performed as one consecutive segment – for example, if $t_i=5$, the pair can dance together for 1.5 seconds, then the two mice can form different pairs or dance alone for some time, and then they can form a pair again and dance for the remaining 3.5 seconds. It’s OK to split this dancing time into more than two segments, too.

Now Stofl is wondering how to put all those moves together into one big dance for all mice. More specifically, you need to help Stofl design a dance with the shortest overall duration that allows mice $i$ and $i+1$ (or $N-1$ and $0$ for $i=N-1$) to dance as a pair for at least $t_i$ seconds for each $i$.

### Input/Output

All subtasks have the same input and output format.

#### 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 mice.
• On the second line there are $N$ integers $t_{0},t_{1},{\dots},t_{N-1}$, the durations of the dance moves for each pair of adjacent mice.

#### Output

For the $t$-th test case, output a line containing “Case #t:”, followed by a space and an integer $M$: the number of sections in the dance you designed. A section is a part of the dance during which the pairs do not change. In the following $M$ lines, describe the sections. Each section is described by its duration in seconds (a floating-point number), followed by a space and a string of $N$ characters without spaces. If the $i$-th mouse is dancing alone, the $i$-th character of that string should be a dot (.). If the $i$-th mouse is dancing together with the $i+1$-th mouse (or, in case $i=N-1$, with the 0-th mouse), the $i$-th character of that string should be a less-than sign (<). If the $i$-th mouse is dancing together with the $i-1$-th mouse (or, in case $i=0$, with the $N-1$-th mouse), the $i$-th character of that string should be a greater-than sign (>).

• The total duration of the dance is at most $A\cdot(1+10^{-6})$, where A is the shortest possible duration.
• For each $i$ such that $0 < t_i$, the total duration of the sections where the $i$-th and the $i+1$-th mice dance together (or the $N-1$-th and 0-th for $i=N-1$) is at least $t_i\cdot(1-10^{-6})$.
• Each section is well-formed: the duration is non-negative (zero is OK), and the mice are correctly paired up.
• $M$ is at most $3\cdot N$.

It is guaranteed that there always exists a dance with the shortest possible duration that has at most $3\cdot N$ sections.

### Subtask 1: Three Mice (5 Points)

In this subtask there are only three mice dancing.

#### Limits

• $T=30$.
• $N=3$.
• $0 \le t_i \le 10^{6}$ for all $0\le i.
• For at least one $i$, $0 < t_i$.

#### Example

Input:

1
3
1 2 3

Output:

Case #0: 3
1.0 <>.
3 >.<
2 .<>

Comment:

The total duration of this dance is 6 seconds. Note that there are many other outputs that would also be accepted.

### Subtask 2: All the Same (10 Points)

In this subtask all pairs of adjacent mice have to dance together for exactly 1 second.

#### Limits

• $T=30$.
• $3 \le N \le 100$.
• $t_i=1$ for all $0\le i.

#### Example

Input:

2
4
1 1 1 1
5
1 1 1 1 1

Output:

Case #0: 2
1 <><>
1 ><><
Case #1: 5
0.5 <><>.
0.5 <>.<>
0.5 .<><>
0.5 ><>.<
0.5 >.<><

Comment:

In the second case, the total duration of the dance is 2.5 seconds, and it consists of 5 sections of 0.5 seconds each. Each pair of adjacent mice dance together in two of those sections, therefore each pair of adjacent mice dance together for 1 second ($0.5 + 0.5$).

### Subtask 3: With a Zero (12 Points)

In this subtask the last and the first mice do not have to dance together.

#### Limits

• $T=30$.
• $3 \le N \le 100$.
• $0 \le t_i \le 10^{6}$ for all $0\le i.
• $t_{N-1}=0$.
• For at least one $i$, $0 < t_i$.

#### Example

Input:

1
5
1 2 3 2 0

Output:

Case #0: 2
3 <><>.
2 .<><>

### Subtask 4: Even Mice (16 Points)

In this subtask the number of mice is even.

#### Limits

• $T=30$.
• $4 \le N \le 100$.
• $0 \le t_i \le 10^{6}$ for all $0\le i.
• For at least one $i$, $0 < t_i$.
• $N$ is even.

#### Example

Input:

1
6
1 2 3 2 5 1

Output:

Case #0: 2
5 <><><>
2 ><><><

### Subtask 5: Odd Mice (57 Points)

In this subtask the number of mice is odd.

#### Limits

• $T=30$.
• $3 \le N \le 99$.
• $0 \le t_i \le 10^{6}$ for all $0\le i.
• For at least one $i$, $0 < t_i$.
• $N$ is odd.

#### Example

Input:

1
7
1 2 5 2 5 2 5

Output:

Case #0: 7
4.333333333333 >.<><><
1.333333333333 .<><><>
0.333333333333 <><><>.
0.333333333333 <>.<><>
0.333333333333 <><>.<>
0.333333333333 ><><>.<
0.333333333333 ><>.<><

## Ferry Rerouting

Indonesia consists of over 17000 islands, although only 6000 are inhabited. Photo by Rolandandika, CC BY-SA.

Indonesia is the largest archipelagic country in the world, stretching over 5000 kilometres from east to west. It consists of over 17000 islands of which about 6000 are inhabited, with rainforest covering most of these islands.

Mouse Stofl is working in the Indonesian mouse ferry organization, more specifically, he is responsible for planning the routes of the ferries. The $N$ islands currently served by the mouse ferry organization are connected by $N - 1$ ferries, where each ferry connects two islands, in such a way that it’s possible to get from any island to any other island by using ferry-connections.

Recent analysis has showed that the network is not as efficient as it could be. Mouse Stofl has compiled a list of $N - 1$ new connections, so that it’s still possible to get from any island to any other island only using connections from his list. He now wants to replace the old $N - 1$ connections with his new connections.

However, if Mouse Stofl replaced all the connections at once, the other mice would be confused and wouldn’t know which ferries to take. Mouse Stofl decided that he will change exactly one connection per day. This means, every day, he replaces one of the current ferry-connections with an arbitrary new connection, which is not necessarily on his list. However, as the mice continue travelling during this process, at any day, it must be possible to get from any island to any other island.

Mouse Stofl wants the rerouting process to finish and the new connections to be in place as soon as possible. Thus he asks you to find the minimal number of days and which connections he should replace on each day.

### Subtask 1: Number of Days (10 Points)

Mouse Stofl initially isn’t sure about his plan. He fears that it might take too long until the new connections are in place. That’s why he only wants to know the minimal number of days and why he doesn’t need to know which connections to replace.

#### Input

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

• The first line of each test case contains one integer $N$, the number of islands.
• The second and third line contain $N - 1$ numbers each, describing the initial ferry connections. If $a_i$ is the $i$-th number of the first line and $b_i$ the $i$-th number of the second line, then there is initially a ferry connecting the islands $a_i$ and $b_i$ for each $i$.
• The fourth and the fifth line describe the connections of the new list of Stofl, in the same format as lines two and three.

#### Output

For the $i$-th test case print a line “Case #i:” followed by a single integer: the minimal number of days needed until all the new connections are in place.

#### Limits

• $T=100$
• $1 \le N \le 6\,000$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

#### Example

Input:

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

Output:

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

### Subtask 2: Regional Transports (20 Points)

Mouse Stofl has now decided that he wants to implement his plan. However, he is currently only responsible for a small region only consisting of approximately 100 islands.

#### Output

For the $i$-th test case print a line “Case #i:” followed by a single integer $k$: the minimal number of days needed until all the new connections are in place. Then output $k$ lines. The $j$-th line consists of four integers $w_j, x_j, y_j$ and $z_j$, meaning that on day $j$, the connection between $w_j$ and $x_j$ should be replaced by the connection between $y_j$ and $z_j$.

#### Limits

• $T=100$
• $1 \le N \le 100$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

#### Example

Input:

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

Output:

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

### Subtask 3: Inhabited Islands of Indonesia (30 Points)

Mouse Stofl got promoted and is now responsible for all of Indonesia. However, only the inhabited islands are currently served by ferries.

#### Limits

• $T=100$
• $1 \le N \le 6000$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i.
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

### Subtask 4: The World (40 Points)

Mouse Stofl was so successful in his business, that he is now responsible for organizing the ferry routes of the worldwide mouse ferry organization. They connect islands worldwide, however, not all the islands can be served as there are simply too many. The organization currently serves approximately $100\,000$ islands.

#### Limits

• $T=100$
• $1 \le N \le 100\,000$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

Since we can’t ensure that optimized brute-force solutions or heuristics won’t be able to pass, we will manually check all submissions and may retroactively give an accepted submission 0 points.

We expect a solution that runs in $\mathcal O(N\cdot \log(N)^c)$ (for a constant $c$) or $\mathcal O(N\cdot \alpha(N))$, where $\alpha(N)$ is the inverse Ackermann function. See Introduction to Algorithm Design for explanation of the $\mathcal O$-notation.

Furthermore, as we can’t distinguish the different running times, we will manually check your submissions and score them according to this table:

Running time Score
$\mathcal O(N \cdot \alpha(N))$ 40
$\mathcal O(N \cdot \log(N))$ 32
$\mathcal O(N \cdot \log(N)^c)$ for $c > 1$ 25

Note: We need around 15 seconds to verify your submission. Please be patient.

## Tinmining

Tin-mine off the coast of Toboali, on the southern shores of the island of Bangka, Indonesia

Due to its geographic location in the Southeast Asian tin belt, Indonesia is one of the biggest exporters of tin. Unfortunately, the tin reserves of Indonesia are about to be depleted. Most mining companies have therefore decided to move their mining operations to the sea around Indonesia.

Inspired by the uprising tin-rush, mouse Binna wants to start her own mining business. A tin-mine on the sea is considerably more complicated than one on land. On the sea, a tin-mine consists of different worker nodes that are interconnected with each other to share resources and mined ore via ships. Each worker node has exactly one port for incoming ships and one for outgoing ships. In order for a node to function properly, it has to be connected to the whole network.

Binna has investigated $N$ tin deposits arranged in a circular pattern. Each worker node placed on a deposit will have a different stability level. More stable nodes are more robust and so have a bigger storage capacity for mined ore. Therefore ships can only transport mined ore in one direction, from the less stable node to the more stable one. The more nodes are connected to the whole network, the more efficient the mine can operate because more deposits can be exploited.

In a traditional tin-mine, the mined ore is transported in large trucks. Trucks are very agile and can easily maneuver around each other. On the sea however, the ore has to be transported with ships. Because ships loaded to the brim with ore are heavy and have a lot of inertia, it is important that different ship routes do not cross each other.

### Input/Output

All subtasks have the same input and output format.

#### 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 tin deposits.
• A second line follows with $N$ integer values $a_{0},{\dots},a_{N-1}$, the different levels of stability in a circular order.

#### Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the total number of worker nodes which are needed for the optimal solution (including the one mouse Binna already constructed).

### Subtask 1: First Mine (15 Points)

In a rush of enthusiasm, mouse Binna has already constructed the worker node that requires the highest level of stability. She now wants to know the best strategy for exploiting the highest number of tin deposits. Given a list of $N$ numbers, the different levels of stability in a circular manner, compute the size of the optimal choice of worker nodes.

#### Limits

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

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

#### Example

Input:

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

Output:

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

### Subtask 2: Scaling up (15 Points)

After starting a small mining business, Binna has collected enough capital to start bigger mining operations.

#### Limits

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

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

### Subtask 3: Efficient exploitation (15 Points)

After scaling up her mining operations, mouse Binna realises that her tin mine is not performing optimally. She realises that it is not always optimal to build the worker node that requires the highest level of stability. So she asks you to find the optimal without the restriction that this node is built.

#### Limits

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

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

#### Example

Input:

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


Output:

Case #0: 4
Case #1: 5

### Subtask 4: Scaling up (15 Points)

After testing the new algorithm, mouse Binna is very happy with the result and wants to scale up this new strategy.

#### Limits

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

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

### Subtask 5: Theoretical (10 + 30 Points)

Hand in a document that solves the two problems described below.

#### a) Risk minimization (10 Points)

Mouse Binna has now built many different mining operations. She now has the opportunity to buy a very large mining territory in which she could scan $N$ locations. She wants to find a lower bound on the amount of the number deposits she will be able to mine in the worst case.

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

More specifically, if $k$ is the maximal amount of deposits that can be mined, show that

$k \geq \frac{ \sqrt {N} } { C }$

For some constant $C > 0$ of your liking.

#### b) Algorithm depending on $k$ (30 Points)

Describe an algorithm that solves the task in subtask 3 and 4 and analyze it. This is a theoretical task, so you should reason why your solution is correct and what asymptotic running time and memory usage your solution has.

Let $k$ be is the maximal amount of mining nodes that can be used in the optimal solution. Find an algorithm that is fast when $k$ is small!

See the table below in ‘Grading’ to see how many points can be achieved for a given runtime and memory usage.

Hand in a document (preferably PDF) that describes

• why your algorithm is correct
• analyze its running time and memory usage.

If your algorithm is correct, we will give you points according to the table below.

Running time Memory usage Max score
$O(N^{3})$ $O(N^{2})$ 5
$O(N^{2}\cdot \log N)$ $O(N)$ 15
$O(N \cdot k)$ $O(N)$ 30

Note that $k$ here is the maximal amount of mining nodes that can be used in the optimal solution. Additional log factors only cause minor point deductions.