nskybytskyi's blog

By nskybytskyi, history, 3 years ago,

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!

• +80

 » 3 years ago, # | ← Rev. 3 →   +8 In English, strongly connected components usually refer to a concept on directed graphs. I believe you meant to refer to biconnected components as the concept used to reduce problem D to a rooted tree LCA problem. (EDIT: Actually, it is more specifically 2-edge-connected components. But "bridge-finding" is OK and certainly gets the point across!).
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Ah, okay. Can't say that I like this name tho, so I will probably refer to it as the bridge-finding instead.
 » 3 years ago, # |   0 Auto comment: topic has been updated by nskybytskyi (previous revision, new revision, compare).