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

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

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

Junior only | harvest | ‒/100 | ‒/17 | ‒/18 | ‒/19 | ‒/21 | ‒/25 |

Junior only | exhibition | ‒/100 | ‒/7 | ‒/23 | ‒/31 | ‒/39 | |

Junior only | cruisetrip | ‒/100 | ‒/20 | ‒/25 | ‒/25 | ‒/30 | |

Both | calendar | ‒/100 | ‒/16 | ‒/12 | ‒/21 | ‒/18 | ‒/33 |

Both | labyrinth | ‒/100 | ‒/12 | ‒/11 | ‒/19 | ‒/26 | ‒/32 |

Both | pyramids | ‒/100 | ‒/14 | ‒/16 | ‒/30 | ‒/40 | |

Regular only | irrigation | ‒/100 | ‒/4 | ‒/13 | ‒/21 | ‒/24 | ‒/38 |

Regular only | caravan | ‒/100 | ‒/10 | ‒/10 | ‒/20 | ‒/35 | ‒/25 |

Regular only | 1h | ‒/100 | ‒/25 | ‒/25 | ‒/25 | ‒/25 |

You may use any programming language to solve the tasks of the first round. To solve a practical task, you have to design a program, download an input file, run the program on the data in that file, write the results in another file and upload it along with the source code to the website, which will grade your submission and display the number of points that you’ve earned as well as an explanation if you did not get all the possible points. In order to read the data in the input file, make sure that your program either reads directly in that file or redirect the standard input to it (in a terminal running on Linux, Windows or OS X, you can do that by using the command ‘yourprogram < inputfile’, replacing ‘yourprogram’ and ‘inputfile’ by the paths to the actual program and input file). More elaborate explanations about how to solve the tasks of the first round await you on our wiki and our training page. Note that in case you get stuck on the tasks, you can move to next task and try again later: no need to solve them in order.

You should also hear about our workshops! In October and November, we offer workshops in two parts about programming and algorithmics. It’s a great opportunity to learn all you need for the first round and to meet other like-minded participants. Whether you’re a beginner or an experienced programmer, it’s worth it to come. More info and registration here.

Don’t hesitate to contact us at info@soi.ch if you have any question about programming or the tasks.

The first 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 second round 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.

The 3 best juniors and 3 best regular participants will be awarded with prizes during the SOI Day in January (if someone is among the 3 best juniors and 3 best regular participants, they win both prizes). Also, we will give the Rainbow Award to the participant who has solved the first round in the Regular category using the most programming languages. The last submission with a nonzero score for each subtask counts.

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

In the town of Bloomsville, Mouse Binna runs a community garden where townsfolk can rent a plot to grow their own fruits and vegetables. Each year, Binna hosts a Harvest Day, where everyone brings the fruits and vegetables they’ve grown to share with the community.

This year, Mouse Binna wanted to ensure that every resident of Bloomsville received an equal share of the harvest, so she provided each person with a basket to fill. But right before the townsfolk came to collect their shares, Binna noticed that some baskets had lots of fruits and vegetables, while others had just a few.

Determined to spread the joy of the harvest equally, Mouse Binna decides to redistribute items from their baskets to balance out their hauls.

Mouse Binna’s challenge is to figure out the minimum number of items she has to move from one basket to another to ensure everyone went home with an equal amount of harvest.

In this subtask, Mouse Binna is not concerned about the number of items she has to swap and only asks you to find out whether it’s possible to swap the items in the baskets so that everyone has the same amount of items in their baskets or not.

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

The first line of the test case contains a single integer number $n$ — the total number of baskets.

The second line contains $n$ integer numbers: $a_i$ — the number of items in the $i$ -th basket.

For the $i$-th test case, output a line “`Case #i: YES`” if it’s possible to swap the items in the baskets so that everyone has the same amount of items in their baskets, or “`Case #i: NO`” otherwise.

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

- $1 \le n \le 1000$
- $0 \le a_i \le 1000$

Input:

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

Output:

Case #0: YES Case #1: NO Case #2: YES

Comment:

To submit for this subtask, please log in.

In this and all following subtasks, Mouse Binna is interested in the minimum number of items she has to move from one basket to another to ensure everyone went home with an equal amount of harvest. Additionally, in this subtask, Binna heard that all farmers in Bloomsville had an exceptionally bad harvest this year and are only able to bring exactly one item. To make sure to spread some joy, she invited her friend from a neighboring town, in the hope that she has had a better harvest this year.

Same as subtask 1.

For the $i$-th test case, output a line “`Case #i: x`” where $x$ is the minimum number of items Binna has to move.

In this and all following subtasks, it is guaranteed that Binna can distribute the items to the baskets equally (in particular that means for all the following cases the answer in Subtask 1 would be yes).

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

- $1 \le n \le 1000$
- $0 \le a_{0}\le 1000$
- $a_i = 1$ for all $i>0$

Input:

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

Output:

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

To submit for this subtask, please log in.

Luckily, the times of the bad harvest are over and the fields have been flourishing again this year. Oddly enough, Mouse Binna notices that everyone arrives with a very similar amount of items. Maybe the rain this year was very evenly distributed over Bloomsville and thus everyone harvested almost the same amount of crops? When doing the math Binna notes that the minimum and the maximum number of items brought by the inhabitants of Bloomsville only differs by $2$.

Same as subtask 2.

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

