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.
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.
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