Friday, April 21, 2017

Episode 17 - Binary Lifting

Try these problems:

I realize the last few weeks have been a bit rough for Div2 viewers. The problems have been near ICPC World Finals level and I want to vary the difficulty of topics to make sure everyone can enjoy the show. This week I'll be covering a technique that is more accessible! This technique is called binary lifting. It is a technique for quickly walking up a rooted tree.

In last week's episode, I discussed the solution to the problem Ski Resort from NAIPC. The problem required us to compute LCAs (least common ancestors) quickly on rooted trees. I'll be expanding on how to do that in this episode.

You'll also learn how to quickly know the length of paths in trees, find bottle neck edges quickly in weighted graphs, and other useful tricks.

See you live! (stream, time)

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. I've posted this during contest so I had to remove it, but here it's a nice problem for this topic https://www.hackerrank.com/contests/w33/challenges/path-matching

      Delete
  2. Here is how to build MST when weight is Manhattan (L1) distance https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ (I had to read it a couple of times before got the idea)

    ReplyDelete