Second Round 2025/2026 - Swiss Olympiad in Informatics

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

Category	Task	Total	Subtask 1	Subtask 2	Subtask 3	Subtask 4	Subtask 5	Subtask 6	Subtask 7
Junior only	registanpattern	‒/100	‒/11	‒/17	‒/29	‒/43
Junior only	timuridriders	‒/100	‒/8	‒/9	‒/14	‒/18	‒/24	‒/27
Both	mousedances	‒/100	‒/6	‒/12	‒/15	‒/13	‒/18	‒/14	‒/22
Both	fire	‒/100	‒/12	‒/19	‒/21	‒/22	‒/26
Both	roborbuy	‒/100	‒/10	‒/15	‒/10	‒/25	‒/40
Both	bukhara	‒/100	‒/7	‒/15	‒/18	‒/27	‒/33
Regular only	tombexploration	‒/100	‒/17	‒/18	‒/24	‒/41
Regular only	evilruins	‒/100	‒/6	‒/10	‒/19	‒/8	‒/14	‒/43
Regular only	2h	‒/100	‒/25	‒/25	‒/25	‒/25

Tips

You may use any programming language to solve the tasks of the Second 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 Second 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 Second 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

To participate, you need to either have qualified in the first round or scored 500 points in the pre-round. It may take up to five minutes after adding an additional email address in your profile or submitting something in the pre-round for your qualification status to be updated.

The Second 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.

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:

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.

Subtask 2: The entrance (17 points)

The walls at the entrance are up to $20$ meters long! Can you still help Stofl?

Input

Same as subtask 1.

Output

Same as subtask 1.

Limits

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

Example

Input:

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

Output:

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

To submit for this subtask, please log in.

Subtask 3: All the walls (29 points)

The registan is huge! Despite that, the patterns have still the same characteristics everywhere. Stofl would be overjoyed if you could help him out on this ambitious task.

Input

Same as previous subtasks.

Output

Same as previous subtasks.

Limits

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

To submit for this subtask, please log in.

Subtask 4: All the registans (43 points)

Binna wasn’t impressed so far. So if this didn’t impress Binna, surely he needs to go even bigger than that and combine all walls of every registan in Uzbekistan.

Input

Same as previous subtasks.

Output

Same as previous subtasks.

Limits

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

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

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:

Riders may only be dispatched from the villages with watchtowers.
Each rider travels only inward, toward the capital, never outward.
Each rider continues travelling until it has reached the capital or the next village is already occupied.
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.

Subtask 1: Orders of Samarkand (8 points)

To test your understanding of the rules, Mouse Stofl wants you to predict which fortress each rider will stop at, given a list of dispatch orders.

Input

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

The first line contains the integer $N$ , the number of villages (with watchtowers or fortresses).
Each of the $N-1$ following lines contain the integers $a_i, t_i$ , meaning there is a road from village $i+1$ to village $a_i$ which takes $t_i$ hours to ride on.
The next line contains the integer $M$ , the number of riders which will be dispatched.
The next line contains $M$ integers, $d_{0}, d_{1}, {\dots}, d_{M-1}$ , the cities with the watchtowers from which the riders will be dispatched (in this order).

Output

For the $i$ -th test case, output a line “Case #i: r_0 r_1 ... r_{M-1}”, where $r_i$ is the city in which rider $i$ will halt.

Limits

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

$2 \le N \le 10^{3}$
$1 \le M \le 10^{3}$
$1 \le t_i \le 10^{6}$ for all $0 \le i < N$

Example

Input:

Output:

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

Comment:

In the first testcase, the first rider will start at village $1$ , then go to village $0$ . The next rider starts at village $2$ , but the next village, $0$ , is already occupied, so they stay at village $2$ .

In the second testcase, the first rider will start at village $2$ , then go to village $1$ , then go to village $0$ .

Disclaimer: Generation may take a few seconds.

To submit for this subtask, please log in.

Subtask 2: Caravan Trail to Samarkand (9 points)

Being satisfied that you understood the rules, Mouse Stofl will first give you an easier version of the puzzle, taking place along a caravan trail from the furthest away village all the way to Samarkand. In this version, there is exactly one capital and one village with a watchtower. All other villages have exactly one road leading in and one leading out.

Input

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

The first line contains the integer $N$ , the number of cities and watchtowers combined.
Each of the $N-1$ following lines contain the integers $a_i, t_i$ , meaning there is a road from village $i+1$ to village $a_i$ which takes $t_i$ hours to ride on.

Output

For the $i$ -th test case, output a line “Case #i: K”, where $K$ is the minimum total time required to man every fortress.

Limits

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

$2 \le N \le 10^{6}$
$1 \le t_i \le 10^{6}$ for all $0 \le i < N$

Note: You may exceed the maximum recursion depth.

Example

Input:

Output:

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

Comment:

In the first testcase, is it best to dispatch the first rider from the watchtower in city

2

, who will take

3

hours to reach village

0

. Then, it is best to dispatch a second rider from watchtower in city

2

, who will take

2

hours to reach village

1

. Now, every fortress has been manned in

3+2 = 5

hours.

Disclaimer: Generation may take a few seconds.

To submit for this subtask, please log in.

Subtask 3: Equal Roads of Bukhara (14 points)

Next, Mouse Stofl gives you a map centered around Bukhara. The unique feature is that all roads have length $1$ .

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

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

$2 \le N \le 10^{6}$
$t_i = 1$ for all $0 \le i < N$

Example

Input:

Output:

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

Disclaimer: Generation may take a few seconds.

To submit for this subtask, please log in.

