Saturday, May 6, 2017

Episode 19 - Knapsack

This week's episode will cover knapsack and subset sum. I'll be going over some of the basics of the pseudo-polynomial time algorithm and some of the variants. Gradually, I'll move into more complex variants and related techniques before ending with the solution to this problem:

I recommend attempting the above problem. Even though it is knapsack (which is generally considered simple), the problem is quite tough. I hope this episode has something interesting for everyone!

As I'm the author of this problem, I'll be running through how I came up with the problem and some of the tricks I learned from other problems that became relevant to the solution. I hope you will find this episode a very thorough treatment of knapsack and subset sum in general.

Here is another difficult problem related to subset sum you should be able to solve after this episode:

In other news, I participated in the TCO regional event in Austin last weekend. It was great to meet many new friends. Some even watch this show! Overall, it was a fun event and I recommend attending any TCO event in the future. For this contest, I employed a new strategy of listening to a waterfall during the contest to help me focus. Do you have a special technique for focusing during contests?

Tomorrow will be the regional event at ITMO in St. Petersburg. I'm sure many top competitors will be attending. Check it out if you live near there! It seems there will be a mirror of this contest online. :)

I'm also looking to make Algorithms Live! more useful. Some viewers have requested written versions of each episode. Unfortunately, I don't have enough time to convert each episode into a written version. If any viewers are up for the task, it would be extremely helpful. :) I'd be happy to send my notes and code written during the episode. Please contact me on Codeforces if this sounds interesting to you.

Another suggestion was to include time tags in the video description for specific topics in each episode. As I cover multiple topics, this will help viewers navigate to pieces of interest. I'll be starting on this process (slowly) for each episode. You can help by leaving a comment with time tags for your favorite old episode. Do you have any other suggests for improving this show? Let me know in the comments!

See you live! (stream, time)

11 comments:

  1. Hi, Matt! Do you have a sample solution or test cases for "jewel thief"? I am struggling with TLE at kattis TT

    ReplyDelete
    Replies
    1. http://serjudging.vanb.org/?p=924

      Delete
    2. AC! so the secret was to cache "time overtakes" value instead of doing binary search all over again when adding new partial solution in "the bag". That only affects constant in O() but my timing was 6.8 out of 8 second so it was a deal breaker.
      I see that there are solutions (also in c++) AC around one second time and wonder: is there another approach to this problem?

      Delete
    3. My Java solution is much faster than that (or should be). Perhaps your implementation is doing operations that are slow in C++? Cleaning up your implementation can also improve in practice runtime.

      If you post the code on pastebin, I can take a look.

      Delete
    4. Here it is: https://github.com/metaflow/contests/blob/master/kattis/thief/thief.cpp
      (sorry for macro usage)

      Delete
  2. Btw, I have tried to listen to "waterfall" during last atcoder contest - it was OK, I have not experienced any loss of concentration thought performance was at about the same level. Usually I listen to BT-binary universe album and do it exclusively during contests to make some kind of mental habit. Do you still listening to "white noise" and found it productive?

    ReplyDelete
    Replies
    1. I enjoy BT as well. His +/- album is great for background music. I still listen to white noise when I compete. My advantage is purely based on my subjective experience. It helps me focus without distracting me and prevents my mind from wandering too much to things that aren't the contest.

      Delete
  3. 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
    Replies
    1. 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

      Delete
  4. I really want to thank Dr Emu for saving my marriage. My wife really treated me badly and left home for almost 3 month this got me sick and confused. Then I told my friend about how my wife has changed towards me. Then she told me to contact Dr Emu that he will help me bring back my wife and change her back to a good woman. I never believed in all this but I gave it a try. Dr Emu casted a spell of return of love on her, and my wife came back home for forgiveness and today we are happy again. If you are going through any relationship stress or you want back your Ex or Divorce husband you can contact his whatsapp +2347012841542 or email emutemple@gmail.com website: Https://emutemple.wordpress.com/

    ReplyDelete