I am getting tle in SPOJ GCDEX despite following 'A Dance with mobius function' blog. Please help.
My Solution: https://pastebin.com/TyQzd9Aw
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I am getting tle in SPOJ GCDEX despite following 'A Dance with mobius function' blog. Please help.
My Solution: https://pastebin.com/TyQzd9Aw
Name |
---|
Auto comment: topic has been updated by JacobianDet (previous revision, new revision, compare).
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
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
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.
Thanks, I get that now