First Round SOI 2016

Subtask 1: Small Cable Car (10 Points)

The cable car has already been built by Stofl. There are exactly 3 pillars, which are installed in distances of 1. Help Stofl to decide if the view can be enjoyed or not.

Stofl does not only want to build a model cable car, but $T$ of them. Each of those cable cars has its own pillars and is independent of the others.

Example

Sample input for subtask 1.

Input:

2
3
3 5 7
3
3 5 10

Output:

Case #1: yes
Case #2: no

Comment:

Case #1: For the first cable car, the slope between the first and the second pillar is 2, which is also the case between the second and the third pillar. The slope does not change. Hence the view can be enjoyed.

Case #2: For the second cable car, the slope between the first to the second pillar is 2 as well, but the slope between the second to the third pillar is 5. As the slope changes, the view cannot be enjoyed optimally.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download Input Submit C++ Solution

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Output

Check output

Problem with newlines?

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.

Output

Source Code

Upload

Subtask 2: Long Cable Car (20 Points)

While you solved the first subtask, Mouse Stofl bought an extension kit for his cable car. Equipped with this kit, he now has $10\,000$ pillars to dispose. He picks $N$ of them and installs them as in Subtask 1. Again, help Stofl to figure out whether the view can be enjoyed.

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

Case #1: no
Case #2: yes
Case #3: yes

Subtask 3: Find an Enjoyable Part (30 Points)

Mouse Stofl has installed $N$ pillars, again equally spaced. As Stofl has a lot of room, he built a long row of pillars. Now he wants to find the longest part of this row that can be used to build a cable car from which the view can be enjoyed optimally. As Stofl is lazy, he does not want to move any pillar. Therefore, the enjoyable part should be contiguous. Help Stofl to find the longest contiguous enjoyable part.

2
10
2 3 10 11 12 13 14 15 16 500
5
3 20 25 30 35

Case #1: 7
Case #2: 4

Subtask 4: Removing Pillars (40 Points)

After Stofl has played around with the cable car from subtask 3 long enough, he would like to build a new one. He has, again, installed all pillars in a row. However, now he is willing to remove some of the pillars. After he has removed some pillars, he moves the remaining pillars back together, so that they are equally spaced again. Help Stofl remove the smallest number of pillars, such that the remaining pillars can be used to form the longest cable car possible, under the constraint that the view can be enjoyed optimally.

2
5
100 200 300 400 500
7
22 24 25 26 100 28 30

Case #1: 0
Case #2: 2

Input

The input is given in the same format for all subtasks: On the first line, there is a number $T$, describing the number of test cases.

After that, there follow three lines for each test case:

• On the first line, there is a single nonnegative integer $N$, the length of the tunnel in meters.
• One line consisting of $N$ integers follows, the respective elevations above sea level $c_i$ of the roof at position $i$.
• One line consisting of $N$ integers follows, the respective elevations above sea level $f_i$ of the floor at position $i$.

The position $i = 1$ is the northmost position, $i = N$ the southmost.

Output

In all subtask, for each test case you should find a certain distance $D$. For each test case, print a line in the format Case #i: D, where $i$ is the number of the test case (for the first test case we have $i = 1$), and $D$ is the required distance.

Subtask 1: Stationary (20 Points)

The building inspector stands at the door on the north and would like to know how far he can see into the tunnel.

Constraints

• $T = 100$
• $1 \leq N \leq 10^{3}$
• $0 \leq f_i < c_i \leq 10^{9}$

Examples

1
4
7 9 6 8
6 2 1 5

Case #1: 2

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 2: Short Walk (20 Points)

The inspector passes through the tunnel and would like to know, what the maximum distance which he can see during his walk is.

Constraints

• $T = 100$
• $1 \leq N \leq 10^{3}$
• $0 \leq f_i < c_i \leq 10^{9}$

Examples

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

Case #1: 5

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 3: Long Walk (40 Points)

This subtask is identical to subtask 2, but the tunnel is allowed to be significantly longer now.

Constraints

• $T = 100$
• $1 \leq N \leq 10^{6}$
• $0 \leq f_i < c_i \leq 10^{9}$

Examples

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

Case #1: 6

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 4: Clearing the Tunnel (20 Points)

