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://naipc17.kattis.com/problems/naipc17.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)

1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete