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)