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.

Task | Category | Subtask 1 | Subtask 2 | Subtask 3 | Subtask 4 | Subtask 5 |
---|---|---|---|---|---|---|

stairracing (0/100) | Junior only | 0/25 | 0/25 | 0/25 | 0/25 | |

secretcode (0/100) | Junior only | 0/25 | 0/25 | 0/25 | 0/25 | |

bamboo (0/100) | both | 0/15 | 0/25 | 0/25 | 0/35 | |

batteryfix (0/100) | both | 0/10 | 0/10 | 0/10 | 0/70 | |

lilypads (0/100) | both | 0/15 | 0/25 | 0/20 | 0/40 | |

changifalls (0/100) | Regular only | 0/15 | 0/15 | 0/20 | 0/25 | 0/25 |

satay (0/100) | Regular only | 0/20 | 0/20 | 0/10 | 0/50 |

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.

This year, the first round includes 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 qualify as a junior, you can choose to participate in the Junior or in the Regular category or in both.

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). Furthermore, the 8 best juniors and the 16 best regular participants qualify for our camp in Sarnen. As for the second round, it will be open to the top 20 of the Junior category and the top 40 of the Regular category.

FInally, on top of those already described, two special prizes will be awarded during the SOI Day 2021. First, the Creativity Prize, which will go to the author of the best submission for our creativity task. Second, the Rainbow Award, given to the participant who has solved the first round in the Regular category using the most programming languages. Only the last submission with a strictly positive number of points 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.

The Asian tower running scene began in Raffles City, Singapore in 1987, where Swissotel The Stamford hotel was chosen as the venue of a vertical marathon across a mere 1336 staircase steps.

Mouse Binna is the main organizer of such an event. For this year’s edition, she’d like to organize a *triathlon*: the racing track starts with a vertical downward section, followed by a horizontal section, followed by a vertical upward section. She has already chosen a street through Singapore where she wants to host the event. On each side of the street, there are exactly *N* skyscrapers at unit distance such that each skyscraper on one side of the street is facing another skyscraper on the other side. Mouse Binna knows the height of each skyscraper and she will choose a racing track that has the largest total length, starting on the roof of one of the skyscrapers, going down the stairs to the street, where it will lead to a skyscraper on the other side of the street and end on its roof. The total length of the racing track is given by the sum of heights of the skyscrapers and their distance along the street.

Mouse Binna has chosen a street with only one skyscraper on each side.

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 length
*N*of the street. (Here,*N*= 1.) - The second line contains the height
*a*of the skyscraper on one side of the street. - The third line contains the height
*b*of the skyscraper on the other side of the street.

You should output *T* lines, one for each test case. For the *i*-th test case, output “`Case #i: l`”, where *l* is equal to the maximum length of the racing track Mouse Binna can choose.

*T*= 100*N*= 1- 1 ≤
*a*,*b*≤ 1336

Input:

2 1 2 3 1 1336 1

Output:

Case #0: 5 Case #1: 1337

Comment:

In both cases, there are exactly two possible tracks, both with the same total length. (The racing tracks start on the roof of one of the two skyscrapers, go down to the street and up to the roof of the other skyscraper.)

To submit for this subtask, please log in.

Mouse Binna has chosen a street with two skyscrapers on each side.

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 length
*N*of the street. (Here,*N*= 2.) - The second line contains the heights
*a*_{0}and*a*_{1}of the skyscrapers on one side of the street. - The third line contains the heights
*b*_{0}and*b*_{1}of the skyscrapers on the other side of the street.

Same as subtask 1 – *T* lines of the form “`Case #i: l`”, where *l* is the maximum total length.

*T*= 100*N*= 2- 1 ≤
*a*_{i},*b*_{i}≤ 10^{6}

Input:

3 2 1 1 1 1 2 1336 1336 1 1 2 1 1336 1 1336

Output:

Case #0: 3 Case #1: 1338 Case #2: 2672

Comment:

To submit for this subtask, please log in.

Mouse Binna has chosen a street with up to 1000 skyscrapers on each side.

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 length
*N*of the street. - The second line consists of
*N*numbers*a*_{i}describing the heights of the skyscrapers on one side of the street. - The third line consists of
*N*numbers*b*_{i}describing the heights of the skyscrapers on the other side of the street.

*T*= 100- 1 ≤
*N*≤ 1000 - 1 ≤
*a*_{i},*b*_{i}≤ 10^{6}

Same as subtasks 1 and 2.

Mouse Binna has chosen a street with up to 10^{5} skyscrapers on each side.

Same as subtask 3.

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

Mouse Stofl has recently been interested in the field of cryptography. After learning about different types of encryption protocols, he has decided to invent his own, Stofl’s Secret Hash (SSH). Ideally, the decryption process should be as simple as possible, so that as many mice as possible could receive secure messages. He spent so much time coming up with a complicated encoding method, that he doesn’t know if a simple decoding method even exists.

Stofl decides that a decoding method is simple if he can replace each letter of the alphabet with another letter to retrieve the decrypted cleartext from the encrypted message. This replacement policy is called the translation table of an encryption. For example, if we are given the sentence: “I like cats” by using a translation table that replaces each `c` with an `h`, we recieve the sentence: “I like hats”.

As he wants to give the decoding table to his friends, he found a nice way to write them down. He first writes down the character which `a` will be replaced with, then the one `b` will be replaced with and so on. So if his translation table is `cca`, then `a` gets replaced with `c`, `b` gets replaced with `c` and `c` gets replaced with `a`.

Mouse Stofl would like to know if a simple decoding exists. He decides to start with words only containing the letters `a` and `b`.

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

The first and only line of the testcase consists of two strings. The first string is the encrypted message. The second string is the decrypted cleartext.

For the *i*-th test case, if a valid translation table exists, output a line “`Case #i: Yes`”, followed by a line with a valid translation table. Otherwise, output a line “`Case #i: No`”.

For each translation table, only the first two letters are considered.

There are *T* = 100 test cases.
In every test case, 1 ≤ *L* ≤ 1000, where *L* is the number of letters in a word.

Each word only contains the letters `a` and `b`.

Input:

4 abb baa aaa aba aba aaa bbb bbb

Output:

Case #0: Yes ba Case #1: No Case #2: Yes aa Case #3: Yes ab

Comment:

To submit for this subtask, please log in.

Stofl is now ready to check his encoding methods on words with any letters of the alphabet.

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

The first and only line of the testcase consists of two strings. The first string is the encrypted message. The second string is the decrypted cleartext.

Each word consists of lowercase letters.

For the *i*-th test case, if a valid translation table exists, output a line “`Case #i: Yes`”, followed by a line with a valid translation table. Otherwise output a line “`Case #i: No`”. Note that you need to print the whole translation table (that is, for all lowercase letters), even if some letters are unused.

There are *T* = 100 test cases.
In every test case, 1 ≤ *L* ≤ 1000, where *L* is the number of letters in a word.

Input:

4 abc cab aac abc xyz aaa abc xyz

Output:

Case #0: Yes cabaaaaaaaaaaaaaaaaaaaaaaa Case #1: No Case #2: Yes aaaaaaaaaaaaaaaaaaaaaaaaaa Case #3: Yes xyzaaaaaaaaaaaaaaaaaaaaaaa

Comment:

To submit for this subtask, please log in.

While Stofl invented his encryption protocol, Binna independently developed her own. Both mice decide that a simple decoding method is preferable, however, they disagree on which encryption method should be used. They now want to find translation tables such that their encrypted words decrypt to the same words. Additionally, they want these words to have as many unique letters as possible.

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

The first line contains two integers *N* and *L*, the number of encrypted words (here, always 2) and the length of each word. *N* lines follow describing the encrypted word of each mouse.

Each word consists of lowercase letters.

For the *i*-th test case, output a line “`Case #i: U D`”, where *U* is an integer representing the number of unique letters in the decrypted word and *D* is the decrypted word. After that, *N* lines follow, with the translation table of each mouse.

There are *T* = 100 test cases.
In every test case, *N* = 2 and 1 ≤ *L* ≤ 1000, where *L* is the number of letters in a word.

Input:

2 2 4 milk lime 2 5 motor happy

Output:

Case #0: 4 cake aaaaaaaaaaekcaaaaaaaaaaaaa aaaaeaaaaaackaaaaaaaaaaaaa Case #1: 3 caaar aaaaaaaaaaaacaaaaraaaaaaaa aaaaaaacaaaaaaaaaaaaaaaara

Comment:

To submit for this subtask, please log in.