Subtask 4: Balanced Roads of Shahrisabz (18 points)

In this subtask, Mouse Stofl gives you a map of the surroundings of Shahrisabz. The unique feature is that the capital has the same distance to every watchtower.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

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

$2 \le N \le 10^{6}$
$1 \le t_i \le 10^{6}$ for all $0 \le i < N$

Example

Input:

Output:

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

Disclaimer: Generation may take a few seconds.

To submit for this subtask, please log in.

Subtask 5: A Province of the Realm (24 points)

In this subtask, Mouse Stofl gives you a map of a small portion of the Timurid Empire, with a small number of villages and roads.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

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

$2 \le N \le 10^{3}$
$1 \le t_i \le 10^{6}$ for all $0 \le i < N$

Example

Input:

Output:

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

Comment:

In the first testcase, it is best to dispatch the first rider from the watchtower in city $1$ , who will ride to village $0$ in $1$ hour.

In the second testcase, there is only one option: dispatching a rider from the watchtower in city $1$ .

Disclaimer: Generation may take a few seconds.

To submit for this subtask, please log in.

Subtask 6: The Empire of Timur (27 points)

Mouse Stofl is now confident that you can solve the original puzzle with a map of the entire Timurid Empire.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

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

$2 \le N \le 10^{6}$
$1 \le t_i \le 10^{6}$ for all $0 \le i < N$

Disclaimer: Generation may take a few seconds.

To submit for this subtask, please log in.

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

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

Input

All subtasks use the same input format:

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

The first line contains a single integer $n$ — the number of mice.
The second line contains $n$ integers: the heights of the mice $a_{0}, a_{1}, {\dots}, a_{n-1}$ .

For all subtasks we have $2 \le n$ , and $0 \le a_i \le 10^{9}$ .

Output

For the $t$ -th testcase, output a single line containing “Case #t: x” where $x$ is the smallest possible maximum inconvenience. For a given arrangement, the maximum inconvenience is defined as the maximum absolute difference between heights of adjacent mice. Then you may need to output additional lines depending on the subtask. (see each subtask’s “Output format”). When an arrangement is requested, it must be a permutation of the input heights.

Subtask 1: Tiny line (6 points)

The first melody is danced in a line. Help Stofl arrange a few mice in a line so that the maximum inconvenience is minimized.

Limits

$2\le n\le 3$

Output format

Output two lines per test case: 1. A single integer — the minimal possible maximum inconvenience. 2. $n$ integers — a valid optimal arrangement (the order in the line).

Example

Input:

Output:

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

To submit for this subtask, please log in.

Subtask 2: Medium line (12 points)

The second melody is also danced in a line. Help Stofl arrange a larger group of mice in a line so that the maximum inconvenience is minimized.

Limits

$2 \le n\le 1000$

Output format

Output two lines (same as Subtask 1).

To submit for this subtask, please log in.

Subtask 3: Huge line (15 points)

The third melody is also danced in a line and it is such a popular song that not just Stofl’s village but several other villages march into the dance floor to join in. Help Stofl arrange a huge crowd of mice in a line so that the maximum inconvenience is minimized. To keep output small, output only the optimal value of inconvenience and not the actual arrangement.

Limits

$2 \le n \le 1\,000\,000$

Output format

Output one line containing a single integer — the smallest possible maximum inconvenience.

Example

Input:

Output:

Case #0: 1
Case #1: 3

To submit for this subtask, please log in.

Subtask 4: Medium circle (13 points)

The fourth melody is danced in a circle, so that the last mouse is a neighbor of the first mouse. Arrange the mice so that the maximum inconvenience is minimized.

Limits

$3 \le n \le 1000$

Output format

Output two lines: 1. A single integer — the minimal possible maximum inconvenience on the circle. 2. $n$ integers — a valid optimal circle order (print in a list; wrap-around is implied between last and first mouse).

Example

Input:

2
2
2 1
6
8 5 6 10 10 9

Output:

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

To submit for this subtask, please log in.

Subtask 5: Huge circle (18 points)

The fifth melody is also danced in a circle, with a huge crowd of mice dance joining in. Arrange the mice optimally, and to keep output small, output only the optimal value of inconvenience and not the actual arrangement.

Limits

$2 \le n \le 1\,000\,000$

Output format

Output one line containing a single integer — the minimal possible maximum inconvenience.

Example

Input:

2
2
2 1
6
8 5 6 10 10 9

Output:

Case #0: 1
Case #1: 3

To submit for this subtask, please log in.

Subtask 6: Two medium circles (14 points)

To dance the sixth melody, the mice split into two circles, both non-empty. Arrange the mice in a way that minimizes the maximum inconvenience seen across the two circles.

Limits

$2 \le n \le 1\,000$

Output format

Output four lines: 1. A single integer — the smallest possible maximum over the two circles’ maximum inconvenience values. 2. Two integers: $\ell_{1}\ell_{2}$ — lengths of the two circles (both $> 0$ , $\ell_{1}+ \ell_{2}= n$ ). 3. $\ell_{1}$ integers — a valid arrangement for the first circle 4. $\ell_{2}$ integers — a valid arrangement for the second circle

Example

Input:

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

Output:

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

To submit for this subtask, please log in.

Subtask 7: Two huge circles (22 points)

For the seventh melody, a huge crowd of mice split into two circles, both non-empty. Arrange them in a way that minimizes the maximum inconvenience seen across the two circles. To keep output small, output only the optimal value of inconvenience and not the actual arrangement.

Limits

$2 \le n \le 1\,000\,000$

Output format

Output one line containing a single integer — the smallest possible maximum over the two circles’ maximum inconvenience values.

