MOI2024
A. Trampolines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$n$$$ trampolines are placed in a row and numbered $$$1$$$ through $$$n$$$ from left to right.

Each trampoline $$$i \ (1 \le i \le n)$$$ has a strength $$$t[i] \ (t$$$ is an array of length $$$n$$$).

If one throws a ball on trampoline $$$i$$$, it bounces immediately to the position $$$i + t[i]$$$ and the process repeats from this position to later positions (i.e., from the position $$$j = i + t[i]$$$, it bounces to position $$$j + t[j]$$$) until the ball exits the row, i.e., its position is strictly greater than $$$n$$$ for a given time.

You are given $$$q$$$ queries of two types :

  • Query of type $$$0$$$ : given two integers $$$i$$$ and $$$x$$$, set $$$t[i]$$$ to $$$x$$$ (i.e., $$$t[i] := x)$$$.
  • Query of type $$$1$$$ : starting at position $$$i$$$, output the last position the ball was in before exiting the row and the number of bounces it does before exiting the row (in this order).
Input

The first line: you are given two space separated integers $$$n, q$$$ $$$(1 \le n, q \le 10^5)$$$.

The second line: you will be given $$$n$$$ space separated integers, the array $$$(1 \le t[i] \le 10^5)$$$.

Then $$$q$$$ queries, each query starts with $$$t \in \{0, 1 \}$$$, the type of the query.

Each query of type $$$0$$$ is described by two integers $$$i (1\le i \le n)$$$ and $$$x (1 \le x \le 10^5)$$$. Queries of type $$$1$$$ are described by one integer $$$i (1 \le i \le n)$$$ as described in the statement.

Output

For each query of the second type, output two space separated integers : the last position the ball was in before exiting the row and the number of bounces it does before exiting the row $$$\textbf{(in this order)}$$$.

Scoring

subtaskconstraintsscoring
$$$1$$$$$$1 \le n, q \le 10000$$$$$$5$$$ pts
$$$2$$$there are no queries of type $$$0$$$$$$10$$$ pts
$$$3$$$No additional constraints$$$85$$$ pts

Example
Input
3 3
1 3 2
1 1
0 1 2
1 1
Output
2 2
3 2

B. Yet Another Maximization Problem
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Akram likes to make you suffer subarrays so he made a problem for you.

You are given an array $$$a$$$ of length $$$n$$$ we define the value of a subbarray as the difference between the maximum and the minimum value in it. We split $$$a$$$ into subarrays, find the maximum sum of values of the subarrays of $$$a$$$ amongst all possible splits.

In a split each element should be contained in one and only one subarray.

You are given $$$q$$$ queries of two types, update queries described by $$$3$$$ integers $$$l, r, x$$$ where you should increment $$$a[i]$$$ by $$$x$$$ for all $$$l\le i \le r$$$ , formally $$$\forall i \in [l, r] \ \ a[i] := a[i] + x$$$, queries of the second type require you to output the maximum sum of values if we split $$$a$$$ optimally.

Input

In the first line two space separated integers $$$n, \ q$$$ ($$$1 \le n, q \le 10^5$$$) The second line $$$n$$$ space separated integers describing the array $$$a$$$, $$$-10^8\le a[i] \le 10^8$$$.

Then $$$q$$$ lines each of which starts with an integer $$$t (1\le t \le 2)$$$ : the type of the query, queries of type $$$1$$$ are update queries and are described by $$$3$$$ integers $$$l, r, x (1\le l \le r\le n, -10^8\le x\le 10^8)$$$. Queries of the second type require you to output the maximum sum of values if we split $$$a$$$ optimally.

Output

For each query of the second type output the maximum sum of values if we split $$$a$$$ optimally.

Scoring

subtaskconstraintsscoring
$$$1$$$the array is sorted and there are no updates$$$5$$$ pts
$$$2$$$$$$1 \le n, q \le 200$$$$$$15$$$ pts
$$$3$$$$$$1 \le n, q \le 2000$$$$$$30$$$ pts
$$$4$$$no further constraints$$$50$$$ pts

Example
Input
4 7
-1 3 -6 8
1 4 4 2
2
1 4 4 3
2
1 1 2 -1
1 1 2 -4
2
Output
20
23
23

C. Leaf Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$N$$$ nodes, and an integer $$$K$$$.

Your task is to partition the leaves of the tree into $$$K$$$ groups while respecting the following:

  • a group's valid tour is a path that starts from any leaf of that group, reaches all other leaves of the same group then goes back to its starting point.
  • a group's cost is the minimal traveled distance among all valid tours of that group.
  • The cost of a partition is the sum of its groups' costs.
  • The cost of the partition should be minimal
Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$3 \leq N \leq 10000, 2 \leq K \leq 20$$$)

The next $$$N-1$$$ lines contain two space separated nodes representing an edge $$$u$$$ $$$v$$$ ($$$ 1 \leq u, v \leq n$$$)

Output

A single integer, the minimal cost of a partition among all possible partitions into $$$K$$$ groups.

Scoring
  • (10 points) $$$3 \leq N \leq 30$$$ and $$$2 \leq K \leq 4$$$
  • (20 points) $$$K = 2$$$
  • (30 points) $$$K = 3$$$
  • (40 points) No additional constraints
Example
Input
10 2
10 6
2 10
3 10
4 10
1 2
5 6
8 9
4 8
5 7
Output
12