The tunnel should be improved to a state where it is possible to see one end from the other and thus is able to route the rails straight through horizontally. To this end, one removes obstacles ranging too far into the tunnel from the roof and the floor. (Any pits left after this procedure are filled during a later step, which is not interesting to us now.) However, the total horizontal distance which is traveled during this step should be kept at a minimum to keep costs low. The inspector would like to know the minimum distance the two construction crews need to travel in total (i.e. we consider the sum of both distances), until there exists a horizontal line of sight.

Constraints

• $T = 100$
• $1 \leq N \leq 10^{6}$
• $0 \leq f_i < c_i \leq 10^{18}$

Examples

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

Case #1: 8
Case #2: 5

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Subtask 1: One Matryoshka-set (10 points)

Dimitri has put the Matryoshka dolls into $T$ packages. Stofl opens the packages one by one and tries to nest all dolls that were in the same package into each other. Write a program that tells Stofl if all dolls within one package can be nested within each other.

2
3
1 2 3
1 2 3
3
1 2 3
1 3 2

Case #1: YES
Case #2: NO

Subtask 2: Largest Matryoshka-set (20 points)

As Stofl is a very curious Mouse he would like to know what the maximum number of dolls that can be nested together. As before he only considers one package at a time. Help Stofl find the answer!

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

Case #1: 5
Case #2: 2

Subtask 3: Many dolls (20 points)

A few day after getting the packages Stofl receives a letter from Dimitri, asking for help. Dimitri discovered many more Matryoshka dolls in his Grandmother’s attic. Now he would also like to know the maximum number of dolls he can nest in each other. Dimitri suspects that your solution to subtask 2 may be too slow.

Subtask 4: Group photo (20 points)

Stofl is very happy about his Matryoshka dolls and would really like to post a photo of them on Instagram. Unlike Dimitri Stofl is very tidy, so he has the following rule for placing the dolls in for his photo: In front of every Matryoshka doll Stofl starts a new row of smaller Matryoshka dolls that will be placed next to each other. The height of every doll in that row must be smaller than the doll behind them and the width of the row, which is equal to the sum of all the widths of dolls in the row, must be strictly smaller than the width of the doll behind it. Stofl then applies the same procedure on every new doll until he cannot place any more dolls.

Stofl chooses one single Matryoshka doll to start with before applying his procedure. As Stofl has received many dolls of the same size, you may assume that the input specifies Matryoshka-types which can be used as often as you want. Also measurements show that no two Matryoshka-types have exactly the same height or exactly the same width.

Examples

Example 1

Example 2

Example 3

Input:

3
7
2 3 4 6 8 10 11
2 5 6 1 3 4 9
2
1 100
1 2
4
14 3 4 5
14 3 4 5

Output:

Case #1: 8
Case #2: 100
Case #3: 8

Comment:

In a frontal photograph this can be described as followes:

The big blue 11x9 Matryoshka doll is placed at the back. In front of it we places a row consisting of two 4x6 dolls and one 2x2 and thus uses the maximally allowed width. In front of every doll in the red row Stofl now proceeds to place a new row. This is only possible for the 4x6 dolls, as there is no doll that is smaller than 2x2. The two new rows consist of a single 3x5 doll and are coloured green. In front of each of these a new pink row consisting of a single 2x2 doll is placed. Thus we have reached the final placement which means there will be a total of 8 Matryoshka dolls on the photo.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download Input Submit C++ Solution

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Output

Check output

Problem with newlines?

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.

Output

Source Code

Upload

Subtask 5: Group photo 2 (20 point)

Dimitri, who has discovered Stofl’s photos, would like to show that he too can be tidy on the one hand and on the other hand would also like to that there are even larger Matryoshka dolls. Dimitri uses the same procedure as Stofl did in subtask 4 to place his dolls for the photograph. As before Dimitri is impatient and would like you to write a fast solution, so you may need to optimise your program from subtask 4.

Subtask 1 (20 Points)

Help Stofl find the number of distinct slides on a maximum enjoyable sequence if he wants to start from a given pool.

Example

First test case of sample input visualized.

Input:

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

Output:

Case #1: 4
Case #2: 6
Case #3: 1

Comment:

Case #1: The best sequence of platforms is either $1\to 2 \to 1 \to 5 \to 6$ or $1 \to 2 \to 1 \to 5 \to 4$. Note that in this example, Stofl has to visit a platform twice to have the most fun.