Mouse Binna and Stofl are so fascinated by the topic that they decide to tell all their friends. Their friends find it equally fascinating and decide to invent their own encryption protocols. Once again, they want to find translation tables and words which can be decrypted from the encrypted words. As before, they want the decodings to have as many unique letters as possible.

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

The first line contains two integers *N* and
*L*, the number of encrypted words and the length of each word. *N* lines follow describing the encrypted word of each mouse.

Each word consists of lowercase letters.

For the *i*-th test case, output a line “`Case #i: U D`”, where *U* is an integer representing the number of unique letters in the decrypted word and *D* is the decrypted word. After that, *N* lines follow with the translation table of each mouse.

There are *T* = 100 test cases.
In every test case, 2 ≤ *N* ≤ 100 and 1 ≤ *L* ≤ 1000, where *L* is the number of letters in a word.

Input:

1 3 5 motor happy ember

Output:

Case #0: 2 aaaar aaaaaaaaaaaaaaaaaraaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaara aaaaaaaaaaaaaaaaaraaaaaaaa

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

This year’s IOI will take place in Singapore and thus Mouse Binna is eager to learn about the traditional way of cutting bamboo. In particular, she wants to train cutting bamboo sticks arranged in a line to a certain height pattern. For the cutting work, she possesses a dao, a single-edged sword from Singapore whose primary use is chopping bamboo. Because there are many bamboo sticks to cut and swinging the dao costs a lot of energy, she would like to perform as few swings as possible. However, cutting the bamboo sticks to the patterned height takes up all of her concentration and she cannot figure out the minimal number of swings needed to cut down the bamboo sticks at the same time. Please help her with this calculation!

You are given the list of the heights in the pattern, *h*_{0}, *h*_{1}…*h*_{N − 1}. Binna is still a beginner in bamboo cutting and thus she can only perform a simple strike technique which allows her, for any *i*, *j* and *h*, to cut all bamboo sticks between *h*_{i} and *h*_{j − 1} down to the height *h*. (Formally, the new height for the bamboo sticks in range *i*, *i* + 1, …, *j* − 1 is the minimum of the previous height and the cutting height *h*.) Initially, all bamboo sticks have infinite height.

When Mouse Binna is starting her training, her endurance is still very weak and she limits the number of bamboo sticks to *N* = 3.

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 length of the pattern. - On the following line, a list is given containing the heights
*h*_{0},*h*_{1}…*h*_{N − 1}of the pattern.

For the *i*-th test case, output a line “`Case #i: S`”,
where *S* is the minimal number of swings that Binna needs to accomplish her task.

There are *T* = 100 test cases.
For every test case:

*N*= 3- 1 ≤
*h*_{i}≤ 100 000.

Input:

2 3 3 2 3 3 5 7 1

Output:

Case #0: 2 Case #1: 3

Comment:

Cut 0: from *h*_{0} to *h*_{2} at height 3 resulting in [3, 3, 3]

Cut 1: from *h*_{1} to *h*_{1} at height 2 resulting in [3, 2, 3]

Cut 0: from *h*_{0} to *h*_{2} at height 7 resulting in [7, 7, 7]

Cut 1: from *h*_{0} to *h*_{0} at height 5 resulting in [5, 7, 7]

Cut 2: from *h*_{2} to *h*_{2} at height 1 resulting in [5, 7, 1]

To submit for this subtask, please log in.

After Mouse Binna successfully completed her first training, she would now like to concentrate on long swings. She doesn’t feel completely comfortable with the dao yet and therefore decides to set the pattern heights to either 1 or 2.

Same as in subtask 1.

There are *T* = 100 test cases.
For every test case:

*N*≤ 300 000- 1 ≤
*h*_{i}≤ 2.

Input:

2 6 1 1 1 1 2 1 5 2 2 1 1 1

Output:

Case #0: 3 Case #1: 2

Comment:

Cut 0: from *h*_{0} to *h*_{5} at height 2 resulting in [2, 2, 2, 2, 2, 2]

Cut 1: from *h*_{5} to *h*_{5} at height 1 resulting in [2, 2, 2, 2, 2, 1]

Cut 2: from *h*_{0} to *h*_{3} at height 1 resulting in [1, 1, 1, 1, 2, 1]

Cut 0: from *h*_{0} to *h*_{4} at height 2 resulting in [2, 2, 2, 2, 2]

Cut 1: from *h*_{2} to *h*_{4} at height 1 resulting in [2, 2, 1, 1, 1]

To submit for this subtask, please log in.

