First Round SOI 2021/2022

Input

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

• The first line contains one integer, $N$, the number of coordinates on the picture.
• On the second and last line, there are $N$ space-separated integers $h_{0},h_{1},{\dots},h_{N-1}$, the heights of the mountains at the coordinates $0$ to $N-1$.

Output

For the $i$-th test case, print a line “Case #i:” followed by “yes” if there is a peak on the picture or “no” if there is not.

Limits

• $T=100$.
• $N = 3$.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.

Example

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

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

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

Input

See Subtask 1.

Output

For the $i$-th test case, print a line “Case #i:” followed by a single integer, the number of peaks in that picture.

Limits

• $T=100$.
• $N = 5$.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.

Example

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

Case #0: 2
Case #1: 0

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

Input

See Subtask 1.

Output

See Subtask 2.

Limits

• $T=100$.
• $3 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.

Example

1
7
2 4 3 3 5 1 2

Case #0: 2

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

Input

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

• The first line contains two integers, $N$ and $K$, the number of coordinates on the picture and the number of coordinates that should be included on the picture after it is cut.
• On the second and last line, there are $N$ space-separated integers $h_{0},h_{1},{\dots},h_{N-1}$, the heights of the mountains at the coordinates $0$ to $N-1$.

Output

Print the maximum amount of peaks that one can fit on a contiguous part of the original picture of size $K$.

Limits

• $T=100$.
• $3 \le N \le 10\,000$
• $3 \le K \le 1000$
• $K \le N$
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.

Example

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

Case #0: 2

Interactive visualization

You can move the cutout with your mouse.

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

Input

See Subtask 4.

Output

See Subtask 4.

Limits

• $T=100$.
• $3 \le K \le N \le 1\,000\,000$
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.

Example

See Subtask 4.

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

Input

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

• The first line contains two integers $N$ and $Q$, the number of islands and the number of maximum lengths Binna wants to try out.
• On the second line there are $N$ numbers $h_{0},h_{1},{\dots},h_{N-1}$, the heights of the islands.
• The third line contains $Q$ numbers $k_{0},k_{1},{\dots},k_{Q-1}$, the different values of $K$ Binna is interested in.

Output

For the $i$-th test case print a line “Case #i:” followed by $Q$ numbers, where the $i$-th number is the minimum number of boring ropeways for a system where each ropeway has length at most $k_i$.

Limits

• $T=100$.
• $3 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.
• $Q = 1$.
• $k_{0}=N-2$. This is the special restriction for subtask 1.

Example

3
3 1
3 1 4
1
4 1
1 3 3 7
2
5 1
999999999 1000000000 1 500000000 1
3

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

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

Limits

• $T=100$.
• $2 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.
• $Q = 2$.
• $k_{0}=1$ and $k_{1}=2$. This is the special restriction for subtask 2.

Example

2
3 2
11 22 33
1 2
15 2
3 1 2 1 4 5 4 4 3 3 9 4 7 5 5
1 2

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

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

Limits

• $T=100$.
• $2 \le N \le 5\,000$. This is the special restriction for subtask 3.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.
• $1 \le Q \le 30$.
• $1 \le k_j < N$.

Example

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

Case #0: 7 25 12 2 6 2 2

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

Limits

• $T=100$.
• $2 \le N \le 1\,000\,000$.
• $1 \le h_i \le 10^{9}$ for all $0\le i<N$.
• $1 \le Q \le 100$.
• $1 \le k_j < N$.

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

Input

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

• The first line contains an integer $l$, the minimal size a T-shirt must have so Binna can wear it.
• The second line contains an integer $r$, the maximal size a T-shirt can have so Binna can still wear it.
• The third line contains an integer $s$, the size of the T-shirt that arrived.

Output

For the $i$-th testcase, output a line containing “Case #i:” followed by “Yes” if the T-shirt fits, and “No” it does not.

Limits

• $T = 100$
• $1 \le l \le r \le 100$.
• $1 \le s \le 100$

Example

3
1
5
7
10
20
13
3
100
2

Case #0: No
Case #1: Yes
Case #2: No

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

Input

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

• The first line contains one integer $N$, the number of mice and T-shirts.
• The second line contains $N$ integers: $l_{0}, l_{1}, \ldots, l_{N-1}$, where $l_i$ is the minimal size a T-shirt can have such that the $i$-th participant could wear it.
• The third line contains $N$ integers: $r_{0}, r_{1}, \ldots, r_{N-1}$, where $r_i$ is the maximal size a T-shirt can have such that the $i$-th participant could wear it.
• The fourth line contains one integer $S$, the size of the T-shirts.

