Second Round 2025/2026

Overview

Welcome to the Second 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 2025-11-30T23:59:59+01:00

Registan Pattern

Mouse Stofl and Mouse Binna have finally made it to Uzbekistan’s beautiful registans, which are full of colorful patterns.

Stofl found similarities in the patterns of the registan and he became artistically inspired! Although this time, Stofl had a way too crazy idea.

They came to a wall which is one meter tall and several meters long. The inspiring characteristics of the wall was its modular design every meter. Stofl’s idea was to cut the wall into one meter parts in order to rearrange them, which results in a new but still continuous pattern. However, Binna disliked his idea very much. She doesn’t care about the building itself, but she doesn’t like the lack of innovation. She thinks just rearranging the patterns is boring, so she gave him the challenge to make a unique pattern by dividing the wall into segments of several meters and then flipping all the segments in place.

However, Stofl has already assigned for each meter the position it should go. To impress Binna, he needs to find out how he can divide the wall such that he achieves his original vision by flipping the segments.

Subtask 1: A short wall (11 points)

Stofl has a wall which is $3$ meters long. Can you help him determine how he should divide the wall?

Input

The first line contains the number of test cases $T$. For every test case, two lines will follow:

• The first line contains the integer $N$, the length of the wall in meters.
• The second line contains $N$ integers $a_i$ for $0 \le i < N$, describing Stofl’s assignment. The $i$-th meter of the wall should move to the $a_i$-th meter.

Output

For the $t$-th test case, if it is not possible to achieve Stofl’s assignment by flipping segments, print “Case #t: Impossible”. Otherwise, print “Case #t: Possible” and two additional lines:

• The first line contains the number of segments $M$.
• The second line contains $M$ integers $s_j$, where $s_j$ is the length of the $j$-th segment.

Limits

• $T = 100$
• $N = 3$
• $0 \le a_i < N$ for all $i$, all $a_i$ are distinct

Example

Input:

2
3
0 2 1
3
2 0 1

Output:

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

Solution for Case #0:

Dividing the wall into these two segments achieves that each meter of the wall ends up where Stofl wants it. Meter 1 is flipped by itself and thus remains where it is, while meters 2 and 3 are swapped.

To submit for this subtask, please log in.

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

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

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

Timurid Riders

During the late Middle Ages, Uzbekistan was the heartland of the Timurid Empire, stretching from central Anatolia all the way to northern India, with Samarkand as its capital.

Binnas Birthday is coming up, and Mouse Stofl wants to prepare a special surprise for her. He knows that she is fascinated by the history of the Timurid Empire, and that she loves puzzles. So he came up with a puzzle based on the Timurid Empire.

The Timurid Empire in the puzzle consists of $N$ villages, including the capital, and $N-1$ roads between them, on which riders can travel. The capital Samarkand is always village $0$. The villages bordering the wilderness have watchtowers to guard the borders. These villages can be recognized because they have exactly one road leading out and are not the capital. All other villages, including the capital, contain fortresses.

The puzzle further follows these rules:

1. Riders may only be dispatched from the villages with watchtowers.
2. Each rider travels only inward, toward the capital, never outward.
3. Each rider continues travelling until it has reached the capital or the next village is already occupied.
4. A new rider may only be dispatched once the previous rider has reached its final destination.

The goal is to decide from which watchtower to release each rider, and in what order, so that every fortress in the empire is manned in the least possible total time.

Stofl asked you to solve the puzzle, so that he can see if it is fit for Binna.

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

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

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

Case #0: 5
Case #1: 5
Case #2: 19

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

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

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

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

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

Case #0: 1
Case #1: 5
Case #2: 7

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

Mouse Dances

Mouse Stofl and friends are hosting a grand dance festival. All through the night, mice gather next to each other holding paws with their neighbors, swaying to the music, spinning in step, and pausing now and then for a nibble of cheese before the next melody begins.

