You are not logged in. Please login at to post your questions!


[closed] TLE in YVNUM

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 :

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

vijju123's gravatar image

5★vijju123 ♦♦
accept rate: 18%

closed 25 Dec '18, 16:42

Optimizing tip -
Ctrl+F then %

(25 Dec '18, 00:26) aryanc4036★

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) vijju123 ♦♦5★

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

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!


answered 25 Dec '18, 00:19

ankusht's gravatar image

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) vijju123 ♦♦5★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 24 Dec '18, 20:30

question was seen: 294 times

last updated: 25 Dec '18, 16:42