Example

Input:

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

Output:

Case #0: 0
Case #1: 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).

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:

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:

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

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:

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.

Subtask 4: Few fire sources (22 points)

The number of fire sources is small.

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

To submit for this subtask, please log in.

Subtask 5: More fire sources (26 points)

Both the grid size and the number of fire sources are large.

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$

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?

Subtask 1: The road between Samarkand and Bukhara (10 points)

Input

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

The first line contains the number of merchants $N$ .
The second line contains the string $s$ where $s_i$ is either $l$ or $r$ , indicating the direction of the $i$ -th merchant.
The third line contains $N$ spaces integers $p_i$ , indicating the price of the goods of the $i$ -th merchant.

Output

For each test case, output a line Case #i: P, where $P$ is the minimum amount of money Stofl needs to spend to get all the goods.

Limits

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

$2 \le N \le 10^{3}$
$2 \le p_i \le 10^{6}$ for all $0 \le i < N$

Example

Input:

Output:

Case #0: 3
Case #1: 0

Comment:

Case #0: Stofl can rob the second merchant, but then, he can’t rob the first one because he’s alarmed, so he needs to buy it for

3

Case #1: Stofl robs everyone from left to right, without buying anything.

To submit for this subtask, please log in.

Subtask 2: The road across Uzbekistan (15 points)

The road is longer now, can you still answer Stofl’s question?

Input & Output

Same as subtask 1.

Limits

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

$2 \le N \le 10^{5}$
$2 \le p_i \le 10^{6}$ for all $0 \le i < N$

To submit for this subtask, please log in.

Subtask 3: Interrupting the alarms (10 points)

Stofl doesn’t like merchants being alarmed. Therefore he will hire mercenaries to interrupt the alarms of the merchants. Between any two adjacent merchants, he can hire a mercenary to stop the alarms from spreading further. This will interrupt any alarm signal from passing, not only the alarms from the merchants next to the mercenaries.

The mercenaries are in dire need of money, so they offer their service for $W$ mouse coin. In this subtask it holds that $W=1$ .

Input

On the first line on each test case, you will now get two spaced integers $N$ and $W$ , corresponding to the number of merchants and the price of hiring a mercenary. The rest of the input is the same as subtasks 1 and 2.

Output

For each test case, output a line Case #i: P, where $P$ is the minimum amount of money Stofl needs to spend to get all the goods. $P$ also includes the amount Stofl spends on mercenaries.

Limits

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

$2 \le N \le 10^{5}$
$W = 1$
$2 \le p_i \le 10^{6}$ for all $0 \le i < N$

Example

Input:

1
4 1
rrll
6 3 5 4

Output:

Case #0: 1

Comment:

Case #0: Stofl hires a mercenary between the second and the third merchant, then he robs the merchants in the order 1, 0, 2, 3 to. Therefore he needs

1

mouse coin for hiring.

To submit for this subtask, please log in.

Subtask 4: The mercenaries need money (25 points)

The mercenaries between Samarkand and Bukhara do not offer their service for so cheap. Can you still answer’s Stofl question?

Input & Output

Same as subtask 3.

Limits

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

$2 \le N \le 10^{3}$
$1 \le W \le 10^{6}$
$2 \le p_i \le 10^{6}$ for all $0 \le i < N$

To submit for this subtask, please log in.

Subtask 5: The ultimate heist (40 points)

Stofl wants to rob the entire Silk Road! There are a lot of merchants and the prices can get very high!

Input & Output

Same as subtask 3 and 4.

Limits

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

$2 \le N \le 300\,000$
$1 \le W \le 10^{9}$
$2 \le p_i \le 10^{9}$ for all $0 \le i < N$

To submit for this subtask, please log in.

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

Emirate of Bukhara

During her travels through time and space Mouse Binna has arrived in the Emirate of Bukhara. In the Chor Minor she has stumbled across a mysterious machine. There is a sequence of boxes in a row, with a sliding cover that always leaves exactly one box uncovered. There seems to be some kind of riddle to be solved from the contests of the boxes. The room Binna is in seems to have a strange effect on her, it messes with her mind and she is very sceptical about her ability to remember anything. Luckily, each of the boxes stores $1$ number and additionally Mouse Binna can take some notes. She has $1000$ reusable notepads available. Each notepad only holds one number at any time, but Mouse Binna can erase and reuse the notepads she does not need anymore. In the beginning there is a $0$ on every notepad.

You need to help Mouse Binna solve the problem. Through a space time portal, you can send Mouse Binna instructions on how to operate the machine to solve the problem. To make sure Binna understands your instructions, you need to write it in the following standardised TTL (time travelers language).

Language definition

Your program should be composed of the following operations. You should put one statement per line, statements that take values or condition can be composed of

