Hi guys,

I am annoyed by constant TLE’s in this question. My O(NLogN) solution takes 1.86 on T=10 and N=10^{10^5} (i.e. when length of N is of order 10^5)

Any tips on optimizing it further?

Link : https://www.codechef.com/viewsolution/22076971

My logic was, iterate through every digit, and calculate its contribution at once using fast exponentiation. Say, we are finding contribution of i’th digit, we know the pattern will be like-

The same digit will appear after N-1 places again in Y_N.

There will be a jump of 2*N-1 when the digit goes from first place to last.

GP with same ratio maintained again, i.e. digit repeats at N-1 interval.

Hence, I add Digit*(Sum of powers of 10) which can be calculated by formula for sum of the 2 GPs.