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.
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.
ReplyDeleteIf 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.
In classical 0/1 knapsack, the order of weights didn't matter as they resulted in the same profit but here in this case, you need order or elements because the points you score depends upon the order you choose problems so we use exchange arguments to get the order of problems which results optimal result.
DeleteDr. Osofo is a great spell caster, My marriage of 14 years was having a problem and my husband request for a divorce i was so heart broken because i love him so much that i can't let him just go, So i was doing some research on the internet on how to fix up my broken marriage i saw some review about Dr osofo how he help people with a love spell so i contacted him and tell him my problems he only reply me with some words and told me what to do after 48hours you wouldn't believe my husband come back house with much love and caring. kindly contact dr osofo if you have any problem with your relationship or marriage via: (osofo.48hoursolutioncenter@gmail.com ) you can also whatsapp him +2349065749952
ReplyDeleteEFFECTIVE LOVE SPELL TO GET EX HUSBAND/BOYFRIEND OR EX WIFE/GIRLFRIEND AND CURE HERPES AND INFERTILITY THAT WORKS WITHIN 24 HOURS.
ReplyDeleteContact 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
A GREAT SPELL CASTER (DR. EMU) THAT HELP ME BRING BACK MY EX GIRLFRIEND.
ReplyDeleteAm 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