Instruction	Explanation
MOVE x	Move the head of the machine by $\|x\|$ to the right if $x > 0$ and to the left if $x < 0$
READ	Read the value from the current box
WRITE v	Write the value into the current box
RAMWRITE i v	Write the value $v$ into notepad $i$
RAMREAD i	Read the value out of the $i$ th notepad
IF cond	Start an if condition block, if the condition is true, go on to the next line, else jump to END IF
END IF	Ends the condition block
WHILE cond	Start a while loop. If cond is true, go on to the next line, else jump after the matching END WHILE
END WHILE	End of the while loop, jump to the WHILE statement
+ x y	Compute the sum of x and y
* x y	Compute the product of x and y
- x y	Compute x - y
/ x y	Compute x / y, the division is done on integers and rounded towards 0
MOD x y	Compute x mod y, where x mod y is defined as x - (x / y) * y
& x y	Compute the bitwise AND of x and y
\| x y	Compute the bitwise OR of x and y
^ x y	Compute the bitwise XOR of x and y
<< x y	Compute the value of x shifted to the left by y digits.
< x y	Return TRUE if x < y, else return FALSE
<= x y	Return TRUE if x <= y, else return FALSE
== x y	Return TRUE if x == y, else return FALSE
!= x y	Return TRUE if x != y, else return FALSE
> x y	Return TRUE if x > y, else return FALSE
>= x y	Return TRUE if x >= y, else return FALSE
! x	Returns TRUE if x is FALSE and FALSE if x is TRUE
&& x y	Returns TRUE if x and y are TRUE and FALSE otherwise
\|\| x y	Returns FALSE if x and y are FALSE and TRUE otherwise
INT cond	Returns 1 if the condition is TRUE and 0 otherwise

The largest number Mouse Binna knows is $2^{63}-1$ . If you try to use numbers that are bigger than that or smaller than $-2^{63}$ Mouse Binna’s brain is gonna explode and your program wraps the number around.

You can use constants in your program by using the standard decimal notation.

Your program can execute at most $1\,000\,000\,000$ instructions and you can nest at most $1\,000$ instructions in one expression.

The head of the machine always starts in the leftmost box.

The sum of $|x|$ over all your move operations can be at most $1000\cdot\text{Number of boxes}$ and you have $1000$ RAM cells to access, i.e., if you call RAMREAD or RAMWRITE with $i \ge 1000$ your machine explodes.

Mouse Binna was able to secure a copy of the machine for you so that you can test your code. Download the code as Compile the following code with your favorite C++ compiler (or open and run it in the editor of your choice). Note that the interpreter assumes that there are two files in the same directory: program.txt, the code you want to test and boxes.txt, a file that contains two lines, the first line should contain an integer $N$ , the number of boxes. The second line should contain $N$ space separated integers, the initial state of the tape.

