JacobianDet's blog

TLE IN SPOJ GCDEX
By JacobianDet, history, 7 years ago, In English

I am getting tle in SPOJ GCDEX despite following 'A Dance with mobius function' blog. Please help.

My Solution: https://pastebin.com/TyQzd9Aw

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by JacobianDet (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've noticed that your approach has complexity O(nlogn + sqrt(n)*T), I don't really know why exactly it still gives TLE even with some optimizations I made (even memoizing answers doesn't work), but I think there is an approach to get O(nlogn + T) complexity, maybe the upper bound for the value of sqrt(n)*T makes it hard to pass the strict Time Limit.

Your Solution with some optimizations (still TLE :( ):

https://pastebin.com/B2RKyUhV

My solution for the problem in O(nlogn + T):

https://pastebin.com/tC0CtDAJ

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks, this got AC. But why is the blog method not working.

    Blog : https://www.quora.com/profile/Surya-Kiran/Posts/A-Dance-with-Mobius-Function

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I think it's because the post is from 2015 and the problem time limit was continuously updated, at the end of the statement it's announced that some AC solutions may get TLE after it.

      Anyways, if the starting solution didn't pass the time limit, you'd need to improve any part of the algorithm that may cause it: In this case, the complexity per query might ruin the execution time so it's the first candidate.

      My solutions preprocess each n and gets in a sieve style. After that just makes preffix sums to get the outer sum for each n and that would be the answer for each one.

      It just goes one step further that the blog's solution.

      → Reply