After her second training session, Binna got used to bamboo cutting and wants to further raise the difficulty and removes the height limit of the previous subtask. Even though she was able to improve her endurance during the training, the endurance rests her limiting factor and cutting at many different heights is very energy-sapping. Hence, she limits the number of bamboo sticks to 1000.

Same as in subtask 1.

There are *T* = 100 test cases.
For every test case:

*N*≤ 1000- 1 ≤
*h*_{i}≤ 100 000.

Input:

1 8 8 2 5 2 1 5 5 8

Output:

Case #0: 5

Comment:

Cut 0: from *h*_{0} to *h*_{7} at height 8 resulting in [8, 8, 8, 8, 8, 8, 8, 8]

Cut 1: from *h*_{4} to *h*_{4} at height 1 resulting in [8, 8, 8, 8, 1, 8, 8, 8]

Cut 2: from *h*_{1} to *h*_{6} at height 5 resulting in [8, 5, 5, 5, 1, 5, 5, 8]

Cut 3: from *h*_{3} to *h*_{3} at height 2 resulting in [8, 5, 5, 2, 1, 5, 5, 8]

Cut 4: from *h*_{1} to *h*_{1} at height 2 resulting in [8, 2, 5, 2, 1, 5, 5, 8]

To submit for this subtask, please log in.

After all of those training sessions, Mouse Binna became a true bamboo cutting expert and she is now able to cut patterns for any number of sticks *N*.

Same as in Subtask 1.

There are *T* = 100 test cases.
For every test case:

*N*≤ 300 000- 1 ≤
*h*_{i}≤ 100 000.

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

Mouse Stofl has taken his laptop with him to Singapore to practice for IOI. Unfortunately his computer was built to be resistant against the cold weather (in case he wants to go skiing) but not against the humid hot weather of Southeast Asia and therefore his battery broke. After examining the battery, he realized that he can easily fix the broken battery by connecting the poles, which are placed on a circle, with heat-resistant wires.

After some research he found the rules of the battery:

- There are 2⋅
*N*poles evenly distributed on the circle. - Every pole has a potential level
*p*_{i}between 0 and 2⋅*N*− 1. - Every potential level occurs exactly once.

And the rules he must follow to ensure a running battery:

- Every pole must be connected to exactly one other pole by a wire.
- Wires are not allowed to overlap.
- A wire connecting a pole with potential
*p*_{i}and*p*_{j}has power |*p*_{i}−*p*_{j}|. For the computer to work, the sum of the powers has to be maximized.

If there are several ways to connect the poles correctly, then Stofl can choose any of the correct ways. Help him to figure out how he should wire his broken battery!

The first line contains the number of test cases *T*.
This is followed by *T* test cases in the following format:

The first line of the test case contains *N*, half the number of poles.
A second line follows with a list containing the potential levels *p*_{0}, *p*_{1}, …*p*_{2⋅N − 1}. The list is guaranteed to be a permutation of {0, 1, …, 2⋅*N* − 1}.

(Note: *p*_{0} corresponds to the potential level at the “top” of the circle (like 12 on a clock) and the other levels are in clockwise order.)

For the *i*-th test case, output a line “`Case #i:`”, followed by a description of the wires.
Output *N* lines, each describing a wire by two numbers *a* and *b*, meaning Stofl connects pole *a* and pole *b* by a wire.
Of course, the wiring should follow the above stated rules.
Note: *a* and *b* correspond to the position of the poles, *not* their level.

Stofl wrongly assumes that the potential levels are ordered and therefore asked you first to solve this simpler case.

There are *T* = 100 test cases.
In every test case:

- 1 ≤
*N*≤ 1 000 *p*_{i}=*i*

Input:

2 2 0 1 2 3 1 0 1

Output:

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

Comment:

The solution 0 – 1 and 2 – 3 wouldn’t maximize the sum of powers.

The solution 0 – 2 and 1 – 3 would maximize the sum of powers, but the wires overlap.

This is the only possibility.

To submit for this subtask, please log in.

After realizing his wrong assumption, he now asks you to solve the correct case on a smaller scale.

There are *T* = 100 test cases.
In every test case: 1 ≤ *N* ≤ 10.

Input:

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

Output:

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

Comment:

3 – 0 and 2 – 1 would be also a correct solution.

To submit for this subtask, please log in.

Now Stofl asks you to solve the problem for his computer-sized battery.