Interpreter (Expand)Copy

  #include <bits/stdc++.h>

  using namespace std;

  #define all(x) x.begin(), x.end()
  #define sz(x) (int)x.size()

  //--------CODE--------//

  struct Token {
  enum Type {
      INT,
      MOVE,
      READ,
      WRITE,
      RAMREAD,
      RAMWRITE,
      IF,
      WHILE,
      END,
      PLUS,
      MINUS,
      PROD,
      DIV,
      MOD,
      BITAND,
      BITOR,
      BITXOR,
      SHL,
      LESS,
      GREAT,
      LESSEQ,
      GREATEQ,
      EQ,
      DIFF,
      NOT,
      AND,
      OR,
      TOINT,
      OUT,
      COLOUT,
      ENDL,
      EOFF
  };

  Type t;
  string_view s;

  Token(Type t, string_view s) : t(t), s(s) {}
  };

  pair<bool, int> svtoi(string_view &sv) {
  int n = 0;
  auto res = from_chars(sv.data(), sv.data() + sv.size(), n);
  if (res.ec == errc::invalid_argument)
      return {false, 0};
  if (res.ptr != sv.data() + sv.size())
      return {false, 0};
  return {true, n};
  }

  struct Lexer {
  char *prog;

  Lexer(char *prog) : prog(prog) {}

  char peek() { return to_upper(*prog); }
  char get() { return to_upper(*prog++); }

  Token next() {
      while (is_space(peek()))
      get();
      switch (peek()) {
      case 'A':
      case 'B':
      case 'C':
      case 'D':
      case 'E':
      case 'F':
      case 'G':
      case 'H':
      case 'I':
      case 'J':
      case 'K':
      case 'L':
      case 'M':
      case 'N':
      case 'O':
      case 'P':
      case 'Q':
      case 'R':
      case 'S':
      case 'T':
      case 'U':
      case 'V':
      case 'W':
      case 'X':
      case 'Y':
      case 'Z':
      case '+':
      case '*':
      case '/':
      case '&':
      case '|':
      case '^':
      case '<':
      case '>':
      case '=':
      case '!':
      return instruction();
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
      return integer();
      case '-':
      return minus();
      case '#':
      return comment();
      case '\n':
      return exact(Token::ENDL);
      case '\0':
      return exact(Token::EOFF);
      }

      cerr << "Unsupported character '" << peek() << "'\n";
      exit(1);
  }

  bool is_space(char c) { return c == ' ' || c == '\t'; }
  char to_upper(char c) { return (c >= 'a' && c <= 'z') ? c | 0x20 : c; }

  string_view get_word() {
      char *l = prog;
      while (!(is_space(peek()) || peek() == '\n' || peek() == '\0' ||
              peek() == '#'))
      get();
      return string_view(l, prog - l);
  }

  Token instruction() {
      string_view instr = get_word();
      if (instr == "MOVE")
      return Token(Token::MOVE, instr);
      if (instr == "READ")
      return Token(Token::READ, instr);
      if (instr == "WRITE")
      return Token(Token::WRITE, instr);
      if (instr == "RAMREAD")
      return Token(Token::RAMREAD, instr);
      if (instr == "RAMWRITE")
      return Token(Token::RAMWRITE, instr);
      if (instr == "IF")
      return Token(Token::IF, instr);
      if (instr == "WHILE")
      return Token(Token::WHILE, instr);
      if (instr == "END")
      return Token(Token::END, instr);
      if (instr == "+")
      return Token(Token::PLUS, instr);
      if (instr == "*")
      return Token(Token::PROD, instr);
      if (instr == "/")
      return Token(Token::DIV, instr);
      if (instr == "MOD")
      return Token(Token::MOD, instr);
      if (instr == "&")
      return Token(Token::BITAND, instr);
      if (instr == "|")
      return Token(Token::BITOR, instr);
      if (instr == "^")
      return Token(Token::BITXOR, instr);
      if (instr == "<<")
      return Token(Token::SHL, instr);
      if (instr == "<")
      return Token(Token::LESS, instr);
      if (instr == ">")
      return Token(Token::GREAT, instr);
      if (instr == "<=")
      return Token(Token::LESSEQ, instr);
      if (instr == ">=")
      return Token(Token::GREATEQ, instr);
      if (instr == "==")
      return Token(Token::EQ, instr);
      if (instr == "!=")
      return Token(Token::DIFF, instr);
      if (instr == "!")
      return Token(Token::NOT, instr);
      if (instr == "&&")
      return Token(Token::AND, instr);
      if (instr == "||")
      return Token(Token::OR, instr);
      if (instr == "INT")
      return Token(Token::TOINT, instr);
      if (instr == "OUT")
      return Token(Token::OUT, instr);
      if (instr == "COLOUT")
      return Token(Token::COLOUT, instr);

      cerr << "Unsupported instruction '" << instr << "'\n";
      exit(1);
  }

  Token integer() {
      string_view number = get_word();
      auto [success, n] = svtoi(number);
      if (success)
      return Token(Token::INT, number);

      cerr << "Invalid integer '" << number << "'\n";
      exit(1);
  }

  Token minus() {
      string_view instr = get_word();
      if (instr == "-")
      return Token(Token::MINUS, instr);
      auto [success, n] = svtoi(instr);
      if (success)
      return Token(Token::INT, instr);

      cerr << "Invalid integer '" << instr << "'\n";
      exit(1);
  }

  Token comment() {
      while (peek() != '\n')
      get();
      return next();
  }

  Token exact(Token::Type t) { return Token(t, string_view(prog++, 1)); }
  };

  struct Interpreter {
  int head = 0;
  int pc = 0;
  int total_movement = 0;
  int step_counter = 0;
  int max_steps;
  int max_move;
  char *program_text;
  std::vector<int> ram;
  vector<int> tape;
  vector<vector<Token>> program;
  std::vector<int> jump_map;

  Interpreter(char *program_text, vector<int> initial_tape, int max_steps,
              int max_memory, int max_move)
      : max_steps(max_steps), max_move(max_move), program_text(program_text),
          tape(initial_tape) {
      lex();
      build_jump_map();
      ram.resize(max_memory);
  }

  void lex() {
      Lexer lex(program_text);
      program.push_back({});
      while (true) {
      Token token = lex.next();

      if (token.t == Token::ENDL) {
          if (!program.back().empty())
          program.push_back({});
      } else if (token.t == Token::EOFF) {
          if (program.back().empty())
          program.pop_back();
          break;
      } else
          program.back().push_back(token);
      }
  }

  void build_jump_map() {
      jump_map.resize(sz(program), -1);
      vector<pair<Token, int>> st;
      for (int i = 0; i < sz(program); i++) {
      Token &op = program[i][0];
      if (op.t == Token::IF || op.t == Token::WHILE)
          st.push_back({op, i});
      if (op.t == Token::END) {
          if (st.empty()) {
          cerr << "Mismatched END at line " << i + 1 << "\n";
          exit(1);
          }
          auto [start_op, start_line] = st.back();
          st.pop_back();
          if (sz(program[i]) == 1) {
          cerr << "END instruction type not specified at line " << i + 1
              << "\n";
          exit(1);
          }
          if (start_op.t != program[i][1].t) {
          cerr << "Mismatched block: " << start_op.s << " at line "
              << start_line + 1 << " ended by " << op.s << " "
              << program[i][1].s << " at line " << i + 1 << "\n";
          exit(1);
          }

          jump_map[start_line] = i + 1;
          jump_map[i] = start_line;
      }
      }
      if (!st.empty()) {
      cerr << "Unclosed " << st.back().first.s << " block starting at line "
          << st.back().second << "\n";
      exit(1);
      }
  }

  void run() {
      while (pc < sz(program)) {
      step_counter++;
      if (step_counter > max_steps) {
          cerr << "Execution step limit (" << max_steps << ") exceeded\n";
          exit(2);
      }

      int current_pc = pc;
      int tok_idx = 0;

      Token &op = program[pc][tok_idx++];

      int idx, val;
      switch (op.t) {
      case Token::MOVE:
          val = eval_int(tok_idx, op);
          head += val;
          if (head < 0 || head > sz(tape)) {
          cerr << "Tape head moved out of bounds. Head at " << head
              << ", but tape size is " << sz(tape) << "\n";
          exit(3);
          }
          total_movement += abs(val);
          if (total_movement > max_move) {
          cerr << "Execution movement limit (" << max_move << ") exceeded\n";
          exit(2);
          }
          break;
      case Token::WRITE:
          if (head >= (int)tape.size()) {
          cerr << "Trying to write past the end of the tape (" << head << ")\n";
          exit(3);
          }
          tape[head] = eval_int(tok_idx, op);
          break;
      case Token::RAMWRITE:
          idx = eval_int(tok_idx, op);
          if (idx >= (int)ram.size()) {
          for (int i = 0; i < 5; i++) {
              cerr << ram[i] << " " << endl;
          }
          cerr << "Memory index " << idx << " is above memory limit "
              << ram.size() << " when writing\n";
          exit(3);
          }
          if (idx < 0) {
          cerr << "Memory index " << idx << " is below 0 when writing\n";
          exit(3);
          }
          val = eval_int(tok_idx, op);
          ram[idx] = val;
          break;
      case Token::IF:
      case Token::WHILE:
          if (!eval_bool(tok_idx, op)) {
          assert(jump_map[pc] != -1);
          pc = jump_map[pc];
          }
          break;
      case Token::END:
          if (program[pc][tok_idx++].t == Token::WHILE) {
          assert(jump_map[pc] != -1);
          pc = jump_map[pc];
          }
          break;
      case Token::OUT:
          cout << "OUT " << eval_bool(tok_idx, op) << "\n";
          goto end_of_program;
      case Token::COLOUT:
          cout << "COLOUT " << eval_int(tok_idx, op) << " "
              << eval_int(tok_idx, op) << "\n";
          break;
      default:
          // No effect
          break;
      }

      if (pc == current_pc)
          pc++;
      }

  end_of_program:
      cout << total_movement << "\n" << step_counter << "\n";
      for (int i : tape)
      cout << i << " ";
      cout << "\n";
  }

  int eval_int(int &tok_idx, Token &caller) {
      if (tok_idx >= sz(program[pc])) {
      cerr << "Unexpected end of expression\n";
      exit(1);
      }

      Token &op = program[pc][tok_idx++];

      int idx;
      switch (op.t) {
      case Token::READ:
      if (head >= (int)tape.size()) {
          cerr << "Trying to read past the end of the tape (" << head << ")\n";
          exit(3);
      }
      return tape[head];
      case Token::TOINT:
      return eval_bool(tok_idx, op) ? 1 : 0;
      case Token::INT:
      return svtoi(op.s).second;
      case Token::RAMREAD:
      idx = eval_int(tok_idx, op);
      if (idx >= (int)ram.size()) {
          cerr << "Memory index " << idx << " is above memory limit "
              << ram.size() << " when reading\n";
          exit(3);
      }
      if (idx < 0) {
          cerr << "Memory index " << idx << " is below 0 when reading\n";
          exit(3);
      }
      return ram[idx];
      case Token::PLUS:
      return eval_int(tok_idx, op) + eval_int(tok_idx, op);
      case Token::MINUS:
      return eval_int(tok_idx, op) - eval_int(tok_idx, op);
      case Token::PROD:
      return eval_int(tok_idx, op) * eval_int(tok_idx, op);
      case Token::DIV:
      return eval_int(tok_idx, op) / eval_int(tok_idx, op);
      case Token::MOD:
      return eval_int(tok_idx, op) % eval_int(tok_idx, op);
      case Token::BITAND:
      return eval_int(tok_idx, op) & eval_int(tok_idx, op);
      case Token::BITOR:
      return eval_int(tok_idx, op) | eval_int(tok_idx, op);
      case Token::BITXOR:
      return eval_int(tok_idx, op) ^ eval_int(tok_idx, op);
      case Token::SHL:
      return eval_int(tok_idx, op) << eval_int(tok_idx, op);
      default:
      cerr << "Operator '" << caller.s << "' requires an integer, but '" << op.s
          << "' doesn't return one.\n";
      exit(4);
      }
  }

  bool eval_bool(int &tok_idx, Token &caller) {
      if (tok_idx >= sz(program[pc])) {
      cerr << "Unexpected end of expression\n";
      exit(1);
      }

      Token &op = program[pc][tok_idx++];

      switch (op.t) {
      case Token::NOT:
      return !eval_bool(tok_idx, op);
      case Token::LESS:
      return eval_int(tok_idx, op) < eval_int(tok_idx, op);
      case Token::GREAT:
      return eval_int(tok_idx, op) > eval_int(tok_idx, op);
      case Token::LESSEQ:
      return eval_int(tok_idx, op) <= eval_int(tok_idx, op);
      case Token::GREATEQ:
      return eval_int(tok_idx, op) >= eval_int(tok_idx, op);
      case Token::EQ:
      return eval_int(tok_idx, op) == eval_int(tok_idx, op);
      case Token::DIFF:
      return eval_int(tok_idx, op) != eval_int(tok_idx, op);
      case Token::AND:
      return eval_bool(tok_idx, op) && eval_bool(tok_idx, op);
      case Token::OR:
      return eval_bool(tok_idx, op) || eval_bool(tok_idx, op);
      default:
      cerr << "Operator '" << caller.s << "' requires an boolean, but '" << op.s
          << "' doesn't return one.\n";
      exit(4);
      }
  }
  };

  signed main() {
  // err codes
  // 1: SyntaxError
  // 2: RuntimeError
  // 3: OverflowError
  // 4: TypeError

  ifstream box_stream;
  box_stream.open("boxes.txt",ofstream::in);

  ifstream program_stream;
  program_stream.open("program.txt",ofstream::in);
  int tape_len;
  box_stream >> tape_len;
  int max_steps = 1000000000;
  int max_memory = 1000;
  int max_move = 1000*tape_len;

  vector<int> tape(tape_len);
  for (int &i : tape)
      box_stream >> i;

  string line;
  string program = "";
  while (getline(program_stream, line)) {
      if (line == "EOF")
      break;
      program += line + "\n";
  }

  Interpreter(program.data(), tape, max_steps, max_memory, max_move).run();
  }