- $1 \le n \le 1000$
- $0 \le a_{0}\le 1000$
- $|a_i - a_j| \le 2$ for all $i,j$

Input:

3 4 1 3 2 2 4 2 4 3 3 9 1 1 3 1 3 3 2 2 2

Output:

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

To submit for this subtask, please log in.

For the next festival, Mouse Binna notices a wide variety of brought crops both in type and in number. She deduces that there are no special conditions that hold this year and she has to find the minimum amount of items she has to move without any additional assumptions to ensure she does not do any extra work this year.

Same as subtask 3.

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

- $1 \le n \le 1000$
- $0 \le a_i \le 1000$.

Input:

4 4 3 1 3 1 2 2 2 5 14 8 4 3 6 3 20 3 1

Output:

Case #0: 2 Case #1: 0 Case #2: 8 Case #3: 12

To submit for this subtask, please log in.

This year was a very good year for the farmers of Bloomsville and everyone brings enormous amount of fruits and vegetables (up to one billion each). Mouse Binna deduces that there are no special conditions that hold this year and she has to find the minimum amount of items she has to move without any additional assumptions to ensure she does not do any extra work this year.

Same as subtask 4.

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

- $1 \le n \le 10^{5}$
- $0 \le a_i \le 10^{10}$.

Attention: The numbers in this subtask will get very large. If you use integers (e.g. in C++) then you should switch to a larger datatype (e.g. long long) instead to avoid overflows.

Input:

2 4 3 1 3 1 2 0 10000000000

Output:

Case #0: 2 Case #1: 5000000000

To submit for this subtask, please log in.

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

Mouse Stofl wants to make an exhibition of the most expensive paintings that exist, based on his reasoning that the most valuable paintings are also the most beautiful. However, that might be a bit boring, so he additionally has the constraint that, for any painter included in the exhibition, there are at least two paintings of this painter. That way, visitors will be better able to see the individual style of each painter.

Obviously, with all the most expensive paintings in one place, he needs an insurance. For calculating the insurance costs, he needs to know the total value of all the paintings in the exhibition. Since he isn’t yet sure how big the exhibition is going to be, he just wants to calculate it for every possible number of paintings, from 2 up to all the paintings.

This might be a nice idea, but who is actually going to borrow Stofl his most expensive paintings for the exhibition? For now, he just has access to the paintings that he has made himself.

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

- The first line contains two integers $K$ and $N$, the number of painters, and the total number of paintings.
- Each of the $K$ following lines contains a number $N_i$, followed by $N_i$ numbers $v_{i, 0},v_{i, 1},{\dots},v_{i, N_i-1}$, the values in Egyptian pounds of all the $N_i$ paintings of painter $i$.

In this subtask, we always have $K=1$.

For the $t$-th test case print a line “`Case #t:`” followed by $N-1$ numbers,
where the $i$-th number ($0 \le i < N-1$) is the total value of all paintings of the
most expensive exhibition with $i+2$ paintings, and where no painter has
exactly one painting in the exhibition.
It is guaranteed that such an exhibition exists for each $i$.

- $T=100$
- $K=1$
- $2 \le N_i$ for all $0\le i<N$
- $N = \sum_i N_i$
- $N \le 1000$
- $1 \le v_{i, j} \le 10^{5}$ for all $0\le i<N$, $0\le j<N_i$

Input:

3 1 2 2 4 3 1 3 3 8 5 7 1 4 4 3 3 3 3

Output:

Case #0: 7 Case #1: 15 20 Case #2: 6 9 12

Comment:

Case #0: There are only two paintings of value $4+3=7$ Egyptian pounds, so we have to take both.

Case #1: The two most expensive paintings have value $8+7=15$ EGP. All three paintings are worth 20 EGP.

To submit for this subtask, please log in.

Just one painter is clearly not enough. Stofl additionally asked Mouse Binna whether he could borrow her paintings, and luckily she agreed.

Same as in subtask 1.

In this subtask, we always have $K=2$.

- $T=100$
- $K=2$
- $2 \le N_i$ for all $0\le i<N$
- $N = \sum_i N_i$
- $N \le 5000$
- $1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

Input:

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

Output:

Case #0: 12 17 15 20 Case #1: 13 16 24 29 31 32

Comment:

Case #0: The paintings of painter 0 are all more expensive than those of painter 1,
so we only take these for exhibitions with two or three paintings.
However, if we want four paintings, we have to take both paintings of painter 1,
and the exhibition ends up worth less than with just three paintings.

To submit for this subtask, please log in.

Mouse Stofl made a lot of phone calls to various galleries, and finally found the Bibliotheca Alexandrina, who was willing to lend some paintings from its collection to Stofl.

Same as in subtask 1.

- $T=100$
- $1 \le K \le 500$
- $2 \le N_i$ for all $0\le i<N$
- $N = \sum_i N_i$
- $N \le 1000$
- $1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

Input:

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

Output:

Case #0: 14 17 26 29 36 39 41 42 Case #1: 14 18 28 32 38 42 46 49 52 55 58 60 61 62

To submit for this subtask, please log in.

The previous exhibition was a huge success. Afterwards, many art owners contacted Mouse Stofl and offered to lend their paintings for an even bigger exhibition.

Same as in subtask 1.

- $T=100$
- $1 \le K \le 40000$
- $2 \le N_i$ for all $0\le i<N$
- $N = \sum_i N_i$
- $N \le 80000$
- $1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

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

