Video Lectures for Dynamic Programming on Trees || CSES Tree algorithms section

Revision en1, by kartik8800, 2020-07-07 20:15:19

Hello Codeforces!!

In this blog, I want to present to you a beginner-friendly video lecture series on dynamic programming on trees/an editorial for the CSES tree algorithms section.

CSES is a brilliant problemset for people wanting to get started at competitive programming and get good at it.

My aim till now has been to make the explanations intuitive, crisp and clear. I feel even a beginner will be able to benefit from these video lectures.

So let's get started.
Link to the problems

Subordinates

Explanation : https://youtu.be/fGznXJ-LTbI
AC code : https://github.com/kartik8800/CSES/blob/master/Subordinates

Tree Matching

Explanation : https://youtu.be/RuNAYVTn9qM
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Matching

Tree Diameter

Explanation : https://youtu.be/qNObsKl0GGY
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Diameter

Tree Distances I

Explanation : https://youtu.be/N7e4CTfimkU
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%201

Tree Distances II

Explanation : https://youtu.be/nGhE4Ekmzbc
AC code : https://github.com/kartik8800/CSES/blob/master/Tree%20Distances%202

Company Queries I

This problem uses a technique(the technique itself uses DP) known as Binary lifting. I will be adding a detailed lecture on binary lifting with code.

Explanation : Expect it to be added very soon

Company Queries II

This problems requires us to know a technique to calculate LCA of two nodes in a tree in O(logN) time. Evaluation of LCA in O(logN) can be done using binary lifting. I will add a more detailed video soon.

Explanation : Expect it to be added very soon

Distance Queries

Problem Statement : what is the distance between nodes a and b?
Short explanation : Let LCA(a,b) be node x, what is distance between a and x?
Preprocess the levels of all the nodes in the tree.

lvl[i] : level of node i in the tree.
Ans to query distance(a,b) = (lvl[a] — lvl[x]) + (lvl[b] — lvl[x]) where x is the LCA(a,x).

Again finding LCA of two nodes can be done in O(logN) time and levels of all nodes can be found in O(N) time preprocessing.

Will try to add the remaining problems also as soon as possible for me.

I am also planning to add video lecture series on more topics which might be helpful to beginners as well intermediates. I will be open to feedback and suggestions.

I hope people find this helpful :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English kartik8800 2020-12-09 12:18:57 344 Tiny change: '-cameras/)\nsolution' -> '-cameras/)<br>\nsolution'
en7 English kartik8800 2020-12-04 11:10:00 316
en6 English kartik8800 2020-07-18 20:31:39 494 Tiny change: 'echniques.\n<strong>' -> 'echniques.<br>\n<strong>'
en5 English kartik8800 2020-07-17 03:25:11 274
en4 English kartik8800 2020-07-09 01:07:31 187 Tiny change: 'ful :)\n\nUPD: added de' -> 'ful :)\n\n<strong>UPD</strong>: added de'
en3 English kartik8800 2020-07-07 20:56:07 164
en2 English kartik8800 2020-07-07 20:45:27 676
en1 English kartik8800 2020-07-07 20:15:19 2779 Initial revision (published)