Subtask 1: Reversing the boxes (7 points)

To start of Mouse Binna want to simply reverse order the values are in.

Input & Limits

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

The first line contains the integer $N$ , the number of Boxes the machine has.

In this subtask $T$ will always be 2 and Case 0 will always have $N=100$ and Case 1 will have $N=40\,000$ .

Output

For the $i$ -th test case output “Case #i:” followed by your program. Your program should reverse the values in the boxes, i.e., the value of BOX 0 goes into BOX N-1 and the other way round etc.

Evaluation

Your program will be tested on a number of examples. In each example, your program will find a machine with exactly $N$ boxes, where each box has a value $b_i$ with $0 \le b_i \le 2^{63}-1$ .

Scoring

You will get $33\%$ of the points for solving Case 0 and $67\%$ of the points for solving Case 1.

Example

Input:

1
2

Output:

Case #0:
RAMWRITE 0 READ
MOVE 1
RAMWRITE 1 READ
WRITE RAMREAD 0
MOVE -1
WRITE RAMREAD 1

Comment:

In this program we read both values in to the RAM and write them into the other cell.

To submit for this subtask, please log in.

Subtask 2: Sorting the boxes (15 points)

Now that Binna knows how to reverse the boxes, she wants to approach more difficult tasks. Can you write a program that sorts the number in the boxes in increasing order?

