Thursday, February 23, 2017

Episode 9 - Solution Bags

Give these problems a try:

This week's episode of Algorithms Live! will cover solution bags. This is less of an algorithm or data structure and instead a different way of thinking of problems involving data structures. You can also view it as a different approach to dynamic programming that naturally yields itself to data structure optimizations.

During the discussion, I'll be going over maintaining an invariant on a data structure and how this can make basic data structures more powerful. My goal will be to change your way of thinking about data structure problems. Instead of guessing of what data structures might be relevant, we will list what our data structure needs to do and design our data structure from there. The data structure will reveal itself naturally from this analysis. I find this technique leads to simpler data structures.

Consider this problem: https://open.kattis.com/problems/whiteboard

Many solvers during this contest used segment trees, but a simple solution using only an ordered set (TreeSet in Java, multiset in C++) also exists. Finding solutions using this type of simple data structure will be easier after learning this way of thinking.

Also during this episode, I will discuss the min queues and their relationship with maintaining an invariant on a data structure. Using this data structure, we will solve the problem of finding the diameter of an almost tree.

See you live! (time, stream, channel)

Other news: This Saturday UCF will compete in this joint north american practice: https://open.kattis.com/contests/naipc17-p02. The practice is open to anyone to join. I'll be competing as UCF Death Valley.

