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

Правка en2, от nskybytskyi, 2021-01-13 17:16:33

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!

Теги #youtube, #lca, #rmq, #binary-lifting, #sparse table problems, #connected components

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)