Qualification Round 2024/2025 - Swiss Olympiad in Informatics

Overview

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

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

Category	Task	Total	Subtask 1	Subtask 2	Subtask 3	Subtask 4	Subtask 5
Junior only	cheesemachine	‒/100	‒/10	‒/13	‒/17	‒/26	‒/34
Junior only	rotation	‒/100	‒/10	‒/16	‒/11	‒/27	‒/36
Both	landscaping	‒/100	‒/13	‒/19	‒/17	‒/22	‒/29
Both	trampoline	‒/100	‒/8	‒/14	‒/29	‒/14	‒/35
Both	train	‒/100	‒/23	‒/15	‒/20	‒/16	‒/26
Both	hikingsigns	‒/100	‒/13	‒/15	‒/16	‒/27	‒/29
Regular only	circuit	‒/100	‒/20	‒/20	‒/20	‒/20	‒/20
Regular only	cakeicing	‒/100	‒/10	‒/15	‒/75
Regular only	qrh	‒/100	‒/25	‒/25	‒/25	‒/25

Tips

You may use any programming language to solve the tasks of the Qualification 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 macOS, you can do that by using the command ‘yourprogram < inputfile’, replacing ‘yourprogram’ and ‘inputfile’ by the paths to the actual program and input file). More elaborate explanations about how to solve the tasks of the Qualification 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 about algorithmics. It’s a great opportunity to learn all you need for the Qualification 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 Qualification 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.

You qualify for the finals and the Sarnen Camp if you are placed under the

top 8 of the Junior category, and/or
top 16 of the Regular category.

Additionally, we may distribute wildcards.

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

Cheese Machine

Binna designed a new machine to produce the best cheese throughout Mouseland. She is now testing it to make sure the cheese produced is in fact the best you can find before revealing the machine to the public. Each second, she notes down the results of her test: a number which combines the flavor of the cheese, the size of the cheese, the time elapsed since the machine was turned on, and the quantity of cheese produced. After gathering some amount of data, she would like to know if there is an anomaly in the results she received. If such an anomaly occurred, she would need to dismantle the machine to fix the issue. If no anomaly occurred, then the machine should be working correctly and she would like to predict the next result she should receive.

The machine’s output is easily predictable if the machine is working correctly. In fact, if everything works correctly, the machine’s result should always increase or always decrease by the same amount each second. An anomaly has occurred if the results Binna received don’t respect this rule at some point.

Knowing that, could you tell Binna if the machine produced an anomaly or, in the case no anomalies are detected, which result $P$ she should receive next?

Input/Output

All subtasks have the same input and output format.

Input

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

The first line contains one positive integer $N$ , the number of second Binna ran her test.
The second line contains $N$ integers, the $i$ -th one, $R_i$ , corresponding to the result she got after the $i$ -th second.

Output

For the $t$ -th testcase, output a single line:

If an anomaly was detected, output Case #t: NO.
If no anomalies were found, output Case #t: followed by $P$ , the predicted result Binna should receive next.

Subtask 1: A small test (10 points)

Binna only ran her test for two seconds because she didn’t want to stress her machine too much, and was eager to try the first wheel of cheese her machine produced.

Limits

$T=100$
$N=2$
$-10^{6}\le R_i \le 10^{6}$

Example

Input:

Output:

Case #0: 3
Case #1: 20
Case #2: 0
Case #3: -15
Case #4: 42

Comment:

Case #0: The first result is

1

and the second is

2

. Because the difference between

1

and

2

1

, the next result Binna should receive

3

Case #1: The first result is

10

and the second is

15

. Because the difference between

10

and

15

5

, the next result Binna should receive

20

Case #2: The first result is

10

and the second is

5

. Because the difference between

10

and

5

-5

, the next result Binna should receive

0

To submit for this subtask, please log in.

Subtask 2: Small test, no problems (13 points)

Binna improved her machine and assures you that no anomalies were produced during her test, but she only ran it for three seconds.

Limits

$T=100$
$N=3$
$-10^{6}\le R_i \le 10^{6}$
No anomalies are present in the results.

Example

Input:

Output:

Case #0: 25
Case #1: -2
Case #2: 42

Comment:

Case #0: The first result is

10

, the second

15

and the third

20

. Because the difference between any two consecutive results is always

5

, the result Binna should receive is

25

Case #2: All three results are

42

. Because the difference between any two results is always

0

, the result Binna should receive is again

42

To submit for this subtask, please log in.

Subtask 3: Imprecise machine (17 points)

Binna didn’t like the taste of the cheese produced by her last machine. Unfortunately, her machine wasn’t perfect after all, even if she didn’t catch any anomalies. Because of an urgent meeting, Binna was once again only able to test her machine for three seconds before leaving. However, her test has a great chance to contain anomalies because of the bad taste.

Limits

$T=100$
$N=3$
$-10^{6}\le R_i \le 10^{6}$

Example

Input:

Output:

Case #0: NO
Case #1: 25
Case #2: 42

Comment:

Case #0: An anomaly is detected since the difference between

10

and

12

2

but the one between

12

and

15

3

To submit for this subtask, please log in.

Subtask 4: Finally a perfect machine (26 points)

