Friday, March 31, 2017

Episode 14 - Exchange Arguments

Give these problems a try:

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)

No comments:

Post a Comment