×

# [closed] TLE in YVNUM

 0 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? 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. asked 24 Dec '18, 20:30 15.4k●1●20●66 accept rate: 18% Optimizing tip - Ctrl+F then % (25 Dec '18, 00:26) Ctrl+F then % I want to remove TLE to get AC, not for another WA :/ Which are the redundant ones which I can remove without getting WA? :) (25 Dec '18, 16:25)

### The question has been closed for the following reason "The question is answered, right answer was accepted" by vijju123 25 Dec '18, 16:42

 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 answered 25 Dec '18, 00:19 4★ankusht 36●2 accept rate: 100% 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. (25 Dec '18, 16:27)

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×720
×74
×51

question asked: 24 Dec '18, 20:30

question was seen: 294 times

last updated: 25 Dec '18, 16:42