A brief hiatus

As I mentioned in Episode 20, I'll be going on a brief hiatus from running weekly episodes of Algorithms Live! from now until mid-June. The reason is I'm attending ICPC World Finals over the next few days and immediately after will be helping with the USACO training camp. I was a bit concerned with the quality of episodes while traveling. I also want to take a much needed break. Once I'm back in Orlando, I'll resume my regular weekly episodes. If you are lucky enough to be attending the world finals, please say hello!

You could even call the first 21 episodes of Algorithms Live! season one. The first run has been exciting! The show has featured three interesting guests: Deon Nicholas, Lewin Gan, and Makoto Soejima. (I hope to bring more guests on during the summer months.) The channel has also reached 1000 subscribers. The show has a global audience with the most popular countries being India, Brazil, and the United States. I hope many of you have found the show useful and interesting.

Thanks for watching and I'll be back soon! :)

Episode 20 - Bitmask Dynamic Programming

Here are some problems related to this week's episode:

• FloorBoards
• OrderOfTheHats
• Reach for the Stars

The topic this week will be bitmask dynamic programming. In particular I will discuss the so called "rolling bitmask" technique and how it is useful in solving certain types of dynamic programming problems.

See you live! (stream, time)

Episode 19 - Knapsack

This week's episode will cover knapsack and subset sum. I'll be going over some of the basics of the pseudo-polynomial time algorithm and some of the variants. Gradually, I'll move into more complex variants and related techniques before ending with the solution to this problem:

• https://open.kattis.com/problems/thief

I recommend attempting the above problem. Even though it is knapsack (which is generally considered simple), the problem is quite tough. I hope this episode has something interesting for everyone!

As I'm the author of this problem, I'll be running through how I came up with the problem and some of the tricks I learned from other problems that became relevant to the solution. I hope you will find this episode a very thorough treatment of knapsack and subset sum in general.

Here is another difficult problem related to subset sum you should be able to solve after this episode:

• http://main.edu.pl/en/archive/oi/20/pol

In other news, I participated in the TCO regional event in Austin last weekend. It was great to meet many new friends. Some even watch this show! Overall, it was a fun event and I recommend attending any TCO event in the future. For this contest, I employed a new strategy of listening to a waterfall during the contest to help me focus. Do you have a special technique for focusing during contests?

Tomorrow will be the regional event at ITMO in St. Petersburg. I'm sure many top competitors will be attending. Check it out if you live near there! It seems there will be a mirror of this contest online. :)

I'm also looking to make Algorithms Live! more useful. Some viewers have requested written versions of each episode. Unfortunately, I don't have enough time to convert each episode into a written version. If any viewers are up for the task, it would be extremely helpful. :) I'd be happy to send my notes and code written during the episode. Please contact me on Codeforces if this sounds interesting to you.

Another suggestion was to include time tags in the video description for specific topics in each episode. As I cover multiple topics, this will help viewers navigate to pieces of interest. I'll be starting on this process (slowly) for each episode. You can help by leaving a comment with time tags for your favorite old episode. Do you have any other suggests for improving this show? Let me know in the comments!

See you live! (stream, time)

Episode 18 - Tree Traversal Trickery

Try these problems:

• Family Fortune
• Knapsack

Last week, I mentioned I would be running this episode on Wednesday due to travelling to the TCO regional event in Austin. It turns out there is an SRM at this time! So this week's episode will take place a day later.

In this episode, I will cover a handful of tricks involving preorder and postorder numbers on trees and some neat properties involving them. I'll also discuss two different approaches for solving the problems linked above.

See you live! (stream, time)

Episode 17 - Binary Lifting

Try these problems:

• https://open.kattis.com/problems/tourists
• http://codeforces.com/contest/519/problem/E
• https://www.codechef.com/problems/DRAGONST

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)

Episode 16 - Ski Resort

NAIPC 2017 took place this weekend as well as the Open Cup version (GP of America). I'm hoping many of you enjoyed the problems and found them interesting. The set was challenging for many teams. You can find the official standings to each contest here:

• https://naipc17.kattis.com/standings
• http://opentrains.snarknews.info/~ejudge/res/res10376

MIT won NAIPC solving 10 problems. On the Open Cup side, Tsinghua University impressively solved all 11 problems towards their victory! ITMO also had a strong performance. Well done! It should be an exciting ICPC World Finals in a few weeks.

In this week's episode, I will be covering a solution to the toughest problem from this contest. Only Tsinghua University managed to solve it in both contests. You can find the problem here:
https://open.kattis.com/problems/skiresort

Dominator trees seem to be trendy in competitive programming at the moment. This problem appears to play the part. Yet there is a solution to this problem that makes no use of dominator trees! Still, this problem is a good excuse to explain dominator trees and how to construct them simply for directed acyclic graphs. There are also a few other tricks and observations needed to solve this problem.

See you live! (stream, channel)

Episode 15 - Split the Sequence

At the start of last week's episode, I mentioned my decision to split the episode in two. The last problem, Split the Sequence, is beautiful and I felt it deserved its own episode.

I highly recommend you try the problem yourself if you haven't already:

• Problem B: Split the Sequence

This week's episode we will systematically move through the solution, approaching faster and faster runtimes, as we make observations about the problem structure. See if you can spot the greedy property you need to solve the problem. We'll be discussing the proof of this property using the exchange argument technique from last week's episode.

See you live! (time, stream)