Here you can see, which tasks you have already solved. Don’t let anything stop you from picking a task at the top and getting on it!

Here you can find information and details about the first round.

We’d happily give you an introduction during one of the workshops.

This contest is over.

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

numberriddle | ‒/100 | ‒/25 | ‒/25 | ‒/25 | ‒/25 | ||

superpowers | ‒/100 | ‒/20 | ‒/20 | ‒/20 | ‒/20 | ‒/20 | |

cupsort | ‒/100 | ‒/10 | ‒/20 | ‒/20 | ‒/20 | ‒/30 | |

funny | ‒/100 | ‒/10 | ‒/10 | ‒/10 | ‒/25 | ‒/10 | ‒/35 |

dissertation | ‒/100 | ‒/10 | ‒/20 | ‒/20 | ‒/20 | ‒/30 | |

submarine | ‒/100 | ‒/25 | ‒/25 | ‒/50 |

Mouse Amir loves riddles and mathematics. Whenever he travels alone, he creates and solves puzzle games to make time pass faster. His favourite game is called the number riddle. The goal of the game is to create a valid equation out of randomly picked numbers. Amir prefers a simple version, where he is only allowed to perform additions and subtractions. He randomly picks numbers and places $+$ and $-$ in between. Even though it’s tempting to use the $-$ to create signed numbers, Amir strictly uses is as an operator between two values.

Mouse Amir always starts with an easy task. He picks two random numbers: $n_{0}, n_{1}$ and a target value $R$. Amir now tests if he can reach the value $R$ by adding the two numbers or subtracting the second number from the first number.

The first line contains one integer $T$, the number of test cases. Each test case consists of two lines: The first line contains two integers: $N$, the number of values Amir picks and $R$, the value he tries to reach. The second line contains $N$ integers: $n_i$, the numbers Amir adds or subtracts from each other.

For the $i$-th test case, display a single line “`Case #i: YES`”, if it is possible to reach the number, “`Case #i: NO`” if not.

- $T = 100$
- $N = 2$
- $0 \le R = 15$
- $0 \le n_i \le 10$

Input:

3 2 5 2 3 2 5 8 3 2 6 2 8

Output:

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

Comment:

The first two calculations are $2+3=5$ and $8-3=5$.

For the third case, $2+8=10$ and $2-8=-6$ both are unequal to $6$.

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

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.

Mouse Amir is quite good at mental arithmetics. Adding a few dozen numbers is a piece of cake. However, he doesn’t like to subtract numbers.
As before, he thinks of a series of numbers and tries to insert an operator between them.
Using all numbers, is it possible to reach $R$ with **at most one subtraction**?

The input format is the same as in subtask 1. The first line contains one integer $T$, the number of test cases. Each test case consists of two lines: The first line contains two integers: $N$, the number of numbers Amir picks and $R$, the number he tries to reach. The second line contains $N$ integers: $n_i$, the numbers Amir adds or subtracts from each other.

The output format is the same as in subtask 1.
For the $i$-th test case, display a single line “`Case #i: YES`”, if it is possible to reach the number, “`Case #i: NO`” if not.

- $T = 100$
- $2\le N \le 100$
- $0 \le R = 10000$
- $0 \le n_i \le 100$

Input:

3 2 5 2 3 3 5 3 8 10 3 5 8 3 10

Output:

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

Comment:

Case #1: $2+3=5$

Case #2: $3-8+10=5$

Case #3: $-8+3+10=5$ is invalid, the $-$ can’t be used as a sign.

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

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.

Mouse Amir realises that with more subtractions it is more likely to build an equation.
As before, he thinks of a series of numbers and tries to insert an operator between them.
Using all numbers, is it possible to reach $R$ with **at most two subtraction**?

The input format is the same as in subtask 1. The first line contains one integer $T$, the number of test cases. Each test case consists of two lines: The first line contains two integers $N$, the number of numbers Amir picks and $R$, the number he tries to reach. The second line contains $N$ integers $n_i$, the numbers Amir adds or subtracts from each other.

The output format is the same as in subtask 1.
For the $i$-th test case, display a single line “`Case #i: YES`”, if it is possible to reach the number, “`Case #i: NO`” otherwise.

- $T = 100$
- $2\le N \le 100$
- $0 \le R = 10000$
- $0 \le n_i \le 100$

Input:

2 3 5 16 8 3 3 8 16 10 2

Output:

Case #1: YES Case #2: YES

Comment:

Case #1: $16-8-3=5$

