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.Category | Task | Total | Subtask 1 | Subtask 2 | Subtask 3 | Subtask 4 | Subtask 5 |
---|---|---|---|---|---|---|---|

Junior only | peaks | ‒/100 | ‒/10 | ‒/10 | ‒/30 | ‒/20 | ‒/30 |

Junior only | ropeways | ‒/100 | ‒/10 | ‒/20 | ‒/30 | ‒/40 | |

both | tshirts | ‒/100 | ‒/5 | ‒/10 | ‒/20 | ‒/25 | ‒/40 |

both | clawsort | ‒/100 | ‒/15 | ‒/10 | ‒/20 | ‒/55 | |

both | dancing | ‒/100 | ‒/5 | ‒/10 | ‒/12 | ‒/16 | ‒/57 |

Regular only | rerouting | ‒/100 | ‒/10 | ‒/20 | ‒/30 | ‒/40 | |

Regular only | tinmining | ‒/100 | ‒/15 | ‒/15 | ‒/15 | ‒/15 | ‒/40 |

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.

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.

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

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.

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

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:

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.

See Subtask 1.

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

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

Input:

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

Output:

Case #0: 2 Case #1: 0

Comment:

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

See Subtask 1.

See Subtask 2.

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

Input:

1 7 2 4 3 3 5 1 2

Output:

Case #0: 2

Comment:

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.

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

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

- $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<N$.

Input:

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

Output:

Case #0: 2

Comment:

You can move the cutout with your mouse.

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!

See Subtask 4.

See Subtask 4.

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

See Subtask 4.

Don't hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

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<j$ 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$.

All subtasks have the same input and output format.

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.

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

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

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

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.

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

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

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

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

- $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<N$.
- $1 \le Q \le 30$.
- $1 \le k_j < N$.

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

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.

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

Don't hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

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.

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?

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.

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

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

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`”.

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?

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.

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.

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

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:

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.

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.

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.

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

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:

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.

See Subtask 3.

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

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

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

See Subtask 3.

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

Don't hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

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?

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.

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.

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.

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

Input:

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

Output:

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

Comment:

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

To start with, he only asks you to sort three numbers.

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.

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 “`.`”.

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

Input:

2 3 2 0 1 3 0 1 2

Output:

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

Comment:

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?

Same as subtask 2.

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

Input:

2 1 0 2 1 0

Output:

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

Comment:

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.

Same as subtasks 2 and 3.

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

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:Your total score is the minimum score over all test cases.

Click below for some reference values for this function:

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

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

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

All subtasks have the same input and output format.

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.

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 (`>`).

Your answer will be accepted if the following conditions hold:

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

In this subtask there are only three mice dancing.

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

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.

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

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

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$).

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

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

Input:

1 5 1 2 3 2 0

Output:

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

In this subtask the number of mice is even.

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

Input:

1 6 1 2 3 2 5 1

Output:

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

In this subtask the number of mice is odd.

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

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

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.

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.

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.

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.

- $T=100$
- $1 \le N \le 6\,000$
- $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$
- 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.

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

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.

See subtask 1.

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

- $T=100$
- $1 \le N \le 100$
- $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$
- 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.

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

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

See subtask 2.

- $T=100$
- $1 \le N \le 6000$
- $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$.
- 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.

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.

See subtask 2.

- $T=100$
- $1 \le N \le 100\,000$
- $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$

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.

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.

All subtasks have the same input and output format.

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.

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

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.

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]$.

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

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

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]$.

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.

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]$.

Input:

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

Output:

Case #0: 4 Case #1: 5

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

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

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

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.

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.

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.

Check out the wiki for more information on how to solve/write theoretical tasks: Theoretical Intro

Hand in a document (preferably PDF) that describes

- how your algorithm works
- 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.

Rank | Username | Total (500) | peaks (100) | ropeways (100) | tshirts (100) | clawsort (100) | dancing (100) |
---|---|---|---|---|---|---|---|

loading ... |

Rank | Username | Total (500) | tshirts (100) | clawsort (100) | dancing (100) | rerouting (100) | tinmining (100) |
---|---|---|---|---|---|---|---|

loading ... |

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