Wednesday, July 26, 2017

Episode 28 - Sparse Tables and LCA

In this week's episode, I will be discussing the relationship between the lowest common ancestor problem of a rooted tree and range minimum query. Tree traversals can be saved as a sequence and the idea is the foundation behind Euler tour trees. This idea is also how you relate lowest common ancestor queries to range minimum query.

Though segment trees are a nice solution to range minimum query, I'll be coding the sparse table solution, which is closely related to the binary lifting technique. This gives another lens to view this problem through. Sparse table has the added benefits of an O(1) query.

On the personal life side of things, I had some issues where my PhD adviser backed out of moving to the university I was planning to attend this fall. This is what caused the scheduling issue for the episode a few weeks ago. I've decided to go back into industry and am looking for jobs and staying with friends over the next few weeks. What this means for Algorithms Live! is episodes will be at strange times for a bit. I'll try to run at least one episode a week with less notice until my life balances back out. Thank you for being understanding!

See you live! (stream, channel)

Sunday, July 23, 2017

Episode 27 - Topological Sort and Kosaraju's Algorithm

Today is a surprise bonus episode of Algorithms Live! If viewers recall, I missed an episode due to some scheduling problems a few weeks ago. This episode will make up for that.

In this episode, I will cover two techniques that relate well to each other. In the first half of the episode, I will discuss two methods for finding the topological sort of a graph. In the second half, I will cover Kosaraju's algorithm for finding strongly connected components.

See you live! (streamtime)

Friday, July 21, 2017

Episode 26 - Fibonacci Machine

This week's episode will cover the solution to an old segment tree problem I enjoy:

In episode 4, I covered segment trees. This problem requires a segment tree modified for an interesting purpose. I truly love Polish problems and this problem is a nice augmented segment tree problem. I recommend giving it a try before seeing the solution.

See you live! (stream, time)

Saturday, July 15, 2017

Episode 25 - Desert Wind

One of the viewers, Mikhail Goncharov, has happily contributed time links to an old episode of algorithms live. You can see the links in the description of the knapsack episode. It is now way easier to navigate the episode to find a useful subtopic being discussed. This expanded description also gives a nice outline so you get an overview of an old episode. Thank you so much! If anyone else would like to contribute similar time links, just send me an overview of the episode in this form (either PM through Codeforces or YouTube):

00:00 Introduction
03:23 Technique 1
5:31 Problem Name
13:21 Technique 2
14:30 Coding

I really appreciate this type of contribution. If you can contribute to even one episode, please do!

In this week's episode, I will be discussing an old problem that I find interesting, Desert Wind. You can the problem statement here:

The episode should be a bit shorter than usual but I hope you will all still enjoy it. I should be done right before the start of this week's Codeforces Educational Round.

See you live! (time, stream)

Friday, July 7, 2017

Episode 24 - 2SAT

Sadly, due to some personal matters, I had trouble scheduling a time for last week's episode. So I'll be running that episode tonight. I'll make a surprise bonus episode sometime in the future to make up for it.

This week's episode will cover 2SAT (2-satisfiability). You can attempt these problems:

This topic is a bit tricky to explain depending on your background and knowledge base. To make things a bit easier, I'll be using concepts taught in the first chapter of Rosen's Discrete Mathematics. I'll be aligning with the notation and assume some basic familiarity with propositional logic and deductions.

The goals of this episode are to demonstrate how to make 2SAT problems easier to implement, pull the answer out, find the lexicographically first answer, and discuss the problem's relationship to strongly connected components.

See you live! (time, stream)

Thursday, June 22, 2017

Episode 23 - Strongly Connected Components

This week's episode will expand upon the technique involving low links to directed graphs. The result is Tarjan's strongly connected components algorithm. I'll be addressing how to extract these components and some additional helpful properties that are implicit to the algorithm.

Here are a few problems you can try solving involving SCC's:
See you live! (time, stream)

Friday, June 16, 2017

Episode 22 - Biconnected Decompositions

In this week's episode I will be discussing the types of meta-graphs that can be formed from 2-edge-connected and 2-vertex-connected components.

Here are a few problems that are relevant to this technique:

I will only be discussing a subset of these problems. You may find the others useful to solve on your own to practice this technique.

See you live! (time, stream)

Saturday, June 10, 2017

Episode 21 - DFS Lowlink