Case #2: The best sequence of platforms is $3\to 4 \to 5 \to 6 \to 1 \to 2 \to 3$. Stofl can visit every platform because they are connected in a loop.

Case #3: The best sequence of platforms is $2 \to 2$. In this example, Stofl is trapped on a platform which is only connected to itself. Thus he can’t reach any of the other platforms.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download Input Submit C++ Solution

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Output

Check output

Problem with newlines?

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.

Output

Source Code

Upload

Subtask 2 (20 Points)

The starting pool can now be chosen by Stofl himself. Your task is to find the number of distinct slides on a maximum enjoyable sequence starting from any of the $N$ pools. In the input format, $S$ is therefore omitted now.

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

Case #1: 4
Case #2: 4

Subtask 3 (20 Points)

In anticipation of even more fun, Stofl decided to visit an even larger amusement park, featuring nearly one million unique pools. Stofl is still allowed to choose the starting pool.

Subtask 4 (40 Points)

This is a theoretical subtask, you do not have to provide any source code. Submit a proof that your solution to subtask 2 and/or 3 is correct (see guide) including an asymptotic analysis of the algorithm’s runtime and memory usage.

The contest is over, you can no longer submit.

Subtask 1: Calculate Paths (20 Points)

Mouse Stofl starts in village $A$ and mouse Vladimir starts in village $B$. Calculate how far they have to travel until they visited all villages.

1
4 1 1
0 1 5 6
1 0 2 10
5 2 0 14
6 10 14 0

Case #1: 22 17

Subtask 2a: Example with Different Distances (10 Punkte)

Mosue Stofl wants to know if it is possible to choose the distance between the $N$ villages in a way that the total distance of Stofl is exactly $D$ longer than the distance of Vladimir. Note that as previously, all distance are pairwise distinct.

1
4 5

Case #1: 4 1 1
0 1 5 6
1 0 2 10
5 2 0 14
6 10 14 0

Subtask 2b: Example with Equal Distances (10 Points)

Now Stofl wants to know if it is also possible for $D=0$. Input and output are the same as in subtask 2a.

Subtask 3 (60 Points)

In general, the distances between two villages don’t have to be different. If there are ties for the shortest/farthest away village, Stofl and Vladimir select an arbitrary one (you cannot influence their choice). It also can happen that the distance between two villages is equal to $0$.

Prove, that for all distances, Stofl can never be faster as Vladimir. Formally: Given $N$ villages ($N\ge 3$), where each village is connected with every other village with integer distances $\ge 0$. Show that the distance of mouse Stofl is greater or equal than the distance that mouse Vladimir travels.

Or, regarding the previous subtasks, that there is no example for $D<0$.

The proof is not obvious. You cannot simply write that it is clear, because Vladimir always takes the smaller distances. Maybe Vladimir is in a position where he can only take very expensive paths. Try to write your arguments clear and precise. We don’t expect a strict mathematical proof, but the arguments have to be founded.

The game

One full run of the game

Each player handles one vehicle and the game takes place on a map consisting of squares. A game consists of several rounds. In each round, each player announces which square he would like to move to. After all players have announced their moves, they all move simultaneously. There is one constraint though: the velocity vector (the vector between the two preceding positions, or, in other words, the vector between the last and the next position) may only change by 1 in each direction. On the racing track, there are multiple different checkpoints, which must all be visited in an arbitrary order before the goal can be reached (the squares where the goal is located may, of course, be visited earlier, but the game does not complete in this case.) Multiple players can be on the same square at the same time.

Additionally, each player is given one cheese as well as one mouse trap. Players passing near cheese will be unable to change their velocity vectors for a small time, while the mouse trap brings all players near to it to a full stop.

Some notes about cheese and mouse traps (in the following, both referred to as “objects”):

• The objects can be placed at an arbitrary time and they become active at the end of the current round, after all players have been moved.
• The objects are active during one round only, after that, they will be removed.
• Arbitrarily many objects can be placed in one round, as long as the maximum number for the entire game is not surpassed.
• Each player is given 1 cheese and 1 mouse trap per game.
• The objects can be placed on an arbitrary field, it does not have to be nearby the player.
• The objects affect all players, even the one who placed them.
• The objects affect players located up to a distance of 2 squares. Imagine a square with side length 5, where the object is located on the middle field. All fields in this square are affected by the object.
• The cheese influences affected players during two rounds. Assuming the cheese is placed in round $i$, and player A is in the square affected by the cheese, the player will be unable to change their velocity vector in rounds $i+1$ and $i+2$.
• At certain places in the game server and its documentation, the terms “Bomb” and “Freezer” appear. Those refer to mouse traps and cheese respectively.

