Algorithms Thread 8: Tree Basics (+ Gym Contest)

Revision en5, by SecondThread, 2020-09-02 05:56:30

Algorithms Thread Episode 8: Tree Basics

Episode 8 of Algorithms Thread comes out in <90 minutes! This one is a bit more beginner-friendly and covers the following ideas:

  • Graph/Tree Diameters
  • Binary Lifting
  • Tree Flattening with Euler tours

Also, to make sure you have actually learned that stuff, I made a custom Gym set on CodeForces that will last two weeks that hopefully is really good practice for making sure you have learned this stuff. Here is a link to the gym set; it will be available 45 minutes after the video comes out so that people have time to watch the video before starting the set, if they are interested in penalty points. All of the problems in the gym are original to this set (in their flavortext at least, some are simple enough that I'm sure they have appeared in other contests before).

The new gym integration was heavily inspired by Errichto's Matrix Expo set format. Let me know whether it's helpful. I think it might be, but also it's a pretty big time commitment to make it, so whether I keep doing them depends on how helpful they are to people.

If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and I'll leave you all with this:


Solutions

Update: Video solutions to all problems

Tags algorithmsthread, #trees, binary lifting, euler tour

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English SecondThread 2020-09-02 06:11:06 121
en5 English SecondThread 2020-09-02 05:56:30 122
en4 English SecondThread 2020-08-16 21:30:00 20 Tiny change: 's Thread [is out now!](https:/' -> 's Thread [comes out in <90 minutes!](https:/' (published)
en3 English SecondThread 2020-08-16 09:22:16 11 Tiny change: 'commitment, so whet' -> 'commitment to make it, so whet'
en2 English SecondThread 2020-08-16 09:20:34 38
en1 English SecondThread 2020-08-16 09:16:18 1400 Initial revision (saved to drafts)