Episode 16 - Ski Resort

NAIPC 2017 took place this weekend as well as the Open Cup version (GP of America). I'm hoping many of you enjoyed the problems and found them interesting. The set was challenging for many teams. You can find the official standings to each contest here:

• https://naipc17.kattis.com/standings
• http://opentrains.snarknews.info/~ejudge/res/res10376

MIT won NAIPC solving 10 problems. On the Open Cup side, Tsinghua University impressively solved all 11 problems towards their victory! ITMO also had a strong performance. Well done! It should be an exciting ICPC World Finals in a few weeks.

In this week's episode, I will be covering a solution to the toughest problem from this contest. Only Tsinghua University managed to solve it in both contests. You can find the problem here:
https://open.kattis.com/problems/skiresort

Dominator trees seem to be trendy in competitive programming at the moment. This problem appears to play the part. Yet there is a solution to this problem that makes no use of dominator trees! Still, this problem is a good excuse to explain dominator trees and how to construct them simply for directed acyclic graphs. There are also a few other tricks and observations needed to solve this problem.

See you live! (stream, channel)

Episode 15 - Split the Sequence

At the start of last week's episode, I mentioned my decision to split the episode in two. The last problem, Split the Sequence, is beautiful and I felt it deserved its own episode.

I highly recommend you try the problem yourself if you haven't already:

• Problem B: Split the Sequence

This week's episode we will systematically move through the solution, approaching faster and faster runtimes, as we make observations about the problem structure. See if you can spot the greedy property you need to solve the problem. We'll be discussing the proof of this property using the exchange argument technique from last week's episode.

See you live! (time, stream)

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)