Sunday, April 16, 2017

Episode 16 - Ski Resort

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)

5 comments:

  1. Hi Matt! Could you please update link to the problem: https://naipc17.kattis.com/problems/skiresort ?

    ReplyDelete
    Replies
    1. Fixed! Thank you for letting me know the link was broken. :)

      Delete
    2. Thank 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 :)

      Delete
    3. Finally 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.

      Delete
    4. Nice work! Also, all the test cases for NAIPC problems can be downloaded here:
      http://serjudging.vanb.org/?p=1050

      Delete