Case #2: $16-10+2=8$ fewer subtractions are still a valid possibility.

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

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.

Mouse Stofl learns about Amir’s game and they start playing it together. Unlike the previous tasks, the number of subtractions is unlimited. As before, all the numbers have to be used.

Mouse Stofl is a MOI (Mouse Olympiad in Informatics) participant. By reading the provided scripts and attending the workshops he learned about an elegant solution.

The input format is the same as in subtask 1. The first line contains one integer $T$, the number of test cases. Each test case consists of two lines: The first line contains two integers: $N$, the number of numbers Amir picks and $R$, the number he tries to reach. The second line contains $N$ integers: $n_i$, the numbers Amir adds or subtracts from each other.

The output format is the same as in subtask 1.
For the $i$-th test case, display a single line “`Case #i: YES`”, if it is possible to reach the number, “`Case #i: NO`” otherwise.

- $T = 100$
- $2\le N \le 100$
- $0 \le R \le 10\,000$
- $0 \le n_i \le 100$

Input:

4 3 5 16 8 3 3 8 16 10 2 3 8 4 2 2 3 8 2 4 6

Output:

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

Comment:

Case #1: $16-8-3=5$

Case #2: $16-10+2=8$

Case #3: $4+2+2=8$

Case #4: $-2+4+6=8$ but the $-$ can’t be used as a sign.

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

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.

Do not navigate away while your solution is running.

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

Mouse Stofl invented a device which allows him to transform superheroes such that they change the side (i.e. the good ones get bad and vice versa). He plans to use this device at the next superhero convention. Help him save the world and remove the power from the bad superheroes.

Each superhero has a strength $k$ (an integer). If he is bad it holds $k < 0$, otherwise $k > 1$ (i.e. he is good). When the device is used on a superhero, the new strength is $-k$. To determine which side is stronger Stofl sums up all strengths. Help him maximize this sum $S$.

You have to choose $C$ times a superhero on which the device is applied. You can choose one hero several times.

The first line contains one integer $T$, the number of test cases.

For each test case there is one line with an integer $C$ (see description), an integer $N$ (number of superheroes) and $N$ space separated integers, the strengths of the superheroes.

Print for each test case one line with “`Case #i: S`” where $i$ is the index of the test case (first test case is $i = 1$) and $S$ is the sum we are looking for.

- $T = 100$
- $0 \le C \le 10^{4}$
- $1 \le N \le 10^{4}$
- $1 \le |k| \le 10^{6}$

Input:

3 3 5 4 -3 1 2 -7 2 5 1 2 3 4 5 5 5 -7 1 2 3 4

Output:

Case #1: 15 Case #2: 15 Case #3: 17

Comment:

We choose the superheroes with the following strengths:

Case #1: -3, 1, -7

Case #2: 1, 1

Case #3: -7, 1, 1, 3, 3

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

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.

Do not navigate away while your solution is running.

You have to choose exactly $C$ different superheroes.

Same as for subtask 1.

Same as for subtask 1.

Attention: the sum we are looking for can get too big for a 32-bit integer (use for example in C++ `long long int` instead of `int` to prevent this problem).

- $T = 100$
- $0 \le C \le 10^{4}$
- $1 \le N \le 10^{4}$
- $C \le N$
- $1 \le |k| \le 10^{6}$

Input:

3 3 5 4 -3 1 2 -7 2 5 1 2 3 4 5 5 5 -7 1 2 3 4

Output:

Case #1: 15 Case #2: 9 Case #3: -3

Comment:

We choose the superheroes with the following strengths:

Case #1: -3, 1, -7

Case #2: 1, 2

Case #3: -7, 1, 2, 3, 4

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

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.

Do not navigate away while your solution is running.

You have to choose $C$ continuous heroes on which the device should be applied. The heroes stand in a line which means the first and the last one are not neighbors.

Same as for subtask 2.

Same as for subtask 2.

- $T = 100$
- $0 \le C \le 10^{6}$
- $1 \le N \le 10^{6}$
- $C \le N$
- $1 \le |k| \le 10^{6}$

Input:

3 3 5 4 -3 1 2 -7 2 5 1 2 3 4 5 5 5 -7 1 2 3 4

Output:

Case #1: 5 Case #2: 9 Case #3: -3

Comment:

We choose the superheroes with the following strengths:

Case #1: 1, 2, -7

Case #2: 1, 2

Case #3: -7, 1, 2, 3, 4

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

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.

Do not navigate away while your solution is running.

