Friday, March 10, 2017

Episode 11 - Convex Hull Optimization

This week will cover the solutions to these problems:

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:

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

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;

2 comments:

  1. Hi Matt! Where can I get inputs for Machine Works? I have found the problem at icpcarchive but with no inputs.

    ReplyDelete
    Replies
    1. This page has the 2011 data: https://icpc.baylor.edu/worldfinals/problems

      Delete