Try these problems:
Last week, I mentioned I would be running this episode on Wednesday due to travelling to the TCO regional event in Austin. It turns out there is an SRM at this time! So this week's episode will take place a day later.
In this episode, I will cover a handful of tricks involving preorder and postorder numbers on trees and some neat properties involving them. I'll also discuss two different approaches for solving the problems linked above.
See you live! (stream, time)
Wednesday, April 26, 2017
Friday, April 21, 2017
Episode 17 - Binary Lifting
Try these problems:
I realize the last few weeks have been a bit rough for Div2 viewers. The problems have been near ICPC World Finals level and I want to vary the difficulty of topics to make sure everyone can enjoy the show. This week I'll be covering a technique that is more accessible! This technique is called binary lifting. It is a technique for quickly walking up a rooted tree.
In last week's episode, I discussed the solution to the problem Ski Resort from NAIPC. The problem required us to compute LCAs (least common ancestors) quickly on rooted trees. I'll be expanding on how to do that in this episode.
You'll also learn how to quickly know the length of paths in trees, find bottle neck edges quickly in weighted graphs, and other useful tricks.
See you live! (stream, time)
- https://open.kattis.com/problems/tourists
- http://codeforces.com/contest/519/problem/E
- https://www.codechef.com/problems/DRAGONST
I realize the last few weeks have been a bit rough for Div2 viewers. The problems have been near ICPC World Finals level and I want to vary the difficulty of topics to make sure everyone can enjoy the show. This week I'll be covering a technique that is more accessible! This technique is called binary lifting. It is a technique for quickly walking up a rooted tree.
In last week's episode, I discussed the solution to the problem Ski Resort from NAIPC. The problem required us to compute LCAs (least common ancestors) quickly on rooted trees. I'll be expanding on how to do that in this episode.
You'll also learn how to quickly know the length of paths in trees, find bottle neck edges quickly in weighted graphs, and other useful tricks.
See you live! (stream, time)
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)
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)
Friday, April 7, 2017
Episode 15 - Split the Sequence
At the start of last week's episode, I mentioned my decision to split the episode in two. The last problem, Split the Sequence, is beautiful and I felt it deserved its own episode.
I highly recommend you try the problem yourself if you haven't already:
This week's episode we will systematically move through the solution, approaching faster and faster runtimes, as we make observations about the problem structure. See if you can spot the greedy property you need to solve the problem. We'll be discussing the proof of this property using the exchange argument technique from last week's episode.
See you live! (time, stream)
I highly recommend you try the problem yourself if you haven't already:
This week's episode we will systematically move through the solution, approaching faster and faster runtimes, as we make observations about the problem structure. See if you can spot the greedy property you need to solve the problem. We'll be discussing the proof of this property using the exchange argument technique from last week's episode.
See you live! (time, stream)
Subscribe to:
Posts (Atom)