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.

CategoryTaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
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

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.

Don’t hesitate to contact us at info@soi.ch if you have any question about programming or the tasks.

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 5 best juniors qualify for a Junior Camp in Dezember. The top 8 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.

Peaks

https://upload.wikimedia.org/wikipedia/commons/thumb/0/0d/Eiger_M%C3%B6nch_Jungfrau_01.jpg/1024px-Eiger_M%C3%B6nch_Jungfrau_01.jpg

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 NN integers h0,,hN1h_{0},{\dots},h_{N-1}. Each number hih_i represents the height of the mountains at the horizontal coordinate ii on the postcard. There is a peak at coordinate ii if and only if that coordinate has two neighbours that are lower than it. That means there is a peak at ii when hi>hi1h_i>h_{i-1} and hi>hi+1h_i>h_{i+1}. Note, in particular, that there is never a peak at coordinates 00 and N1N-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=3N=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 TT. TT test cases follow of the following format:

  • The first line contains one integer, NN, the number of coordinates on the picture.
  • On the second and last line, there are NN space-separated integers h0,h1,,hN1h_{0},h_{1},{\dots},h_{N-1}, the heights of the mountains at the coordinates 00 to N1N-1.

Output

For the ii-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=100T=100.
  • N=3N = 3.
  • 1hi1091 \le h_i \le 10^{9} for all 0i<N0\le i<N.

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

To submit for this subtask, please log in.

Subtask 2: Medium Picture (10 Points)

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

Input

See Subtask 1.

Output

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

Limits

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

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 11 and 33.
Case #1: There is no peak.

To submit for this subtask, please log in.

Subtask 3: Large Picture (30 Points)

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

Input

See Subtask 1.

Output

See Subtask 2.

Limits

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

Example

Input:

1
7
2 4 3 3 5 1 2

Output:

Case #0: 2

Comment:

Case #0: There are peaks at coordinates 11 and 44.

To submit for this subtask, please log in.

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 KK 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 KK in the NN given integers that contains the largest amount of peaks.

Input

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

  • The first line contains two integers, NN and KK, 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 NN space-separated integers h0,h1,,hN1h_{0},h_{1},{\dots},h_{N-1}, the heights of the mountains at the coordinates 00 to N1N-1.

Output

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

Limits

  • T=100T=100.
  • 3N100003 \le N \le 10\,000
  • 3K10003 \le K \le 1000
  • KNK \le N
  • 1hi1091 \le h_i \le 10^{9} for all 0i<N0\le i<N.

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 44 to 99. Note that it is not possible to reach three peaks by using coordinates 55 to 1010: on the picture resulting from the cut, the mountains at coordinates 55 and 1010 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.

To submit for this subtask, please log in.

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!

Input

See Subtask 4.

Output

See Subtask 4.

Limits

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

Example

See Subtask 4.

To submit for this subtask, please log in.

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

Ropeways

https://live.staticflickr.com/7179/28039191326_21f6f3e44e_c.jpg

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 00 to N1N-1. Mouse Binna wants to connect island 00 (Pulau Timang) with island N1N-1 using a set of ropeways.

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

You are given the heights h0,h1,,hn1h_{0},h_{1},{\dots},h_{n-1} of islands on the shore. A ropeway from ii to jj is fun if hi>hjh_i>h_j (it goes down very fast) and is boring if hihjh_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 00 to N1N-1 using the least amount of boring ropeways, for different values of KK.

Input/Output

All subtasks have the same input and output format.

Input

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

  • The first line contains two integers NN and QQ, the number of islands and the number of maximum lengths Binna wants to try out.
  • On the second line there are NN numbers h0,h1,,hN1h_{0},h_{1},{\dots},h_{N-1}, the heights of the islands.
  • The third line contains QQ numbers k0,k1,,kQ1k_{0},k_{1},{\dots},k_{Q-1}, the different values of KK Binna is interested in.

Output

