| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
This is one of my favourite dp optimizations. I made a tutorial on it. Here I discuss how the trick works and how you can use it. I also discuss the problem Frog 3 from atcoder dp contest.
Here is the video: Link
The code that I discuss: Link
Better template of CHT: Link
Let me know if you like the tutorial or not :)
Maybe codeforces should monitor which blogs show up on the homepage? based on all the educative blogs we are seeing on black magic recently!!
I recently learned wavelet trees. This data structure can handle the following types of range queries in logarithmic time:
But I couldn't find the array based implementation of it anywhere, and as I don't like pointers(also pointer based implementations are often slower than array based ones because of the dynamic memory allocation), I implemented it myself. Here is the implementation: https://github.com/thisIsMorningstar/Competitive_Programming/blob/main/templates/wavelet_tree.cpp
I stress tested this with a bruteforce code against a couple thousand random testcases and it passed. But if you find any bugs in it, do let me know :).
You can learn about wavelet trees from here: https://codeforces.me/blog/entry/52854
I have seen some online judges which show the author's name on the statement page. I think that is a nice gesture towards the author of the problem for his contribution(and it feels great when that name is yours ;-;). Why doesn't codeforces do that?
