Please site resources to understand techniques used in YVNUM

Here is the link to the problem https://www.codechef.com/COOK101B/problems/YVNUM. Please help me to understand the approach and intuition behind the solution. Please site any useful resources.

Check the unofficial editorial over here

The problem simply states,

  • Take current string as input string.

  • shift the input string and concatenate with current string. Repeat (n-1) times.

  • Treat final string as a number and output it with mod 10^9 + 7.

Where n = length of string.

Example:

Input string 456, output = 456564645

  • The maximum length of the input string is 10^5, so the maximum length of the concatenated string would be 10^5*10^5.

  • Also, a number xyz in decimal system is formed by x*10^2 + y*10^1 + z*10^0

  • (a+b) mod m can be written as ((a mod m) + (b mod m)) mod m.

Now let’s consider the same problem but without shifting, so answer for string 456 would be 456456456. We can make this number by,

((4*(10^8 % m ) ) % m) + ((5*(10^7 % m ) ) % m) + ((6*(10^6 % m ) ) % m) + ((4*(10^5 % m ) ) % m) … n^2 terms.

Where n is the length of the string.

But the above won’t work when n is 10^5, it’d run out of time.

((456*(10^6 % m ) ) % m) + ((456*(10^3 % m ) ) % m) + ((456*(10^0 % m ) ) % m). n terms.

This would work in O(n).

But what if instead of 456, the string is huge ?

If the string length is 10^5, we can’t take it into an integer format and multiply. We need to convert the string into a number mod m.

So again we do the same to calculate the actual number i.e if the string is 12345678912345678...10^5 terms,

((1*(10^(99999)) % m ) ) % m) + ((2*(10^(99998) % m ) ) % m) + ((3(10^(99997) % m ) ) % m) … 10^5 terms

Let’s say we get this number as x.

We do the same thing for x as we did for 456.

This would result in our final answer.

Now, let’s return to our original question.

  • The only change is the shift

  • Note that x (from above) changes here in each step.

In input string 456, x was 456. Meaning, concatenate x, n times. But here, we need to concatenate different numbers every time. 456,564,645. Calculating each number independently would result in O(n^2) which again won’t work.

But the numbers are not totally different to be calculated independently.

xyzw shifted, yzwx, zwxy, wxyz

xyzw*1 + 0

yzw*10 + x*1

zw*100 + xy*1

w*1000 + xyz*1

(Num from i till end)* (10^i) + (prefix till i-1) // 0 based

We can calculate suffix and prefix in O(n) and get x_i. Treating them as different x_is final result can be calculated.

a^b mod m in O(log(b))

Hint: Modular arithmetic, Observations. Precompute powers of 10 and process each cyclic shift in O(1) time. See my solution CodeChef: Practical coding for everyone

@taran_1407 Without precomputation of powers of 10, it still works tho.