For the ii-th test case print a line “Case #i:” followed by QQ numbers, where the ii-th number is the minimum number of boring ropeways for a system where each ropeway has length at most kik_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 N2N-2 (thus it is one short to cover the whole range). Note that in this subtask Q=1Q=1 and k0=N2k_{0}=N-2.

Limits

  • T=100T=100.
  • 3N10000003 \le N \le 1\,000\,000.
  • 1hi1091 \le h_i \le 10^{9} for all 0i<N0\le i<N.
  • Q=1Q = 1.
  • k0=N2k_{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: 313-1 and 141-4. The second ride is boring.
Case #1: The two ropeways will be 131-3 and 373-7 which are both boring.
Case #2: There are the following options:
  • 99999999910000000001999999999\leadsto 1000000000\leadsto 1: 1 boring ride
  • 99999999911999999999\leadsto 1\leadsto 1: 1 boring ride
  • 9999999995000000001999999999\leadsto 500000000\leadsto 1: 0 boring rides
  • 999999999100000000011999999999\leadsto 1000000000\leadsto 1\leadsto 1: 2 boring rides
  • 99999999910000000005000000001999999999\leadsto 1000000000\leadsto 500000000\leadsto 1: 1 boring ride
  • 999999999100000000015000000001999999999\leadsto 1000000000\leadsto 1\leadsto 500000000\leadsto 1: 2 boring rides

It is optimal to have exactly 0 boring rides.

To submit for this subtask, please log in.

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 11 or 22. Note that in this subtask Q=2Q=2 and k0=1k_{0}=1 and k1=2k_{1}=2.

Limits

  • T=100T=100.
  • 2N10000002 \le N \le 1\,000\,000.
  • 1hi1091 \le h_i \le 10^{9} for all 0i<N0\le i<N.
  • Q=2Q = 2.
  • k0=1k_{0}=1 and k1=2k_{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

To submit for this subtask, please log in.

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 KK, but first on a segment with fewer islands. Note that in this subtask N5000N\le 5\,000.

Limits

  • T=100T=100.
  • 2N50002 \le N \le 5\,000. This is the special restriction for subtask 3.
  • 1hi1091 \le h_i \le 10^{9} for all 0i<N0\le i<N.
  • 1Q301 \le Q \le 30.
  • 1kj<N1 \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

To submit for this subtask, please log in.

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 KK. Everything is the same as in the previous subtask, except that NN and QQ can be much larger.

Limits

  • T=100T=100.
  • 2N10000002 \le N \le 1\,000\,000.
  • 1hi1091 \le h_i \le 10^{9} for all 0i<N0\le i<N.
  • 1Q1001 \le Q \le 100.
  • 1kj<N1 \le k_j < N.

To submit for this subtask, please log in.

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

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 ss. Binna can wear any T-shirt of size at least ll and at most rr. Can she wear the T-shirt that arrived?

Input

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

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

Output

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

Limits

  • T=100T = 100
  • 1lr1001 \le l \le r \le 100.
  • 1s1001 \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 11 and at most 55. The next line is “7”, which means that the ordered T-shirt has size 77. 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 1010 and 2020 and the ordered T-shirt has size 1313. Thus she can wear it.
Case #2: No, a T-shirt of size 22 is too small for Binna.

To submit for this subtask, please log in.

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 NN participants: participant ii can wear a T-shirt of size at least lil_i and at most rir_i.

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

Input

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

  • The first line contains one integer NN, the number of mice and T-shirts.
  • The second line contains NN integers: l0,l1,,lN1l_{0}, l_{1}, \ldots, l_{N-1}, where lil_i is the minimal size a T-shirt can have such that the ii-th participant could wear it.
  • The third line contains NN integers: r0,r1,,rN1r_{0}, r_{1}, \ldots, r_{N-1}, where rir_i is the maximal size a T-shirt can have such that the ii-th participant could wear it.
  • The fourth line contains one integer SS, the size of the T-shirts.

Output

For the ii-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=100T = 100
  • 1N1001 \le N \le 100
  • 0S1090 \le S \le 10^{9}.
  • 0liri1090 \le l_i \le r_i \le 10^{9} for all ii.

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 66.
Case #1: None of the participants can wear a T-shirt of size 7373.

To submit for this subtask, please log in.

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 MM 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 TT. TT test cases follow of the following format:

  • The first line contains two integers NN and MM, the number of mice and the number of T-shirts.
  • The second line contains NN integers: l0,l1,,lN1l_{0}, l_{1}, \ldots, l_{N-1}, where lil_i is the minimal size a T-shirt can have such that the ii-th participant could wear it.
  • The third line contains NN integers: r0,r1,,rN1r_{0}, r_{1}, \ldots, r_{N-1}, where rir_i is the maximal size a T-shirt can have such that the ii-th participant could wear it.
  • The fourth line contains MM integers: s0,s1,,sM1s_{0}, s_{1}, \ldots, s_{M-1}, describing the size of the T-shirts.

Output

For the ii-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=100T = 100
  • 1N1041 \le N \le 10^{4}
  • 1M1041 \le M \le 10^{4}
  • sjris_j \le r_i for all ii and jj. This is the special restriction for this subtask.
  • 0liri1090 \le l_i \le r_i \le 10^{9} for all ii.
  • 0sj1090 \le s_j \le 10^{9} for all jj.

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.

To submit for this subtask, please log in.

Subtask 4: Everything (25 Points)

Finally, the MM 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.

Input/Output

See Subtask 3.

Limits

  • T=100T = 100
  • 1N1041 \le N \le 10^{4}
  • 1M1041 \le M \le 10^{4}
  • 0liri1090 \le l_i \le r_i \le 10^{9} for all ii.
  • 0sj1090 \le s_j \le 10^{9} for all jj.

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

To submit for this subtask, please log in.

Subtask 5: Many Participants (40 Points)

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

Input/Output

See Subtask 3.

Limits

  • T=100T = 100
  • 1N1061 \le N \le 10^{6}
  • 1M1061 \le M \le 10^{6}
  • 0liri1090 \le l_i \le r_i \le 10^{9} for all ii.
  • 0sj1090 \le s_j \le 10^{9} for all jj.

To submit for this subtask, please log in.

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

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 NN positions, and it starts at position 00. 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 NN 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 TT. TT test cases follow in the following format:

  • The first line of the test case contains the number of cards NN.
  • The second line contains the NN numbers which are written on the cards from left to right. Every number between 00 and N1N-1 appears exactly once.
  • The third line contains the list of commands, which consists of KK 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 TT lines, one for each test case. For the ii-th test case, output “Case #i:” followed by NN numbers, the numbers on the cards from left to right after the robot has executed the commands.

Limits

  • T=100T = 100
  • 2N2002 \le N \le 200
  • 0K10000 \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 11 and moves it to the right, exchanges it with the 00, then moves back and puts the 00 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 22 is at the right place, but now 00 and 11 are in the wrong order.

Interactive visualization

To submit for this subtask, please log in.

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?

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

Input

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

  • The first line of the test case contains the number of cards NN.
  • The second line contains the NN numbers which are written on the cards from left to right. Every number between 00 and N1N-1 appears exactly once.

Output

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

Limits

  • T=100T = 100
  • N=3N = 3
  • K100K \le 100 (you can send at most 100100 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.

Interactive visualization

To submit for this subtask, please log in.

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?

Input/Output

Same as subtask 2.

Limits

  • T=100T = 100
  • 1N1011 \le N \le 101
  • K10000000K \le 10\,000\,000
  • The ii-th testcase has N=i+1N=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=1N=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.

Interactive visualization

To submit for this subtask, please log in.

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=100T = 100
  • K400000K \le 400\,000
  • For limits on NN 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 2N72 \le N \le 7.

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

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

    Let AA be the number of operations you need in your solution.
    Let SS be the number of operations of our master solution.
    Then you get the following amount of points:
    25+10tan(arctan(3)max(0,min(1,1AS400000S)))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
    6884068\,840 55
    6884168\,841 54
    8000080\,000 51
    9000090\,000 48
    100000100\,000 46
    200000200\,000 34
    300000300\,000 28
    400000400\,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 400000400\,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).

To submit for this subtask, please log in.

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

Dancing Mice

Mouse Stofl is organizing a stage dance for NN mice. The NN 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=5N=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 N1N-1 can form a pair with mouse 0), and so on.

For each pair of adjacent mice ii and i+1i+1 (or N1N-1 and 00 for i=N1i=N-1), Stofl has prepared a sequence of dance moves that they will perform as a pair, which lasts for tit_i seconds. These moves do not have to be performed as one consecutive segment – for example, if ti=5t_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 ii and i+1i+1 (or N1N-1 and 00 for i=N1i=N-1) to dance as a pair for at least tit_i seconds for each ii.

Input/Output

All subtasks have the same input and output format.

Input

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

  • The first line contains one integer NN, the number of mice.
  • On the second line there are NN integers t0,t1,,tN1t_{0},t_{1},{\dots},t_{N-1}, the durations of the dance moves for each pair of adjacent mice.

Output

For the tt-th test case, output a line containing “Case #t:”, followed by a space and an integer MM: 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 MM 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 NN characters without spaces. If the ii-th mouse is dancing alone, the ii-th character of that string should be a dot (.). If the ii-th mouse is dancing together with the i+1i+1-th mouse (or, in case i=N1i=N-1, with the 0-th mouse), the ii-th character of that string should be a less-than sign (<). If the ii-th mouse is dancing together with the i1i-1-th mouse (or, in case i=0i=0, with the N1N-1-th mouse), the ii-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(1+106)A\cdot(1+10^{-6}), where A is the shortest possible duration.
  • For each ii such that 0<ti0 < t_i, the total duration of the sections where the ii-th and the i+1i+1-th mice dance together (or the N1N-1-th and 0-th for i=N1i=N-1) is at least ti(1106)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.
  • MM is at most 3N3\cdot N.

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

Subtask 1: Three Mice (5 Points)

In this subtask there are only three mice dancing.

Limits

  • T=30T=30.
  • N=3N=3.
  • 0ti1060 \le t_i \le 10^{6} for all 0i<N0\le i<N.
  • For at least one ii, 0<ti0 < 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.

To submit for this subtask, please log in.

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=30T=30.
  • 3N1003 \le N \le 100.
  • ti=1t_i=1 for all 0i<N0\le i<N.

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.50.5 + 0.5).

