Episode 39 - String Concatenation

This week's episode of Algorithms Live! features David Harmeyer (SecondThread). In this episode, we discuss his problem String Concatenation from Facebook Hacker Cup 2021 Round 2. We recorded the video over the weekend and will be premiering the video on YouTube this week. During the premier both David and I will be available on the chat to answer any questions.

See you there!

Episode 37 - Venture Cup

This week's episode of Algorithms Live! features the return of scott_wu. In the episode we discuss his involvement in Venture Cup, the interest of venture capitalists and tech companies in competitive programming, his work as a commentator for this year's Topcoder Open, the relationship of esports to competitive programming, and the problem 626F - Group Projects from the first Venture Cup. Most of the episode is podcast style, so I've included time links in advance to make it is easier to navigate to parts of the discussion that interest you. :)

The episode is available at this link. Enjoy!

Episode 36 - El Toll Caves

This week's episode features Mikhail Tikhomirov (Endagorion). You may know Mikhail from his many problems in Codeforces or other online judges. He has been a finalist of TCO and Google Code Jam and helped host the Barcelona Programming Bootcamp. Mikhail is an ICPC coach for Moscow Institute of Physics & Technology. His teams have earned two gold medals and a silver medal at ACM ICPC World Finals in the past few years. He also has a YouTube channel where he regularly post screencasts.

In this episode we will be discussing his problem El Toll Caves from the Barcelona Bootcamp. This is a math intensive problem with close relationship to the Euclidean algorithm.

If you have any questions for Mikhail, please leave comments on this post with the question or ask the question live during the stream.

See you live! (episode)

Episode 35 - Looking for a Challenge?

This week's episode features Tomasz Idziaszek as a special guest. Tomasz was an ICPC World Finalist from 2005 and a TCO Finalist from 2004-2005. He is an author of over 100 problems, including many hard and interesting problems from Algorithmic Engagements. He was an editor for the polish educational magazine Delta and the famous competitive programming book "Looking for a Challenge?". In 2018 he was a problem setter for the IOI. He also maintains the website http://www.algonotes.com/ that offers interesting educational materials on advanced algorithms.

In this episode we discuss the history behind "Looking for a Challenge?" and his famous problem Termites, which was included in the book. This problem is truly beautiful and I hope many of you will enjoy the episode.

Update: Anyone interested in the getting a copy of the Looking for a Challenge book can find information in this blog post. You can also solve the recommended Woodworms task by seeing the problem statement at this link and on an online judge in this link.

Episode 34 - Educational Streaming w/ Errichto

This week's episode will feature Errichto and will take place on Sunday, December 16th. If you are interested in viewing the live stream, you can find the link here or view the video after the stream following the same link.

Many of you know Errichto as a prolific problem writer and his recent appearances in TCO, Google Code Jam, Facebook Hacker Cup, and many other programming contest finals. He represented the University of Warsaw in the 2018 ACM ICPC World Finals, where his team placed 14th. This year he started an educational stream for competitive programming that is growing in popularity.

In this episode, we will discuss the benefits of educational streaming in competitive programming and ideas for making competitive programming more popular. Topics will include: how programming contests relate to e-sports, broadcasts for programming competition finals and how they can be improved, and algorithms videos on YouTube and what we would like to see in the future for popularizing the sport. I think this will be a fun podcast style stream. Please ask questions on this post for ideas that you would like to see discussed.

As with all Algorithms Live! episodes, we will be discussing an interesting algorithmic programming challenge. In this episode, we will discuss Errichto's problem Disjoint Triangles. As build up to this problem, we will also be discussing Interstellar Battle from Bubble Cup earlier this year. This is sure to be an exciting episode with many interesting topics and ideas.

See you live!

Episode 33 - Maximum Flow Intuition

During September I attended the IOI as the USA team's deputy leader. The event was lots of fun and I met many new friends, some of which will be future episode guests. While attending I also presented my paper on Tidal Flow, an algorithm I invented while training for ICPC contests. The paper also served as an extensive study on maximum flow algorithms. During testing I implemented many new flow algorithms and decided it would be fun to share some of these algorithms in an extended flow series.

The first episode of this series is now available here. I'll be going over terminology, proofs, algorithms, and patterns as the series expands. There is much to talk about. I'll be interspersing the episodes with some guest episodes I've been planning. Hopefully this variety will keep the episodes exciting for all viewers.

In other news, I've received many requests to start a GitHub repository to store all of the code I write during episodes. Such a repository is now available here.

Episode 32 - Fracturing Search

It has been several months since I've created an episode of Algorithms Live! but I'm excited to restart the show. I'll be making some changes to the format of the show that I'm hoping some of you will really like. Before I get into all of that I want to share some personal updates and explain what I've been doing the past few months.

Sadly, things did not work out with drive.ai. I enjoyed the experience, met many interesting people, and learned a great many things. Not working while in the bay area is terrifying so I had to dedicate most of my time figuring out how to leave the bay area and setting up my next life steps.