There are *T* = 100 test cases.
In every test case: 1 ≤ *N* ≤ 1 000.

Same as Subtask 2.

To submit for this subtask, please log in.

After fixing his computer, Stofl decides to start a battery fixing workshop (when he’s back from IOI). To ensure the safety of other computers, he asks you to prove the correctness of your algorithm. He also asks you to guarantee that your algorithm runs fast enough and uses as little memory as possible.

Describe an algorithm that can solve the task 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.

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, and
- what its running time and memory usage are.

For this task, we give you the option to hand in your solution earlier to receive a feedback. This includes comments on parts of your solution which are unclear and a rough estimate of points. Afterwards, you may adjust your solution and send it in again for more points.

To receive feedback, you have to submit a solution before 30.10.2020 23:59. If you have submitted a solution, you will get a feedback for it on 02.11.2020.

If everything is correct, we will give you points based on the table below.

Running time | Memory usage | Max score |
---|---|---|

O(N^{2}) |
O(N^{2}) |
15 |

O(N⋅logN) |
O(N⋅logN) |
30 |

O(N) |
O(N) |
40 |

O(N⋅logN) |
O(logN) |
60 |

O(N⋅logN) |
O(1) |
70 |

If you are not familiar with the *O*() notation, you can read about it here.

Note: You can assume that the input is given as a read-only array, which means you can’t change the values. This array doesn’t count to your memory, so only additional memory counts to your memory analysis.

Try to send in your solution, even if it is incomplete or slow. We also award partial points for crucial observations which are helpful to solve the task.

To submit for this subtask, please log in.

Note: This story is fictional. Don’t try to fix your batteries at home this way!

The Singapore river is full of lily pads, all neatly ordered in a line. Frog Pepe discovered that they are very bouncy and wants to use them to jump around.

By jumping on the i-th lily pad, Frog Pepe can bounce to any lily pad
that’s between *a*_{i} to *b*_{i} steps away from it. In other words by
jumping on lily pad *i* (0 ≤ *i* < *N*) he can reach all lily pads *j*
(0 ≤ *j* < *N*) with *a*_{i} ≤ |*i* − *j*| ≤ *b*_{i}.

Frog Pepe starts on lily pad *S*.
Help him reach lily pad *F* in as few as bounces as possible.

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

- the first line contains,
*N*,*S*and*F*– the number of lily pads, the index of the start lily pad, and the index of the target lily pad. - the second line contains
*N*numbers*a*_{i}, the minimal bounciness of the*i*−*th*lily pad. - the third line contains
*N*numbers*b*_{i}, the maximal bounciness of the*i*−*th*lily pad.

For the *i*-th test case print a line “`Case #i:`” followed by a
single integer: the minimal number of jumps to go from *S* to *F*.
If it is impossible to get from *S* to *F*, print -1 instead.

In all subtasks:

- There are
*T*= 100 test cases. - 0 ≤
*S*,*F*<*n*. - 1 ≤
*a*_{i}≤*b*_{i}≤*n*for all*i*.

1 ≤ *N* ≤ 100 and *a*_{i} = 1 for all *i*.

To submit for this subtask, please log in.

1 ≤ *N* ≤ 10^{6} and *a*_{i} = 1 for all *i*.

To submit for this subtask, please log in.

Jewel Changi is a nature-themed entertainment complex on the landside of Changi Airport in Singapore. Its centrepiece is the world’s tallest indoor waterfall, the Rain Vortex, which is surrounded by a terraced forest setting.

While visiting Jewel Changi on her way to IOI, Mouse Binna was impressed by the architecture of the terraced forest setting, and she especially enjoyed the looks of the waterfalls. Binna was wondering if one could build an even bigger waterfall within the Jewel Changi, and suddenly she could be found mapping out the whole area and calculating the perfect location for a waterfall.

Jewel Changi consist of multiple terraces in the shape of a circle, the predominant shape in its architecture. Terraces are flat areas delimited by walls. Terraces can be nested, i.e. some platform can reside inside another platform, but they never intersect.

Mouse Binna only considers waterfalls that are not too long, meaning
they can pass through at most *L* terraces that are successively
receding. Formally, let *t*_{0}, …, *t*_{k − 1} be a sequence of
terraces. It is a viable location of a waterfall exactly when:

