Editorial for Baltic OI '14 P3 - Sequence - Olympiads Online Judge

Editorial for Baltic OI '14 P3 - Sequence

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

We try all possible $N$ $N$ values (starting from smallest - $1$ $1$ ). With each $N$ $N$ , we check if it is the answer using brute force - checking if all sequence numbers contain the required digits.

Time complexity: $\mathcal O(NK)$ $O (N K)$

$N$ $N$ - correct answer.

Since $K \le 1000$ $K \leq 1000$ and $N \le 1000$ $N \leq 1000$ in the first subtask, this solution is enough for it.

Subtask 2

If the full solution is programmed inefficiently, it is possible to acquire an $\mathcal O(K^2)$ $O (K^{2})$ solution.

Time complexity: $\mathcal O(K^2)$ $O (K^{2})$

Subtask 3

We are assuming that all elements of the given sequence are equal. Let's denote this digit as $d$ $d$ .

If $1 \le d \le 8$ $1 \leq d \leq 8$ , then our answer is $N = d \times 10^x = d0 \dots 0$ $N = d \times 10^{x} = d 0 \dots 0$ .

If $d = 9$ $d = 9$ , then $N = 8 \dots 89$ $N = 8 \dots 89$ (some number of digits 8 and one digit 9 at the end).

If $d = 0$ $d = 0$ , then $N = 10^x = 10 \dots 0$ $N = 10^{x} = 10 \dots 0$ .

The length of $N$ $N$ depends on $K$ $K$ . For example, if $K = 5$ $K = 5$ and our sequence is 3 3 3 3 3, then $d = 3$ $d = 3$ and $N = d0 \dots 0 = 30 \dots 0 = 30$ $N = d 0 \dots 0 = 30 \dots 0 = 30$ . If $K = 11$ $K = 11$ and $d = 3$ $d = 3$ , then $N = d0 \dots 0 = 30 \dots 0 = 300$ $N = d 0 \dots 0 = 30 \dots 0 = 300$ .

Time complexity: $\mathcal O(1)$ $O (1)$

Subtask 4

We'll solve our task by solving a more complex task first: for each $i^\text{th}$ $i^{th}$ sequence element we'll declare sequence $A_i$ $A_{i}$ . $A_i$ $A_{i}$ is the sequence of digits which $i^\text{th}$ $i^{th}$ sequence element has to have. For our initial task, $A_i = \{d_i\}$ $A_{i} = {d_{i}}$ , where $d_i$ $d_{i}$ - ... (DMOJ editor note: did the author get lazy here?)

Let's denote $N = (X)y$ $N = (X) y$ , where $y = N \bmod 10$ $y = N mod 10$ is the last digit and $X = \lfloor \frac{N}{10} \rfloor$ $X = ⌊ \frac{N}{10} ⌋$ . Now we have to try all possible $y$ $y$ values $(0, 1, \dots, 9)$ $(0, 1, \dots, 9)$ . After we have locked $y$ $y$ with one of the possible values, our sequence looks like this:

$\displaystyle (X)y, (X)y+1, \dots, (X)8, (X)9, (X+1)0, (X+1)1, \dots, (X+1)8, (X+1)9, (X+2)0, \dots$ $(X) y, (X) y + 1, \dots, (X) 8, (X) 9, (X + 1) 0, (X + 1) 1, \dots, (X + 1) 8, (X + 1) 9, (X + 2) 0, \dots$

After removing last digit, we get sequence $X, \dots, X, X+1, \dots, X+1, X+2, \dots$ $X, \dots, X, X + 1, \dots, X + 1, X + 2, \dots$

What digits does $X$ $X$ have to have? $(X)y$ $(X) y$ has $A_1$ $A_{1}$ , so $X$ $X$ must have $A_1 \setminus \{y\}$ $A_{1} ∖ {y}$ . $(X)(y+1)$ $(X) (y + 1)$ has $A_2$ $A_{2}$ , so $X$ $X$ must have $A_2 \setminus \{y+1\}$ $A_{2} ∖ {y + 1}$ and so on.

By merging these requirements, we can get a new sequence of sets $B_1, B_2, \dots$ $B_{1}, B_{2}, \dots$ . $B_1$ $B_{1}$ declares the required digits for $X$ $X$ , $B_2$ $B_{2}$ - for $X+1$ $X + 1$ , and so on. We repeat the same steps with our new sequence. What happens when we repeat these steps? We started with sequence length $K$ $K$ , so after the first step, our new sequence length will be not bigger than $\lfloor \frac{K}{10} \rfloor+1$ $⌊ \frac{K}{10} ⌋ + 1$ . So after $\log K$ $\log K$ steps our sequence will be of length $1$ $1$ or $2$ $2$ - at this step, we can produce the answer.

Time complexity: $\mathcal O(K \log K)$ $O (K \log K)$

Comments

There are no comments at the moment.