To submit for this subtask, please log in.

Subtask 3: With a Zero (12 Points)

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

Limits

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

Example

Input:

1
5
1 2 3 2 0

Output:

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

To submit for this subtask, please log in.

Subtask 4: Even Mice (16 Points)

In this subtask the number of mice is even.

Limits

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

Example

Input:

1
6
1 2 3 2 5 1

Output:

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

To submit for this subtask, please log in.

Subtask 5: Odd Mice (57 Points)

In this subtask the number of mice is odd.

Limits

  • T=30T=30.
  • 3N993 \le N \le 99.
  • 0ti1060 \le t_i \le 10^{6} for all 0i<N0\le i<N.
  • For at least one ii, 0<ti0 < t_i.
  • NN 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 ><>.<><

To submit for this subtask, please log in.

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

Ferry Rerouting

https://www.nationsonline.org/gallery/Indonesia/Piaynemo-West-Papua.jpg

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 NN islands currently served by the mouse ferry organization are connected by N1N - 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 N1N - 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 N1N - 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 TT. TT test cases follow.

  • The first line of each test case contains one integer NN, the number of islands.
  • The second and third line contain N1N - 1 numbers each, describing the initial ferry connections. If aia_i is the ii-th number of the first line and bib_i the ii-th number of the second line, then there is initially a ferry connecting the islands aia_i and bib_i for each ii.
  • 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 ii-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=100T=100
  • 1N60001 \le N \le 6\,000
  • 0ai,bi,ci,di<n0 \le a_i, b_i, c_i, d_i < n for all 0i<N0\le i<N
  • 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

To submit for this subtask, please log in.

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.

Input

See subtask 1.

Output

For the ii-th test case print a line “Case #i:” followed by a single integer kk: the minimal number of days needed until all the new connections are in place. Then output kk lines. The jj-th line consists of four integers wj,xj,yjw_j, x_j, y_j and zjz_j, meaning that on day jj, the connection between wjw_j and xjx_j should be replaced by the connection between yjy_j and zjz_j.

Limits

  • T=100T=100
  • 1N1001 \le N \le 100
  • 0ai,bi,ci,di<n0 \le a_i, b_i, c_i, d_i < n for all 0i<N0\le i<N
  • 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

To submit for this subtask, please log in.

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.

Input/Output

See subtask 2.

Limits

  • T=100T=100
  • 1N60001 \le N \le 6000
  • 0ai,bi,ci,di<n0 \le a_i, b_i, c_i, d_i < n for all 0i<N0\le i<N.
  • 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.

To submit for this subtask, please log in.

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 100000100\,000 islands.

Input/Output

See subtask 2.

Limits

  • T=100T=100
  • 1N1000001 \le N \le 100\,000
  • 0ai,bi,ci,di<n0 \le a_i, b_i, c_i, d_i < n for all 0i<N0\le i<N
  • 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.

Grading

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 O(Nlog(N)c)\mathcal O(N\cdot \log(N)^c) (for a constant cc) or O(Nα(N))\mathcal O(N\cdot \alpha(N)), where α(N)\alpha(N) is the inverse Ackermann function. See Introduction to Algorithm Design for explanation of the O\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
O(Nα(N))\mathcal O(N \cdot \alpha(N)) 40
O(Nlog(N))\mathcal O(N \cdot \log(N)) 32
O(Nlog(N)c)\mathcal O(N \cdot \log(N)^c) for c>1c > 1 25

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