One round is organized as follows:

1. All players indicate the square they would like to move to. They must meet the constraints on their velocity vectors. Players may also place objects at this time.
2. All players are moved to their indicated field.
3. The placed objects are evaluated and their effects on players are applied.

If a player moves outside the racing track, they are moved back to the checkpoint last visited, and the velocity vector is reset to 0/0. It is allowed to move outside the track, i.e. a blocked square, or a square outside the map (even though it appears unclear why one would want to do this…).

What is a vector

In each turn, the initial vector (2 / 1) can be changed
by one in each dimension.

If you have already been taught about vectors in school, you may skip this part.

A vector can be thought of as an arrow which points in a certain direction. In order to represent such a direction, multiple numbers are taken together to form a new object, called a vector. In our case, we have two dimensions. The cars have a position on the X-axis (“left-right”) as well as on the Y-Axis (“up-down”). Therefore, the vector we use for the velocity also consists of two numbers. This vector tells us, by how many fields the car moves per round. The first number describes the change on the X-axis, the second number describes the change on the Y-axis.

For the Y-axis, there are two conventions: either the numbers increase upwards, or downwards. In school, you will probably learn the first variant, which is probably more intuitive: the elevation above sea level grows upwards, as do e.g. numbers on floors in high buildings. In informatics, the second variant is also common though. E.g. the position of a window is represented as a distance to the left upper corner of the screen (and therefore, the number for the Y-axis grows as the window moves further down). This is sensible e.g. in a text editor, where line numbers grow downwards. We will use the second variant, such that numbers grow downwards.

Example: Assuming the car is located at position (5 / 8) (i.e. 5 squares right of the origin and 8 squares below the origin. The origin is located at the upper left corner of the map). If the car currently is moving at a velocity of (2 / 3), it will be located at position (7 / 11) in the next round. The arrow represented by the velocity vector points 2 squares to the right and 3 squares downwards. If one moves this arrow to the current position, it will point right to the target sqaure (7 / 11).

You are able to change the velocity vector by 1 in each direction and each round. I.e. if you are traveling with a velocity vector of (2 / 3), you have 9 possible ways to choose your velocity:

• Maintaining the velocity: (2 / 3)
• Changing the velocity on the X-axis by 1: (1 / 3), (3 / 3)
• Changing the velocity on the Y-axis by 1: (2 / 2), (2 / 4)
• Changing the velocity by 1 on both axes: (1 / 2), (1 / 4), (3 / 2), (3 / 4)

Input and Output

The program will be restarted for each game. Communication is done over standard I/O. In order to be able to solve the task, you will need a program provided by us, which you can download at the end of this description. In this section, everything that is important about handling this program will be explained.

On the first line there are given $W$ (width of the map), $H$ (height of the map) and $P$ (number of players)

$H$ lines consisting of $W$ characters each follow. The $i$-th character in the $j$-th line corresponds to the element at position (i / j). The characters have the following meaning.

After reading this information, the player prints X Y, describing his desired starting position (an arbitrary field which is marked with $=$).

At the begin of each round, the server will print a single line with 1. P lines follow, describing the current state of the other players:

N X Y VX VY B F

The ID of the player (N, the players are numbered from 0 to P-1, your program always has the ID 0), the current position (X Y) the current velocity (VX VY) as well as the number of remaining mouse traps (B) and cheese (F). The players are sorted by ID.

On the next line follow B F, the numbers of placed mouse traps as well as cheese. There follow B + F lines containing X Y N, describing the position of one object as well as the ID of the player who has placed it. The first B lines describe mouse traps, the remaining ones describe cheese.

After that, the program should print the desired action(s). First, if desired, it should place mouse traps and cheese with B X Y or F X Y. The last line describes the desired square with M X Y. (I.e. the vehicle should move to position (X / Y)). Here, the velocity vector may change by at most 1 in each direction. If the old position is (AX / AY), the new position is (NX / NY) and the original velocity vector is (VX / VY), we have: |(NX - AX) - VX| <= 1 and |(NY - AY) - VY| <= 1.