You can choose any number of continuous superheroes.

The first line contains one integer $T$, the number of test cases.

For each test case there is one line with an integer $N$ (number of superheroes) and $N$ space separated integers, the strengths of the superheroes.

Print for each test case one line with “`Case #i: S`” where $i$ is the index of the test case (first test case is $i = 1$) and $S$ is the sum we are looking for.

- $T = 100$
- $1 \le N \le 10^{4}$
- $1 \le |k| \le 10^{6}$

Input:

3 5 4 -3 1 2 -7 5 1 2 3 4 5 5 -7 1 2 3 4

Output:

Case #1: 11 Case #2: 15 Case #3: 17

Comment:

We choose the superheroes with the following strengths:

Case #1: -3, 1, 2, -7

Case #2: We don’t choose any heroes

Case #3: -7

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

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.

Do not navigate away while your solution is running.

Same as subtask 4 but there are more superheroes.

Same as for subtask 4.

Same as for subtask 4.

- $T = 100$
- $1 \le N \le 10^{6}$
- $1 \le |k| \le 10^{6}$

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

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.

Do not navigate away while your solution is running.

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

Mouse Stofl is participating in a cup sorting competition, where there are $N$ cups of different colors on the table and he has to order them according to a given pattern. He learned how to swap two adjacent cups very elegantly. But swapping fast is not enough to win, he also needs to minimize the number of swaps he performs to reach the required end configuration. He asks for your help to determine the minimum number of swaps in the different rounds of the competition.

All cups are either red or blue. Stofl needs to put all red cups to the left of the blue cups. Is it possible with $\le 1$ move? The colors red and blue are represented by the numbers 0 and 1 in the input.

The first line contains one integer $T$, the number of test cases. $2\cdot T$ lines follow, two per test case: For each test case, the first line contains an integer $N$, the number of cups on the table. The second line contains $N$ integers $c_i$, $i$ from $1$ to $N$, numbers for the color of each cup.

For the $i$-th test case, display a single line “`Case #i: YES`”, if it is possible with $\le 1$ move, “`Case #i: NO`” otherwise.

- $T = 100$
- $1 \le N \le 10^{4}$
- $0 \le c_i \le 1$ for each $i$ from $1$ to $N$

Input:

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

Output:

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

Comment:

Case #1: swap 3rd and 4th cup

Case #2: impossible with not more than one swap

Case #3: already in the desired configuration

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

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.

Do not navigate away while your solution is running.

Again, all cups are either red or blue and Stofl needs to put all red cups to the left of the blue cups. But this time he wants to know the minimum number of swaps he needs to perform.

The input format is the same as in Subtask 1.

For the $i$-th test case, display a single line “`Case #i: S`”, where S is the minimum number of swaps needed.

The limits are the same as in Subtask 1.

Input:

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

Output:

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

Comment:

Case #1: swap 3rd and 4th cup

Case #2: swap 3rd and 4th cup, then 2nd and 3rd, then 1st and 2nd

Case #3: already in the desired configuration

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

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.

Do not navigate away while your solution is running.

This time each cup has a different color, and Stofl needs to order them like the rainbow. For the numbers in the input, this means that he needs to sort them in increasing order.

The first line contains one integer $T$, the number of test cases. $2\cdot T$ lines follow, two per test case: For each test case, the first line contains an integer $N$, the number of cups on the table. The second line contains $N$ integers $c_i$, numbers for the color of each cup.

For the $i$-th test case, display a single line “`Case #i: S`”, where S is the minimum number of swaps needed.

- $T = 100$
- $1 \le N \le 10^{4}$
- $0 \le c_i \le 10^{6}$ for each $i$ from $1$ to $N$

Input:

2 3 10 5 6 4 1 2 4 3

Output:

Case #1: 2 Case #2: 1

Comment:

Case #1: swap 1st and 2nd cup, then 2nd and 3rd

Case #2: swap 3rd and 4th cup

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

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.

Do not navigate away while your solution is running.

Everything is the same as in subtask 3, except that there can be multiple cups of the same color.

The input format is the same as in Subtask 3.

The output format is the same as in Subtask 3.

The limits are the same as in Subtask 3.

Input:

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

Output:

Case #1: 3 Case #2: 2

Comment:

Case #1: swap 1st and 2nd cup, then 2nd and 3rd, then 3rd and 4th

Case #2: swap 1st and 2nd cup, then 4th and 5th

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

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.

Do not navigate away while your solution is running.

