Episode 5 - Geometric Sweeps

Exciting news! Algorithms Live! is now eligible for a custom URL:
https://www.youtube.com/c/AlgorithmsLive

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:

• Segment Cutting
• Hongcow Draws a Circle
• Area of Effect
• Logging
• Cell Phone

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.

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)

Episode 3 - Rolling Hashes and Bloom Filters

For this week, you should try this problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1370

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)

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, stream, channel)

Edit: For those interested in implementations of the discussed solutions, they can be found on David Van Brackle's judging blog: http://serjudging.vanb.org/?p=924.