*k*≤*L*, i.e. it flows through at most*L*terraces.*t*_{i}and*t*_{i + 1}are adjacent terraces, meaning either*t*_{i}is directly inside*t*_{i + 1}or vice versa.- The water always flows down, meaning the height of terrace
*t*_{i}must be strictly larger than the one of*t*_{i + 1}.

The height difference of a waterfall is the difference of altitudes
from terrace *t*_{0} to terrace *t*_{k − 1}.

Since Binna is already exhausted from mapping out the area, help her figure out the maximum height difference.

Based on a quick glance, Binna assumed that all circles have the center at the Rain Vortex at location (0, 0). She thinks this can give her a good idea of the height difference already.

The first line contains the number of test cases *T*.
*T* test cases follow. The first line of each test case contains
two integers *N* and *L*, the number of platforms and the maximum
length. The following *N* lines contain 4 numbers each: *x*_{i}, *y*_{i},
*r*_{i} and *h*_{i}, meaning that the *i*-th terrace has center at
coordinate (*x*_{i}, *y*_{i}), its radius is *r*_{i} and the altitude is *h*_{i}.

Note that in this subtask, *x*_{i} = *y*_{i} = 0.

For the *i*-th test case print a line “`Case #i:`” followed by a
single integer: the maximum height difference of a viable waterfall.

*T*= 100.- 1 ≤
*L*≤*N*≤ 1 000 000. - 0 ≤
*h*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. - 1 ≤
*r*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. *x*_{i}=*y*_{i}= 0 for all 0 ≤*i*<*N*. This is the special restriction for subtask 1.

Input:

3 5 3 0 0 0 3 0 0 1 2 0 0 2 1 0 0 3 4 0 0 4 1 5 3 0 0 1 4 0 0 4 3 0 0 0 1 0 0 2 1 0 0 3 2 6 4 0 0 340073108 5 0 0 355849419 20 0 0 706293447 21 0 0 809063052 72 0 0 878401727 14 0 0 999963596 29

Output:

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

To submit for this subtask, please log in.

Taking a closer look, Mouse Binna noticed that not all circles
actually are centered at (0, 0). However, she noticed another trend:
smaller circles have smaller altitude. In fact, Binna discovered that
the approximately coincide, i.e. *r*_{i} ≈ *h*_{i} and she decides to
compute the maximum height difference using that approximation.

Same as subtask 1.

*T*= 100.- 1 ≤
*L*≤*N*≤ 1000. - 0 ≤
*h*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. - 1 ≤
*r*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. - − 10
^{9}≤*x*_{i},*y*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. *r*_{i}=*h*_{i}for all 0 ≤*i*<*N*. This is the special restriction for subtask 2.

To submit for this subtask, please log in.

Mapping out the airport a second time, it turns out that none of the assumptions from before actually hold.

Same as subtasks 1 and 2.

*T*= 100.- 1 ≤
*L*≤*N*≤ 1000. - 0 ≤
*h*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. - 1 ≤
*r*_{i}≤ 10^{9}for all 0 ≤*i*<*N*. - − 10
^{9}≤*x*_{i},*y*_{i}≤ 10^{9}for all 0 ≤*i*<*N*.

To submit for this subtask, please log in.

After a full day of measuring, Binna finally produced high-detail
maps with up to *N* = 10^{6} terraces.

Before she starts computing waterfall location, Binna wants to do some preparation work: for each terrace, she wants to know the index of its adjacent outer terrace.

Similar to subtasks 1, 2 and 3, but this time the *L* is missing,
since it’s not needed.

Let’s denote the outer terrace of *i* as *p*_{i}. If *i* is already
the outer-most terrace, *p*_{i} = − 1.

For each test case, output a single number, the hash of all outputs:

*T*= 100.- 1 ≤
*L*≤*N*≤ 1 000 000. - Same limits for
*h*_{i},*r*_{i},*x*_{i}and*y*_{i}as subtask 3.

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*(*n*) (or *O*(*n*log*n*) or *O*(*n*(log*n*)^{2})). See Introduction to Algorithm Design on what those symbols mean.

Unless you exploit how the tests are generated or were squeezing your solution through the time limit, you should be fine.

*Note*: We need around 20sec to generate the input (depending on your
browser and machine) and another 20sec to verify your submission.
Please be patient.

To submit for this subtask, please log in.

Finally, time has come to compute the perfect location for the waterfall. Mouse Binna is very excited and has already decided to call it the “Changi Falls”. Can you help Mouse Binna one last time?

