# Hanoi selection round for Vietnamese Olympiad in Informatics 2023-2024

**Duration:** 180 minutes for each day
**Allowed languages:** C++, Python and Pascal

## Day 1 (October 21, 2023)
| # | Problem | Points |
| --- | ----------------- | ------ |
| I | [DCH](#I---DCH) | 5 |
| II | [TSX](#II---TSX) | 5 |
| III | [SMM](#III---SMM) | 5 |
| IV | [TDL](#IV---TDL) | 5 |

## Day 2 (October 22, 2023)
| # | Problem | Points |
| --- | --------------- | ------ |
| V | [DCD](#V---DCD) | 7 |
| VI | [NX](#VI---NX) | 7 |
| VII | [CT](#VII---CT) | 6 |

# I - DCH
Given three non-negative integers $N$, $K$ and $X$. Assume $S_i$ is the array of numbers in $[0, N]$ which has remainder equal to $i$ when divide by $K$, **sorted in decreasing order**. Then we create an array $A = S_X + S_{X+1} + \ldots +S_{K-1} + S_0 + S_1 + \ldots + S_{X-1}$.

For example, with $N = 10$, $K = 4$ and $X = 2$:
- $S_2 = [10, 6, 2]$,
- $S_3 = [7, 3]$,
- $S_0 = [8, 4, 0]$,
- $S_1 = [9, 5, 1]$,
- $A = [10, 6, 2, 7, 3, 8, 4, 0, 9, 5, 1]$.

## Task
Given $Q$ queries, each query has three non-negative integers $N$, $K$, $X$ and a positive integer $D$. Find the $D$-th element of array $A$.

## Input
- The first line: a positive $Q$ $(Q \le 10^6)$ - the number of queries,
- Each of the next $Q$ lines: four integers $N$, $K$, $X$ and $D$ $(0 \le X < K < N \le 10^{18}, D \le N + 1)$.

## Output
$Q$ lines, each line contains an integer - answer of each query.

## Sample test
### Input

2
10 4 2 5
10 3 0 6

### Output

3
7

### Note
In the second query: $N = 10$, $K = 3$ and $X = 0$:
- $A = [9, 6, 3, 0, 10, 7, 4, 1, 8, 5, 2]$,
- The $6$-th element is $7$.

## Constraints
- 50% of points: $Q, N \le 10^3$,
- 30% of points: $X = 0$, $Q \le 10^5$,
- 20% of points: No additional contraints.

# II - TSX
Given a string $S$ consists of lower-case Latin letters. Each letter 'a', 'b', ..., 'z' is indexed from 1 to 26. The value of a string is defined as the sum of the absolute values of the difference in order between the characters in the string and the first character of that string.

For example, $S=``cadc"$, the value of $S$ is:
$|`c`-`c`| + |`a`-`c`| + |`d`-`c`| + |`c`-`c`|$
$= |3 - 3| + |1 - 3| + |4 - 3| + |3 - 3|$
$= 0 + 2 + 1 + 0$
$= 3$

## Task
Find a **substring** (a segment of consecutive characters) of $S$ which has the **maximum** value and its first and last character must be **equal**.

## Input
A string with length $N$ ($N \le 10^6$).

## Output
An integer - the maximum value of a substring of $S$.

## Sample tests
| Input | Output | Note |
| ----------- | ------ | ------------------------------ |
| `bcacadbac` | `8` | Choose substring $``cacadbac"$ |
| `abcaczc` | `25` | Choose substring $``caczc"$ |

## Constraints
- 50% of points: $N \le 10^2$,
- 30% of points: $N \le 10^4$,
- 20% of points: No additional contraints.

# III - SMM
Given an array $A$ with $N$ elements, each element has value from $1$ to $9$. $S_{L, R}$ is the integer, which get by concatenating all elements from position $L$ to $R$ of $A$. For example, $A=[2, 6, 5, 7, 4]$, then $S_{2, 5} = 6574$.

An integer is called lucky if it **does not** contain the substring $``13"$. For example, $6, 12, 31, 103, \ldots$ are lucky numbers, while $13, 5713, 321321, \ldots$ are not.

## Task
You have to perform $Q$ queries of two types:
- Type 1: Print the number of lucky numbers not exceed $S_{L, R}$,
- Type 2: Replace the $i$-th element of $A$ by $X$.

## Input
- The first line: two positive integers $N$ and $Q$ $(N, Q \le 2 * 10^5)$,
- The second line: $N$ elements of array $A$, no space in between $(1 \le A_i \le 9, 1 \le i \le n)$,
- Each of the next $Q$ lines contains one of the following type of query:
- $1 \space L \space R$: Print the number of lucky numbers not exceed $S_{L, R}$ $(1 \le L \le R \le N$), modulo $10^9 + 7$,
- $2 \space i \space X$: Replace the $i$-th element of $A$ by $X$ $(1 \le i \le n, 1 \le X \le 9)$.

## Output
Print out the answer for each query of type 1.

## Sample test
### Input

6 3
849613
1 1 2
2 3 4
1 4 4

### Output

84
7

### Note
- First query: the lucky numbers not exceed $84$ are $0, 1, 2, \ldots, 12, 14, 15, \ldots, 84$,
- Second query: $A = 844613$,
- Third query: the lucky numbers not exceed $6$ are $0, 1, 2, 3, 4, 5, 6$.

## Constraints
- 20% of points: $N \le 6, Q = 1$,
- 20% of points: $N \le 6$,
- 20% of points: $N \le 100$,
- 20% of points: $Q \le 2000$,
- 20% of points: No additional constraints.

# IV - TDL
TR is a system for direct data exchange between computers being tested at school X. The school has $N$ computers numbered from $1$ to $N$. The computers all use the TR system and are connected to each other according to a tree graph.

Initially, the system has a data file being stored by **one or two** computers. The school wants to transmit this file to all other computers in the system. The data transmission mechanism of the TR system is as follows: every minute, each computer in the system can transmit data to **at most one** other computer directly connected to it.

## Task
Given the index(es) of the computers which stores the data files at the beginning. Find the **minimum** time required so that all the computers can receive the data file.

## Input
- The first line: a positive integer $N$ $(1 < N \le 10^5)$,
- Each of the next $N - 1$ lines: two different positive integer $x$, $y$ $(1 \le x, y \le N)$ - indexes of two directly connected computers,
- The next line: an integer $M$ $(1 \le M \le 2)$ - the number of the computers which store the data files at the beginning,
- The last line contains $M$ positive integers - indexes of the computers which store the data files at the beginning.

## Output
The minimum time required so that all the computers can receive the data file.

## Sample tests
### Test 1
#### Input

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

#### Output

3

#### Note
- At the beginning, computer $1$ stores the data file,
- Minute 1: computer $2$ receives the data file,
- Minute 2: computers $3$ and $5$ receive the data file,
- Minute 3: computers $4$ and $6$ receive the data file.
### Test 2
#### Input

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

#### Output

2

#### Note
- At the beginning, computers $1$ and $2$ store the data file,
- Minute 1: computers $3$ and $5$ receive the data file,
- Minute 2: computers $4$ and $6$ receive the data file.

# V - DCD
Given a positive integer $N$. Find an array which satisfy **all** the following conditions:
- The numbers of elements is greater than $2$, all elements of the array are **positive** integers,
- The array is sorted in **non-decreasing** order and the absolute values of two consecutive elements are **equal**,
- The sum of all elements is $N$,
- If there are many such array, take the array which has the **maximum** number of elements,
- If there are still many such array, take the array which has the **minimum** first element.

## Input
A positive integer $N$ $(N \le 10^9)$.

## Output
A line contains the required array. If you can not find any such array, print $-1$.

## Sample tests
| Input | Output | Note |
| ----- | ------- | ---- |
| `12` | `1 4 7` | Arrays $[2, 4, 6]$ and $[2, 3, 5]$ also have sum of $12$ and the number of elements is $3$. But array $[1, 4, 7]$ has the minimum first element. |
| `20` | `2 3 4 5 6` | Array $[2, 4, 6, 8]$ also have sum of $20$. But array $[2, 3, 4, 5, 6]$ has more elements. |

## Constraints
- 40% of points: $N \le 10^3$,
- 30% of points: $N \le 10^5$,
- 30% of points: No additional constraints.

# VI - NX
Given an array $S$ consists of $N$ strings $S_1, S_2, \ldots, S_N$. Each string in $S$ consists of lowercase Latin letters. With each string $S_i$ $(1 \le i \le N)$, choose a **non-empty substring**, call it string $T_i$. Then, concatenate $T_1, T_2, \ldots T_N$, call it string $P$.

## Task
Given a positive integer $K$, find the string $P$ which has length $K$ and is **lexicographically smallest**.

## Input
- The first line: two positive integer $N$ (the size of array $S$) and $K$ (the length of string $P$),
- $i$-th line of the next $N$ lines contains string $S_i$

It is guaranteed that $1 \le N \le K \le \sum_{i=1}^{N} |S_i| \le 4000$ ($|S_i|$: the length of string $S_i$)

## Output
A line contains the required string $P$.

## Sample tests
### Test 1
#### Input

2 3
aen
bbb

#### Output

abb

#### Note
- Get substring "a" from string "aen",
- Get substring "bb" from string "bbb".
### Test 2
#### Input

2 3
bb
adh

#### Output

bad

#### Note
- Get substring "b" from string "bb",
- Get substring "ad" from string "adh",

## Constraints
- 30% of points: $N = 2; \space |S_1|, |S_2| \le 100$,
- 30% of points: $1 \le N \le 50; \space |S_1| = |S_i| \le 10 \space (1 \le i \le N)$,
- 40% of points: No additional constraints.

# VII - CT
Given $N$ intervals on the $OX$-axis. Two intervals are called **intersect** if they have **at least one** common point.

## Task
You have to select two sets of intervals $S_1$ and $S_2$ which satisfy **all** the following conditions:
- Each of the given $N$ intervals can be in **at most one** set,
- **Every** two intervals of each set are **intersect**,
- The **minimum** size of $S_1$ and $S_2$ is **maximum**.

## Input
- The first line: a positive integer $N$ - the number of intervals,
- $i$-th line of the next $N$ lines contains two integers $l_i, r_i$ $(1 \le l_i \le r_i \le 10^9)$ - the left and right endpoints of $i$-th interval, respectively,

## Output
Print the **maximum minimum** size of $S_1$ and $S_2$.

## Sample test
### Input

5
4 7
1 8
8 10
2 6
11 12

### Output

2

### Note
There are many ways to choose two sets:
- If $S_1$ consists of the $1$-st, $2$-nd and $4$-th interval, $S_2$ consists of $3$-rd or $5$-th interval, then the minimum size of $S_1$ and $S_2$ is $1$,
- If $S_1$ consists of the $1$-st and $4$-th interval, $S_2$ consists of $2$-nd and $4$-th interval, then the minimum size of $S_1$ and $S_2$ is $2$,

We are interested in the maximum value, thus, the answer is $2$.