Codeforces 1202B - You Are Given a Decimal String Solution

Tags: brute force

The realization to this problem to make is that even though there can be up to 2*10^6 characters in the string, the number of combinations of 2 adjacent characters is 10*10 (00, 01, 02... all combinations). So then, for each of these combinations, you calculate the frequencies of each combination and keep that in an array. 

Then, you iterate over every counter (0-0, 0-1, 0-2...) let's call them i and j, and then for each counter, iterate over all combinations of possible adjacent characters (00, 01, 02...), let's call the first one a and second one b (like in 01, a is 0 and b is 1). Use a BFS (breadth first search) to find the shortest path from a to b using the i-j counter, and make sure that if a == b, then the BFS doesn't end when you put a into the queue (because the BFS checks if the current node is equal to b). If it's not possible for the i-j counter to reach b, then the answer for this counter is -1. Otherwise, the answer is (the frequency of a and b next to each other in the string)*((shortest distance from a to b using i-j counter)-1), and this is added to the sum for this counter. There's a -1 for the distance from a to b because the distance still counts b, which is already in the string.

Example:

08408

For the frequencies:
08: 2
84: 1
40: 1

Then iterate over each counter:
Let's say, i = 0  j = 1 (counter 0-1)
Then iterate over each adjacent number combinations:
Let's say, a = 0  b = 8
Starting from 0, the minimum distance from 0 to 8 using a 0-1 counter is 8. Since 08's frequency is 2, we add 2*(8-1) to the 0-1 counter's sum.

My submission (I'm using links w/ ads, tell me if it doesn't work for you): http://stfly.io/uhWA3r