Qualification Round 2024/2025

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.

Input/Output

All subtasks have the same input and output format.

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.

5
2
1 2
2
10 15
2
10 5
2
5 -5
2
42 42

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

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.

3
3
10 15 20
3
13 8 3
3
42 42 42

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

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.

3
3
10 12 15
3
10 15 20
3
42 42 42

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

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.

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

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

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.

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

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

Input and Output

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

3
3 4
soi
1 0
1 2
1 1
1 0
5 4
binna
1 1
1 0
1 2
1 4
5 6
mouse
1 0
1 4
1 0
1 1
1 2
1 3

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

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.

2
3 5
pjp
3 2
2 1 2
1 0
1 1
1 2
6 14
mfegaw
1 5
3 0
1 5
3 0
2 4 5
1 2
2 0 3
1 3
3 4
3 2
3 3
3 5
1 1
1 0

Case #0: jpp
Case #1: wwemaw

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.

3
3 9
soi
1 0
1 2
1 1
1 0
2 0 2
1 0
1 2
1 1
1 0
5 7
binna
2 0 1
1 1
1 0
1 2
1 4
2 1 2
1 1
5 8
mouse
1 0
1 4
2 0 4
1 0
1 1
1 2
2 1 3
1 3

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

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.

2
3 16
bul
1 0
3 1
1 0
3 1
1 0
3 1
1 0
3 0
1 0
3 1
1 0
3 1
1 0
3 1
1 0
3 0
5 6
stofl
3 2
1 0
1 1
1 2
1 3
1 4

Case #0: blubblub
Case #1: flsto

Subtask 5: Escape (36 Points)

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

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.

2
3
1 2 1
3
1 2 2

Case #0: YES
Case #1: NO

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?

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

Case #0: 3
Case #1: 5

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.

2
3
1 2 2
5
1 2 3 4 1

Case #0: 3
Case #1: 5

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.

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

Case #0: 3
Case #1: 5

Subtask 5 (29 points)

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

Input/Output

All subtasks have the same input and output format.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

To submit for this subtask, please log in.

Subtask 1: Mini Railway Line (23 points)

Mouse Binna starts from designing a mini railway line.

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

Case #0: 1
Case #1: 5

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

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

Case #0: 1
Case #1: 3

Subtask 3: Medium Railway Line (20 points)

There are a considerable number of stations and trains.

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.

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

Case #0: 4
Case #1: 2

Subtask 5: Long Railway Line (26 points)

There are a lot of stations and trains.

Input and Output

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

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.

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

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.

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

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.

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

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.

To submit for this subtask, please log in.

Subtask 5 (29 Points)

No further constraints.

To submit for this subtask, please log in.

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 and the values of $N$ and $M$ for each subtask is given in the corresponding section.

Output

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

Example

2
1 1
1 2

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

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(expected_size(n, m) / size);
  double D = get_score(expected_depth(n, m) / depth);
  return S * D * max_score;
}

The values of expected_size and expected_depth for all the inputs are specified in the subtask sections. 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.

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.

Subtask 3 (20 points)

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

Subtask 4 (20 points)

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

Subtask 5 (20 points)

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

The Game

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.

• ‘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$ and strictly positive $d$ 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$
• $0 \le l \le B$

Beispiel

Open the example in the visualization

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. Games that are part of a tournament don’t count for this subtask. 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. Games that are part of a tournament don’t count for this subtask. 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.