But dancing is not always easy. When neighbors differ too much in height, their little paws strain with effort, their backs stretch or stoop too much and before long the mismatched neighbors grow tired and let go. The greater the height difference, the greater the inconvenience — and the sooner the dance floor empties.

To keep the celebration alive until sunrise, the mice must choose their places wisely: arranging themselves so that the maximum inconvenience between any two neighbors is as small as possible. Depending on the melody, they may form a line, gather in a circle, or even whirl apart into two circles — but always with the same goal: minimize the maximum inconvenience, and keep the dancing going through the night.

For each subtask, help Stofl arrange the mice for a different melody so that he can minimize the maximum inconvenience between neighbors.

2
2
2 1
3
1 5 2

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

2
2
2 1
3
1 5 2

Case #0: 1
Case #1: 3

2
2
2 1
6
8 5 6 10 10 9

Case #0: 1
2 1
Case #1: 3
5 8 10 10 9 6

2
2
2 1
6
8 5 6 10 10 9

Case #0: 1
Case #1: 3

2
2
2 1
7
8 5 6 10 10 9 1

Case #0: 0
1 1
2
1
Case #1: 3
6 1
5 8 10 10 9 6
1

2
2
2 1
7
8 5 6 10 10 9 1

Case #0: 0
Case #1: 3

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

Fire

Mouse Binna is on an adventure in a vast forest that is modeled as an $N \times N$ grid. Lately, the weather has been extremely dry, and the forest is about to catch fire. Binna is located at the top-left corner of the grid $(0, 0)$, while an underground shelter lies at the bottom-right corner $(N-1, N-1)$, offering safety from the fire.

At time $0$, fire starts in $M$ distinct cells of the grid — these are called fire sources. At each unit of time, the fire spreads:

• any cell that is currently on fire will remain on fire, and
• its $4$ direct neighbors (up, down, left, right) also catch fire.

Binna wants to know the latest time $L$ such that a safe path exists from her current location $(0, 0)$ to the underground shelter $(N-1, N-1)$. Both endpoints and all cells on the path must not be on fire at time $L$. Moves are allowed only in the $4$ directions: up, down, left, right. If no such path exists even at time $0$, then $L=-1$.

Subtask 1: Single fire source (12 points)

At time $0$, there is exactly one fire source.

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$, $M$, representing the size of the grid and the number of fire sources.
• Each of the next $M$ lines contains two integers $X_i$ and $Y_i$ — the row and column of a fire source.

Output

For each test case, output a line “Case #i: L”, where $L$ represent the latest time such that there still exists a safe path, or $-1$ if no safe path exists even at time $0$.

Limits

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

• $2 \le N \le 10^{9}$
• $M = 1$
• $0 \le X_i, Y_i \le N-1$ for all $0 \le i \le M-1$

Example

Input:

3
7 1
1 3
4 1
2 1
4 1
1 1

Output:

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

Comment:

Case #0: The grid evolves as follows. From time $3$ onward, there is no safe path to the underground shelter, so the latest time is $2$.

To submit for this subtask, please log in.

Subtask 2: Aligned fire sources (19 points)

All fire sources are in the same row.

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^{9}$
• $1 \le M \le 5000$
• $0 \le X_i, Y_i \le N-1$ for all $0 \le i \le M-1$
• $X_i=X_j$ for all $0 \le i,j \le M-1$

Example

Input:

2
7 3
4 0
4 1
4 3
20 2
15 2
15 6

Output:

Case #0: 2
Case #1: 12

Comment:

Case #0: The grid evolves as follows. From time $3$ onward, there is no safe path to the underground shelter, so the latest time is $2$.

To submit for this subtask, please log in.

Subtask 3: Small grid (21 points)

The grid size is limited.

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 500$
• $1 \le M \le 5000$
• $0 \le X_i, Y_i \le N-1$ for all $0 \le i \le M-1$

Example

Input:

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

Output:

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

Comment:

Case #0: The grid evolves as follows. From time $4$ onward, there is no safe path to the underground shelter, so the latest time is $3$.

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

