TLE in YVNUM

general
, ,
1

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 : CodeChef: Practical coding for everyone

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.

2

I removed the memoization from your code and changed int mod = pow(10,9) + 7 to const int mod = 1e9+7 and it passes. Don’t know why though!
https://www.codechef.com/viewsolution/22079088

2 Likes
3

Optimizing tip -
Ctrl+F then %

4 
Ctrl+F then %

I want to remove TLE to get AC, not for another WA :confused:

Which are the redundant ones which I can remove without getting WA? :slight_smile:

5

Thanks a lot!!

Well, it seems to me that the TL was poorly set keeping only linear solution in mind :/. Many of the fastExpo ones not preprocessing power of 10 failed because of taking 0.X extra seconds.

When making it const, compiler might do some random optimizations, which are completely dependent on the machine - that make it pass.