During the last few months, I worked on making videos for Interview Kickstart. This has been interesting because I started to think about how I could change the format of Algorithms Live! so that it is more useful using some of the ideas from making IK videos. One difficulty in running the show is finding a guaranteed quiet place to schedule a live episode. When I originally ran the show, I would run the episodes late at night in my office at UCF. Not having a dedicated quiet office has hurt running the show live. So I've decided to run more polished pre-recorded episodes as an experiment. Let me know what you think of the new format!

So now on to more exciting and fun news. The first is I'll be attending the IOI this year as USA's deputy leader. So if you are attending IOI, please say hi! I'll also be presenting a paper on Tidal Flow this year at the IOI Conference (journal, paper). Tidal Flow is a maximum flow algorithm I invented while training for the ICPC World Finals in 2012. My team wanted an iterative fast flow algorithm that was also easy to implement and understand. The result was the Tidal Flow algorithm. I taught this technique, along with many other fast flow algorithms, while training teams at UCF for many years and the algorithm enjoyed popular usage among our teams. If you decide to read the paper or use the algorithm, I'd be interested to know what you think of it.

Earlier this summer, I helped coach at the USACO training camp. One problem I set during the camp was an enumeration problem. The problem is given a weighted graph, print the cost of the kth smallest spanning tree (where n <= 50, m <= (n choose 2), k <= 10,000). Give this problem a try. Can you get something that runs efficiently on random, fully connected graphs? After the contest I presented the concept of fracturing search as a method for solving this type of enumeration problem. The technique is generally applicable, and many of the USACO finalists found it interesting. The idea is based off Murty's assignment ranking algorithm (paper, altlink). There is even an paper that solve this same problem using the technique (paper). So I've decided to turn this technique and problem into an episode. I hope you enjoy the idea as much as I do.

So here is episode 32 (episode). I'd love to hear thoughts of the episode and the new format. Is this format better? What should be changed? I have many more episodes planned and will be releasing them regularly following this year's IOI.

Episode 31 - Orchestra

This week's episode will feature a special guest, Scott Wu. Scott is the top ranked Codeforces member in the US. He helped Harvard earn a gold medal in ICPC World Finals 2016. He also achieved three gold medals at the IOI 2012-2014, achieving a perfect score in 2014.

We will be discussing his problem, Orchestra, from 8VC Venture Cup 2016. We'll be taking a deep dive into this problem and learning several tricks to bringing the runtime down gradually. If you have any questions you would like answered by Scott in the broadcast, please leave them in the comments on this post!

See you live! (time, stream)

Episode 30 - Treaps

This week's episode will cover the treaps. The main advantage of treaps is an easy to implement binary search tree data structure. I'll be discussing why I think they are a useful data structure and a handful of useful tricks that make them more powerful than segment trees.

Here are some useful notes for learning more about treaps:

• Jeff Erickson's treap notes
• Proving depth of a treap
• Randomized Reduction Lemma

See you live! (time, stream)

Episode 29 - Rainbow Roads

I'm happy to announce Algorithms Live! will be returning tomorrow! I'm sorry to have been away for so long. With the amount of travel, reading and preparations for some research ideas, working on ICPC contests, and wanting to focus on my job search, it was difficult to reliably schedule episodes. Plans for the future of this show are exciting. I used some of this time to map out where I wanted these episodes to go. A few of the episodes are based on your requests.

So now for big changes! I recently started a new job at drive.ai working as a simulation engineer. For those that don't know, my research background is in simulation and training in virtual environments. I'm happy to be applying some of this knowledge to self-driving cars and happy that drive.ai is supportive of me continuing to run Algorithms Live!

The other piece of exciting news is I moved to California. I've finally met Lewin in person and hopefully will meet many other competitive programmers in the bay area and have them on the show. :)

Being in California allowed me to finally attend one of Donald Knuth's Christmas lectures in person. Many of you will remember my Christmas tree lecture from last year. This year was a bit different. Donald gave an exploratory lecture where he demonstrated the excitement of diving deep down rabbit holes while doing research and some combinatorial geometry. It was exciting and humorous but oddly enough, the lecture was not about trees!

I'm going to rectify this dilemma, as it wouldn't be Christmas without talking about one of my favorite classes of graphs. This week's episode will once again feature Lewin Gan. We will discuss his ACM ICPC problem "Rainbow Roads" that was used in several regions in the US. You can try the problem by solving one of the following regionals in Codeforces gym:

• South East USA Regional Contest
• Pacific Northwest Regional Contest

This will be my last episode of 2017 to ease back into things. I'll be going on holiday break this week, but will start running regular weekly episodes at the start of 2018. I've missed running this show and hope that many of you will like the future episodes to come!

See you live! (stream, time)

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)

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! (stream, time)

Episode 26 - Fibonacci Machine

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

• Fibonacci Machine

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)

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:

• Desert Wind

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)

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:

• ICPC Pacific Northwest 2016 (Illumination)
• Piece It Together
• Palindromic DNA
• Beaming with Joy

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)

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:

• Proving Equivalences
• Field Plan

See you live! (time, stream)

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:

• Mining Your Own Business
• It Takes a Village
• Lucky Cities
• Unique Path

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)

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)

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)