NAIPC 2017 took place this weekend as well as the Open Cup version (GP of America). I'm hoping many of you enjoyed the problems and found them interesting. The set was challenging for many teams. You can find the official standings to each contest here:
MIT won NAIPC solving 10 problems. On the Open Cup side, Tsinghua University impressively solved all 11 problems towards their victory! ITMO also had a strong performance. Well done! It should be an exciting ICPC World Finals in a few weeks.
In this week's episode, I will be covering a solution to the toughest problem from this contest. Only Tsinghua University managed to solve it in both contests. You can find the problem here:
https://open.kattis.com/problems/skiresort
Dominator trees seem to be trendy in competitive programming at the moment. This problem appears to play the part. Yet there is a solution to this problem that makes no use of dominator trees! Still, this problem is a good excuse to explain dominator trees and how to construct them simply for directed acyclic graphs. There are also a few other tricks and observations needed to solve this problem.
See you live! (stream, channel)
Hi Matt! Could you please update link to the problem: https://naipc17.kattis.com/problems/skiresort ?
ReplyDeleteFixed! Thank you for letting me know the link was broken. :)
DeleteThank you! Do you know where can I download testcases for this problem? I have hit a wall with TLE on 40/89 on kattis and have no clue what is wrong :)
DeleteFinally nailed it :) turns out that my implementation when every node is an object by itself and edges are just pointers is way slower than arrays of indexes.
DeleteNice work! Also, all the test cases for NAIPC problems can be downloaded here:
Deletehttp://serjudging.vanb.org/?p=1050
EFFECTIVE 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
Wynn Resorts - Dr. Maryland
ReplyDeleteWynn 인천광역 출장샵 Resorts. 안산 출장마사지 4111 Las Vegas 당진 출장안마 Blvd 속초 출장샵 South, Las Vegas, NV 89109. Phone: 702.770.6663. 경주 출장마사지 Website: www.wynnlasvegas.com/rooms.