Algorithms Live! is returns! Both the ICPC World Finals and USACO camp were excellent. Thank you to anyone who reached out and said hello at WF. It was fun meeting some of you and I received many great suggestions for improving the show. Meeting USACO campers was exciting as well. I'm happy to see these videos are relevant and useful for IOI training. It was a blast hanging out and discussing problems/techniques while writing as many challenging cow themed problems as possible.

Now it is time to resume making episodes. This week, I will be exploring some useful techniques for modifying depth first search on undirected graphs. This will allow us to extract articulation points, bridges, and 2-vertex/edge connected components, efficiently. I'll also be going over some tricks for making theses techniques more resilient to parallel edges and self-loops. Better yet, I'll implement these techniques. :)

I'll be expanding on different uses for this technique and some neat problems related to them in future weeks.

See you live! (time, stream)

Wednesday, May 17, 2017

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! :)

Friday, May 12, 2017

Episode 20 - Bitmask Dynamic Programming

Here are some problems related to this week's episode:
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)

Saturday, May 6, 2017

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:

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:

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)

Wednesday, April 26, 2017

Episode 18 - Tree Traversal Trickery

Try these problems:

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)

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)

Sunday, April 16, 2017

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:

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:

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)

Friday, April 7, 2017

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:

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)

Friday, March 31, 2017

Episode 14 - Exchange Arguments

Give these problems a try:

Often competitive programmers will attempt to guess the greedy properties of the problems they are trying to solve. They will then code the solution and will be satisfied if the solution passes the data. But is there a way to tell if your greedy assumption is correct before you code it?

In this week's episode, I will be discussing one such technique called the exchange argument. This is a way to prove the correctness of a greedy property on a solution. Often this technique can show that some manner of sorting is always optimal. Did you know this argument can also be used to derive the correct sorting property? I'll also be presenting a few properties that are not sorting but use the exchange argument.

The episode will conclude with a discussion of one of my favorite problems: Split the Sequence from APIO 2014. Maxim Akhmedov wrote a truly beautiful problem here and I highly recommend you try solving it before the episode.

See you live! (time, stream)

Thursday, March 23, 2017

Episode 13 - YATP

Try solving this problem:

This week's episode will see the return of Lewin Gan, the author of this problem. We'll be discussing the solution to this problem in detail. This problem was the toughest problem in last year's NAIPC. It combines both techniques covered the last two weeks, convex hull optimization and divide and conquer on trees.

Lewin and I used different approaches to solve this problem. You can find both solutions here: We'll be discussing both ideas in detail.

I recommend watching the previous two episodes before this week's episode:

See you live! (time, stream)

Saturday, March 18, 2017

Episode 12 - Divide and Conquer on Trees

Try solving these problems:

This week's episode will cover divide and conquer on trees (centroid decomposition).

See you live! (time, stream)

Friday, March 10, 2017

Episode 11 - Convex Hull Optimization

This week will cover the solutions to these problems:

This week's episode focuses on the technique of convex hull optimization. We'll be viewing the technique through the lens of solution bags so I recommend watching episode 9 if you haven't already. I'll be live coding solutions to both problems. Expect a longer than usual episode!

This technique can also be combined with other techniques to solve more interesting problems. Here are a few examples:

We can also generalize the technique to different classes of functions:

The motivation, for viewing the technique through the lens of solution bags, is to make it easier to see these generalizations. Instead of a specific black box pattern, we will see this technique as a special case of solution bags.

See you live! (time, stream)

Update: At the end of the episode there was a bug in the code for the second problem. It turned out to be a pesky backwards inequality and a one character fix.