Output

For the $i$-th testcase, output a line containing “Case #i:” followed by a single integer, the number of T-shirts that can be assigned to mice satisfying the constraints described above.

Limits

• $T = 100$
• $1 \le N \le 100$
• $0 \le S \le 10^{9}$.
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.

Example

2
5
1 7 3 5 10
4 9 8 10 15
6
3
4 100 80
70 120 1000
73

Case #0: 2
Case #1: 0

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

Input

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

• The first line contains two integers $N$ and $M$, the number of mice and the number of T-shirts.
• The second line contains $N$ integers: $l_{0}, l_{1}, \ldots, l_{N-1}$, where $l_i$ is the minimal size a T-shirt can have such that the $i$-th participant could wear it.
• The third line contains $N$ integers: $r_{0}, r_{1}, \ldots, r_{N-1}$, where $r_i$ is the maximal size a T-shirt can have such that the $i$-th participant could wear it.
• The fourth line contains $M$ integers: $s_{0}, s_{1}, \ldots, s_{M-1}$, describing the size of the T-shirts.

Output

For the $i$-th testcase, output a line containing “Case #i:” followed by a single integer, the number of T-shirts that can be assigned to mice satisfying the constraints described above.

Limits

• $T = 100$
• $1 \le N \le 10^{4}$
• $1 \le M \le 10^{4}$
• $s_j \le r_i$ for all $i$ and $j$. This is the special restriction for this subtask.
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.
• $0 \le s_j \le 10^{9}$ for all $j$.

Example

2
3 4
1 7 3
4 9 8
3 2 4 2
5 4
12 17 3 1 9
20 30 15 22 31
4 14 13 7

Case #0: 2
Case #1: 4

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

Input/Output

See Subtask 3.

Limits

• $T = 100$
• $1 \le N \le 10^{4}$
• $1 \le M \le 10^{4}$
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.
• $0 \le s_j \le 10^{9}$ for all $j$.

Example

2
3 4
1 7 3
4 9 8
5 2 9 2
5 4
12 17 3 1 9
20 30 15 22 31
4 14 33 17

Case #0: 3
Case #1: 3

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

Input/Output

See Subtask 3.

Limits

• $T = 100$
• $1 \le N \le 10^{6}$
• $1 \le M \le 10^{6}$
• $0 \le l_i \le r_i \le 10^{9}$ for all $i$.
• $0 \le s_j \le 10^{9}$ for all $j$.

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

Input

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 the number of cards $N$.
• The second line contains the $N$ numbers which are written on the cards from left to right. Every number between $0$ and $N-1$ appears exactly once.
• The third line contains the list of commands, which consists of $K$ characters “>” or “<”, terminated by a single “.”.

It is guaranteed that after executing all commands of a test case, the robot will end up with an empty claw.

Output

You should output $T$ lines, one for each test case. For the $i$-th test case, output “Case #i:” followed by $N$ numbers, the numbers on the cards from left to right after the robot has executed the commands.

Limits

• $T = 100$
• $2 \le N \le 200$
• $0 \le K \le 1000$

Example

2
2
1 0
><>.
3
2 0 1
>><><<>.

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

Interactive visualization

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

Input

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 the number of cards $N$.
• The second line contains the $N$ numbers which are written on the cards from left to right. Every number between $0$ and $N-1$ appears exactly once.

Output

You should output $T$ lines, one for each test case. For the $i$-th test case, output “Case #i:” followed by a list of commands, which consists of $K$ characters “>” or “<”, followed by “.”.

Limits

• $T = 100$
• $N = 3$
• $K \le 100$ (you can send at most $100$ commands to the robot)

Example

2
3
2 0 1
3
0 1 2

Case #0: ><>><<.
Case #1: .

Interactive visualization

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

Input/Output

Same as subtask 2.

Limits

• $T = 100$
• $1 \le N \le 101$
• $K \le 10\,000\,000$
• The $i$-th testcase has $N=i+1$.
• The numbers are sorted in decreasing order.

Note that every input file looks exactly the same.

Example

2
1
0
2
1 0

Case #0: .
Case #1: ><><><><>.

Interactive visualization

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

Input and Output

Same as subtasks 2 and 3.

Limits

• $T = 100$
• $K \le 400\,000$
• For limits on $N$ see below.

Scoring

You can get a variable amount of points for this subtask.