Rob or Buy

The Silk Road in Uzbekistan was a trade route, where merchants travelled to cities like Samarkand to exchange silk, spices and other goods. The many markets and caravans made it a center of commerce across Uzbekistan and other parts of Asia. It was a lively road with a lot of merchants and travelers, but also thieves and robbers!

On the road, there are $N$ merchants in a line, numbered from $0$ to $N-1$. Each of them sells some goods. The goods of the $i$-th merchant cost $p_i$ mouse coins. There is the myth of the “Silk Road’s great heist” in which the entire road was robbed in lightning speed! That’s why the merchants on the road created an alarming network to notify other merchants of an ongoing robbery. Each merchant is assigned a direction which is either $l$ for left, or $r$ for right. After a merchant is robbed, he will notice the robbery and alarm every merchant on his left or right respectively. Any merchant that is alarmed this way will pay extra attention and robbing the merchant becomes impossible.

Mouse Stofl wants to do the thievery himself and wants to get all the goods sold on the Silk Road. But since it’s impossible to steal from alarmed merchants, he will need to buy some of the goods. So the questions is, what is the minimum amount of money he needs to spend, if Stofl robs and buys the goods in the perfect order?

2
2
rl
3 5
3
lll
10 48 39

Case #0: 3
Case #1: 0

1
4 1
rrll
6 3 5 4

Case #0: 1

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

Emirate of Burkhara

Under construction, coming very soon*

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

Tomb exploration

Shah-i-Zinda is a famous necropolis (a large old cemetary) in Uzbekistan. Mouse Binna and a large team of passionate archeologists are preparing to enter an old, cursed, and unexplored tomb to bring back all the valuable historical unseen items they can find for the local museum. This project is of the upmost importance as all previous tombs explored were scavenged centuries ago because no curse protected them.

The tomb’s cryptic curse is written in majestic carved letters above the entrance: “He who exits these sacred grounds, shall suffer the weight of his hefty theft.”

Fully prepared to endure the consequences of their actions for the historical sake of the country (the team is as passionate about history as you can get), the entire team led by Binna enters the tomb. They travel multiple galleries with walls covered in beautiful artworks dating back to centuries. They of course progress with great care and take tons of pictures of everything they can see. After hours of exploration – mice have small legs and can’t travel very fast – they finally arrive at the main room of the tomb. On shelves they see $N$ small lined up statues which should be brought back to the surface for everyone to enjoy.

In front of this incredible spectacle, Binna can’t resist the urge to keep track of the order of the statues so they can reconstruct the way they are arranged in the museum. She also recalls what the curse said above the entrance and finally understands what it was all about: When exiting the tomb, everyone carrying statues will be inevitably cursed. In addition, for a specific mouse, the curse effect will be proportional to the weight of the heaviest statue they are carrying. The $i$-th statue in the line will have weight $w_i$. That is, if mouse $m$ carries some statues and the heaviest statue is statue $i$ with weight $w_i$, then the curse mouse $m$ will suffer will be of importance $w_i$.

When entering the tomb, the team brought many bags with them, each bag can carry at most $K$ statues. Due to the size of the bags relative to the size of a mouse, a mouse can only carry at most $1$ bag out of the tomb.

Binna wishes to minimize the sum of the curses the team will have to endure once they leave.

To help them keep track of the order of the many statues, the mice have decided that each bag containing statues will contain statues with incrementing positions. That is, the $b$-th bag containing $c_b$ with $c_b \leq K$ statues, will contain the statues at the positions $i_b, i_{b+1}, i_{b+2}, \dots, i_{b+c_b-1}$.

The team can use as many bags as they want and there are more than enough mice to carry all the filled bags.

Can you help Binna minimize the sum of the maximum weight of the statues present in each bag?

2
5 2
7 8 9 10 11
3 3
9 5 2

Case #0: 27
Case #1: 9

1
5 2
8 7 10 11 5

Case #0: 24

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

Case #0: 24
Case #1: 11

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

