https://cses.fi/problemset/task/2072/
Treap is the intended solution to this task, but I didn't know treap well enough to write it on the spot. I did however know skiplist (which imo is less complicated) and so I ended up implementing this goofball:
...tags: programming cses
https://cses.fi/problemset/task/2416/
I had been kinda stuck on this for a while, mostly because I was trying to use some weird segtree bash.
...tags: programming cses
Actually very similar problem to IOI11p2 (Race) which I did last weekend, using centroid decomposition and then naive dp. Decided to write this one in C*, which was surprisingly easy.
...tags: programming cses
@ the halfway point
it only gets harder...
tags: programming cses
I swear binary exponentiation on matrices is actually magic.
While explaining this CSES problem to a friend, it occured to me that I could improve my O(n) solution, which used state machine DP, into a O(log n) one, by using matrix exp.
But even though I've used it quite a few times before, it still feels like magic. Take this task for example:
...tags: programming cses math