| # | User | Rating |
|---|---|---|
| 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 |
| # | User | Contrib. |
|---|---|---|
| 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 |
| 9 | nor | 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.net/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?
