LGCPC 2025

I participated in the LGCPC 2025 finals, placing in the 20s. As awards were only given to the top three contestants, I felt rather little pressure, though this naturally led to a lack of motivation.

Problem B was a typical dynamic programming problem, though its implementation unfortunately took quite a while.

Problem C had an interesting setting. It could be modeled as a random walk with three moves (stay, left, or right), which led to the trinomial coefficients. We had to calculate the equation below for all $L\le N\le R$.

During the contest, I was unable to find a solution with a time complexity better than $O((R−L)N)$. It turns out by separating the $i$ and $N−2i$ terms, the expression forms a convolution that can be solved in $O(N\log N)$ using the FFT or NTT.