16 comments:

  1. Another problem for practice: http://codeforces.com/contest/797/problem/F

    ReplyDelete
  2. Hi there, great video by the way. I was wondering if you can point me to some resources or tutorials on how to use deltaing like you described in the video? I tried to apply it to the subset sum problem but was unsuccessful

    ReplyDelete
    Replies
    1. Here's my solution to the Minimal Subarray Length problem using the technique he described if you're still having trouble:
      https://pastebin.com/THDh3shA

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  4. Dr. 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

    ReplyDelete
  5. How I Got My Ex Husband Back..Am so excited to share my testimony of a real spell caster who brought my husband back to me. My husband and I have been married for about 6 years now. We were happily married with two kids, a boy and a girl. 3 months ago, I started to notice some strange behavior from him and a few weeks later I found out that my husband is seeing someone else. He started coming home late from work, he hardly care about me or the kids anymore, Sometimes he goes out and doesn't even come back home for about 2-3 days. I did all I could to rectify this problem but all to no avail. I became very worried and needed help. As I was browsing through the internet one day, I came across a website that suggested that Dr Aluya can help solve marital problems, restore broken relationships and so on. So, I felt I should give him a try. I contacted him and and told him my problems and he told me what to do and i did it and he did a spell for me. 48 hours later, my husband came to me and apologized for the wrongs he did and promise never to do it again. Ever since then, everything has returned back to normal. I and my family are living together happily again.. All thanks to Dr Aluya Powerful Love Spell that really works. If you have any problem contact him and i guarantee you that he will help you. He will not disappoint you. Email him at: aluya.48hoursspelltemple@gmail.com or whatsapp him on: +2348110493039

    ReplyDelete
  6. My name is Louis Edmond, I am from USA. I want to share a testimony about Dr Aluya, a great spell caster who is very straight forward with his words of casting spells. When my Wife left me for another Man i was so confused,but one a day a friend of mine gave me the email address of this great spell caster called dr Aluya, I contacted this man and explained to him all that i was going through,he then told me to be calm and not worry anymore because my case is a very easy one. At first I never believed all that he was saying until when my husband returned home two days later begging me to forgive him for all that he had done to me and to please accept him back into my life,I was so amazed,I never believed it was going to happen that fast.
    This man is truly great indeed. Contact him today for a perfect solution to your love problem, aluya.48hoursspelltemple@gmail.com.  or whatsApp him  +2348110493039

    ReplyDelete
  7. 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
  8. I am sharing this testimony to partners suffering in their relationships because there is an enduring solution.
    My husband left me and our 2 kids for another woman for 3 years. I tried to be strong just for my kids but I could not control the pains that torment my heart. I was hurt and confused. I needed help, so I did some research on the internet and came across a site where I saw that Dr. Aluya a spell caster, can help get lovers back. I contacted him and he did a special prayer and spells for me. To my surprises, after some days, my husband came back home. That was how we reunited again and there was a lot of love, joy and peace in the family.
    You can as well contact Dr.  Aluya  , a powerful spell-caster for solutions on his contact aluya.48hoursspelltemple@gmail.com or directly on Whats App: +2348110493039         aluya.48hoursspelltemple@yahoo.com      https://draluya48hoursspelltemple.webs.com/  

    ReplyDelete
  9. This is a testimony that i will tell to every one to hear. i have been married four 2 years and on the fifth year of my marriage, another man had a spell to take my lover away from me and my wife left me and the kids and we have suffered for 2 years until i meant a post where this man Dr, Aluya have helped someone and i decided to give him a try to help me bring my love wife home and believe me i just send my picture to her and that of me and after 15hours as he have told me, i saw a car drove into the house and behold it was my wife and she have come to me and the kids and that is why i am happy to make every one of you in similar to met with this man and have your lover back to your self His email:aluya.48hoursspelltemple@gmail.com OR aluya.48hoursspelltemple@yahoo.com https://draluya48hoursspelltemple.webs.com/

    WhatsApp him at (+2348110493039)thank so much.

    ReplyDelete
  10. My husband and I have been married for about 7 yrs now. We were happily married with two kids, a boy and a girl. 3 months ago, I started to notice some strange behavior from him and a few weeks later I found out that my husband is seeing someone. He started coming home late from work, he hardly care about me or the kids anymore, Sometimes he goes out and doesn't even come back home for about 2-3 days. I did all I could to rectify this problem but all to no avail. I became very worried and needed help. As I was browsing through the Internet one day, I came across a website that suggested that Dr Aluya can help solve marital problems, restore broken relationships and so on. So, I felt I should give him a try. I contacted him and he did a spell for me. Two days later, my husband came to me and apologized for the wrongs he did and promise never to do it again. Ever since then, everything has returned back to normal. I and my family are living together happily again.. All thanks to Dr Aluya . If you need a spell caster that can cast a spell that truly works, I suggest you contact him. He will not disappoint you. This is his E-mail: aluya.48hoursspelltemple@gmail.com    OR       aluya.48hoursspelltemple@yahoo.com  Whats App +2348110493039

    https://draluya48hoursspelltemple.webs.com/

    ReplyDelete
  11. Dr. Obodubu Monday is recognised all over the world of marine kingdom, As one of the top fortunate and most powerful native doctor of charms casts from the beginning of his ancestors ship until now Dr. Obodubu Monday lives strong among all other native doctors, there have never been any form of impossibility beyond the control of Dr. Obodubu Monday it doesn't matter the distance of the person with the problems or situation, all you have to do is believe in the native doctor Dr. Obodubu Monday cast that works, he always warns never to get his charms cast if you do not believe or unable to follow his instruction. it is the assignment of the native doctor Dr. Obodubu Monday to offer services to those in need of spiritual assistance not minding the gravity of your situations or distance as long as water, sea, ocean, lake, river, sand, etc. are near you, then your problems of life would be controlled under your foot. if you need any spiritual help on any of these call Doctor Obodubu on :+2349058774809
    Get Your Love Back
    Fruit Of The Womb
    Fibroid
    Business Boom
    Financial Breakthrough
    Get Rich Without Ritual
    Do As I Say
    Bad Dream
    Promise And Fail
    Epilepsy
    Land/Court Case
    Mental Disorder
    Political Appointment
    Visa Approval
    Cancer
    Examination Success
    Spend And Get Back
    Good Luck
    Natural Neath
    Hypertension
    Stroke
    Sickle cell
    Impotency
    Win Court case
    Promotion At Work
    Commanding Tone
    Protection Ring
    Marriage Success
    Love Ring
    Favour Ring
    Recover Lost Glory
    Spiritual Power For Men Of God
    Travel Success Ring
    Job Success
    Lotto/Pool Win/betnaija win
    And Many
    More make haste to call or Or WhatApp Baba Doctor Obodubu Monday on +2349058774809 for spiritual problem today and you will surely get solution to all your predicament

    ReplyDelete
  12. 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
  13. Good day to you, here is a quick one, just in case you are desperately in need of a trustworthy spell caster to help revive your crumbled relationship. Here is one that is truly versatile, compassionate and reliable when it comes to spell casting.. Doctor Abolo spelling home is the right choice for you. Contact and explain to him and I can assure you that the rest would be complete magic, my love life was on the verge of collapse until I ordered for a love spell while all due procedures were properly followed, I am a living witness that Doctor Abolo spell magic does work that is why i'm using all medium to let the world know of this great witch doctor who brought back peace and unity to my home, Talk to him today and have your emotional setbacks wiped out totally.
    You reach him at these contacts! Abolospell@gmail.com

    ReplyDelete