The Nile is a famous river in Egypt and one of the longest in the world. Mouse Stofl, who recently heard about the river, is planning to rent a cruise ship and travel on the Nile to appreciate the magnificent landscape. He wants to be the coolest mouse in his friend group by surprising them with all the photos he’s going to take during the trip. He wants to visit three different cities in Egypt to replenish his supplies and asks for your help to plan the route he’s going to take. On the map he gave you, the Nile is divided into a grid of $N$ rows and $M$ columns with islands positioned on some grid cells. Every $10$ minutes, the boat can move to an adjacent grid cell provided no island is occupying the cell. A cell is adjacent to another one if both cells share a common side, diagonals are not permitted.

Because he has high standards, Mouse Stofl wants the cruise to be as long as possible without travelling through the same grid cell twice and without travelling upstream because of his limited supplies. This means for each movement you can travel one cell left, one cell right or one cell down. Fortunately for you Stofl has already made sure there exists a trip which satisfies his constraints but he did not know how to make sure the trip was the longest one possible.

Mouse Stofl has the authorization to start his trip anywhere on the upper row of the grid if there is water there and must travel downstream to any of the cells on the bottom row of the grid.

All subtasks have the same input and output format.

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 $M$, the number of rows and columns of the grid respectively.
- The next $N$ lines will contain $M$ characters either “
`#`” or “`.`”. “`#`” indicates the cell contains an island, “`.`” indicates you can travel freely from and to this cell.

A valid trip from the top row to the bottom one is guaranteed to exist.

For the $t$-th test case, output a line “`Case #t:`”, followed by the number $L$, the maximum possible length of a trip.

The first destination Stofl wants to reach is Sohag. The width of the Nile until Sohag is very narrow. On the map you have to prepare the trip, the Nile is separated into only two columns.

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

Input:

2 3 2 .. .# .# 5 2 #. #. .. .. .#

Output:

Case #0: 4 Case #1: 6

Comment:

To submit for this subtask, please log in.

After his first stop, the Nile is becoming wider and Mouse Stofl now has more freedom when travelling. The Nile is now represented with at most $20$ columns on the map.

- $T=100$
- $2 \le M \le 20$
- $1 \le N \le 5\cdot 10^{5}$

Input:

2 3 5 ...#. .#.#. ...#. 5 6 ...#.. ..##.. ...#.. .#.... .#.#..

Output:

Case #0: 7 Case #1: 13

Comment:

To submit for this subtask, please log in.

Mouse Stofl left Asyut and is now heading to Cairo on the largest part of the Nile. The map you have doesn’t have a width restriction. However his boat has a technical problem which causes the boat’s steering mechanism to malfunction. Because of that Mouse Stofl is unable to steer enough to make his boat travel in all directions. He can now either go down or to the right. That means for each grid cell the boat can either go to the cell directly to its right or the one directly downwards. Even with the problems he is facing Stofl does not want to cancel his trip so he wants you to create him a trip which never goes left.

Same as in the previous subtasks. Additionally, in this subtask it is guaranteed that there exists a valid trip from the top row to the bottom row which only requires Stofl to move down and to the right. You need to output the longest possible length of such a trip.

- $T=100$
- $2 \le N \cdot M \le 5\cdot 10^{6}$

Input:

2 5 6 ...#.. ..##.. ...#.. .#..#. .#.#.. 7 8 .##.#.#. #..#..#. .#...... ...##.## ##.##..# ...#.#.# .#...#.#

Output:

Case #0: 7 Case #1: 8

Comment:

To submit for this subtask, please log in.

Mouse Stofl managed to fix the problem with his boat’s steering and now only needs to finish his trip. He can again go in all three directions, left, right or down.

- $T=100$
- $2 \le N \cdot M \le 5 \cdot 10^{6}$

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

Mouse Binna had to leave Mouseland for Egypt in order to plan the upcoming IMOI (the International Mouse Olympiad in Informatics). Unfortunately, Egypt is very warm and Binna finds it very hard to get work done. She now has one month to finalize the planning of IMOI which also lasts one month. As it is well known, every month of the mice-calendar contains exactly $n$ days. She still has $m$ event to plan before the competition starts. The $i$-th event starts on day $l_i$ and ends on day $r_i$. Luckily, Mouse Binna is very good at multitasking and can handle as many events as needed on the same day.

Additionally, Mouse Stofl reminded her that the SOI camp is scheduled to happen the same month as IMOI and should last exactly $k$ days. However, she can choose when in the month the camp will happen to ease the planning.

To keep her organisation schedule easy to follow, she decides to plan an entire day of events during a single day of preparation and does not work on any other day during this day. That is on the $i$-th day of preparation she will do the necessary work to plan the $j$-th day of IMOI, where $0 \le i,j \le n-1$.

As the weather is much warmer than Mouseland’s chill countrylands, her productivity decreases as time goes on. On the first day, she has a productivity score of $n-1$ and every day loses one productivity point up to her last preparation day where she has productivity score of $0$.

As Mouse Binna is very dedicated she wants IMOI and the SOI camp to run as smoothly as possible, hence she wants to work on the days that have more events first. In fact, she estimates her work’s worth as the sum of each’s tasks accomplished times the productivity on that day. That is if she had $a$ tasks on a day with productivity $b$, her score for that day is $a \cdot b$.