Here is the broken line (line 72):
if (above != null && below != null && <=

Here is the correct line:
if (above != null && below != null && >=

Thursday, March 2, 2017

Episode 10 - Pitcher Pouring

Give these problems a try:

This week's episode will extend the idea for solution bags to pitcher pouring algorithms. This technique leverages two data structures in tandem to efficiently solve problems.

See you live! (time, stream, channel)

Thursday, February 23, 2017

Episode 9 - Solution Bags

Give these problems a try:

This week's episode of Algorithms Live! will cover solution bags. This is less of an algorithm or data structure and instead a different way of thinking of problems involving data structures. You can also view it as a different approach to dynamic programming that naturally yields itself to data structure optimizations.

During the discussion, I'll be going over maintaining an invariant on a data structure and how this can make basic data structures more powerful. My goal will be to change your way of thinking about data structure problems. Instead of guessing of what data structures might be relevant, we will list what our data structure needs to do and design our data structure from there. The data structure will reveal itself naturally from this analysis. I find this technique leads to simpler data structures.

Consider this problem:

Many solvers during this contest used segment trees, but a simple solution using only an ordered set (TreeSet in Java, multiset in C++) also exists. Finding solutions using this type of simple data structure will be easier after learning this way of thinking.

Also during this episode, I will discuss the min queues and their relationship with maintaining an invariant on a data structure. Using this data structure, we will solve the problem of finding the diameter of an almost tree.

See you live! (time, stream, channel)

Other news: This Saturday UCF will compete in this joint north american practice: The practice is open to anyone to join. I'll be competing as UCF Death Valley.

Thursday, February 16, 2017

Episodes 7 and 8 - Steiner Trees and AtCoder

This weekend will feature two Algorithms Live! episodes. This will hopefully make up for last week's technical difficulties.

Episode 7 will take place tomorrow and cover Steiner Trees. I'll be covering the solution idea to Ticket to Ride from NWERC 2006. You can find the problem here:

SPOJ also has the problem if you would like to try it:

I'll be discussing two approaches for solving Steiner Tree problems for different bounds and some optimizations for making the approaches faster. I'll also live code the solution to Ticket to Ride.

Here is the info for the new Episode 7: (time, stream, channel)

On Sunday, Makoto Soejima will join Algorithms Live! to make up last week's episode. This episode will now be Episode 8. He will answer many of your posted questions, discuss AtCoder, and discuss the problem "90 and 270". You can find more information about the episode in the previous post.

Here is the info for Episode 8: (time, stream, channel)

See you live!

Sunday, February 12, 2017

Technical Difficulties with Episode 7

Makoto and I are very sorry to have to cancel this week's episode. We attempted to load Google Hangouts for the YouTube live stream. Unfortunately, the stream loading was stuck on 99% and the Start Broadcast button never appeared.

This is the first time this error has happened for me. As I write this post, the start broadcast button now loads. I believe the bug has something to do with rescheduling the live stream to before our initial broadcast time but it could be a number of things. If you saw the Codeforces update, we rescheduled the broadcast to an hour earlier to avoid conflicts with CS Academy Round #18. The button loaded after our original time passed. I've also read up on potential workarounds if this problem occurs in the future.

So here is my plan for this week. I will run my usual episode of Algorithms Live! on Friday this week to see if the technical problems are corrected. Then on Sunday I will run the AtCoder episode with Makoto. I'll update this blog later in the week with more details.

See you all next week!

Thursday, February 9, 2017

Episode 7 - AtCoder

*Please note that this week’s episode of Algorithms Live! will take place at a special day and time.

This week’s episode will feature a special guest, Makoto Soejima, the author of the above problem. Makoto was the Topcoder SRM Coordinator from 2011-2015. He is currently the admin of AtCoder. Makoto is a three time TCO champion (2010, 2011, 2016). Makoto was also the Google Code Jam champion in 2011. He represented University of Tokyo at ACM ICPC World Finals in 2013 (St. Petersburg, Russia)  and 2015 (Marrakesh, Morocco); placing 3rd each time and earning a gold medal. He recently started a blog on competitive programming that I’m sure many of you will be interested in reading. (If you are not already reading.) Makoto is also my favorite problem writer. He regularly writes creative and interesting problems for programming contests. It will be very exciting to have him on the show!

This week we will be discussing AtCoder, his experience as a Topcoder admin, and problem writing. We will also discuss his problem 90 and 270. If you have questions for Makoto that you would like to have answered on the show, please leave them as comments.

See you live! (time, stream, channel)

Thursday, February 2, 2017

Episode 6 - USACO Dec '16

Try solving these two problems:

Both these problems are interesting, but I find the editorials are troublesome to understand. My view is the editorials for these problems aren't bad, but these problems are easier to explain through a whiteboard and talking. This is why I've chosen to review them. Both are beautiful problems and should be quite fun to discuss. If you competed in USACO recently, you may have an interest in knowing how they are solved and should watch this episode!

I've received many comments on what should be covered in future weeks. I'd like to talk about a few of these ideas and how I plan to cover them. One request was for the technique "convex hull optimization". This is a fun advanced technique in competitive programming. I'll be spending multiple weeks to build up to this technique and cover several interesting problems that can be solved using it. I'll also discuss a more general technique for reasoning about a class of problem that includes "convex hull optimization".

I received a few suggestions to cover treaps. This is great because I love treaps! Any binary search trees that can be split in O(log n) time results in a malleable data structure much more flexible than segment trees. I also want to discuss splay trees as an alternative to treaps. Curbing the excitement, I'll be delaying these episodes for a bit. The reason is I want to follow these episodes with episodes on link-cut trees and euler tour trees.

There were also requests to cover suffix arrays, flow problems, 2D segment trees, centroid decomposition, and many more. I'll be delighted to cover all those things. Of course, I'll be peppering in a few weeks just covering problems I find interesting to keep variation. Future weeks will also have more guests! The guest episodes will focus on problems or techniques the guests will like to cover. It should be an interesting next few months. :)

See you live! (time, stream, channel)

Thursday, January 26, 2017

Episode 5 - Geometric Sweeps

Exciting news! Algorithms Live! is now eligible for a custom URL:

A special thank you to everyone that subscribed and viewed episodes to make this possible!

This week's episode will feature a special guest, Lewin Gan. Lewin writes problems regularly for Topcoder, Codeforces, and USACO. He is also judge and problem writer for the ICPC contests: NAIPC and Pacific Northwest Regional Contest. He was also an ICPC World Finalist in 2014 competing for University of California, Berkeley.

We will be discussing geometric sweeps. During the discussion, we will cover solutions for two of Lewin's interesting problems and a solution for a problem I set for NAIPC'15. We'll also take a segue into inversive geometry as an alternative method to solving one of his problems.

You can view all of Lewin's Topcoder problems here and Codeforces problems here. I'm sure you will find several of his problems interesting.

Here are the problems we will be discussing and a few more using related techniques:

See you live! (time, stream, channel)

Update: Lewin wanted to pass on the discussion of the O(log log P) optimization for the binary search in Hongcow Draws a Circle. You can find that here.

Thursday, January 19, 2017

Episode 4 - Segment Trees

By popular request, this week's episode will cover segment trees. This data structure is a bit of a strange one. When I first learned them, the structure was referred to as an interval tree. Academic literature has a very different data structure called interval tree. Later on, I heard the data structure referred to as segment tree, but once again theoretical computer science has a different data structure called segment tree. The Croatian Open Competition in Informatics (COCI) refers to them as a tournament tree, but this name is also a bit misleading. Despite the confusion on the name, this data structure technique is extremely useful and flexible in competitive programming.

I recommend reviewing the merge sort algorithm before viewing this episode as the structure of segment tree closely mirrors the structure of merge sort's recursion. I'll be thorough in both the theoretical and implementation basics of this wonderful data structure.

See you live! (time, stream, channel)

Thursday, January 12, 2017

Episode 3 - Rolling Hashes and Bloom Filters

For this week, you should try this problem:

In Episode 3, I will cover the natural marriage of two ideas: rolling hashes and bloom filters. I'll be covering the idea behind the rolling hash technique, how Rabin-Karp works using this technique, and how the hashes can be stored in a bloom filter. I'll also show how a bloom filter is faster in practice than using the usual hash table when storing string hashes.

See you live! (time, stream, channel)

Thursday, January 5, 2017

Episode 2 - Fancy Antiques

Try solving this problem.

This week's episode will feature our first guest, Deon Nicholas. Deon is an ICPC World Finalist from the University of Waterloo placing 13th in 2015. He is also a judge for NAIPC and the author of "Fancy Antiques", the problem we will cover this week.

This problem is particularly interesting to me. Despite being solved by only two teams, it has a remarkably simple solution. Moreover, the analysis of why the solution works, and is efficient, is beautiful. I believe such techniques are not well known given the low solve rate and should make for an interesting discussion. We'll be discussing the problem in detail, techniques for solving the problem more efficiently than the bounds require, and ideas for attacking similar problems. We'll also discuss an alternative solution by another judge from the contest, Lewin Gan.

This is our first week in the talk show format. Over the next few weeks, I hope to have many more guests. If you would like to see someone in particular on the show, please give their name in the comments. :)

See you live! (time, streamchannel)

Edit: For those interested in implementations of the discussed solutions, they can be found on David Van Brackle's judging blog: