Thursday, February 2, 2017

Episode 6 - USACO Dec '16

Try solving these two problems:


Both these problems are interesting, but I find the editorials are troublesome to understand. My view is the editorials for these problems aren't bad, but these problems are easier to explain through a whiteboard and talking. This is why I've chosen to review them. Both are beautiful problems and should be quite fun to discuss. If you competed in USACO recently, you may have an interest in knowing how they are solved and should watch this episode!

I've received many comments on what should be covered in future weeks. I'd like to talk about a few of these ideas and how I plan to cover them. One request was for the technique "convex hull optimization". This is a fun advanced technique in competitive programming. I'll be spending multiple weeks to build up to this technique and cover several interesting problems that can be solved using it. I'll also discuss a more general technique for reasoning about a class of problem that includes "convex hull optimization".

I received a few suggestions to cover treaps. This is great because I love treaps! Any binary search trees that can be split in O(log n) time results in a malleable data structure much more flexible than segment trees. I also want to discuss splay trees as an alternative to treaps. Curbing the excitement, I'll be delaying these episodes for a bit. The reason is I want to follow these episodes with episodes on link-cut trees and euler tour trees.

There were also requests to cover suffix arrays, flow problems, 2D segment trees, centroid decomposition, and many more. I'll be delighted to cover all those things. Of course, I'll be peppering in a few weeks just covering problems I find interesting to keep variation. Future weeks will also have more guests! The guest episodes will focus on problems or techniques the guests will like to cover. It should be an interesting next few months. :)

See you live! (time, stream, channel)

2 comments:

  1. I think after each live episode , you can update some problem link ( about 3 - 5 ) related to the technique you mentioned from easy to hard for practice purpose.

    ReplyDelete