radoslav11's blog

By radoslav11, history, 5 years ago, In English

Hi!

So recently I saw that quite a lot of people have created YouTube channels related to competitive programming and as I had nothing to do today an idea of me doing the same came to my mind. So as I wanted to do something that might be just a bit useful, I decided to do a tutorial on Virtual/Auxiliary Trees as my first video (which is a concept that can be used in some problems related to trees). I chose this as a topic, because I couldn't find a decent tutorial on it.

Here is a link to the video and my channel. I hope you'll enjoy it.

Any feedback will be appreciated, even if it's in the lines of "pls don't ever create a new video". Also if there are some concepts that you might be interested in me covering, feel free to comment/message me. Actually, any video ideas will be very much appreciated!

Right now I'm thinking of covering Burnside lemma (with problems) as I couldn't find a good tutorial on that too. Also I will probably upload some screencast with commentary.

Update: made a new video about Li Chao trees. Here (https://www.youtube.com/watch?v=-StmrE2gY44&t=16s) is a link if someone is interested.

  • Vote: I like it
  • +218
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Why these tags? lol

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I watched random parts (maybe 10 minutes total) and your video is great. I'm talking about both the topic and video quality. Please do more!

Next time say in a blog what the video is about, so people would know if it's worth watching for them or not. I would say that it's perfect for people who prepare for IOI or so. It's about answering queries "given a set of $$$k$$$ vertices in a tree, find the sum of distances of all $$$k^2$$$ pairs of them". If somebody knows this and just wants to make sure about the solution, here's the one-sentence summary (but watch the video if you don't know this!):

Spoiler
»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

pls don't ever create a new video

»
5 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I'm now up to implementation part — what I missed in the "ideas" part is how we setup distances between nodes in our new weighted tree. I assume it's just standard LCA to find distances, but might be worth a mention, since some people might not want to watch the implementation part. Otherwise — I like the quality of the video, everything was nice and smooth and well prepared, keep it up!

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

year 2025:cf blogs replaced by youtube

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by radoslav11 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

It was fun to learn this new trick! Thank you! Subscribed!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody share the proof of why auxiliary/virtual tree of set of k nodes contains at max 2*k-1 nodes.

Or to be precise how does taking LCA of k-1 adjacent nodes pair (sorted by DFS time order of original tree) make sure to include LCA of all pairs of k nodes.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    Suppose you have two vertices $$$u, v$$$ (not necessarily adjacent in the ordering $$$a$$$).

    Firstly assume that the LCA is not among the original vertices and neither of them is an ancestor of the other.

    Then $$$u, v$$$ are in the distinct subtrees $$$T_u, T_v$$$ of their LCA, and wlog suppose $$$u$$$ comes before $$$v$$$. Now in $$$a$$$, consider the last vertex that is in $$$T_u$$$, and the first vertex that is not in $$$T_u$$$ but in the subtree of their LCA (this exists since $$$v$$$ is a vertex not in $$$T_u$$$). Note that the LCA of these two adjacent vertices is the LCA of $$$u, v$$$, so this case is done.

    The other cases are pretty similar.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I couldn't find any in detail tutorial on virtual trees and accidentally found yours. Thank you so much for the great and step by step explanation.

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it