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;

7 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
  2. This comment has been removed by the author.

    ReplyDelete
  3. Can you provide us with the codes used during the live stream?

    ReplyDelete
  4. EFFECTIVE LOVE SPELL TO GET EX HUSBAND/BOYFRIEND OR EX WIFE/GIRLFRIEND AND CURE HERPES AND INFERTILITY THAT WORKS WITHIN 24 HOURS.

     Contact Dr. Odunga at odungaspelltemple@gmail.com OR Whats App/CALL +2348167159012

    I got my ex husband back to me and also got fertile and gave birth to twin girls after 12 years of marriage.
    When I came online last year, I saw a testimony about Doctor ODUNGA and how he has been helping people with marriage issues and I decided to contact him. We spoke on email at odungaspelltemple@gmail.com and later he gave me his WhatsApp number which is +2348167159012. He assured me he would help me get my ex husband back after 3 years of no contact. Doctor Odunga is the best spell caster I must say. My husband called me after 24 hours of contact. The third day, I received natural herbs for fertility and after using it, I became fertile and conceived. I and my husband reconnected, had sex and I was pregnant. Presently I am happy to say I am the mother of twin girls and this is ALL THANKS TO DOCTOR ODUNGA. I came online to say this If you need help, I believe you are saved with this man.  

    Contact his email at odungaspelltemple@gmail.com

     OR Whats App/Call +2348167159012 and you too will give a testimony too to help others

    ReplyDelete
  5. A GREAT SPELL CASTER (DR. EMU) THAT HELP ME BRING BACK MY EX GIRLFRIEND.
    Am so happy to testify about a great spell caster that helped me when all hope was lost for me to unite with my ex-girlfriend that I love so much. I had a girlfriend that love me so much but something terrible happen to our relationship one afternoon when her friend that was always trying to get to me was trying to force me to make love to her just because she was been jealous of her friend that i was dating and on the scene my girlfriend just walk in and she thought we had something special doing together, i tried to explain things to her that her friend always do this whenever she is not with me and i always refuse her but i never told her because i did not want the both of them to be enemies to each other but she never believed me. She broke up with me and I tried times without numbers to make her believe me but she never believed me until one day i heard about the DR. EMU and I emailed him and he replied to me so kindly and helped me get back my lovely relationship that was already gone for two months.
    Email him at: Emutemple@gmail.com  
    Call or Whats-app him: +2347012841542

    ReplyDelete
  6. Hi viewers, I'm posting this Because i found lots of people having marriage problems which I also experienced. I recently found help from a man called Dr. Oselumen he did a great job that made my man fell back in love with me again after ten months of separation. I want you to know there are fake online spell Dr .s if someone out there needs help, can email this great spell caster, droselumen@gmail. com check or connect with him on WhatsApp +2348054265852. He will give you the best result. 
    CONTACT HIM FOR ANY KIND OF HELP,MONEY SPELL,LOTTERY SPELL,PREGNANCY SPELL,DIVORCE SPELL,SPELL TO STOP COURT CASE AND WIN ANY COURT PROBLEM,DEATH SPELL,BUSINESS SPELL,HEALING SPELL,SPELL TO REMOVE BLACK MAGIC OUT FROM YOUR LIFE,FAMILY AND MARRIAGE PROBLEM.

    ReplyDelete