You Are Given a Decimal String...
Contest: Educational Codeforces Round 70 (Rated for Div. 2)
Difficulty rating: 1700
Tags: brute force, dp, shortest paths

Suppose you have a special $$$x$$$-$$$y$$$-counter. This counter can store some value as a decimal number; at first, the counter has value $$$0$$$.

The counter performs the following algorithm: it prints its lowest digit and, after that, adds either $$$x$$$ or $$$y$$$ to its value. So all sequences this counter generates are starting from $$$0$$$. For example, a $$$4$$$-$$$2$$$-counter can act as follows:

1. it prints $$$0$$$, and adds $$$4$$$ to its value, so the current value is $$$4$$$, and the output is $$$0$$$;
2. it prints $$$4$$$, and adds $$$4$$$ to its value, so the current value is $$$8$$$, and the output is $$$04$$$;
3. it prints $$$8$$$, and adds $$$4$$$ to its value, so the current value is $$$12$$$, and the output is $$$048$$$;
4. it prints $$$2$$$, and adds $$$2$$$ to its value, so the current value is $$$14$$$, and the output is $$$0482$$$;
5. it prints $$$4$$$, and adds $$$4$$$ to its value, so the current value is $$$18$$$, and the output is $$$04824$$$.

This is only one of the possible outputs; for example, the same counter could generate $$$0246802468024$$$ as the output, if we chose to add $$$2$$$ during each step.

You wrote down a printed sequence from one of such $$$x$$$-$$$y$$$-counters. But the sequence was corrupted and several elements from the sequence could be erased.

Now you'd like to recover data you've lost, but you don't even know the type of the counter you used. You have a decimal string $$$s$$$ — the remaining data of the sequence.

For all $$$0 \le x, y < 10$$$, calculate the minimum number of digits you have to insert in the string $$$s$$$ to make it a possible output of the $$$x$$$-$$$y$$$-counter. Note that you can't change the order of digits in string $$$s$$$ or erase any of them; only insertions are allowed.

Input format:
The first line contains a single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^6$$$, $$$s_i \in \{\text{0} - \text{9}\}$$$) — the remaining data you have. It's guaranteed that $$$s_1 = 0$$$.

Output format:
Print a $$$10 \times 10$$$ matrix, where the $$$j$$$-th integer ($$$0$$$-indexed) on the $$$i$$$-th line ($$$0$$$-indexed too) is equal to the minimum number of digits you have to insert in the string $$$s$$$ to make it a possible output of the $$$i$$$-$$$j$$$-counter, or $$$-1$$$ if there is no way to do so.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's take, for example, $$$4$$$-$$$3$$$-counter. One of the possible outcomes the counter could print is $$$0(4)8(1)4(7)0$$$ (lost elements are in the brackets).

One of the possible outcomes a $$$2$$$-$$$3$$$-counter could print is $$$0(35)8(1)4(7)0$$$.

The $$$6$$$-$$$8$$$-counter could print exactly the string $$$0840$$$.

Example input:
0840

Example output:
-1 17 7 7 7 -1 2 17 2 7 
17 17 7 5 5 5 2 7 2 7 
7 7 7 4 3 7 1 7 2 5 
7 5 4 7 3 3 2 5 2 3 
7 5 3 3 7 7 1 7 2 7 
-1 5 7 3 7 -1 2 9 2 7 
2 2 1 2 1 2 2 2 0 1 
17 7 7 5 7 9 2 17 2 3 
2 2 2 2 2 2 0 2 2 2 
7 7 5 3 7 7 1 3 2 7

Editorial:
All you need to know to solve this task is the minimal number of steps to move from any digit $$$a$$$ to any digit $$$b$$$ for fixed $$$x$$$ and $$$y$$$ (let's denote it as $$$ds[a][b]$$$). Shortest path? BFS? Floyd? Of course, you can use it, but you can think a little harder and save nerves and time.
Since order of choosing operations $$$x$$$ and $$$y$$$ doesn't matter for transferring from $$$a$$$ to $$$b$$$, so only number of $$$x$$$-s and $$$y$$$-s are matter. Let's denote them as $$$cnt_x$$$ and $$$cnt_y$$$. Since adding any fixed value $$$10$$$ times are meaningless, so $$$cnt_x, cnt_y < 10$$$.
Now you can, for each $$$x < 10$$$, for each $$$y < 10$$$, for each $$$a < 10$$$ iterate over all possible $$$cnt_x < 10$$$ and $$$cnt_y < 10$$$. Digit $$$b$$$ you'd move to is equal to $$$(a + cnt_x \cdot x + cnt_y \cdot y) \mod 10$$$. Just relax value of $$$ds[a][b]$$$ by $$$cnt_x + cnt_y$$$.
Now you can, for each $$$x$$$ and $$$y$$$, calculate the answer by iterating over string $$$s$$$ by summing $$$ds[s[i]][s[i + 1]] - 1$$$ (number of inserted values is less by one than number of steps).
But, it will work only in C++, since the language is fast and $$$2 \cdot 10^8$$$ basic operations are executed in less than 0.5 second.
But the model solution is written in Kotlin. How is it? The string $$$s$$$ can be long, but there are only $$$10 \times 10$$$ different neighbouring digits, so you can just one time precalculate $$$cf[a][b]$$$ — the number of such $$$i$$$ that $$$s[i] = a$$$ and $$$s[i + 1] = b$$$. And calculate the answer not by iterating over $$$s$$$ but by multiplying $$$ds[a][b]$$$ by $$$cf[a][b]$$$.
The result complexity is $$$O(|s| + A^5)$$$, where $$$A = 10$$$. But $$$O(A^2(n + A^3))$$$ will pass on fast languages like C++.
P.S.: There are no real problem with I/O — both Python and Kotlin read one string up to $$$2 \cdot 10^6$$$ in less than 0.5 seconds.