thisIsMorningstar's blog

By thisIsMorningstar, history, 16 months ago, In English

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 :)

Full text and comments »

  • Vote: I like it
  • +37
  • Vote: I do not like it

By thisIsMorningstar, history, 18 months ago, In English

Maybe codeforces should monitor which blogs show up on the homepage? based on all the educative blogs we are seeing on black magic recently!!

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

By thisIsMorningstar, history, 20 months ago, In English

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.net/blog/entry/52854

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

By thisIsMorningstar, history, 2 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +216
  • Vote: I do not like it