Editorial for Baltic OI '14 P3 - Sequence - DMOJ: Modern 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)$ ~\mathcal O(NK)~

$N$ ~N~ - correct answer.

Since $K \le 1000$ ~K \le 1000~ and $N \le 1000$ ~N \le 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)$ ~\mathcal O(K^2)~ solution.

Time complexity: $\mathcal O(K^2)$ ~\mathcal 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 \le d \le 8~, then our answer is $N = d \times 10^x = d0 \dots 0$ ~N = d \times 10^x = d0 \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 = d0 \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 = d0 \dots 0 = 30 \dots 0 = 300~.

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

Subtask 4

We'll solve our task by solving a more complex task first: for each $i^\text{th}$ ~i^\text{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^\text{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 \bmod 10~ is the last digit and $X = \lfloor \frac{N}{10} \rfloor$ ~X = \lfloor \frac{N}{10} \rfloor~. 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$

After removing last digit, we get sequence $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 \setminus \{y\}~. $(X)(y+1)$ ~(X)(y+1)~ has $A_2$ ~A_2~, so $X$ ~X~ must have $A_2 \setminus \{y+1\}$ ~A_2 \setminus \{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$ ~\lfloor \frac{K}{10} \rfloor+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)$ ~\mathcal O(K \log K)~

Comments

There are no comments at the moment.