Now, Stofl needs to order a huge amount of cups. The desired order is as in subtasks 3 and 4.

The first line contains one integer $T$, the number of test cases. $2\cdot T$ lines follow, two per test case: For each test case, the first line contains an integer $K$, the number of cup groups (see below) in the input. The second line contains $K$ pairs of integers $n_i$ and $c_i$, $i$ from $1$ to $K$, describing the cup groups. A cup group consists of $n_i$ cups of the same color $c_i$.

For the $i$-th test case, display a single line “`Case #i: S`”, where S is the minimum number of swaps needed.

- $T = 100$
- $1 \le K \le 10^{6}$
- $1 \le n_i \le 10^{6}$ for each $i$ from $1$ to $K$
- $1 \le \sum_{i=1}^K n_i \le 10^{10}$
- $0 \le c_i \le 10^{9}$ for each $i$ from $1$ to $K$
- $0 \le S < 2^{63}$

Input:

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

Output:

Case #1: 3 Case #2: 4

Comment:

Case #1: all cups written out: `10 5 5 6`; swap 1st and 2nd cup, then 2nd and 3rd, then 3rd and 4th

Case #2: all cups written out: `1 1 1 1 1 2 2 2 4 4 3 3`

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

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.

Do not navigate away while your solution is running.

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

Mouse Ali found a strange C++98 source file on his old computer. He must have written it years ago. In that file, there is the following function:

long long funny(long long a, long long b) { long long x = 1; while (x < b) { x *= 2; } long long s = x%b; while (a >= b) { a = (a & (x-1)) + s*(a/x); } return a; }

Regrettably, Mouse Ali has no idea whatsoever what his though processes were when he wrote this source file. However, even being as humble as he is, he still is very certain that this code must be brilliant.

Clearly it would be devastating if the insights hidden in this code were lost for future generations.
Maybe *you* are able to figure out what exactly it is that `funny` computes?

Mouse Ali has translated the code into idiomatic Python, hoping it would become easier to understand in the process. Unfortunately, he was not smarter than before when he finished, but maybe the translated version is of some use to you:

