Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

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

Revision en1, by nskybytskyi, 2021-01-13 17:16:26

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 strongly connected components 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!

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 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 nskybytskyi 2021-01-13 17:16:33 0 (published)
en1 nskybytskyi 2021-01-13 17:16:26 1312 Initial revision (saved to drafts)