Input & Limits

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

The first line contains the integer $N$ , the number of Boxes the machine has.

In this subtask $T$ will always be 3 and Case 0 will always have $N=100$ , Case 1 will have $N=3000$ and Case 2 will have $N=40\,000$ .

Output

For the $i$ -th test case output “Case #i:” followed by your program. Your program should sort the values in the boxes. I.e. after your program terminates, the smallest value should be in BOX 0, the next smallest in BOX 1, etc.

Evaluation

Your program will be tested on a number of examples. In each example, your program will find a machine with exactly $N$ boxes, where each box has a value $b_i$ with $0 \le b_i \le 2^{63}-1$ .

Scoring

You will get $17\%$ of the points for solving Case 0, $33\%$ of the points for solving Case 1 and $50\%$ of the points for solving Case 2.

To submit for this subtask, please log in.

Subtask 3: Is the graph connected? (18 points)

Mouse Binna remembers that in school she learned about graphs. She wonders if the machine can be used to solve graph theory problems? In the all following subtasks, the input in the boxes are edges of a graph. The vertices of the graph will be labeled $0,1,{\dots},N-1$ . As the boxes are quite small and only fit a single integer, the edge between $u$ and $v$ is stored as $100\,000\cdot u + v$ .

You also receive a new instruction to output a boolean answer!

Instruction	Explanation
OUT b	Output a boolean value

Your program will terminate after the first OUT instruction is reached

Input & Limits

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 Boxes the machine has. This number also represents the number of edges in the graph.

In this subtask $T$ will always be 4 and Case 0 will always have $N=20$ and $M=50$ , Case 1 will have $N=100$ and $M=200$ , Case 2 will have $N=200$ and $M=10\,000$ , and Case 3 will have $N=100\,000$ and $M=200\,000$ .

Output

For the $i$ -th test case output “Case #i:” followed by your program. Your program should output TRUE if the graph described by the edges in the boxes is connected and FALSE otherwise.

Evaluation

Your program will be tested on a number of examples. In each example, your program will find a machine with exactly $M$ boxes, where each box has a value $b_i$ with $0 \le b_i \le 100\,000\cdot (N-1) + (N-2)$ .

Scoring

You will get $14\%$ of the points for solving Case 0, $21\%$ for solving Case 1, $28\%$ of the points for solving Case 2 and $37\%$ of the points for solving Case 3.

To submit for this subtask, please log in.

Subtask 4: Is the graph bipartite? (27 points)

Mouse Binna wonders if she can also solve more advanced graph problems. Can you help her figure out whether a graph is bipartite? That means that there is an assignment of the numbers $0$ and $1$ to the vertices of the graph such that for every edge the two endpoints of the edge have different colors.

You also receive a new instruction to output colors of a vertex!

Instruction	Explanation
COLOUT u c	Output color $c$ for vertex $u$

Your program should again use the OUT istruction from the previous subtask once it determined whether the graph is bipartite. Your program is terminated when you output a bool. After the program terminated, if you outputted OUT TRUE, you should have also outputted a color for every vertex at least once. If you outputted the color of a vertex multiple times, the last color counts. You need to output a correct coloring for all cases where your program returns TRUE.

Input & Limits

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 Boxes the machine has. This number also represents the number of edges in the graph.

Output

For the $i$ -th test case output “Case #i:” followed by your program. Your program should output TRUE if the graph described by the edges in the boxes is bipartite and FALSE otherwise. If your output was TRUE you should also output a valid coloring of the graph. If the output was FALSE any printed colors will be ignored.

Evaluation

Scoring

You will get $14\%$ of the points for solving Case 0, $21\%$ for solving Case 1, $28\%$ of the points for solving Case 2 and $37\%$ of the points for solving Case 3.

To submit for this subtask, please log in.

Subtask 5: Use as few colors as possible (33 points)

For the final subtask, Mouse Binna finds an arbitrary graph in the machine and wants to color it with as few colors as possible.

Input & Limits

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 Boxes the machine has. This number also represents the number of edges in the graph.

Output

For the $i$ -th test case output “Case #i:” followed by your program. Your program should use the COLOUT function to output a color for each vertex.

Evaluation

Scoring

You will get $14\%$ of the points for solving Case 0, $21\%$ for solving Case 1, $28\%$ of the points for solving Case 2 and $37\%$ of the points for solving Case 3. Within each subtask, you will be scored against the number of colors that you use.

Metric	Points
$\Delta(G)+1$	$80\%$
better than that	Depending on the number of colors

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

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?

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 two integers $N$ and $K$ , the number of statues on shelves and the maximum number of statues a bag can contain respectively.
The second line contains $N$ strictly positive integers. The $i$ -th integer is $w_i$ , the weight of the $i$ -th statue

