Hello coders, recently I came across this thing that many people who are new to CP often find it difficult to reduce the time complexity of their algorithm. They know the O(n^2) or any higher complexity algorithm but find it hard to reduce it to better time complexity. I request my fellow coders who are now comfortable in reducing the time complexity of their algorithms, to share their approaches and thought processes. This will help many people to think along those lines and eventually get better. Thanks and hope this post may help many.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.05.2024 04:26:01 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
You may consider a hash based solution
Ohh yeah, the hash based solution, works every time
$$$O(n^2)$$$ to $$$O(1)$$$ in seconds.
It's O(N) to put it into the hashset thonk
And get hacked everytime.(if there is open hacking and you didn't make at least double randomized hashing)
And what about open addressing? ;)
Yeah, those hashing resolvers are cool. But notice, that if collisions happens a lot, it might get hacked from TLE not from only WA. Also, resolving collisions while hashing a string is not recommended. It slows down the algorithm by a lot. For example, if you saw a hash collision, you need to compare the whole length of the substring of the string with the other one. Collision Resolvers will work well if only one of the substring exist. That means, no other substrings that are similar to each other would exist. Randomized Double hashing is the safest for now with a very low chance of collisions which nearly always pass.