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)

1 comment:

  1. I think this is similar to the 0/1 knapsack problem if it is like 0/1 knapsack problem then why we are using greedy approach we should solve it like 0/1 knapsack using DP.
    If it is different from 0/1 knapsack then why we are using DP to solve it because we have computed the optimal order then we should simply calculate the maximum reward by considering that no problem has more required time than total duration and reward should not be negative.
    Please correct me if I am wrong.