Output

For the $t$ -th test case, output a line “Case #t:”, followed by the number $S$ , the minimum possible sum of the maximum weight of the statues in each bag.

Subtask 1: Ordered statues (17 points)

When inspecting the statues more closely, Binna realizes that the statues weights are monotonic. That is, the statues are sorted from lightest to heaviest or heaviest to lightest.

Limits

$T=100$
$1 \leq N \leq 10^{6}$
$1 \leq K \leq N$ ;
$1 \leq w_i \leq 10^{9}$ for all $i$

Example

Input:

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

Output:

Case #0: 27
Case #1: 9

Comment:

Case #0: We can use

3

bags, the first one will contain the statue at position

0

and the maximum weight will be

7

, the second bag will contain the statues at position

1

and

2

and it’s maximum weight will be

9

, and the last bag will contain the statues

3

and

4

with a maximum weight of

11

. Thus the sum is

7 + 9 + 11 = 27

. It can be shown that no smaller sum can be achieved.

Case #1: We can put all statues in one bag with a maximum weight of

9

. Thus the minimum sum is also

9

To submit for this subtask, please log in.

Subtask 2: Handbags (18 points)

Binna passed by during her afternoon walk and only brought her collection of handbags which can fit 2 statues (you know about the size restrictions on the airplane flights…)

Limits

$T=100$
$1 \leq N \leq 10^{5}$
$K = 2$ ;
$1 \leq w_i \leq 10^{9}$ for all $i$

Example

Input:

1
5 2
8 7 10 11 5

Output:

Case #0: 24

Comment:

Case #0: We can use

3

bags, the first one will contain the statue at position

0

and

1

and the maximum weight will be

8

, the second bag will contain the statues at position

2

and

3

and it’s maximum weight will be

11

, and the last bag will contain the statue

3

with a maximum weight of

5

. Thus the sum is

8 + 11 + 5 = 24

. It can be shown that no smaller sum can be achieved.

To submit for this subtask, please log in.

Subtask 3: Small bags (24 points)

Binna wasn’t expecting to find so many statues and only brought small bags in the tomb.

Limits

$T=100$
$1 \leq N \leq 10^{5}$
$1 \leq K \leq \min(N, 100)$ ;
$1 \leq w_i \leq 10^{9}$ for all $i$

Example

Input:

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

Output:

Case #0: 24
Case #1: 11

Comment:

Case #0: We can use

3

bags, the first one will contain the statue at position

0

and

1

and the maximum weight will be

8

, the second bag will contain the statues at position

2

and

3

and it’s maximum weight will be

11

, and the last bag will contain the statue

3

with a maximum weight of

5

. Thus the sum is

8 + 11 + 5 = 24

. It can be shown that no smaller sum can be achieved.

Case #1: We can use

3

bags, one with statue

0

, one with statues

1, 2

and

3

, and one with statue

4

. The sum of the maximum weight in each bag is

1 + 9 + 1 = 11

To submit for this subtask, please log in.

Subtask 4: The great find (41 points)

The team has never seen as many historical artifacts in one room and have come prepared with large bags.

Limits

$T=100$
$1 \leq N \leq 10^{6}$
$1 \leq K \leq N$ ;
$1 \leq w_i \leq 10^{9}$ for all $i$

Example

Input:

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

Output:

Case #0: 24
Case #1: 11

Comment:

Case #0: We can use

3

bags, the first one will contain the statue at position

0

and

1

and the maximum weight will be

8

, the second bag will contain the statues at position

2

and

3

and it’s maximum weight will be

11

, and the last bag will contain the statue

3

with a maximum weight of

5

. Thus the sum is

8 + 11 + 5 = 24

. It can be shown that no smaller sum can be achieved.

Case #1: We can use

3

bags, one with statue

0

, one with statues

1, 2

and

3

, and one with statue

4

. The sum of the maximum weight in each bag is

1 + 9 + 1 = 11

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

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:

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

Subtask 4: Collapsed chambers (8 points)

Binna and Stofl are now interested in general cave systems. For now, they are only concerned in systems where many chambers have collapsed under the rocks. So, not many chambers are accessible anymore.

Input & Output

Same as previous subtasks

Limits

$T = 100$
$2 \le N \le 20$
$0 \le c_i \le 10$ for all $0 \le i < N$

To submit for this subtask, please log in.

Subtask 5: Equally sized entrances (14 points)

Stofl and Binna have big ambitions and want to also solve large general cave systems. Luckily, for now, the entrances look exactly the same, thus covering them up gives the same amount of points. They feel otherworldly…

Input & Output

Same as previous subtasks

Limits

$T = 100$
$2 \le N \le 100\,000$
For all chambers on the surface $c_i = 1$ .

To submit for this subtask, please log in.

Subtask 6: The evil aura (43 points)

The evil aura surrounding the ruins created a very spooky and huge cave system. This feels like the work of a divine being, which was able to hold this huge alien cave system together after all the years.

This is the final test, who is the true hero of the world?

Input & Output

Same as previous subtasks

Limits

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

To submit for this subtask, please log in.

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

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.

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

Rank	Username	Total (600)	regista… (100) registanpattern	timurid… (100) timuridriders	mouseda… (100) mousedances	fire (100)	roborbuy (100)	bukhara (100)
	loading ...

Regular Ranking

Rank	Username	Total (700)	mouseda… (100) mousedances	fire (100)	roborbuy (100)	bukhara (100)	tombexp… (100) tombexploration	evilruins (100)	2h (100)
	loading ...