When a problem has a time limit of 1 second per test case or anything for that matter, how can I calculate the expected runtime of my program in seconds or ms?
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | atcoder_official | 148 |
| 5 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.07.2024 11:13:32 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
It comes with experience.
TheRe are MANy iNCompREheNsIBLe opTImiZAtIons iN MoDErN cPu and meMorY. FROm C++COdE TO aSSeMblY Is eNOUGH TO COnsuMe a peRsOn's lIfE. iT IS ALmOsT impOsSiblE To fIND A metHod tO accUrATeLY cALCuLAte tHE time ReQuIred FOr a PrOgram tO RuN.
a MoRe EfFECtivE metHoD Is To EStImATe tHe iNcreMEnTaL COMPLExItY, OR (WHEn THe iNcReMENTAl COmpLexIty IS DifFicult to CAlcUlATE) genERATE thE lArgEst dAta AND run IT lOcaLlY.
I think if the time complexity of your program if f(n), then you must have f(n) <= 10^9 to work. Thats a good heuristic anyways. So 10^5 you can use n * sqrt(n) or nlgn or n time complexity, or n= 10^4 you can use n^2, or n= 30 you can use 2^n (maybe, depends on constant factors). If n=10^9 you need linear time, or something very close to linear like maybe n *lg(lg(n)). More exact than that is just random stuff you learn. Like hashmaps are slow, so it might make a solution with right asymptotic performance not work still.
Almost all problems have time limit 1s or roughly that, so this heuristic works well.
This is a good comment except you use 1e9 instead of 1e8. I have never seen a linear algo work for 1e9, and if it does it's certainly the exception rather than the rule.
Even when you get something to a complexity that reaches something like 1e8 (like a n² dp for n = 10000) you need to be really careful about constant factors (recursive dps never work and sometimes the order in which you declare the states in your dp table matters, dp[n][m] might pass but dp[m][n] might not). Saying that checking for 1e9 is a good heuristic is crazy.
Hmmm. I think I agree with you. I am saying f(n) = 10^9 is an upper bound. Ie if its worse than that, forget it. However, it might not work even if f(n) = 10^9. I think I have done problems in linear time with n = 10^9. I can't find any right now though. Maybe I am wrong and am misremembering.
https://codeforces.com/blog/entry/12755
Here I see some people posting scripts to count number of operations on codeforces servers, and get 4 * 10^9 operations albeit with extremely simple code.
Maybe this will help you.