You are not logged in. Please login at www.codechef.com 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 : 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.

asked 24 Dec '18, 20:30

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
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! https://www.codechef.com/viewsolution/22079088

link

answered 25 Dec '18, 00:19

ankusht's gravatar image

4★ankusht
362
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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×720
×74
×51

question asked: 24 Dec '18, 20:30

question was seen: 294 times

last updated: 25 Dec '18, 16:42