I am getting tle in SPOJ GCDEX despite following 'A Dance with mobius function' blog. Please help.
My Solution: https://pastebin.com/TyQzd9Aw
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | orzdevinwang | 3844 |
| 3 | jqdai0815 | 3682 |
| 4 | jiangly | 3618 |
| 5 | Benq | 3529 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3443 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | atcoder_official | 162 |
| 3 | maomao90 | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.12.2024 02:29:53 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
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