Regarding Yalalovichik Numbers (Dec Cookoff)

general
1

Hello ,
I solved the question in O(|N|.log(|N|) time , still i am getting tle .
About my approach :For example if N=123 then Y(N) = 123231312 => Y(N) = (123000000 + 231000 + 312)
MOD=1000000007 .
Now Y(N) %MOD = [(123%MOD) * pow(10,6)%MOD + …] I calculated modulo of all rotated strings in O(N + NlogN) time [N=length of string <=1e5].

Similarly , Modulo of powers of 10 can also be calculated in log(N) using efficient power function .
So , with this complexity the solution should pass the test cases .

Here is my submission : https://www.codechef.com/viewsolution/22071431
Please help me as I am bewildered and confused as to where did I go wrong.

2

int d = n.size();
arr[0] = n;
rep(i,1,d)
{
string t1 = n.substr(0,i) , t2 = n.substr(i,(d-i));
t1=t2+t1;
arr[i]=t1;
}
substr function takes linear time complexity, so the complexity goes to \mathcal{O}(\mid{N}\mid^2)

Take a look here for understanding how you can do it without the substr function