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:

1. Number of elements in subarray A[L...R] that are less than or equal to y.
2. Number of occurrences of element x in subarray A[L...R].
3. The kth smallest element in subarray A[L...R].

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.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?