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.
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.
Hint: Modular arithmetic, Observations. Precompute powers of 10 and process each cyclic shift in O(1) time. See my solution https://www.codechef.com/viewsolution/22054715
@taran_1407 Without precomputation of powers of 10, it still works tho.