Because of all the work she has to do, she does not have time to choose when she will plan which tasks, so she charged you to choose the order that will maximise her productivity. And who knows, if you do it well, she might even invite you to the camp!

In this subtask $k=0$, which means that Binna doesn’t have to do the camp planning, because Stofl already did it for her.

However, all IMOI events starts on the first day of the competition, i.e. $l_i=0$ for all $0 \le i \le m-1$.

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

The first line of the test case contains three integer numbers $n$, $m$ and $k$ — the number of days, the number of IMOI events and the length of the camp.

The following $m$ lines contains two integer numbers in each: $l_i$ $r_i$ — the $i$-th event starts on the $l_i$-th day and ends on the $r_i$-th day (inclusive).

For the $i$-th test case, output a line `"Case #i: "` followed by single integer number $s$ — the maximum total productivity score Binna can get for all events.

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

- $1 \le n \le 1000$
- $0 \le m \le 1000$
- $k = 0$
- $0 = l_i \le r_i < n$ for all $0 \le i \le m-1$.

Input:

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

Output:

Case #0: 14 Case #1: 9 Case #2: 6

Comment:

To submit for this subtask, please log in.

Stofl still did the camp planning for Binna ($k = 0$), but now the IMOI events can start on any day, i.e. $0 \le l_i \le r_i < n$ for all $0 \le i \le m-1$.

Same as subtask 1.

Same as subtask 1, except that for $l_i$ we have $0 \le l_i < n$.

Input:

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

Output:

Case #0: 9 Case #1: 8 Case #2: 6

Comment:

To submit for this subtask, please log in.

In this subtask Mouse Binna is still getting help from Mouse Stofl with the Camp planning but a month in Mouseland can be very long and there are a lot of events to be planned for IMOI.

Same as subtask 2.

Same as subtask 2, but $n \le 10^{5}$ and $m \le 10^{5}$.

Input:

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

Output:

Case #0: 9 Case #1: 8 Case #2: 6

To submit for this subtask, please log in.

In this and the next subtasks Mouse Binna has to do the camp planning as well. Note that in this subtask the length of a month is shorter and there are less events to plan than in Subtask 3.

Same as subtask 2.

Same as subtask 2, but $0 \le k \le n$.

Input:

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

Output:

Case #0: 14 Case #1: 11 Case #2: 8

Comment:

To submit for this subtask, please log in.

In this subtask the months in Mouseland can be very long again and there are a lot of events to plan for IMOI.

Same as subtask 4.

Same as subtask 4, but $n \le 10^{5}$ and $m \le 10^{5}$.

Input:

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

Output:

Case #0: 47 Case #1: 1 Case #2: 0 Case #3: 56

To submit for this subtask, please log in.

The famous explorer Mouse Binna is undergoing an expedition in the ancient tomb of the Great Mouse Pharaoh Stofl. While wandering through the labyrinth of the Pharaoh, she unexpectedly steps on an unsuspicious stone activating one of the many grave traps. Fortunately, as a famous explorer would, she came prepared with a plan for deactivating such a trap. For this she needs to rearrange torches in the labyrinth in a specific way:

The labyrinth consists of $N$ chambers. There are $N-1$ corridors, each connecting two chambers. It is possible to walk from any chamber to any other chamber using one or more of the corridors. Furthermore, there are no cycles in the labyrinth.

Each of the chambers has either a torch or no torch in it. Mouse Binna has a map of the labyrinth showing in which chambers a torch should be and in which not, to deactivate the trap. Unfortunately, the current distributions of the torches might not be according to her map, so she needs to move some torches.

She can take a torch from one chamber and move it to another chamber which is directly connected via a corridor and where there is no torch already. (Two torches in one chamber destabilized the labyrinth endangering Binna’s life further). As carrying a torch through a corridor might also destabilize the labyrinth, she wants to minimize the amount of time a torch moves through a corridor. (As an experienced and modern explorer she does not care how long she walks, or if she needs to walk without a torch, as she has her trusty headlamp).

Can you help her find the minimal amount of times a torch moves through a corridor?

The first line contains the number of test cases $T$. This is followed by $T$ test cases in the following format: The first line of the test case contains $N$, the number of chambers in the labyrinth.

$N$ lines follow, each line has two characters $m_i$ $t_i$, either “`0`” or “`1`”, separated by a space.
The first character represents the number of torches that should be present in the chamber at the end.
The second character represents the number of torches in the chamber at the beginning.
The total number of torches that should be in the end is the same as the number of torches in the beginning.

Then $N-1$ more lines follow, describing the structure of the labyrinth. Each line with two integers $v_i$ $u_i$, separated by a space, representing a corridor between the chamber $v_i$ and $u_i$.

For the $i$-th test case, output single line “`Case #i:`”, followed by a single integer, the minimal amount of time a torch moves through a corridor.

For every input, it is guaranteed that there is a sequence of torch moves that places a torch in each chamber according to the map.

You might hit recursion limit, memory limit, stack limit or similar, if you are using recursive functions in python. See this wiki article on possible solutions for these problems.

The Mukhtar Tomb is of a very special shape. There is a central chamber with the mummy of the Pharaoh, with index $0$. Every other chamber is connected to the central chamber.

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

- $1 \le N \le 100\,000$
- $u_i = 0$

Input:

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

Output:

Case #0: 2 Case #1: 0

Comment:

In this example, the tomb has four chambers, chamber $0$ centered in the middle and three chambers connected to it.

We need to move the torch away from chamber $1$, and move a torch into chamber $3$. Unfortunately, we cannot directly do this.

Instead, we first move the torch from chamber $1$ to chamber $0$ getting chamber $1$ correct, but chamber $0$ wrong.

Then move the torch from chamber $0$ to chamber $3$.

Chamber $0$ has no torch anymore, but chamber $3$ has, as desired by the map.

So the solution is `2` as we moved a torch through corridor $1-0$ and through $0-3$.

In this case there is only one chamber without any torch, so there is nothing to do.

To submit for this subtask, please log in.

In the dark tomb there exists only one torch in the whole labyrinth.

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

- $1 \le N \le 100\,000$
- $c_i = 1$ for one $i$ and $c_i = 0$ for all else
- $t_i = 1$ for one $i$ and $t_i = 0$ for all else

Input:

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

Output:

Case #0: 3 Case #1: 2

Comment:

The labyrinth is ordered on a line like this: $0-1-2-3$.

We need to move the torch from chamber $3$ all the way to chamber $0$, to match the pattern on her map.

Similar as `Case #0` in subtask 1.

To submit for this subtask, please log in.

All the chambers are ordered in a line. Can you make use of this to reorder the torches?

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

- $1 \le N \le 1\,000\,000$
- $u_i = v_i - 1$ for $1 \le u_i \le N-1$

Input:

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

Output:

Case #0: 3 Case #1: 6

Comment:

Similar as `Case #0` in subtask 2.

Move the torch from chamber $2$ to chamber $4$, passing through $2$ corridors.

Then move the torch from chamber $1$ to chamber $4$, passing through $2$ corridors again.

Finally, move the torch from chamber $0$ to chamber $3$, passing through $2$ corridors again.

Since the corridors $1-2$ and $2-3$ are passed through twice, they are also counted twice in the solution.

To submit for this subtask, please log in.

Tomb of Mouse Tutankhamun does not contain many chambers, as they died at a young age.

As Tutankhamun did not get a pyramid like other pharaohs, the layout of his tomb is modeled after a pyramid. This means that there are $h$ chambers ordered on a line, representing the left side of the ‘pyramid’. Starting from the first chamber of this ‘left line’, there is another line, with $h-1$ chambers. Starting from the second chamber of this ‘left line’, there is another line, with $h-2$ chambers. Continue like this until the last chamber of this ‘left line’ (here there is no further line, as it would contain $0$ chambers). In total there will be $n = \frac{h \cdot (h + 1)}{2}$ chambers in such a tomb.

Here are two pictures, visualizing the labyrinth of such tombs:

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

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

- $1 \le N \le 1\,000$

Input:

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

Output:

Case #0: 17 Case #1: 3

To submit for this subtask, please log in.

Now that you have mastered all the previous tombs it is time for the challenge. The Tomb of Great Pharaoh Stofl is the largest tomb known to mousekind. In this tomb, there are no additional restrictions on the structure of the labyrinth. Recall that in any labyrinth it is possible to walk from any chamber to any other chamber using one or more of the corridors. Furthermore, there are no cycles in any labyrinth. Can you help Binna escape the Great Pharaoh Stofl’s trap?

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

- $1 \le N \le 1\,000\,000$

To submit for this subtask, please log in.

Mouse Stofl is in charge of organizing the excursions for IMOI 2024 in Egypt. Of course, a trip to see the famous Pyramids cannot be missing from the program. When Stofl arrives in the desert, he is very disappointed to not actually see pyramids but what seems to be an arbitrary pile of stones with $N$ stones.

After taking a closer look, Stofl realizes that these stones can actually form a pyramid and is determined to reconstruct it. The pieces are of different sizes (denoted by $0,1,2,{\dots},N-1$) and Stofl notices that there is exactly one stone of every size (in particular that means that there are exactly $N$ stones).

Next to the pile of stones there are $K-1$ stable patches where Stofl can place the stones. When Stofl tries to place a stone anywhere else in the desert it starts to sink into the sand. The spot below the pile of stone is also stable (so there is a total of $K$ stable patches).

In his class “Pyramid building 1x1” Stofl learned that pyramids need to be built with the largest stone at the bottom and then adding the other stones in decreasing size (that is, the stone with size $N-1$ goes on the bottom, the stone with size $N-2$ on top of it, then the stone with size $N-3$ and so on). The stones are all very heavy and Stofl can only carry one at a time. For every pile of stones, he can pick up the top stone and place it on any other pile or any empty stable patch.

Stofl asks you for help on how to build the pyramid in the place where the pile of stones is currently located.

In this subtask you do not have to plan how to move the stones but only execute Stofl’s instructions. Stofl has already started building the pyramid before you arrived, so in this subtask the stones are arbitrarily distributed as piles on the $K$ stable patches.

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

The first line of each test case contains three numbers $N,K,M$ which represent the number of stones, the number of stable patches (including the ones the stones are currently lying on) and the number of instructions Stofl gives you.

The next $K$ lines will describe the piles of stone. Each of these lines starts with a number $r$ with $0\le r\le N$, the number of stones on this pile, followed by $r$ numbers $s_{0},s_{1},{\dots}s_{r-1}$ where $0 \le s_i\le N-1$ indicating the size of the $i$-th stone on this pile from the bottom to the top (that is, $s_{0}$ is the size of the bottom most stone and $s_{r-1}$ is the size of the stone on top of the pile).

