Episode 14 - Exchange Arguments

Give these problems a try:

• Minimum Scalar Product
• TheProgrammingContestDivOne
• Problem B: Split the Sequence

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)

Episode 13 - YATP

Try solving this problem:

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

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: http://serjudging.vanb.org/?p=924. We'll be discussing both ideas in detail.

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

• https://www.youtube.com/watch?v=OrH2ah4ylv4
• https://www.youtube.com/watch?v=3pk02p1-weU

See you live! (time, stream)

Episode 12 - Divide and Conquer on Trees

Try solving these problems:

• http://www.usaco.org/index.php?page=viewproblem2&cpid=286
• https://www.codechef.com/problems/TESTERS 
• http://www.ioi2011.or.th/hsc/tasks/EN/race.pdf

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

See you live! (time, stream)

Episode 11 - Convex Hull Optimization

This week will cover the solutions to these problems:

• Covered Walkway
• Machine Works (Problem F)

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:

• Yet Another Tree Problem
• Problem B: Split the Sequence

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

• Jewel Thief

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 && below.to(part) <= part.to(above))
   continue;

Here is the correct line:
if (above != null && below != null && below.to(part) >= part.to(above))
   continue;

Episode 10 - Pitcher Pouring

Give these problems a try:

• Estimation
• Billboard

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)

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!