| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
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://mirror.codeforces.com/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?
