Блог пользователя JacobianDet

TLE IN SPOJ GCDEX
Автор JacobianDet, история, 7 лет назад, По-английски

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

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить