I'm just wondering, how fast should my algorithm be in order to avoid TLE (Time Limit Exceeded)?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 16:28:34 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Difficult to tell, around 10^8
for N=20, O(2^N) is nice
for N=30, O(N^5)
for N=100, O(N^3)
for N=1000, O(N^2)
for N=100000, O(N lg N)
for N>10^12, you may need to consider O(1)/O(lg N)
Exactly, it depends highly on basic operations you use. for example
%(mod) is worth nearly dozens ofifoperations...That's not true — integer modulo is fast (exactly as fast as division, to be exact, and integer division is fast nowadays) and floating point modulo is not used that much.
Well, I had a case where I multiplied 100x100 matrices and in the innermost loop I used integer modulo (long long to be precise) and when I put it in the second loop (from the 3rd one) the time decreased by 1 sec
Almost everything you mentioned should run longer than 10s, especially
for N > 1012. Just the O(N3) and O(N5) are possible, if those are dynamics with low constants.
For O(2N), anything above N = 20 requires optimization. If N > 108, you should probably try
, but there are still peculiar complexities like 
.
It's hard to say anything in general, because there are many subtle differences. You really find out what you can afford by experience.
Actually, CF's comment system messed it up. He didn't separate the list with commas rather he split it with newlines which are unfortunately not seen unless you type
<br>Ow... I thought it was separated by commas. That's why I always use Preview before posting.
that means i need to type two new lines to see the actual new line? orz
Thanks!