Binna worked really hard on this new prototype and it now works perfectly. Thus, the test she ran doesn’t contain any anomalies. She also learned from her mistakes and ran the test for much longer than before.

Limits

$T=100$
$2 \le N \le 1000$
$-10^{6}\le R_i \le 10^{6}$
No anomalies are present in the results.

Example

Input:

4
4
9 12 15 18
5
10 15 20 25 30
3
9 7 5
2
42 42

Output:

Case #0: 21
Case #1: 35
Case #2: 3
Case #3: 42

Comment:

Case #0: Because the difference between two consecutive results is always

3

, the next result Binna should receive is

21

To submit for this subtask, please log in.

Subtask 5: The machine needs fixing (34 points)

Binna’s last machine was used so many times to produce cheese for the entire population of Mouseland that some parts broke. After fixing them, the machine unfortunately doesn’t work as well as before and may produce some anomalies when testing it.

Limits

$T=100$
$2 \le N \le 1000$
$-10^{6}\le R_i \le 10^{6}$

Example

Input:

4
4
10 12 15 18
5
10 15 20 25 30
3
9 7 5
2
42 42

Output:

Case #0: NO
Case #1: 35
Case #2: 3
Case #3: 42

Comment:

Case #0: Because the difference between

10

and

12

2

but the difference between all the other consecutive results is always

3

, an anomaly occurred during the test.

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

Rotation

https://upload.wikimedia.org/wikipedia/commons/2/27/Gouffre-v-hdr.jpg

Gouffre de Padirac sinkhole, Photo By Gerald Fauvelle - CC BY-SA 4.0.

Disaster strikes! Stofl was going for a hike in the rainforest when he fell down a sinkhole and ended up trapped in an underground tomb. In the center of the room there is a huge wheel with $N$ letters on it. Stofl can rotate the wheel however he likes as well as swap letters. Only once all the letters are brought into the correct position and the wheel is brought into the correct orientation will the door unlock. Stofl has found some clues on the walls but is not quite sure of the correct solution, so he would like to try out a few modifications and then check what letters are in specific positions on the wheel. Help him by writing a program that can simulate repeatedly rotating the wheel and repeatedly swapping two letters on the wheel and can answer his questions about what letter is currently located at a given position.

Formally the task can be formulated as follows: You are given a string $S$ consisting of $N$ lowercase letters and $Q$ rituals. Each ritual is one of the following types:

Print the $i$ -th character of $S$ .
Swap the two characters at indices $i$ and $j$ in the string.
Perform the following operation $K$ times in a row: delete the last character of $S$ and append it to the beginning (Rotate the wheel by $K$ ).

Input and Output

Input

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

The first line contains two integers, $N$ and $Q$ , the length of the string $S$ and the number of rituals.
On the second line is the string $S$
The next $Q$ lines describe Stofl’s rituals. The first integer is the type of the ritual, which is either $1$ , $2$ , or $3$ .
- If the ritual is of type $1$ , a second integer $i$ follows, the index whose element that Stofl wants to query.
- If the ritual is of type $2$ , two integers $i$ and $j$ follow, the two indices whose elements Stofl wants to swap.
- If the rital is of type $3$ , a second integer $K$ follows, how far Stofl wants to rotate the wheel.

Visualization

Ritual type $2$ is performed transforming $S$ = “programming” into $S'$ = “prmgramoing” ( $i=2$ and $j=7$ ):

Ritual type $3$ is performed transforming $S$ = “programming” into $S'$ = “ngprogrammi” ( $K=2$ ):

-> ->

Output

For the $i$ -th test case, print a line “Case #i:” followed by a string of lowercase letters where the $i$ -th character of the string is the answer to the $i$ -th ritual of type $1$ .

Subtask 1: No modifications (10 Points)

To make sure that you know what you are doing, Stofl wants to test you first whether you can accurately answer rituals whose answers he already knows, namely questions about the original, unmodified wheel. Therefore, in this subtask there are no rituals of types $2$ and $3$ .

Limits

$T=100$
$1 \le N \le 100\,000$
$1 \le Q \le 10\,000$
$0 \le K \le N$
All rituals are of type $1$

Example

Input:

Output:

Case #0: sios
Case #1: ibna
Case #2: memous

Comment:

The first line with “3” indicates that there are three test cases. The next two lines are “3 4” and “soi” and describe the

N

Q

and

S

of the first (”Case #0”) of the four test cases. The next four lines are the rituals of that test case. For each ritual the first number indicates the type of ritual and the second number is the index of the letter to be returned for that ritual.

To submit for this subtask, please log in.

Subtask 2: Small Wheel (16 Points)

Mouse Stofl has found another smaller wheel inside the tomb which must also be solved to open the door. As this one is easier, Stofl will solve this one first. He could do it on his own, but to reassure him of your programming skills (after all, his life is on the line), he still asks you to simulate his rituals and will give you questions to answer.

Limits

$T=100$
$1 \le N, Q \le 100$
$0 \le K \le N$

Example

Input:

Output:

Case #0: jpp
Case #1: wwemaw

Comment:

Case #0: The first ritual transforms the string in the following way: “pjp” -> “ppj” -> “jpp”. The second ritual swaps the characters at index

1

and

2

, but as they are both identical, the string remains unchanged.

To submit for this subtask, please log in.

Subtask 3: No rotations (11 Points)

Now assured that your program is correct, Stofl will start solving the large wheel. His strategy is to initially only swap some letters and only in later subtasks to rotate the wheel. Again, simulate his operations and answer his queries.

Limits

$T=100$
$1 \le N \le 10^{7}$
$1 \le Q \le 10^{6}$
$0 \le K \le N$
There are no queries of type $3$

Example

Input:

Output:

Case #0: siosisoi
Case #1: binan
Case #2: meeouo

To submit for this subtask, please log in.

Subtask 4: No swaps (27 Points)

Now that most letters are in the correct positions, Stofl must rotate the wheel into the correct orientation. As the wheel is very large, he can’t see most of the letters on the other side. Help him by again simulating the rotations he makes and answering his questions.

Limits

$T=100$
$1 \le N \le 10^{7}$
$1 \le Q \le 10^{6}$
$0 \le K \le N$
There are no queries of type $2$

Example

Input:

Output:

Case #0: blubblub
Case #1: flsto

Comment:

Note that the operation in ritual

3

can also be performed zero times, as is the case here.

To submit for this subtask, please log in.

Subtask 5: Escape (36 Points)

To finish solving the wheel, Stofl will need you to be able to handle all three types of rituals.

Limits

$T=100$
$1 \le N \le 10^{7}$
$1 \le Q \le 10^{6}$
$0 \le K \le N$

Example

See Subtask 2.

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

Landscaping

An image of a pyramid-shaped mountain in Boliva

A picture of a pyramid-shaped mountain in Bolivia

Still mesmerized by the pyramids Mouse Binna saw while participating at the MOI (Mouse Olympiad in Informatics) last year in Egypt, she concludes that the world needs more pyramids! Inspired by a picture of a pyramid-shaped mountain in Bolivia, Mouse Binna is determined to try and carve out such mountains herself once she gets there.

Having learned that simplification is a vital problem solving technique, Mouse Binna decides to make use of it here by modeling the terrain as a list of $N$ heights given as $h_{0}, h_{1}, h_{2}, {\dots}, h_{N-1}$ .

The goal is to form a pyramid out of the terrain by making it into a pyramid sequence. A pyramid sequence is defined as a list of integers of the form $1, 2, {\dots}, k-1, k, k-1, {\dots}, 2, 1$ .

After wasting investing countless hours looking for the most efficient digging techniques, Mouse Binna concludes it is best to use a combination of two different landscaping methods.

The first technique makes use of lots of explosive power (who would have thought) to blow the terrain down to the ground at some position. Being afraid of the dangers this method might entail, Mouse Binna decides to use it cautiously and only at either of the ends of the terrain, not somewhere in the middle. In terms of the list, this operation can be used to remove the first or the last element in current the array.
The second technique, while quite a lot safer, certainly not as fun, uses a chisel to slowly dig away at a part of the terrain. In terms of the array, this operation decreases the height of the terrain $h_i$ by $1$ at some position $i$ .

Since Mouse Binna is ready to use all means necessary to create the best pyramid mountains, both operations can be performed any number of times. Can you help Mouse Binna by carving out the biggest pyramid mountains?

Subtask 1 (13 points)

Mouse Binna is looking at a hillside and wants to know whether it already forms a pyramid mountain, without applying any of the landscaping methods just yet.

Input

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

The first line of the test case contains $N$ , the number of tiles. On the second line $N$ values $h[i]$ follow, where the $i$ -th value is the height of the terrain at position $i$ .

Output

For the $i$ -th test case, output a line “Case #i: YES/NO” depending if the list of numbers forms a valid pyramid sequence.

Limits

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

Example

Input:

Output:

Case #0: YES
Case #1: NO

Comment:

Case #0: In this case, the numbers form a valid pyramid sequence.

Case #1: Here, the numbers do not form a valid pyramid sequence as the last integer should be a 1, some landscaping is still needed.

To submit for this subtask, please log in.

Subtask 2 (19 points)

In this subtask, Mouse Binna wants to start carving up some mountains. To start of, however, she only wants to test out her first technique (the explosive one), i.e. you are only allowed to perform operations of type 1 on the list. Can you help her form the longest pyramid sequences?

Input

Same as subtask 1.

Output

For the $i$ -th test case, output a line “Case #i: l”, where $l$ is the length of the longest pyramid mountain that can be formed by landscaping.

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 1000$ and $h_i \le 10^{9}$ . You are only allowed to perform operations of type 1.

Example

Input:

2
5
5 1 2 1 1
7
1 2 1 2 3 2 1

Output:

Case #0: 3
Case #1: 5

Comment:

Case #0: In this case, removing the first and last element in the list yields a valid pyramid sequence.

Case #1: While there are multiple possible pyramid sequences that can be formed, removing the first two elements gives a sequence of length 5, which is the longest possible.

To submit for this subtask, please log in.

Subtask 3 (17 points)

Similar to the previous subtask, Mouse Binna now wants to try the second landscaping method. Or in other words, you are only allowed to perform operations of type 2 in this subtask.

Input & Output

Same as subtask 2.

Limits

Same as in subtask 2, but now you are only allowed to perform operations of type 2.

Example

Input:

Output:

Case #0: 3
Case #1: 5

Comment:

Case #0: Decreasing the last element in the list results in a valid pyramid sequence.

Case #1: Here, a valid pyramid sequence can be formed by decreasing the second-to-last element twice.

To submit for this subtask, please log in.

Subtask 4 (22 points)

Being satisfied by the results from the previous tests, Mouse Binna now wants to use both techniques in conjunction to carve out the biggest pyramid mountains possible.

Input & Output

Same as subtask 2.

Limits

Same as subtask 2, but now you can perform operations of type 1 and 2.

Example

Input:

2
4
1 1 2 2
6
1 2 3 3 2 3

Output:

Case #0: 3
Case #1: 5

Comment:

Case #0: In the first case, the longest pyramid sequence can be formed by removing the first element in the list and decreasing the last element by 1.

Case #1: In the second case, there are multiple possible solutions. Either the first or the last element in the list can be removed and then the other numbers can be decreased accordingly.

To submit for this subtask, please log in.

Subtask 5 (29 points)

In this final subtask, Mouse Binna wants to apply her plans on even bigger mountains.

Input & Output

Same as subtask 2.

Limits

Same as subtask 4, but now $N \le 10^{6}$ .

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

Trampoline

Mouse Stofl is going to visit an amusement park. He is very excited to go to his favorite attraction, the trampoline park.

There are $n$ trampolines in a line. Each trampoline has a jumpiness value associated with it. More formally, the $i$ -th trampoline has a jumpiness value of $j_i$ . Jumping on the $i$ -th trampoline will launch Stofl up and Stofl will land on exactly the $i+j_i$ -th trampoline, where Stofl will continue jumping, until he reaches the $n-1$ -th trampoline where he stops. All trampolines have a jumpiness $>0$ except the $n-1$ -th one which has jumpiness $0$ . It is guaranteed that $i+j_i<n$ for all $i$ , meaning that Stofl will never jump past the last trampoline.

Input/Output

All subtasks have the same input and output format.

Input

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

The first line contains one positive integer $n$ , the number of trampolines in the park.
The second line contains $n$ integers, the $i$ -th one, $j_i$ , corresponding to the jumpiness of the $i$ -th trampoline.

Output

For the $t$ -th testcase, output a single line containing “Case #t: x” where $x$ is equal to the maximum number of trampolines Stofl can visit.

Subtask 1: From the beginning (8 points)

How many trampolines Stofl can visit if he starts at the first trampoline?

Limits

$1\le n\le 100$

Example

Input:

Output:

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

Comment:

Case #0: Stofl will visit the first and the last trampolines.
Case #1: Stofl can visit all trampolines.
Case #2: Stofl will visit first three trampolines and the last one.

To submit for this subtask, please log in.

Subtask 2: From the optimal trampoline (14 points)

How many trampolines Stofl can visit if he selects the starting trampoline optimally?

Limits

$1\le n\le 100$

Example

Input:

Output:

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

Comment:

Case #0: Stofl can visit all trampolines if he starts from the first trampoline.
Case #1: If Stofl starts from the second trampoline, he visits the second, third and fourth trampolines.
Case #2: If Stofl starts from the second trampoline, he visits the second, third and fifth trampolines.

To submit for this subtask, please log in.

Subtask 3: More trampolines (29 points)

The subtask is the same as subtask 2, but with more trampolines.

Limits

$1\le n\le 200\,000$

Example

Input:

Output:

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

Comment:

Case #0: Stofl can visit all trampolines if he starts from the first trampoline.
Case #1: If Stofl starts from the second trampoline, he visits the second, third and fourth trampolines.
Case #2: If Stofl starts from the second trampoline, he visits the second, third and fifth trampolines.

To submit for this subtask, please log in.

Subtask 4: Adjusting one trampoline (14 points)

Stofl can choose the starting trampoline optimally, but he can also adjust the jumpiness of exactly one (any) trampoline with any jumpiness he likes.

Limits

$1\le n\le 100$

Example

Input:

Output:

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

Comment:

Case #0: Stofl can visit all trampolines if he changes the jumpiness of the first trampoline to 111.
Case #1: Stofl can change the jumpiness of the second trampoline to 111, start from the second trampoline and visit all trampolines except the first one.
Case #2: Stofl can change the jumpiness of the second trampoline to 111, start from the first trampoline and visit all trampolines except the third.

To submit for this subtask, please log in.

Subtask 5: No limits (35 points)

The subtask is the same as subtask 4, but with more trampolines.

Limits

$1\le n\le 200\,000$

Example

Input:

Output:

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

Comment:

Case #0: Stofl can visit all trampolines if he changes the jumpiness of the first trampoline to 111.
Case #1: Stofl can change the jumpiness of the second trampoline to 111, start from the second trampoline and visit all trampolines except the first one.
Case #2: Stofl can change the jumpiness of the second trampoline to 111, start from the first trampoline and visit all trampolines except the third.

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

Train

Mouse Binna is a railway engineer. She is designing a straight railway line with $N$ stations, numbered $0, 1, …, N-1$ . Each station has a level. Various trains will operate on this line. Some long-distance trains may only stop at major high-level stations, some local trains may stop at almost all stations.

There is a rule: if a train stops at station $X$ , it must also stop at all stations between its starting & terminal stations (inclusive) whose level is greater than or equal to the level of station $X$ .

For example, with the following levels of these $15$ stations, the IC, IR, RE, R trains comply with the rule. However, the “invalid train” doesn’t comply because it stops at station $9$ but not station $7$ which has the same level.

While the levels of the stations have not been determined, Mouse Binna has already designed the routes for

M

trains, numbered

0, 1, {\dots}, M-1

. Please help her to find the largest

K

, so that with your manipulation of the station levels, all the first

K

trains (numbered

0, 1, {\dots}, K-1

) comply with the rule.

Subtask 1: Mini Railway Line (23 points)

Mouse Binna starts from designing a mini railway line.

Input

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 $M$ , the number of stations and the number of trains.
Each of the $M$ following lines contains an integer $r_i$ , followed by $r_i$ integers $s_{i,0}, s_{i,1}, {\dots},s_{i,r_i-1}$ , the stations that the $i$ -th train stops, in ascending order.

Output

For the $i$ -th test case, output a line “Case #i: K”, where $K$ is the largest number mentioned above.

Limits

There are $T=100$ test cases. In each test case we have:

$2 \le N \le 50$
$1 \le M \le 50$
$2 \le r_i \le N$ for all $0 \le i \le M-1$
$0 \le s_{i,0} < s_{i,1} < {\dots} < s_{i,r_i-1} \le N-1$ for all $0 \le i \le M-1$

Example

Input:

2
4 2
3 0 1 3
3 0 2 3
15 6
3 0 1 14
5 0 1 3 8 14
10 0 1 2 3 4 5 6 8 12 14
9 6 7 8 9 10 11 12 13 14
4 5 6 8 9
4 0 1 2 4

Output:

Case #0: 1
Case #1: 5

Comment:

Case #0: It’s not possible to have both

2

trains comply with the rule. Otherwise, according to train

0

, station

1

’s level is greater than station

2

’s level. However, according to train

1

, we can draw an opposite conclusion.

Case #1: The first

5

trains correspond to the example table in the task description. Although the “invalid train” breaks the rule when the levels are as given in the table, we can manipulate the levels to make the first

5

trains all comply with the rule. Actually, if we change the level of station

7

from

1

0

, the “invalid train” becomes a valid one. However, it can be proved that no matter how we manipulate the station levels, it’s not possible that all

6

trains comply with the rule.

To submit for this subtask, please log in.

Subtask 2: Fixed Length Trains (15 points)

There are a considerable number of stations and trains. All the trains have starting station $0$ and terminal station $N-1$ .

Input

Same as Subtask 1

Output

Same as Subtask 1

Limits

There are $T=100$ test cases. In each test case we have:

$2 \le N \le 5000$
$1 \le M \le 2500$
$2 \le r_i \le N$ for all $0 \le i \le M-1$
$r_{0}+ r_{1}+ {\dots} + r_{M-1} \le 10^{5}$
$0 = s_{i,0} < s_{i,1} < {\dots} < s_{i,r_i-1} = N-1$ for all $0 \le i \le M-1$

Example

Input:

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

Output:

Case #0: 1
Case #1: 3

To submit for this subtask, please log in.

Subtask 3: Medium Railway Line (20 points)

There are a considerable number of stations and trains.

Input

Same as Subtask 1

Output

Same as Subtask 1

Limits

There are $T=100$ test cases. In each test case we have:

$2 \le N \le 5000$
$1 \le M \le 2500$
$2 \le r_i \le N$ for all $0 \le i \le M-1$
$r_{0}+ r_{1}+ {\dots} + r_{M-1} \le 10^{5}$
$0 \le s_{i,0} < s_{i,1} < {\dots} < s_{i,r_i-1} \le N-1$ for all $0 \le i \le M-1$

To submit for this subtask, please log in.

Subtask 4: Direct Trains (16 points)

There are a lot of stations and trains. All the trains are direct; in other words, they don’t have any intermediate stop except the starting and terminal station.

Input

Same as Subtask 1

Output

Same as Subtask 1

Limits

There are $T=100$ test cases. In each test case we have:

$2 \le N \le 10^{5}$
$1 \le M \le 50000$
$r_i = 2$ for all $0 \le i \le M-1$
$r_{0}+ r_{1}+ {\dots} + r_{M-1} \le 10^{5}$
$0 \le s_{i,0} < s_{i,1} \le N-1$ for all $0 \le i \le M-1$

Example

Input:

Output:

Case #0: 4
Case #1: 2

To submit for this subtask, please log in.

Subtask 5: Long Railway Line (26 points)

There are a lot of stations and trains.

Input

Same as Subtask 1

Output

Same as Subtask 1

Limits

There are $T=100$ test cases. In each test case we have:

$2 \le N \le 10^{5}$
$1 \le M \le 50000$
$2 \le r_i \le N$ for all $0 \le i \le M-1$
$r_{0}+ r_{1}+ {\dots} + r_{M-1} \le 10^{5}$
$0 \le s_{i,0} < s_{i,1} < {\dots} < s_{i,r_i-1} \le N-1$ for all $0 \le i \le M-1$

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

Hiking Signs

Mouse Binna has been appointed as director of tourism for Bolivia. She identified the lack of hiking infrastructure as one of the biggest problems and decided this to be the big point she wants to address. The nature is beautiful, there are plenty of interesting landmarks, and there already is a quite extensive road network.

The road network can be described as a set of intersections and a set of roads where each road connects exactly two intersections. The existing road network has the property that between any pair of intersections there is at most one path. Some of the intersections are especially beautiful and are called landmarks.

One piece of feedback Mouse Binna received is that mice can get lost in the wilderness. For that end, Mouse Binna decided to place hiking signs at each intersection. Each hiking sign shows a list of landmarks that can be reached and their respective distances.

Binna wants to build new roads in order to ensure the following:

Each hiking sign should be unique. In other words, no two intersections should have the same set of reachable landmarks, and for each of those landmarks the same distance.
Between any pair of intersections there is at most one path. This property was already present in the initial road network and Binna wants to keep it that way.

Is it possible to build new roads such that the constraint is satisfied? If yes, find a minimal set of roads that Binna needs to build.

Input and Output

All subtasks have the same input and output, and the same limits.

Input

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

The first line contains three positive integers $N$ , $M$ and $K$ – the number of intersections in the network, the number of roads and the number of landmarks.
The second line contains $K$ integers, the landmarks. The landmarks are guaranteed to be given in increasing order.
The following $M$ lines describe the existing roads, each line consisting of two numbers $a$ and $b$ .

Output

For the $t$ -th testcase:

If it is possible to build new roads to satisfy the properties, output Case #t: e, where $e$ is the minimal amount of roads you need to add. Then, print $e$ lines consisting of two numbers describing the roads you want to add.
If it is not possible, output a single line with the words “Case #t: Impossible”.

Limits

In all subtasks we have:

$1 \le N \le 10^{4}$ .
$0 \le M \le N-1$ .
$0 \le K \le N$ .

Subtask 1 (13 Points)

In this subtask we have $M=N-1$ . This means one can go from any intersection to any other intersection using a seqeuence of adjacent roads.

Input:

Output:

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

To submit for this subtask, please log in.

Subtask 2 (15 Points)

In this subtask roads only connect intersections with index at most $M$ . (In other words $a,b\le M$ for all edges $(a,b)$ .) Additionally all intersections larger than $M$ are guaranteed to be landmarks.

Input:

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

Output:

Case #0: 1
0 4

To submit for this subtask, please log in.

Subtask 3 (16 Points)

In this subtask any intersection has at most 2 adjacent roads.

Input:

Output:

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

To submit for this subtask, please log in.

Subtask 4 (27 Points)

In this subtask all components of the road network contain at least one landmark.

Subtask 5 (29 Points)

No further constraints.

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

Circuit

Stofl is really tired of solving conventional tasks in Rust, so he decided to study circuits — a much simpler way of programming than the standard programming languages.

A program defining a circuit consists of several operations, where each operation is defined in the form X = Y op Z, where $X$ is a variable name for the new value, $Y$ and $Z$ reference some previously computed variables or constants, and op is a binary operation, which is restricted to +, - or max. Additionally, there is a special variable in, that represents a 2D-array of size $N \times M$ that is being fed as an input to the circuit, and one special variable out, that represents the output of the circuit.

Below you can find an example circuit that computes the sum of the input elements, assuming $N=2$ and $M=3$ :

column1 = in[0][0] + in[1][0]
column2 = in[0][1] + in[1][1]
two_columns = column1 + column2
column3 = in[0][2] + in[1][2]
out = two_columns + column3

There are the following restrictions for the circuits:

Each variable name might only contain english letters, digits, underscores and square brackets and can not start with a digit and can not be longer than 50 characters.
A variable might appear on the left side at most once.
Any variable appearing on the right side must be defined before, or must reference an input element.
Any constants used on the right side must be positive integers not greater than $10^{9}$ .
Each circuit ends with an operation that has out on the left side.

Stofl already knows how to compute the sum of integer values using his favorite programming language, so to try out programming with circuits he decided to solve a different task. Given a 2D-array with integers from range $[-10^{6}, 10^{6}]$ , a cross is defined as any vertical segment intersecting any horizonal segment. Furthermore, a cross must contain at least one element of the array, i.e. a 0x0 cross is not allowed. An example of a cross can be found below:

Stofl is interested in designing a circuit that computes the value of the maximum sum among all crosses in a given grid. Please help him to design it!

Input

The first line contains a single integer $T$ – the number of test cases. Then $T$ test cases follow, each of them contains one line with two integers $N$ and $M$ – the size of the grid ( $1 \le N, M \le 128$ ). Note that for a given subtask the input will never change.

Output

For each test case, output a circuit that computes the maximum cross in a grid $N \times M$ .

Example

Input:

2
1 1
1 2

Output:

Case #0:
out = in[0][0] + 0
Case #1:
max_single = in[0][0] max in[0][1]
together = in[0][0] + in[0][1]
out = max_single max together

Comment:

Case #0: In this case, the only possibility is to take the single value of in[0][0]. Since, however, all operations take two elements we also need to add a “+ 0” as an identity operation.

Case #1: Here, there are three different options to form a cross by taking either one of the two elements or both of them. Therefore, our solution has to take the maximum out of all three possibilities.

Scoring

This task has 5 subtasks. The score for each test case in each of those subtasks depends on the size of the circuit $S$ and its depth $D$ . The size is defined as the total number of operations (i.e. lines) in your circuit. Meanwhile, the depth is defined as the maximum distance between the out variable and any input variable in terms of operations. Or, in other words, if you were to substitute all the equations into one, the depth is the maximum amount of nested brackets. For example, in the second test case above the combined equation would look like this:

out = (in[0][0] max in[0][1]) max (in[0][0] + in[0][1])

which gives a depth of 2. The score for such a circuit will then be given according to the following snippet (no closed formula as we are not at the math olympiad here, formulas are overrated anyways):

double get_score(double ratio) const {
  return min(1.0, 0.3 + 0.7 * ratio * ratio);
}

double score(int n, int m, double depth, double size, int max_score) const {
  double S = get_score(n * m / size);
  double D = 0.3 * get_score(n * m / depth) + 0.7 * get_score(2 * log(n * m) / depth);
  return S * D * max_score;
}

Then, the score for a test is defined as the minimum score across all test cases. If your circuit is not valid (i.e. contains syntax errors or is not correctly computing the maximum sum among all crosses), you will get Wrong answer and therefore 0 points for the entire subtask.

Subtask 1 (20 points)

$N=1$
$1\le M\le 128$
All integers in the grid are guaranteed to be positive.

To submit for this subtask, please log in.

Subtask 2 (20 points)

$N=1$
$1\le M\le 128$
It is guaranteed that the given array will be a prefix (possibly with size 0) of only negative integers, followed by only positive integers, i.e. the array is of the form: -, -, ..., -, +, +, ..., +. It is guaranteed that the array always contains at least one positive integer.

To submit for this subtask, please log in.

Subtask 3 (20 points)

$N=1$
$1\le M\le 128$

To submit for this subtask, please log in.

Subtask 4 (20 points)

$1\le N,M\le 128$
All integers in the grid are guaranteed to be positive.

To submit for this subtask, please log in.

Subtask 5 (20 points)

$1\le N,M\le 128$
No additional constraints.

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

Cake icing

Mouse Stofl and Mouse Binna want to celebrate the reforestation of the nature reserve with a tasty cake. Unfortunately, even after long discussions, they can’t agree on which icing they should put on the cake.

Thus, they decide to ice the cake in a game against each other.

The Game

The rectangular cake consists of

W \times H

pieces. Each piece (

x

y

) has an importance

a_{x,y}

Stofl and Binna take turns in pouring a jar of their icing onto the cake. They start on a piece (

x

y

). Then, they can move the jar to one of the four adjacent pieces. This way, they ice a sequence of pieces in one pour. When the jar is empty, the pour is finished and the turn goes to the other mouse. Each mouse may pour P jars.

A piece can be iced with different thicknesses. In order to reach a thickness of

d

3^{d-1}

ml of icing is needed, as the cake partially absorbs the icing. If a piece is already iced with thickness

d

, you need at least thickness

d+1

to overpower the taste.

The icing flows evenly out of the jar, therefore all pieces of one pour will be iced with the same thickness. If a piece is already iced, the icing only changes when the thickness of the new pour is strictly larger than the thickness of the current icing.

Binna and Stofl both have a pot with $B$ ml of Icing. For each pour, they can fill some part of the remaining icing into the jar. The amount of icing must be equal to $l \cdot 3^{d-1}$ , where $l$ is the amount of pieces in the pour and $d$ the thickness.

At the end of the game, the importances of all pieces with the icing of a mouse get added. The sum counts as the score for this mouse.

Protocol

The program communicates with the grader over stdin / stdout.

In the beginning, the program recieves general information about the game:
On the first line four integers: WWW HHH BBB PPP, the width of the cake WWW, the height of the cake HHH, the ml of icing in the pot in the beginning BBB and the amount of pours each mouse is allowed PPP.
On the next HHH lines WWW integers each which describe the importances. The importance ax,ya_{x,y}ax,y​ is in the xxx-th column from the left and in the yyy-th row from the bottom. The numbering of rows and columns is 000 based. So the integer to the very left in the bottommost line describes a0,0a_{0,0}a0,0​.
On the next line a character which describes, whether your program should start. If your program should start, it will be an ‘Y’, otherwise an ‘O’.

After that, the game will start. If it is the turn of your program, it should output the pour in the following format:
On the first line four integers: xxx yyy ddd lll, where xxx and yyy describe the starting piece, ddd the thickness and lll the length of the pieces in the pour.
On the next line l−1l-1l−1 characters which describe how the jar moves after each piece. These characters are either ‘U’, ‘D’, ‘R’ or ‘L’. They signify the following movements from piece (iii, jjj):

‘U’ upwards, to ( $i$ , $j+1$ )
‘D’ downwards, to ( $i$ , $j-1$ )
‘R’ to the right, to ( $i+1$ , $j$ )
‘L’ to the left, to ( $i-1$ , $j$ )

The jar is not allowed to go off the cake.

When it’s the opponents turn, your program gets the pour the opponent made in the same format.

A program should print a pour with $l=0$ if it can’t or does not want to pour. However, this still counts as one of its $P$ turns.

Limits

These limits hold for all possible maps. They are thus too loose for the majority of map configurations. More details about the map configurations are in the section Maps.

$1 \le W, H \le 20$
$1 \le B \le 486 \cdot W \cdot H$
$1 \le P \le 2 \cdot W \cdot H$
$0 \le a_{x,y} \le 1000$
$0 \le x < W$
$0 \le y < H$
$1 \le d \le log_{3}(B) + 1$
$1 \le l \le B$

Beispiel

Open the example in the visualization

The cake in the beginning of the game. The importances are represented as black squares. The bigger the square, the greater the importance.

The cake after the first pour of the orange mouse. Three pieces were iced with thickness 7.

The cake after the first pour of the blue mouse. The piece at the bottom left was iced with thickness 8 and now has the blue icing, because 8 > 7.

The cake after the second pour of the orange mouse. The piece at the bottom right was iced with thickness 2.

The cake after the second pour of mouse blue, at the end of the game. Mouse blue iced all the pieces at the right with thickness 3. The piece at the bottom right now has the blue icing (3 > 2), but the piece in the middle right stays orange (3 <= 7).

Here is the communication from the perspective of the orange mouse. The input of the program is marked with “<”, the output with “>”.

< 2 3 3090 2
< 8 166
< 558 706
< 753 430
< Y
> 1 1 7 3
> L D
< 0 0 8 1
<
> 1 0 2 1
>
< 1 0 3 3
< U U

Creativity platform

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

A few notes about the platform:

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

Subtask 1: Play by the rules (10 Points)

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

Subtask 2: Play smart (15 Points)

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

Subtask 3: Tournaments (75 Points)

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

Each tournament is worth a certain amount of points and you will get a fraction of these based on your rank: 100% for rank 1, then 10% less for every following rank until rank 6 (50%), then 5% less for every following rank. Some of the bots are not from participants, so the points you receive might not match the displayed ranking.

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

25.9.2024, 20:00: Early bird tournament, worth 20 points.
9.10.2024, 20:00: Getting started tournament, worth 30 points.
23.10.2024, 20:00: Midway tournament, worth 40 points.
6.11.2024, 20:00: Getting serious tournament, worth 50 points.
20.11.2024, 20:00: Final spurt tournament, worth 60 points.
1.12.2024, 10:00: Creativity tournament, worth 75 points. Ranking will be hidden.

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

The Creativity tournament does not count for the qualification. The results will be hidden until the SOI-Camp. In the SOI-Camp we will present the results and award the winner with a prize. The maximum number of points one can get from this task for Qualification is thus 85.

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

Maps

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

Cake size:
- small: $1 \le W, H \le 6$
- medium: $1 \le W, H \le 10$
- large: $1 \le W, H \le 20$

The number of pieces with importance larger than zero will be noted as $C$ .

Icing amount: How much ml of icing will be in the pot in the beginning:
- little: $\frac{C}{2} < B < 2 \cdot C$
- medium: $4.5 \cdot C < B < 18 \cdot C$
- much: $121.5 \cdot C < B < 486 \cdot C$
Pours: How many pours each mouse is allowed to make:
- few: $\frac{1 + \sqrt{C}}{2} < P < 2 \cdot (1 + \sqrt{C})$
- medium: $\frac{1 + \sqrt{C} + 0.1 \cdot C}{2} < P < 2 \cdot (1 + \sqrt{C} + 0.1 \cdot C)$
- many: $\frac{C}{2} < P < 2 \cdot C$
Centralness: How evenly the importances are spread over the pieces:
- spread: $C \approx W \cdot H$
- medium: $C \approx 0.3 \cdot W \cdot H$
- concentrated: $C \approx 0.1 \cdot W \cdot H$

Hints

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

Use the following commands:

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

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

Additional Tools

If you want to run your bots locally you can download the judge and the visualization here. This also includes a sample C++ bot. There is a short explanation on how to run the judge and visualization included. They are the exact same version which is used on the creativity platform.

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

QRH

The homework part of the qualification round (QRH) consists of 4 tasks, each of which is worth 25 points. You can gain a maximum of 100 points counting towards your score of the regular round.

This helps you get familiar with our grading system which we will use in all our events after the qualification round, including workshops, camp, finals, and team selection.

You can submit in C++ (recommended), Java or Python.

C++:	If you don’t have a setup already, we recommend installing VSCode.
Java:	Read Java on the SOI Grader.
Python:	Read Python on the SOI Grader.

For QRH you can discuss solutions with friends or publicly on Discord, as long as you don’t share source code. We are also happy to help you! If you need help with the grading system or have questions regarding the theory or tasks, don’t hesitate to ask here or in Discord.

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

Junior Ranking

Rank	Username	Total (600)	cheesem… (100) cheesemachine	rotation (100)	landsca… (100) landscaping	trampoline (100)	train (100)	hikings… (100) hikingsigns
	loading ...

Regular Ranking

Rank	Username	Total (700)	landsca… (100) landscaping	trampoline (100)	train (100)	hikings… (100) hikingsigns	circuit (100)	cakeicing (100)	qrh (100)
	loading ...