The next $M$ lines will each contain two numbers, $a$ and $b$ with $0\le a,b\le K-1$, that represent that we moved the top element from stack $a$ to stack $b$. It is guaranteed that this is a legal move (this is, that stack $a$ is not empty).

It is guaranteed that every stone size from $0$ to $N-1$ appears exactly once.

For the $t$-th test case, on the first line print “`Case #t:`”.
This should be followed by $K$ lines, where the $i$-th line first contains a number $r_i$ indicating the number of stones on the $i$-th pile after you executed all of Stofl instruction, followed by $r_i$
numbers $s_{0},s_{1},{\dots},s_{r_i-1}$ separated by spaces, describing the size of the
stones on the $i$-th pile starting with the lowest stone.

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

- $1 \le N \le 1000$,
- $2\le K\le 10$,
- $1\le M\le 10000$.

Input:

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

Output:

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

Comment:

To submit for this subtask, please log in.

The Pyramid of Ahmose is a small pyramid located near Abydos. Mouse Stofl decided this is the perfect location to train you how to build a pyramid.

From now on, all the stones will be on pile $0$ initially and you have to decide how to move the stones to end up with a pyramid at the end.

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

The first line of each test case contains two numbers $N,K$ which represent the number of stones and the number of stable patches (including the one the stones are currently lying on). The next line describes the order of stones on the first pile. There are $N$ numbers, separated by spaces, $s_{0},s_{1},{\dots},s_{N-1}$ where $0 \le s_i\le N-1$ indicating the size of the $i$-th stone on the first pile from the bottom to the top (that is, $s_{0}$ is the size of the bottom most stone and $s_{N-1}$ is the size of the stone on top of the pile).

It is guaranteed that every stone size from $0$ to $N-1$ appears exactly once, in particular, the stones on pile $0$ form a permutation of the numbers from $0$ to $N-1$.

For the $t$-th test case, on the first line print “`Case #t: M`” where $M$ is the number of moves you make to build the pyramid on pile $0$.
This should be followed by $M$ lines, each containing two numbers $a$ and $b$ such that $0\le a,b \le N-1$ indicating you move the top stone from pile $a$ to pile $b$.

The moves you output must result in a pyramid on pile $0$ for your program to get points on this subtask.

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

- $1 \le N \le 10$,
- $K=3$.
- $M\le 27\,000$: Your solution must use at most 27000 moves.

Input:

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

Output:

Case #0: 6 0 1 0 2 0 2 1 0 2 0 2 0 Case #1: 9 0 1 0 1 0 2 0 1 2 0 1 2 1 0 2 0 1 0

To submit for this subtask, please log in.

As you have proven in the last subtask that you do indeed know how to build a pyramid, Stofl leads to the site of the Pyramid of Menkaure, this is a large pyramid close to the city of Giza.

As Stofl wants the reconstructed pyramid to be ready for the start of IMOI 2024, he asks you to try to keep the number of moves you make as low as possible. In particular, to get full points on this subtask you should not use more than $4500$ moves.

Same as Subtask 2

Same as Subtask 2

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

- $1\le N \le 500$,
- $K=3$.
- $M\le 27\,000$: Your solution must use at most 27000 moves.

If you need $4500$ or less moves you get 30 points. If you use more than $4500$ moves, the number of points you get will be

$\lfloor 4500/moves\cdot 30 \rfloor$To submit for this subtask, please log in.

As the final project, Stofl leads you to the pyramid complex of Dashur. As this is a huge pyramid complex, you have more stable patches available than before. That should make it easier right? But Stofl is getting more impatient as IMOI 2024 is approaching soon, so to get full points on this subtask, you should not use more than $2500$ moves.

Same as Subtask 2

Same as Subtask 2

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

- $1 \le N \le 500$,
- $K=5$.
- $M\le 27\,000$: Your solution must use at most 27000 moves.

If you need $2500$ or less moves you get 40 points. If you use more than $2500$ moves, the number of points you get will be

$\lfloor 2500/moves\cdot 40 \rfloor$Input:

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

Output:

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

To submit for this subtask, please log in.

Irrigation canals are a key innovation that allowed the Egyptian agriculture to flourish since the ancient times. In this problem, we will represent the set of irrigation canals in Egypt as an undirected graph, with nodes of the graph corresponding to the junctions and edges of the graph corresponding to the actual canals.

To avoid difficulties with controlling the water flow, there must be no cycles in this graph. In other words, this graph is a forest. Note that it is not necessarily a tree, or in other words it is not necessarily connected. Some junctions might even have no canals connected to them, in other words the graph may have isolated vertices.

Some nodes in this graph correspond to the water sources (typically a junction with a river, or a spring). You need to redesign the existing canal system to maximize the number of junctions that are connected to at least one water source through the canals. In other words, you need to maximize the total size of the connected components containing at least one water source node.

The canal construction is hard work, so you need to do the redesign one improvement at a time. In one improvement, you can choose
one junction as the *pivot junction*, destroy one of the canals connected to the pivot junction, and build a new canal connecting
the pivot junction to any other junction.
Since we destroy one canal and build one canal, the total number of canals stays the same. You may not introduce
cycles when building the new canals, in other words the graph must still be a forest after each improvement. In particular, you
may not have more than one canal between the same pair of junctions, or connect a junction to itself. You may not choose a junction
with no connected canals as the pivot junction, since there would be no canal to destroy.

You can do multiple improvements, but to avoid concentrating too much construction work in one place, each junction may be touched by improvements at most once. Note that each improvement touches three junctions: the pivot junction, the one it is being disconnected from, and the one it is being connected to.

Your goal is to find such a sequence of improvements that touches each junction at most once, and after all improvements are made the number of junctions that are connected to at least one water source is as high as possible. Note that the number of improvements that you do does not matter, only the end result.

All subtasks have the same input and output format.

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

- The first line contains three integers $N$ — the number of junctions, $M$ — the number of canals, and $K$ — the number of junctions that are water sources.
- The next $M$ lines contain two junction numbers each, denoting two junctions connected by a canal. The junctions are numbered from $0$ to $N-1$.
- The next line contains $K$ distinct junction numbers that are water sources.

For the $t$-th test case, output a line containing “`Case #t:`”, followed by two integers $S$ and $P$: the number
of junctions that you have managed to connect to at least one water source through the canals (directly or indirectly), and the number of
improvements that you have made to do so. In the $i$-th of the following $P$ lines, print three integers $a_i$, $b_i$, and $c_i$: the number
of the pivot junction, the number of the junction that the canal being destroyed connects the pivot junction to, and
the number of the junction that the canal being built connects the pivot junction to.

In case there are multiple solutions that lead to the maximum amount of junctions connected to at least one water source, you may output any such solution.

In this subtask there are at most three junctions and exactly one water source.

- $T=100$.
- $1 \le N \le 3$.
- $0 \le M \le N-1$.
- $K=1$.

Input:

1 3 1 1 0 2 1

Output:

Case #0: 2 1 0 2 1

Comment:

After the improvement, junctions $0$ and $1$ are connected.
Since junction $1$ is the water source, two out of three junctions are connected to a water source. It is impossible to
connect all three.

To submit for this subtask, please log in.

In this subtask there are at most seven junctions and exactly one water source.

- $T=100$.
- $1 \le N \le 7$.
- $0 \le M \le N-1$.
- $K=1$.

Input:

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

Output:

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

To submit for this subtask, please log in.

In this subtask there are at most $100$ junctions and exactly one water source.

- $T=100$.
- $1 \le N \le 100$.
- $0 \le M \le N-1$.
- $K=1$.

To submit for this subtask, please log in.

In this subtask there are at most $100$ junctions and the water sources are not connected to each other, directly or indirectly.

- $T=100$.
- $1 \le N \le 100$.
- $0 \le M \le N-1$.
- $1 \le K \le N$.
- There is no sequence of canals connecting one water source to another.

Input:

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

Output:

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

To submit for this subtask, please log in.

In this subtask there are at most $100$ junctions.

- $T=100$.
- $1 \le N \le 100$.
- $0 \le M \le N-1$.
- $1 \le K \le N$.

Input:

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

Output:

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

To submit for this subtask, please log in.

Caravans played an important role in long-distance desert travel and trade in ancient Egypt. Not on camels though! The camel, originating from North America, has not been domesticated until the 3rd millennium BC. Instead, ancient trade has been served on donkey caravans.

Mouse Binna, the vizier of pharaoh Binothris (ca. 2850 BC to 2760 BC), has been tasked to establish new trade routes for her pharao’s empire.

Trade is centered around an oasis that houses some donkeys and the task is to give instructions to those donkeys. There is a route from trade post A to trade post B with an oasis O in the middle. The distance between A and O is $a$, the distance between O and B is $b$.

Wares have to be transported between trade post A ($a$ kilometers left of oasis O) and trade post B ($b$ kilometers right of oasis O), and in subtasks 3-5 also back from B to A.

A a O b B |<==========>|<============>| | | | Trade Oasis Trade post A (donkeys) post B

The transportation needs to happen within one day and that is what the donkeys are for. The $N$ donkeys ($0,1,{\dots},N-1$) are initially stationed at the oasis. The $i$-th donkey can travel at most $d_i$ kilometers in one day. You are given the $d_{0},d_{1}{\dots},d_{N-1}$ in the input.

You can control the donkeys individually by letting them move left (towards A) or right (towards B) by any possibly non-integer amount, and you may switch directions arbitrarily. Note that after donkey $i$ travelled his $d_i$ kilometers, it will not be able to move until the end of the day.

- If a donkey reaches A you can tell it to pick up the wares from the trade post.
- If two donkeys $i$ and $j$ are at the same position and one of the donkeys has the wares, you may switch the wares over from one donkey to the other.
- If a donkey with the wares reaches B you can drop them off. In subtasks 1 and 2 you are done, in subtasks 3 to 5 you have to go back; after you reached B with the first batch of wares from A, you will then get new wares which you have to transport back to A.

In this subtask $b=0$, therefore the oasis and the second trade post are at the same position.

Is it possible to bring wares from A to O with the available donkeys?

A a O |<==========>| | | Trade Oasis & post A Trade post B

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

The first line of the test case contains three numbers $N$, $a$ and $b$.

A second line follows with $N$ integers, distances $d_{0},d_{1},{\dots},d_{N-1}$ the $i$-th donkey can travel.

For the $i$-th test case, output a line “`Case #i: YES`” if it’s possible to send the donkeys from $A$ to $B$ or “`Case #i: NO`” if not.

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