The first line contains the number of test cases *T*.
*T* test cases follow. The first line of each test case contains an
two integers *N* and *L*, the number of platforms and the maximum
length. The following *N* lines contain 5 numbers each: *x*_{i}, *y*_{i},
*r*_{i}, *h*_{i} and *p*_{i}, meaning that the *i*-th terrace has center at
coordinate (*x*_{i}, *y*_{i}), its radius is *r*_{i} and the altitude is *h*_{i}
and its outer terrace has index *p*_{i} (where *p*_{i} = − 1 if it is already
outer-most).

The *p*_{i} correspond to the output of subtask 4, looking at them is
optional, but intended as help.

Same as subtasks 1, 2 and 3.

*T*= 100.- 1 ≤
*L*≤*N*≤ 1 000 000. - Same limits for
*h*_{i},*r*_{i},*x*_{i}and*y*_{i}as subtask 3.

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*(*n*) (or *O*(*n*log*n*) or *O*(*n*(log*n*)^{2})). See Introduction to Algorithm Design on what those symbols mean.

Unless you exploit how the tests are generated or were squeezing your solution through the time limit, you should be fine.

*Note*: We need around 20sec to generate the input (depending on your
browser and machine) and another 20sec to verify your submission.
Please be patient.

To submit for this subtask, please log in.

Satay is a traditional Singaporean dish that consists of meat stripes that are grilled on a skewer. It is often served with peanut sauce and pieces of cucumber and onion.

A group of *N* mice hast just eaten some Satay and they’re left with just the skewers.
Each mouse is holding exactly one skewer. The mice figured it would probably
be easiest to hand all skewers to one mouse, so that only that mouse has
to look for a waste bin.

Some pairs of mice are standing next to each other. The mice want to avoid accidentally hitting bystanders with skewers, so only mice that are standing next to each other may hand skewers to each other. It just so happens that for every pair of mice, there is a unique way of passing skewers from the first mouse to the second mouse, possibly via some other mice.

Whenever a mouse hands skewers to another mouse, there is a risk that the mouse might accidentally drop the skewers. Mouse Stofl has estimated that the risk of dropping the skewers is equal to the number of skewers that were passed. Dropping the skewers is very embarrassing, so you want to minimize the total risk. Can you figure out how to get all skewers to the same mouse?

The first line contains the number of test cases *T*.
*T* test cases follow, each test case consists of three lines.
The first line contains an integer *N* – the number of mice in the group.
The second line contains *N* − 1 integers *a*_{1}, …, *a*_{N − 1} and
the third line contains *N* − 1 integers *b*_{1}, …, *b*_{N − 1}.
For *i* = 1, …, *N* − 1, the mice *a*_{i} and *b*_{i} are standing next to each other.

It is guaranteed that for every pair of distinct mice *a* and *b*,
there is an integer *k* and a unique sequence *a* = *m*_{1}, …, *m*_{k} = *b*
of distinct mice such that *m*_{i} and *m*_{i + 1} are standing next to each
other for all *i*.

For the *i*-th test case, print a line “`Case #i:`” followed by
a single integer: the minimum total risk needed to pass all skewers
to a single mouse.

*T*= 100- 2 ≤
*N*≤ 100 - 0 ≤
*a*_{i},*b*_{i}<*N*

Input:

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

Output:

Case #0: 3 Case #1: 9

Comment:

In case #0, all mice are standing next to mouse 0 and it is optimal to have mouse 0 collect all skewers.
In case #1, there are multiple optimal solutions. You can collect all skewers at mouse 2 or at mouse 3.

To submit for this subtask, please log in.

The mice successfully managed to throw away all skewers without dropping any of them. The Satay was very delicious, so they decided to have some Satay with peanut sauce. The peanut sauce was served on a small plate, so now the mice have to deal with both the skewers and the plates. Mouse Stofl wasn’t happy with how long it took the mouse in subtask 1 to find the trash, so this time, he wants to do it himself.

At the moment, every mouse is holding a plate with a skewer on top of it, and the goal is to get all plates and skewers to Mouse Stofl. Having skewers below or between plates make the stack of plates very unstable, which would greatly increase the risk of dropping the plates, so the mice want to avoid this at all costs.

