Episode 9 - Solution Bags

Give these problems a try:

• Minimum Subarray Length
• Generic Cow Protests (data: http://contest.usaco.org/FEB11.htm)

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: https://open.kattis.com/problems/whiteboard

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: https://open.kattis.com/contests/naipc17-p02. The practice is open to anyone to join. I'll be competing as UCF Death Valley.

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: http://www.csc.kth.se/contest/nwerc/2006/problems/nwerc06.pdf

SPOJ also has the problem if you would like to try it: http://www.spoj.com/problems/TICKET/

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!

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!

Episode 7 - AtCoder

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

Give this problem a try: http://cf16-exhibition-final.contest.atcoder.jp/tasks/cf16_exhibition_final_i

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 3^rd 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)

Episode 6 - USACO Dec '16

Try solving these two problems:

• http://www.usaco.org/index.php?page=viewproblem2&cpid=671
• http://www.usaco.org/index.php?page=viewproblem2&cpid=674

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)