- $1 \le N \le 100$
- $0 \le a \le 100$
- $b = 0$
- $0 \le d_i \le 100$ for all $0 \le i \le N-1$.

Input:

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

Output:

Case #0: NO Case #1: YES Case #2: YES

Comment:

A O W-----------+----------- v<= <= <= <=| donkey 1 |=>v | d_1=5 |--W--------|----------- | v<= <= <=| donkey 2 | =>v | d_2=4 |-----W-----|----------- | v<= <=| donkey 2 | => =>v d_0=4 +-----------W-----------

To submit for this subtask, please log in.

This time trading post B might be at a different location than the oasis. Can we to transport the wares from A to B?

A a O b B |<==========>|<============>| | | | Trade Oasis Trade post A (donkeys) post B

Same as subtask 1.

Same as subtask 1, except that for $b$ we have $0 \le b \le 100$.

Input:

4 5 5 9 6 5 4 4 9 5 5 9 6 5 4 3 9 2 3 3 9 1 2 7 3 5 13

Output:

Case #0: YES Case #1: NO Case #2: YES Case #3: YES

Comment:

Case #0:

5 4 3 2 1 0 ... 9 +--------------| d0=6 +--> | +-----------| d1=5 +--> | +--------| d3=4 +--> | +-----| d2=4 +---->| |--...-> d4=9

To submit for this subtask, please log in.

In this and the next subtasks Mouse Binna has to bring the wares from A to B and back.

Additionally, $a$ and $b$ are not always given, instead you have to find the maximal values for which it is possible to plan a successul trade route.

In this subtask in particular we have $a=0$ so we are dealing with the following situation:

O b B |==============>| first go A->B, |<==============| then B->A. | | Oasis & Trade Trade post A post B

The first line of the test case contains the single integer $N$.

A second line follows with $N$ integers, distances $d_{0},d_{1},{\dots},d_{N-1}$ the $i$-th donkey can travel.

For the $i$-th test case, output a line “`Case #i: b`”, where $b$ is the largest possible distance such that it there exists a trade route from A to B and back.

Your answer is accepted if the absolute error is below $10^{-6}$. In other words, if your output is $x$ and the correct solution is $y$, your output is correct if and only if $|x-y| \le 10^{-6}$.

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

- $1 \le N \le 100$
- $0 \le d_i \le 100$ for all $0 \le i \le N-1$.

Input:

3 1 5 2 3 3 16 7 6 6 5 1 4 3 1 1 1 1 1 1 1 1 4

Output:

Case #0: 2.5 Case #1: 2.25 Case #2: 6.2812347

To submit for this subtask, please log in.

Same as subtask 3, but in this subtask we have $b=0$ so we are dealing with the following situation:

A a O |==============>| first go A->B, |<==============| then B->A. | | Trade Oasis & post A Trade post B

Same as subtask 3.

For the $i$-th test case, output a line “`Case #i: a`”, where $a$ is the largest possible distance such that it there exists a trade route from A to B and back.

Your answer is accepted if the absolute error is below $10^{-6}$.

Same as subtask 3.

Input:

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

Output:

Case #0: 7 Case #1: 5.02222222 Case #2: 5.05882353 Case #3: 3.14141414 Case #4: 2.77777778 Case #5: 3 Case #6: 3.09803922

To submit for this subtask, please log in.

This time we are dealing with the general case:

A a O b B |============|=============>| first go A->B, |<===========|==============| then B->A. | | | Trade Oasis Trade post A (donkeys) post B

Distance $b$ is fixed and given in the input. Help Binna to find the maximum distance $a$ such that trade is possible.

The first line of the test case contains two integers $N$ and $b$.

A second line follows with $N$ integers, distances $d_{0},d_{1},{\dots},d_{N-1}$ the $i$-th donkey can travel.

For the $i$-th test case, output a line “`Case #i: a`” where $a$ is the largest possible distance such that it there exists a trade route from A to B and back. If it is not possible to make a trade route, print -1 instead.

Your answer is accepted if the absolute error is below $10^{-6}$.

Input:

4 3 3 9 11 5 5 1 5 3 3 5 5 4 1 8 6 3 2 5 5 5 3 3 5 5

Output:

Case #0: 5.8 Case #1: 4.21568627 Case #2: 4.88888889 Case #3: -1

To submit for this subtask, please log in.

The homework part of round1 (1H) 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.

1H GraderThis helps you get familiar with our grading system which we will use in all our events after round1, including workshops, camp, round2 and the finals.

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 1H 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.

Rank | Username | Total (600) | harvest (100) | exhibition (100) | cruisetrip (100) | calendar (100) | labyrinth (100) | pyramids (100) |
---|---|---|---|---|---|---|---|---|

loading ... |

Rank | Username | Total (600) | calendar (100) | labyrinth (100) | pyramids (100) | irrigation (100) | caravan (100) | 1h (100) |
---|---|---|---|---|---|---|---|---|

loading ... |

Case #0: Binna could move 2 items from the 2nd basket to the 1st basket, and 1 item from the 4th basket to the 3rd basket and 2 items from the 4th basket to the 5th basket, so that each basket would contain exactly 3 items.Case #1: Binna could not make all baskets contain the same number of items.Case #2: Binna could move 2 items from the 3rd basket to the 1st basket, and 5 items from the 2nd basket to the 4th basket, so that each basket would contain exactly 5 items.