To submit for this subtask, please log in.

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

Tinmining

https://www.aljazeera.com/wp-content/uploads/2021/06/2021-06-07T230125Z_628629816_RC2Y6N95MDTJ_RTRMADP_3_INDONESIA-TIN.jpg?resize=1170%2C780

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 NN 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 TT. TT test cases follow in the following format:

  • The first line of the test case contains NN, the number of tin deposits.
  • A second line follows with NN integer values a0,,aN1a_{0},{\dots},a_{N-1}, the different levels of stability in a circular order.

Output

For the ii-th test case, output a line “Case #i: M”, where MM 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 NN numbers, the different levels of stability in a circular manner, compute the size of the optimal choice of worker nodes.

Limits

There are T=100T=100 test cases. In every test case, 1N1001 \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 NN unique numbers in the range [0,N1][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

To submit for this subtask, please log in.

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=100T=100 test cases. In every test case, 1N1000001 \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 NN unique numbers in the range [0,N1][0,N-1].

To submit for this subtask, please log in.

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=100T=100 test cases. In every test case, 1N1001 \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 NN unique numbers in the range [0,N1][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

To submit for this subtask, please log in.

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=100T=100 test cases. In every test case, 1N50001 \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 NN unique numbers in the range [0,N1][0,N-1].

To submit for this subtask, please log in.

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 NN 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 NN unique numbers in the range [0,N1][0,N-1].

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

kNCk \geq \frac{ \sqrt {N} } { C }

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

b) Algorithm depending on kk (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 kk be is the maximal amount of mining nodes that can be used in the optimal solution. Find an algorithm that is fast when kk 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

Grading

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(N3)O(N^{3}) O(N2)O(N^{2}) 5
O(N2logN)O(N^{2}\cdot \log N) O(N)O(N) 15
O(Nk)O(N \cdot k) O(N)O(N) 30

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

To submit for this subtask, please log in.

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

Attempts

# Task Subtask Score Verdict

Junior Ranking

RankUsernameTotal (500)peaks (100)ropeways (100)tshirts (100)clawsort (100)dancing (100)
loading ...

Regular Ranking

RankUsernameTotal (500)tshirts (100)clawsort (100)dancing (100)rerouting (100)tinmining (100)
loading ...