Caution: If the vehicle is influenced by cheese or a mouse trap, it may differ from the one expected.

Example

> 50 20 2
> ##################################################
> #######..................................#########
> ####......................................aa######
> ###.........##........#############....aaaaaaa####
> ###===.....##########################aaaaaaaaaa###
> ###=======###########################aaaaaaaaa.###
> ###....===###########################aaaaa......##
> ###......############################a.........###
> ###.....###############################.........##
> ###.....###############################........###
> ##$$$$$$################################.......###
> ##$$$$$$################################.......###
> ##$$$$$$################################.......###
> ##.......##############################........###
> ###.......#########################bbbb........###
> ##.........######................bbbbbbb.......###
> ##................................bbbbbbb....#####
> ###................................bbbbbbb..######
> ##########..................#######bbbbbbb.#######
> ##################################################

< 3 4
> 1
> 0 3 4 0 0 1 1
> 1 3 4 0 0 1 1
> 0 0
< M 3 3
> 1
> 0 3 3 0 -1 1 1
> 1 3 3 0 -1 1 1
> 0 0
< M 4 3
> 1
> 0 4 3 1 0 1 1
> 1 4 3 1 0 1 1
> 0 0
< M 4 2
> 1
> 0 4 2 0 -1 1 1
> 1 4 2 0 -1 1 1
> 0 0
< B 37 18
< M 4 3
> 1
> 0 4 3 0 1 0 1
> 1 4 3 0 1 1 1
> 1 0
> 37 18 0
< M 4 5
> 1
> 0 4 5 0 2 0 1
> 1 4 5 0 2 1 1
> 0 0
...
< M 7 8
> 1
> 0 7 8 0 2 0 1
> 1 15 9 0 2 1 0
> 0 0
< M 6 10
> 0

Subtask 1: Find a Path (20 Points)

You play alone and you should find the goal.

You should solve the task using a program, which computes the path at runtime (i.e. you are expected not to determine a specific path by hand and just save it into your program.) Play one game with your program and upload the generated file replay.txt. At the end of this description you can find an explanation on how to run your program.

Use this map as your input.

Subtask 2: Find the Optimal Path (30 Points)

A small map, for which it is feasible to find an optimal path.

You are playing alone, and you should find the shortest path you can. If $O$ is the optimal number of rounds for the given map, and your program uses $R$ rounds, you will be awarded $a^{-(R/O)+1}\cdot 30$ points (where $a=2$).

You must solve the task using a program, which computes the path at runtime (i.e. you are expected not to determine a specific path by hand and just save it into your program.)

Du musst die Aufgabe mit einem Programm lösen, welches den Weg zur Laufzeit berechnet (d.h. Du darfst nicht von Hand einen Weg bestimmen und diesen fest in deinem Programm speichern). Play one game with your program and upload the generated file replay.txt.

Use this map as your input.

Subtask 3: Creativity Tourney (50 Points)

You play against the other participants of the SOI. At SOI day, your programs will compete against each other in a tourney, in order to determine the best programs. You will be awarded points according to the ranking.

Notes

For interactive tasks, it is important that you flush the output buffer after each round, to ensure that the output becomes visible to the server.

Use the following commands:

• C/C++: fflush(stdout);
• C++: cout << flush; (not necessary, if right after printing, a read happensx)
• Pascal: flush(output);
• There are similar commands in other languages.

Furthermore, when reading the input, it is important that your program does not wait for more characters that the server provides as input. Especially spaces or line endings in C format strings are a common source of mistakes. For example, if you have read the last variable in the input using “scanf("%d ",&x);”, the scanf-function will wait for the next character which is not either a space or line ending. However, you will only be provided such a charater when you will already have provided your next move. In order to solve this, use “scanf("%d", &x);”, i.e., no non-printable characters afer the “%d”.

Sample-Bots, Server and Visualisation

During the first round, we will provide the following materials:

• Sample-bots in different programming languages
• A server-program which you can use to let your own program compete against your own and other programs as well as against yourself.
• A visualisation showing simulated games.
• Additional Maps to test your bots.

You can download them here.