My website

There is a useful optimization trick involving DP on trees that I would like to discuss. It was detailed in the comments of this Codeforces blog. In short, you can define a DP over the vertices of a tree and compute its value for each $v$-subtree by combining the children... [Read More]

There is a great problem on Kattis called It’s a Mod, Mod, Mod, Mod World with a short statement: given $p$, $q$, and $n$, find $\sum_{i = 1}^{n} \left[ (pi) \bmod q \right]$. [Read More]

Today I’ll show the randomized solution for the problem E. Game of the Year. To solve it, I used XOR hashing. [Read More]

Today I’ll show the solution to the problem Dating (you can solve this problem on other platforms, such as Codeforces, too). The problem asks you to count the number of pairs of different types with the same number along a specific simple path in a tree. [Read More]

I’ll show you how I ended up implementing a sparse Lazy Segment Tree to solve a problem. There is a problem on oj.uz called Monkey and Apple-trees that involves range updates and range queries, but there is a small issue: the constraints are too large to build a data structure... [Read More]