Lowest Common Ancestor Training [Div. 1 Theory + Walkthrough]

Revision en3, by nskybytskyi, 2021-01-13 18:42:37

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one somewhat advanced gym that I want to cover today, and the reason is that it is only available in Russian :| Or should I say "was" instead of "is"? :D

I translated the statements to English and added them to the contest materials. As usual, I also recorded a problem walkthrough with theoretical material included, in case you ever get stuck or want to refresh the theory.

First I describe the LCA problem itself and explain the binary lifting approach to solve it in $$$\langle \mathcal{O}(n \log n), \mathcal{O}(\log n) \rangle$$$. I then reduce LCA to RMQ, and use Sparse Table to solve RMQ in $$$\langle \mathcal{O}(n \log n), \mathcal{O}(1)\rangle$$$ afterwards. I also give a short preview of Farach--Colton and Bender's $$$\langle \mathcal{O}(n), \mathcal{O}(1)\rangle$$$ algorithm. Finally, we solve an involved problem where you have to find bridges before finding LCA in the condensation graph.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

Tags #youtube, #lca, #rmq, #binary-lifting, #sparse table problems, #connected components


  Rev. Lang. By When Δ Comment
en3 English nskybytskyi 2021-01-13 18:42:37 28 Tiny change: 'e to find strongly connected components before f' -> 'e to find bridges before f'
en2 English nskybytskyi 2021-01-13 17:16:33 0 (published)
en1 English nskybytskyi 2021-01-13 17:16:26 1312 Initial revision (saved to drafts)