• 7 points if you only solve the first 30 test cases (0 to 29), where we have $2 \le N \le 7$.

• 20 points if you only solve the first 60 test cases (0 to 59), where we have $2 \le N \le 50$.

• 25–55 points if you solve all test cases. In all test cases, $2 \le N \le 300$. The score of a test case is calculated as follows.

  Let $A$ be the number of operations you need in your solution.

  Let $S$ be the number of operations of our master solution.

  Then you get the following amount of points:
  $$25+\left\lfloor 10 \cdot \tan(\arctan(3) \cdot \max(0, \min\left(1, 1 - \frac{A - S}{400\,000 - S}\right)))\right\rfloor$$

  Your total score is the minimum score over all test cases.

  Click below for some reference values for this function:

  Expand

  maximum A	possible score
  $68\,840$	55
  $68\,841$	54
  $80\,000$	51
  $90\,000$	48
  $100\,000$	46
  $200\,000$	34
  $300\,000$	28
  $400\,000$	25

Example

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

Case #0: >>><<><<><>>.
Case #1: >><>>><<><<<>><<.
Case #2: >><<>>><>><>><<<<<.

Interactive visualization

Note: The upload limit is 10 MiB. If you exceed that you get an error “413 Request Entity Too Large”. Most likely this is because you exceed the $400\,000$ move limit. In that case, just upload the first 60 test cases (you won’t get more than 20 points anyways if you exceed the limit).

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

Input

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

• The first line contains one integer $N$, the number of mice.
• On the second line there are $N$ integers $t_{0},t_{1},{\dots},t_{N-1}$, the durations of the dance moves for each pair of adjacent mice.

Output

For the $t$-th test case, output a line containing “Case #t:”, followed by a space and an integer $M$: the number of sections in the dance you designed. A section is a part of the dance during which the pairs do not change. In the following $M$ lines, describe the sections. Each section is described by its duration in seconds (a floating-point number), followed by a space and a string of $N$ characters without spaces. If the $i$-th mouse is dancing alone, the $i$-th character of that string should be a dot (.). If the $i$-th mouse is dancing together with the $i+1$-th mouse (or, in case $i=N-1$, with the 0-th mouse), the $i$-th character of that string should be a less-than sign (<). If the $i$-th mouse is dancing together with the $i-1$-th mouse (or, in case $i=0$, with the $N-1$-th mouse), the $i$-th character of that string should be a greater-than sign (>).

Your answer will be accepted if the following conditions hold:

• The total duration of the dance is at most $A\cdot(1+10^{-6})$, where A is the shortest possible duration.
• For each $i$ such that $0 < t_i$, the total duration of the sections where the $i$-th and the $i+1$-th mice dance together (or the $N-1$-th and 0-th for $i=N-1$) is at least $t_i\cdot(1-10^{-6})$.
• Each section is well-formed: the duration is non-negative (zero is OK), and the mice are correctly paired up.
• $M$ is at most $3\cdot N$.

It is guaranteed that there always exists a dance with the shortest possible duration that has at most $3\cdot N$ sections.

Limits

• $T=30$.
• $N=3$.
• $0 \le t_i \le 10^{6}$ for all $0\le i<N$.
• For at least one $i$, $0 < t_i$.

Example

1
3
1 2 3

Case #0: 3
1.0 <>.
3 >.<
2 .<>

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

Limits

• $T=30$.
• $3 \le N \le 100$.
• $t_i=1$ for all $0\le i<N$.

Example

2
4
1 1 1 1
5
1 1 1 1 1

Case #0: 2
1 <><>
1 ><><
Case #1: 5
0.5 <><>.
0.5 <>.<>
0.5 .<><>
0.5 ><>.<
0.5 >.<><

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

Limits

• $T=30$.
• $3 \le N \le 100$.
• $0 \le t_i \le 10^{6}$ for all $0\le i<N-1$.
• $t_{N-1}=0$.
• For at least one $i$, $0 < t_i$.

Example

1
5
1 2 3 2 0

Case #0: 2
3 <><>.
2 .<><>

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

Limits

• $T=30$.
• $4 \le N \le 100$.
• $0 \le t_i \le 10^{6}$ for all $0\le i<N$.
• For at least one $i$, $0 < t_i$.
• $N$ is even.

Example

1
6
1 2 3 2 5 1

Case #0: 2
5 <><><>
2 ><><><

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

Limits