def funny(a, b): x = 1 while x < b: x = 2*x s = x%b while a >= b: a = (a & (x-1)) + s*(a//x) return a

Compute the result of `funny(a, b)` for a few small input values. It is guaranteed that `funny(a, b)` returns a result for all values $(a,b)$ given in the input.

The first line of the input contains a number $T$, the number of pairs $(a,b)$ that you should compute `funny(a, b)` for.
$T$ lines, follow, each containing two integers $a$ and $b$, separated by single spaces.

Print one line in the format “`Case #i: R`” for each test case, where $i$ is the number of the test case (the first test case is assigned the number $i = 1$), and $R$ is the result of `funny(a, b)`.

- $T = 100$
- $0 \le a \le 100$
- $0 \le b \le 100$
`funny(a, b)`returns a result.

Input:

3 1 2 20 11 100 64

Output:

Case #1: 1 Case #2: 9 Case #3: 36

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

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.

Do not navigate away while your solution is running.

Compute the result of `funny(a, b)` for a few small input values. If for any reason, `funny(a, b)` does not return a result for certain input values $(a,b)$, print “`NOTHING`” instead. (Hence, in this case, `R` is not necessarily a number.)

As in subtask 1.

As in subtask 1, except that now “`NOTHING`” is an allowed result.

- $T = 100$
- $0 \le a \le 100$
- $0 \le b \le 100$

Input:

3 1 3 20 12 100 65

Output:

Case #1: 1 Case #2: 8 Case #3: NOTHING

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

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.

Do not navigate away while your solution is running.

Compute the result of `funny(a, b)` also for larger input values now. It is guaranteed that `funny(a, b)` returns a result for all values $(a,b)$ given in the input.

As in subtask 1.

As in subtask 1.

- $T = 100$
- $0 \le a \le 10^{18}$
- $0 \le b \le 10^{18}$
`funny(a, b)`returns a result.

Input:

3 1124615 3132478 20239832878787237 12563819465217352 1000000000000000000 18014398509481984

Output:

Case #1: 1124615 Case #2: 7676013413569885 Case #3: 9208081978490880

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

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.

Do not navigate away while your solution is running.

Explain why your solution for subtask 3 is correct for all nonnegative integers $(a,b)$ (such that `funny(a, b)` returns a result). (Note that this means you also need to justify the correctness of your solution for numbers that exceed $10^{18}$.) Also analyze the running time of your solution. Try to keep the formulation of your arguments as clear and precise as possible. We don’t expect a strictly rigorous mathematical proof, but your arguments should be founded and build on each other.

For this theoretical subtask, you should assume that the data type `long long` can represent arbitrary integers, but also that the basic operations (such as `<`, `<=`, `+`, `-`, `*`, `/`, `%`, `&` and `=`) can be executed in constant time none the less.

For this subtask, you can only obtain points if your solution for subtask 3 is correct for all $(a,b)$ (where $a\ge 0$ and $b\ge 0$ are such that `funny(a, b)` returns a result), and if it has a running time of at most $\mathcal O(\log a + \log b)$. (You can submit for subtask 3 arbitrarily often, and we only consider the last correct submission, hence it is not an issue if your first solution to subtask 3 does not satisfy those criteria initially. For this subtask, we will only correct the last submission.)

Solutions that do not run in constant time will not score all points for this subtask.

**The contest is over**, you can no longer submit.

Compute the result of `funny(a, b)` for large input values. If for any reason, `funny(a, b)` does not return a result for certain input values $(a,b)$, print “`NOTHING`” instead. (Hence, in this case, `R` is not necessarily a number.)

As in subtask 2.

As in subtask 2.

- $T = 100$
- $0 \le a \le 10^{18}$
- $0 \le b \le 10^{18}$

Input:

3 1124615 3132479 20239832878787237 12563819465217353 1000000000000000000 18014398509481985

Output:

Case #1: 1124615 Case #2: 7676013413569884 Case #3: NOTHING

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

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.

Do not navigate away while your solution is running.

Explain why your solution for subtask 5 is correct for all nonnegative integers $(a,b)$. (Note that this means you also need to justify the correctness of your solution for numbers that exceed $10^{18}$.) Also analyze the running time of your solution. Try to keep the formulation of your arguments as clear and precise as possible. We don’t expect a strictly rigorous mathematical proof, but your arguments should be founded and build on each other.

For this theoretical subtask, you should assume that the data type `long long` can represent arbitrary integers, but also that the basic operations (such as `<`, `<=`, `+`, `-`, `*`, `/`, `%`, `&` and `=`) can be executed in constant time none the less.

For this subtask, you can only obtain points if your solution for subtask 5 is correct for all $(a,b)$ (with $a\ge 0$ and $b\ge 0$), and if it has a running time of at most $\mathcal O(\log a + \log b)$. (You can submit for subtask 5 arbitrarily often, and we only consider the last correct submission, hence it is not an issue if your first solution to subtask 5 does not satisfy those criteria initially. For this subtask, we will only correct the last submission.)

Solutions which take only constant time except for computing $x$ score more points than solutions that do not have this property. Full score is only given to solutions whose total running time is in $o(\log(\min(a,b)))$ (i.e. solutions whose running time grows strictly more slowly than logarithmic).

**The contest is over**, you can no longer submit.

After struggling for many years, Maus Stofl has finally finished his dissertation thesis. As soon as he was done, he sent the file to a copy center to have it printed and bound. Unfortunately, the copy center did a very poor job. First of all, they printed the thesis one-sided – i.e., each page on a separate sheet of paper. What’s even worse, before binding the thesis someone shuffled the pages, so they are completely out of order!

The deadline is almost here and Stofl doesn’t have the time to print the thesis again. Therefore, he has decided to fix the printout he has by tearing out some pages. His reasoning is that nobody will care if there are gaps in the thesis as long as all remaining pages are in the correct order. For example, one way of fixing a thesis that has pages in the order $1,5,3,2,4$ is by tearing out the pages with numbers $2$ and $5$. The remaining pages will then be in the correct order: $1<3<4$.

Of course, the longer the thesis Stofl submits, the better for his defense.

In the following subtasks the total number of pages in the thesis is denoted $N$. The page numbers are denoted $a_{1}, a_{2}, {\dots}, a_N$ in the order in which they appeared in the printed copy.

Determine whether Stofl can submit a dissertation thesis that has at least two pages.

The first line of the input contains a single integer $T$ – the number of test cases which follow. Each test case consists of two lines. The first line of each test case contains a single positive integer $N$. The following line contains $N$ distinct integers $a_{1}, a_{2}, {\dots}, a_N$ separated by single spaces.

For the $t$-th test case, print a single line “`Case #t: YES`”, if Stofl can submit a dissertation thesis with at least two pages.
Otherwise print “`Case #t: NO`”.

- $T = 100$
- $2 \le N \le 1000$
- $1 \le a_i \le N$
- all $a_i$ are distinct integers

Input:

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

Output:

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

Comment:

Case #1: One can remove two pages and submit a dissertation thesis consisting of four pages numbered 1, 3, 4, 6.

Case #2: There is exactly one valid solution: tear out page 3 and submit the thesis that contains pages 1 and 2.

Case #3: The only two pages are in reverse order, and there is no way to fix it.

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

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.

Do not navigate away while your solution is running.

Determine the maximum number of pages that Stofl can submit.

The input format is the same as in Subtask 1.

For the $t$-th test case, print a single line “`Case #t: M`”, where $M$ is the maximum possible number of pages
in a thesis that Stofl can submit.

- $T = 100$
- $2 \le N \le 10\,000$
- $1 \le a_i \le N$
- all $a_i$ are distinct integers

Input:

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

Output:

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

Comment:

Case #1: One can remove two pages and submit a dissertation thesis consisting of 4 pages numbered 1, 3, 4, 6.

Case #2: Here, an optimal solution is to use pages 1, 3, 4, 7. Note that if you pick page 5, you will only be able to pick at most two other pages.

Case #3: Stofl must remove at least one of these two pages.

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

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.

Do not navigate away while your solution is running.

In Subtask 2 you helped Stofl compute the maximum number $M$ of pages he can submit. He is going to do exactly that: he wants to submit a thesis that has exactly $M$ pages. Sometimes there can be multiple ways to produce a valid $M$-page thesis. Compute how many theses can Stofl choose from.

The input format is the same as in Subtask 1.

For the $t$-th test case, print a single line “`Case #t: K`”, where $K$ is the number of distinct versions of the dissertation thesis Stofl can submit.
Note that we only count the longest possible theses.
As this number can be very large, compute and output it modulo $10^{9}+7$.

- $T = 100$
- $2 \le N \le 5\,000$
- $1 \le a_i \le N$
- all $a_i$ are distinct integers

Input:

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

Output:

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

Comment:

Case #1: There are four different ways how Stofl can keep four pages: (1,3,5,6), (1,3,4,6), (1,2,5,6) and (1,2,4,6).

Case #2: Stofl can only keep at most four pages in the thesis and there is only one such possibility: (1,3,4,7).

Case #3: Stofl can only pick one out of the two pages. His final thesis will either be (1) or (2).

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

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.

Do not navigate away while your solution is running.

Stofl has already submitted his thesis. He remembers that the printout had $N$ pages. He also remembers that he did exactly what we described above: he removed some (possibly zero) pages to produce the longest possible valid thesis. The last thing he remembers is the value $K$ you computed in subtask 3 – the number of possibilities he had when choosing which pages to keep. (He remembers the exact value $K$, not the value $(K \textvisiblespace\mathrm{mod}\textvisiblespace (10^{9}+ 7))$.)

Stofl would now like to reconstruct the printout he got at the very beginning. Help him: find some permutation of the pages $1,2,{\dots},N$ such that there are exactly $K$ ways to create the longest possible valid thesis.

The first line of the input contains a single integer $T$ – the number of test cases which follow. Each test case consists of a single line with the integers $N$ and $K$, separated by a single space.

For the $t$-th test case, print a single line “`Case #t: a1 a2 ... aN`”, where $a_{1},{\dots},a_N$ is
one possible order of the $N$ pages in the printed thesis. If there are many possible orders, you can print any of them.

- $T = 100$
- $200 \le N \le 1\,000$
- $1 \le K \le 10^{18}$

Input:

3 6 4 7 1 2 2

Output:

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

Comment:

These are the three same cases that were used in Subtask 2.
There are also other correct outputs. For example, in Case #2 another correct output would be the sequence (1,2,3,7,4,5,6).

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

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.

Do not navigate away while your solution is running.

A few years later Stofl thinks back the story of Subtask 4, where he tried to reconstruct the printout. He still knows $K$ (the number of possibilities he had when choosing which pages to keep), but he can’t remember the value of $N$.

Given only $K$, he wants to find some $N$ such that there is a permutation of the pages $1,2,{\dots},N$ that has exactly $K$ ways to create the longest possible valid thesis. But not only that, he wants to find a small value for $N$.

This is a theoretical subtask.

Describe an algorithm that takes a value $K$ and produces a value $N$ and some permutation of $1,2,{\dots},N$ that has exactly $K$ longest possible valid theses. Explain why it is correct and what it’s time and space complexity is.

Then analyze how $N$ depends on $K$. Let’s define the function $f(K)=N$ as the result of your algorithm. In order to score points, your function has to satisfy $f(K) \le C\cdot\log(K)+D$ some constants $C$ and $D$. Pick some values for $C$ and $D$ and prove that the inequality holds. (Formulated differently $f$ satisfies $f(K)=\mathcal O(log(k))$ and we are interested in $C=\max (f(K)/log(K))$.) Try to make your $C$ as small as possible.

**The contest is over**, you can no longer submit.

Mouse Stofl produces cheese and delivers it even to remote places. Amongst others even *across the pond*. But mouse Joël doesn’t like mouse Stofl’s success very much. Therefore he bought some submarines and wants to deep-six the cheese shipment. Help both of them to settle their conflict.

Write a program to control the ships of mouse Stofl or the submarines of mouse Joël respectively. There will be two programs playing against each other: one of them controls the ships and the other one the submarines.

The map we play on is given as a rectangular grid. Each field is water or land. Additionally some water fields are marked as starting points or destination points. On each field there is at most one object (= ship or submarine) per player.

Each ship starts on a starting field and each submarine starts on a destination field. The goal of the player controlling the ships is that as many ships as possible reach any destination field. The goal of the other player (controlling the submarines) is to prevent the ships from reaching a destination point by sinking them.

The two players take turns and the ships start. In each turn each object can perform exactly one action:

- Stay.
- Move. The Euclidean distance between the two fields can be at most $r_m$ (i.e. $(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_m^{2}$) and the destination field has to be free. It is allowed to jump accros land tiles.
- Attack (only submarine). The Euclidean distance between the submarine and the attacked field can be at most $r_a$ (i.e. $(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_a^{2}$).

The submarines can see a ship only if the ship is at most $r_v$ away from the submarine. The ships can see a submarine only if the the submarine sunk a ship in this turn. If a submarine attacks a field on which a ship is located the ship will sink immediately. If a ship lands on a destination field it disappears immediately and other ships can land in the same turn on the same field. Sunken ships as well as ships located on a destination field can’t be moved or attacked anymore.

The communication between program and server is handled using Stdin / Stdout. All coordinates are 0-based and the origin is in the top left corner. The y-coordinates get bigger going down.

At the start the program receives general information about the game:

One line with $m$ $s$ $t$ $r_m^{2}$ $r_v^{2}$ $r_a^{2}$: the side $m$ it should control (0 = ships, 1 = submarines), the number of ships $s$, the number of submarines $t$, the three radii for moving, viewing and attacking each squared (you get the distances squared such that you can calculate only using integers instead of decimal numbers: $(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_m^{2}$). On the next line there is $w$ $h$, the width $w$ and the height $h$ of the map. This is followed by $h$ lines with $w$ characters each (`#` = land, `.` = water, `s` = starting field, `d` = destination field).

Afterwards the program prints for each of its objects (= ship or submarine) a valid starting field $x$ $y$ (i.e. a field `s` for a ship and a field `d` for a submarine), one object per line (i.e. $s$ or $t$ lines).

The protocol depends on the side the program plays for the turns. At the End of the game you will get `-1` for $s_l$ or $s_v$ respectively and your program should exit correctly.

To display a debug point you can print `D x y` anytime. Such an output is of course not an action.

Input: A line with $s_l$, the number of ships that got attacked (and therefore sunk) in the last turn. This is followed by $s_l$ lines each with $x$ $y$ $u$ $v$: the coordinates of a ship $x$ $y$ as well as the coordinates of the submarine $u$ $v$ that attacked the ship.

Output: for each remaining ship (i.e. not sunken and not yet on a destination field) one line with the desired action (`M` for moving) and the destination coordinates for the action. Print `M x y` with the current coordinates if the ship should not move. with The order of the ships has to stay the same for each turn and sunken or arrived ships are skipped.

Input: A line with $s_v$, the number of visible ships. This is followed by $s_v$ lines each with $x$ $y$: the coordinates of a ship. The order of the ships is random and changed in each turn.

Output: for each submarine one line with the desired action (`A` for attack, `M` for moving) and the destination coordinates for the action. The order of the submarines has to stay the same for each turn.

- $0 \le m \le 1$
- $1 \le s, t \le 1000$
- $1 \le r_m, r_v, r_a \le 10^{6}$
- $2 \le w, h \le 1000$

Your program should finish a game with this limits within a “reasonable time” (i.e. within minutes and not hours). Takes a program too long to come up with an answer it loses the current game.

> 1 10 2 9 25 9 > 100 100 [...] > sss..............................................................................................sss > sss..............................................................................................sss > sss..............................................................................................sss > sss..............................................................................................sss > sss..............................................................................................sss > sss.............................................dddd.............................................sss > sss............................................dddddd............................................sss > sss............................................dddddd............................................sss > sss............................................dddddd............................................sss > sss............................................dddddd............................................sss > sss.............................................dddd.............................................sss > sss..............................................................................................sss > sss..............................................................................................sss > sss..............................................................................................sss [...] < 52 49 < 49 52 > 0 < M 54 47 < M 47 52 > 0 < M 51 47 < M 47 55 [...] > 1 > 49 37 < M 49 44 < M 52 65 [...] > 0 < M 52 47 < M 49 70 > 1 > 50 43 < M 52 45 < M 50 68 > 2 > 51 44 > 50 43 < A 51 44 < M 51 68 > 1 > 49 42 < M 53 45 < M 50 67 [...] > 0 < M 26 65 < M 45 73 > 0 < M 25 64 < M 47 75 > 0 < M 23 66 < M 49 75 > -1

We forget about mouse Joël for the moment and we only help mouse Stofl. Write a program that can steer all ships to the destination. The submarines won’t attack. Use `:SUB1` as a submarine command to test your program.

Use the following settings in `submarine.txt`:

map path/to/downloaded/map.txt log logconfig.txt ship_count 10 submarine_count 3 ship_command path/to/your/program.exe submarine_command :sub1 radius_move 9 radius_view 25 radius_attack 9 time_limit 50 round_limit 10000 sleep_time 100 ---

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

You have 15 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.

Do not navigate away while your solution is running.

Now we want to help mouse Joël. All ships move randomly and won’t move on a destination field. Destroy all ships. Use `:SUB2` as a ship command to test your program.

Use the following settings in `submarine.txt`:

map path/to/downloaded/map.txt log logconfig.txt ship_count 10 submarine_count 3 ship_command :sub2 submarine_command path/to/your/program.exe radius_move 9 radius_view 25 radius_attack 9 time_limit 50 round_limit 10000 sleep_time 100 ---

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

You have 15 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.

Do not navigate away while your solution is running.

You play against the other participants of the SOI. At SOI-Day the programs will compete in a tournament to determine the best one. Your program has to be able to play both sides.

You can find the played tournament here.

**The contest is over**, you can no longer submit.

To test your program we added a few maps to the server. Those maps are not necessarily the ones we use for the tournament.

It is important for interactive tasks to flush the output buffer after every turn to make sure the server can see your output.

Use the following commands:

- C/C++:
`fflush(stdout);` - C++:
`cout << flush;`(not necessary if you read afterwards) - Pascal:
`flush(output);` - There are similar commands in other languages.

Furthermore it is important that you don’t wait for more characters than the server gives you as an input. For example spaces or line endings in C format strings are a common source for errors. For example if you read the last variable in the input with “`scanf("%d ", &x);`” it will wait for the next character that is not a space or a line break. You will receive such a character only after you printed your next turn. To solve this use “`scanf("%d", &x);`” instead (no non-printable characters after the “`%d`”).

During the first round we provide the following material:

- Sample bots in different programming languages.
- A server program you can use to test your program against your own or other programs.
- A visualization to display simulated games.
- Some maps to test your bot.

You can download them here.

To run the server you need Java (version 7 or higher). The server program is located in the file `submarine.jar` and the remaining files are configuration files, sample maps and sample bots.

If you double click on `submarine.jar` the game as specified in `submarine.txt` will be simulated. You can start the server using a console (Windows: cmd, Mac: terminal, Linux: Shell) to be able to pass arguments (`java -jar submarine.jar arguments`). You can find the available arguments (and many more information) in the file `usage.md`.

You can adjust most settings in the file `submarine.txt` like for example which program you want to execute. Most of them should be easy to understand but you can find more information in `usage.md`.

- Python
`ship_command python path/to/file.py` - Java
`ship_command java -jar program.jar`or`ship_command java package.MainClass` - compiled program
`ship_command ./path/to/program`

Pack everything into a .zip file.

Rank | Username | Total (600) | numberr… (100) numberriddle | superpo… (100) superpowers | cupsort (100) | funny (100) | dissert… (100) dissertation | submarine (100) |
---|---|---|---|---|---|---|---|---|

loading ... |