Case #0: 24
Case #1: 11

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

Evilruins

Mouse Stofl and Binna are doing multiple cave expeditions in the lands of Uzbekistan, where they try to find crystals and treasures. They already investigated a lot of caves, among which are the famous Boybuloq caverns and the huge Deep Star cave system. In their 33rd expedition, they found something truly terrifying.

At the very bottom of the cave system, they found ruins of an ancient civilization of the “Dark Practitioners”, which was a terrifying cult of moles known for the black magic. In fact, this ruin contains a library full of evil magic that has been lost for centuries. Stofl and Binna need to cover up this ruin as fast as possible such that this dark knowledge doesn’t fall into evil hands.

The cave system is made up of $N$ chambers labeled from $0$ to $N-1$. The chambers are all connected to each other through $N - 1$ channels. The chamber $0$ contains the ruins and is at the very bottom of the cave system. Non ruin chambers with only one channel are cave entrances on the surface, which have different sizes $c_i$. All other chambers are intermediary and lead down towards the ruins. In order to cover up the ruins, Stofl and Binna have to fill the entire cave system with sand from the nearby Kyzylkum Desert. The red sand of the desert is holy and blocks the dark magic from spreading. They will pour sand into one of the entrances filling up one chamber at a time. The sand will fall down towards the ruins until it reaches them or the next chamber in the direction of the ruins is already filled.

Although both Stofl and Binna want to save the world, they also want to be better than the other one in saving the world. That’s why they take alternating turns pouring sand, starting with Stofl. In one turn, they choose a cave entrance and pour sand into it, filling one chamber or the entrance. If the chamber they fill is the entrance itself, they get $c_i$ points for doing so. They cannot choose an entrance which is already filled and play until there are no unfilled chambers. The mouse with more points in the end is deemed “Hero of the world”.

Given the map of the caves, you will need to determine who will get more points by filling up entrances.

Subtask 1: Direct channels (6 points)

Every entrance leads directly to the ruins, with no chambers in between.

An example of a valid structure would look like this:

Input

The first line contains the number of test cases $T$. For each test case, you will get following lines:

• The first line contains $N$, denoting the number of chambers.
• The second line contains $N$ integers $c_i$, denoting the number of points per chamber. Note that it will be $0$ for chambers not on the surface.
• The next $N-1$ lines contains two integers $u_i,v_i$ which denotes a channel between chamber $u_i$ and $v_i$.

Output

For each test case, output a single line Case #i: P where $P = S-B$ where $S$ is the points Stofl gets and $B$ the points Binna gets, assuming they fill up the cave system optimally.

Limits

• $T = 100$
• $2 \le N \le 100\,000$
• $0 \le c_i \le 100\,000$ for all $0 \le i < N$

Example

Input:

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

Output:

Case #0: -4
Case #1: 0

To submit for this subtask, please log in.

Subtask 2: Transportation channels (10 points)

The channels have been dug in a very specific way. There is a central chamber line, and each chamber on that line has zero or more channels directly leading to a cave entrance. They probably used it as a logistics cave.

An example of a valid structure would look like this, where the yellow line indicates central chamber line.

Input, Output & Limits

Same as in subtask 1.

Example

Input:

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

Output:

Case #0: 3
Case #1: -1

To submit for this subtask, please log in.

Subtask 3: Guard chambers (19 points)

Stofl and Binna noticed something interesting: The intermediary chambers have channels only directly to the ruins or entrances. They were likely used as guard post, providing a direct path to the city, but blocking off unwanted visitors from the surface. In addition, a direct path between an entrance at the surface and the ruins never exists.

An example of a valid structure would look like this:

Input, Output & Limits

Same as in subtask 1 and 2.

To submit for this subtask, please log in.

Example

Input:

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

Output:

Case #0: 7
Case #1: -5

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

2H

The homework part of the second round (2H) 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 second round, including workshops, camp, finals, and team selection.

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

For 2H 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

Regular Ranking