• $T=30$.
• $3 \le N \le 99$.
• $0 \le t_i \le 10^{6}$ for all $0\le i<N$.
• For at least one $i$, $0 < t_i$.
• $N$ is odd.

Example

1
7
1 2 5 2 5 2 5

Case #0: 7
4.333333333333 >.<><><
1.333333333333 .<><><>
0.333333333333 <><><>.
0.333333333333 <>.<><>
0.333333333333 <><>.<>
0.333333333333 ><><>.<
0.333333333333 ><>.<><

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

Input

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

• The first line of each test case contains one integer $N$, the number of islands.
• The second and third line contain $N - 1$ numbers each, describing the initial ferry connections. If $a_i$ is the $i$-th number of the first line and $b_i$ the $i$-th number of the second line, then there is initially a ferry connecting the islands $a_i$ and $b_i$ for each $i$.
• The fourth and the fifth line describe the connections of the new list of Stofl, in the same format as lines two and three.

Output

For the $i$-th test case print a line “Case #i:” followed by a single integer: the minimal number of days needed until all the new connections are in place.

Limits

• $T=100$
• $1 \le N \le 6\,000$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

Example

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

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

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

Input

See subtask 1.

Output

For the $i$-th test case print a line “Case #i:” followed by a single integer $k$: the minimal number of days needed until all the new connections are in place. Then output $k$ lines. The $j$-th line consists of four integers $w_j, x_j, y_j$ and $z_j$, meaning that on day $j$, the connection between $w_j$ and $x_j$ should be replaced by the connection between $y_j$ and $z_j$.

Limits

• $T=100$
• $1 \le N \le 100$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

Example

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

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

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

Input/Output

See subtask 2.

Limits

• $T=100$
• $1 \le N \le 6000$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$.
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

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

Input/Output

See subtask 2.

Limits

• $T=100$
• $1 \le N \le 100\,000$
• $0 \le a_i, b_i, c_i, d_i < N$ for all $0\le i<N-1$
• It’s guaranteed that it’s possible to reach any island from any other island only following initial connections and only using the connections from Stofl’s list.

Grading

Since we can’t ensure that optimized brute-force solutions or heuristics won’t be able to pass, we will manually check all submissions and may retroactively give an accepted submission 0 points.

We expect a solution that runs in $\mathcal O(N\cdot \log(N)^c)$ (for a constant $c$) or $\mathcal O(N\cdot \alpha(N))$, where $\alpha(N)$ is the inverse Ackermann function. See Introduction to Algorithm Design for explanation of the $\mathcal O$-notation.

Furthermore, as we can’t distinguish the different running times, we will manually check your submissions and score them according to this table:

Note: We need around 15 seconds to verify your submission. Please be patient.

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

Input

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 $N$, the number of tin deposits.
• A second line follows with $N$ integer values $a_{0},{\dots},a_{N-1}$, the different levels of stability in a circular order.

Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the total number of worker nodes which are needed for the optimal solution (including the one mouse Binna already constructed).

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 100$.

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

Example

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

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

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 100 000$.

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

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

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 100$.

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

Example

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

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

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 5 000$.

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

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

a) Risk minimization (10 Points)

Mouse Binna has now built many different mining operations. She now has the opportunity to buy a very large mining territory in which she could scan $N$ locations. She wants to find a lower bound on the amount of the number deposits she will be able to mine in the worst case.

It is guaranteed that no two tin deposits require a node of the same level of stability. Therefore, the levels of stability are $N$ unique numbers in the range $[0,N-1]$.

More specifically, if $k$ is the maximal amount of deposits that can be mined, show that

For some constant $C > 0$ of your liking.

b) Algorithm depending on $k$ (30 Points)

Describe an algorithm that solves the task in subtask 3 and 4 and analyze it. This is a theoretical task, so you should reason why your solution is correct and what asymptotic running time and memory usage your solution has.

Let $k$ be is the maximal amount of mining nodes that can be used in the optimal solution. Find an algorithm that is fast when $k$ is small!

See the table below in ‘Grading’ to see how many points can be achieved for a given runtime and memory usage.

Check out the wiki for more information on how to solve/write theoretical tasks: Theoretical Intro

Grading

Hand in a document (preferably PDF) that describes

• how your algorithm works
• why your algorithm is correct
• analyze its running time and memory usage.

If your algorithm is correct, we will give you points according to the table below.

Note that $k$ here is the maximal amount of mining nodes that can be used in the optimal solution. Additional log factors only cause minor point deductions.

The contest is over, you can no longer submit.