Unfortunately, the plates are quite heavy, which means the mice have to use
both hands to hold the plates. This severely limits their options:
If two mice are standing next to each other,
the first mouse can always pass any number of skewers to the next mouse.
Additionally, if the second mouse is not holding any skewers,
the first mouse may pass all of its skewers and any number of plates
to the second mouse.
Mouse Stofl estimates that the risk of dropping something
if *x* skewers and *y* plates are passed to another mouse
is *S*⋅*x* + *P*⋅*y* for some constants *S* and *P*.

Can you figure out the least risky way of getting all skewers and all plates to Stofl?

The first line contains the number of test cases *T*.
*T* test cases follow, each test case consists of three lines.
The first line contains three integers *N*, *S* and *P* – the number of mice
in the group and two parameters describing the risk of passing
skewers and plates.
The second line contains *N* − 1 integers *a*_{1}, …, *a*_{N − 1} and
the third line contains *N* − 1 integers *b*_{1}, …, *b*_{N − 1}.
For *i* = 1, …, *N* − 1, the mice *a*_{i} and *b*_{i} are standing next to each other.

It is guaranteed that for every pair of distinct mice *a* and *b*,
there is an integer *k* and a unique sequence *a* = *m*_{1}, …, *m*_{k} = *b*
of distinct mice such that *m*_{i} and *m*_{i + 1} are standing next to each
other for all *i*.

For the *i*-th test case, print a line “`Case #i:`” followed by
a single integer: the minimum total risk needed to pass all skewers and plates
to mouse Stofl (mouse 0).

*T*= 100- 2 ≤
*N*≤ 10^{5} - 1 ≤
*S*,*P*≤ 10^{5} - 0 ≤
*a*_{i},*b*_{i}<*N*

Input:

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

Output:

Case #0: 22 Case #1: 66 Case #2: 48

Comment:

In Case #0, the mice could proceed as follows: Pass one skewer from mouse 1 to mouse 0, then pass two skewers from mouse 0 to mouse 2. After these two steps, all skewers are held by mouse 2. Then pass one plate from mouse 1 to mouse 0 and finally, pass three skewers and one plate from mouse 2 to mouse 0.

To submit for this subtask, please log in.

While mouse Stofl is busy trying to find a trash can, the remaining mice decide to have some more Satay. Can you help them figure out the least risky way of dealing with the plates and skewers afterwards?

The situation is the same as in subtask 2, but there is no mouse Stofl, so you can pick the mouse that collects all the plates and skewers.

Same as in subtask 2.

For the *i*-th test case, print a line “`Case #i:`” followed by
a single integer: the minimum total risk needed to pass all skewers
and all plates to a single mouse.

*T*= 100- 2 ≤
*N*≤ 10^{5} - 1 ≤
*S*,*P*≤ 10^{5} - 0 ≤
*a*_{i},*b*_{i}<*N*

Input:

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

Output:

22 48 38

Comment:

In Case #0, having mouse 0 collect everything carries the least risk.
In Case #1, there are multiple optimal solutions, where either mouse 1 or mouse 2 collects everything.

To submit for this subtask, please log in.

Mouse Stofl is nowhere to be seen, but the mice are still hungry, so they go for some more Satay. This in turn gives them more skewers and plates to deal with, so they again ask you to help them minimize the risk of dropping them.

This is a theoretical subtask. Describe an algorithm that can solve subtask 3 and analyze its running time and memory usage.

You should optimize for *running time* first and *memory usage* second.

Hand in a document (preferably PDF) that describes

- how your algorithm works,
- why your algorithm is correct. In particular, you should explain why your answer is
*feasible*, i.e. describe a strategy for the mice that achieves the total risk you output, and explain why your answer is*optimal*, i.e. show that there is no strategy that results in less total risk. - how much time and memory it uses.

*N*,*S*,*P*are variables. You can assume that basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform and that storing one integer uses a single unit of memory.- To get full points for this subtask, you should aim for
*O*(*N*) runtime and*O*(*N*) memory.

To submit for this subtask, please log in.

# | Task | Subtask | Score | Verdict |
---|

Rank | Username | Total (500) | stairra… (100) stairracing | secretcode (100) | bamboo (100) | batteryfix (100) | lilypads (100) |
---|---|---|---|---|---|---|---|

loading ... |

Rank | Username | Total (500) | bamboo (100) | batteryfix (100) | lilypads (100) | changif… (100) changifalls | satay (100) |
---|---|---|---|---|---|---|---|

loading ... |