I think this format of mini lecture + practice problem set is the best for beginners, as you mentioned, it is also the most time-consuming for you the content creator :) We beginners can watch lectures after lectures but new concepts will never solidify until we put them into concrete implementations and solve problems with them. And a lot of beginners like me do not necessarily have a solid implementation skill, so practice problems definitely help with this as well.
Just wanted to say how much I appreciate this ENTIRE channel. Your personality is so infectious ! After every contest I come straight here and use the videos as editorials. You the best !
You explained pretty much everything in tree which took me 4-5 months becuz I didn't know we can also do that especially segment one. Those begginers who learn from your videos will definately experience time travel ❤️
Loved the new format ! This helps gain much more confidence on the covered concepts instead of just watching a tutorial on some topic and not getting custom problems on that topic.
I really appreciate you devoting a whole week curating these problems, test cases, the video content and recording it and putting it out here for free! god bless you
SOOOOOOO Looking forward to this one!! Please go in depth on Trees and solve a lot of problems with common techniques and tricks (with the actual code!). You channel is a blessing! Keep it up! I'll send you money the day I start earning!
Was an intermediate level stuff ig. Very informative. Euler tours concept was very well explained. Being able to solve path queries using this is amazing. Thanks
Hey man please continue this and thanks for this amazing style of teaching Everytime after a codeforces round just waiting for u to post the solutions video and all videos are super useful
Dude GG. I always thought this stuff was for GMs and never even touched the content on CP-Algorithms. 40 min well spent, I shall get down to the gym now I guess. Also, to answer your final question, yes, I like this format better. You got a like and sub from me.
Such an awesome initiative and I loved the way you teach.Thank you so much . Could you please include 2 to 3 more problems in gym set please so that we gain more confidence.Thank you once again....!!!
You are just awesome. Thanks a lot for this tutorial. The last trick was amazing considering how time-consuming and difficult it is to implement HLD for that thingie.
Hey David! About 2nd problem I find all the leaves that can be a part of diameter and then while printing if it one of these leaves then I increase the diameter by 1 or I just print the original diameter ..is this logic wrong?...it's giving WA verdict on case 14.
The general idea is right: if you add an edge onto a leaf of an original diameter, you increase the answer by one, otherwise it doesn’t change. Make sure you’re correctly identifying all leaves of some diameter correctly though. That part is easy to mess up.
Dude u r one of those few who I feel like paying but I can't coz I am broke (lol)...instead my college professors are taking that money for no reason.....thanks a lot
Can i ask which point will we update when we want to modify the segment tree? The index in the Euler tour which has the starting time of that node or am i mistaken? And for more clarification if we want to assign value v to node x, then i just look for it's start time index in the flatten array and update it in the segment tree? 31:26
Hey man, is it possible to apply the logic of applying BFS on a random node, and then applying BFS from one of the end points of the diameter to a graph with no cycles? Would a graph with no cycle work the same as a tree in this case?
If the graph is connected, a graph with no cycles is a tree. If the graph has multiple components but no cycles, then that's a "Forrest" of trees, and you'd have to check each component. (Otherwise you might start in the wrong one)
33:00 wouldnt it be more efficient to go from the down node and go up until the higher node is reached ? No need to precompute since depths values are already needed for lca
So first of all binary lifting had an extra log factor so it'd be slower. Next, paths can do subtrees, but lifting can't. Finally, binary lifting can't process things with updates. When you update 1 node, you'll have to update O(n) nodes' lift arrays. So essentially it's just not possible to support non-static trees if the queries and mutations are arbitrary.
Hey, sorry for asking this but I am kinda new to your channel . I know the basics about graphs like bfs,dfs,SCC,shortest paths like Dijkstra, Floyd Warshall etc fairly well. Can you please tell if this video and the gym contest on tree basics is suitable for a pupil like me on Codeforces? NO offence but I just don't want to start this only to find out later that it is too hard for me yet. -Please say yes.-
Given some queries on a weighted tree: 1) U, V: find this value max(max weight of an edge which lies on the shortest path between U and V, min weight of an edge which is not a part of the shortest path between U and V) How to solve this?
The max weight of an edge on a path can be done with binary lifting. Min weight of an edge not in the path seems tricky to me. It's possible to do it in n*log^(2) with a persistent segment tree and Version 2 of tree flattening, but it's tricky at least. There might be a better, way that I can't think of right away though.
The general topics are all there: diameters, binary lifting, and subtree aggregates. For some problems you need to use a little math knowledge, but mostly it’s all just a short extension of this video
@@SecondThread Can't seem to really understand how to actually implement E from your gym set. I tried looking for some good tutorial on the web but couldn't find something. Do you plan to make a solution video too? If not, can you share some resources for the same? Thanks :)
"I know how to find diameter of a tree, I didn't start programming last week " No way ngl, I didn't know that tree's got diameter too, forget finding the diameter. Also, I didn't start programming last week 😭😭
I think this format of mini lecture + practice problem set is the best for beginners, as you mentioned, it is also the most time-consuming for you the content creator :) We beginners can watch lectures after lectures but new concepts will never solidify until we put them into concrete implementations and solve problems with them. And a lot of beginners like me do not necessarily have a solid implementation skill, so practice problems definitely help with this as well.
th-cam.com/video/jCHy8PEgIUI/w-d-xo.html
Very true !
Just wanted to say how much I appreciate this ENTIRE channel. Your personality is so infectious ! After every contest I come straight here and use the videos as editorials. You the best !
th-cam.com/video/jCHy8PEgIUI/w-d-xo.html
You have my utmost respect in the community, Knowledge is something you can't repay with anything else.
You explained pretty much everything in tree which took me 4-5 months becuz I didn't know we can also do that especially segment one. Those begginers who learn from your videos will definately experience time travel ❤️
Loved the new format ! This helps gain much more confidence on the covered concepts instead of just watching a tutorial on some topic and not getting custom problems on that topic.
This is by far the most comprehensive tutorial on trees, I've ever come across. Thanks a ton for this one!
I rarely had seen someone like you who helped others like this way. Thanks for this.
I really appreciate you devoting a whole week curating these problems, test cases, the video content and recording it and putting it out here for free! god bless you
It's not high quality, its highest quality content. Thank you.
I love this. Very clear explanation. In short, fabulous work. Please keep up the good work🙏
SOOOOOOO Looking forward to this one!! Please go in depth on Trees and solve a lot of problems with common techniques and tricks (with the actual code!). You channel is a blessing! Keep it up! I'll send you money the day I start earning!
Me too
Thanks guys, I truly appreciate the sentiment, but I don't want to be taking money from people for this, at least not anytime soon :)
Was an intermediate level stuff ig. Very informative. Euler tours concept was very well explained. Being able to solve path queries using this is amazing. Thanks
th-cam.com/video/jCHy8PEgIUI/w-d-xo.html
Tutorial is really helpful. Please continue creating quality video tutorials like this. Thank you so much for sharing your knowledge here.
Hey man please continue this and thanks for this amazing style of teaching
Everytime after a codeforces round just waiting for u to post the solutions video and all videos are super useful
I see tree flattening in the description. I remember messaging you on cf to cover that. Thanks!
Dude GG. I always thought this stuff was for GMs and never even touched the content on CP-Algorithms. 40 min well spent, I shall get down to the gym now I guess. Also, to answer your final question, yes, I like this format better. You got a like and sub from me.
It is a Really helpful way to teach. Please bring more of it. Thanks a lot.
just come to hear "goodmorning everyboddy"
luv man from egypt
th-cam.com/video/jCHy8PEgIUI/w-d-xo.html
Such an awesome initiative and I loved the way you teach.Thank you so much . Could you please include 2 to 3 more problems in gym set please so that we gain more confidence.Thank you once again....!!!
The gym was especially useful. I don't really want to learn new concepts if there's no problem to submit. Also problem statements are great!
You are just awesome. Thanks a lot for this tutorial. The last trick was amazing considering how time-consuming and difficult it is to implement HLD for that thingie.
but that trick works only for mos algorithm isn't it? will that work using segment trees?
Yeah These tutorials are really helpful, I liked this We get to learn new ideas from this. Thanks for such amazing videos
This format is superb!!!
Thanks for the great video! Really loved the new format!
This format lecture + practice problem is the best !!
This was so much worth waiting, awesome work bro 🤩
giving problems along with the video was helpful really appreciated
Click to Create a new whiteboard... -> gets a blackboard
th-cam.com/video/jCHy8PEgIUI/w-d-xo.html
Amazing content:)
Thanks for your efforts towards the community💙
Thank you for all you have done. I appreciate your efforts.
very high quality material ! please bring some on game theory and flow algorithms
Thank you so much sir💗💗🔥🔥 please continue your channel sir
Emmm how it's 9PM and he's still saying good morning everybody xD
Good morning!
He is based in Pacific Time that spans the US west coast, which is 8 hours behind UTC. Besides this is a recorded lecture.
@@linzhang9529 yeah I know but look at the time on his screen
@@amirh8748 oh, lol. I think it has officially become second thread's catch phrase now.
Thanks for all efforts
very helpful man
I had a problem on binary lifting but I got it now
Thanks a lot for this valuable effort!
This is super helpful!
This was very helpful. Thanks a lot!
YOU ARE THE BEST PERIOD.
AMAZING STUFF! thank you
this is very helpful
Can we use bynari search to find LCA, like if we have two nods on same level and wont to find ancestor.
Hey David! About 2nd problem I find all the leaves that can be a part of diameter and then while printing if it one of these leaves then I increase the diameter by 1 or I just print the original diameter ..is this logic wrong?...it's giving WA verdict on case 14.
The general idea is right: if you add an edge onto a leaf of an original diameter, you increase the answer by one, otherwise it doesn’t change. Make sure you’re correctly identifying all leaves of some diameter correctly though. That part is easy to mess up.
Thank you David I'll check that :)
You deserve more subs.
Thanks a lot for the lecture. Practise problems are great and key
Could you please post up such a video on square root decomposition?
Dude u r one of those few who I feel like paying but I can't coz I am broke (lol)...instead my college professors are taking that money for no reason.....thanks a lot
Thanks man, that really means a lot to know this is helpful.
Great work
It's really helpful.Thanks a lot
Can i ask which point will we update when we want to modify the segment tree?
The index in the Euler tour which has the starting time of that node or am i mistaken?
And for more clarification if we want to assign value v to node x, then i just look for it's start time index in the flatten array and update it in the segment tree?
31:26
Yep, the starting index would correspond to that node in the tree.
Thank you :).
Thanks a lot for the tutorial
This video is awesome😀.
I am not able to get AC in tree circumference problem . What to do ? There is no editorial available ..
Can you please do a tutorial on data structures and algorithms for beginners
I just love your videos :)
very good observation 🧐
Hey man, is it possible to apply the logic of applying BFS on a random node, and then applying BFS from one of the end points of the diameter to a graph with no cycles? Would a graph with no cycle work the same as a tree in this case?
If the graph is connected, a graph with no cycles is a tree. If the graph has multiple components but no cycles, then that's a "Forrest" of trees, and you'd have to check each component. (Otherwise you might start in the wrong one)
What is HLD which is continuously referred in the video?
33:00 wouldnt it be more efficient to go from the down node and go up until the higher node is reached ? No need to precompute since depths values are already needed for lca
Not quite sure what you mean. Can you explain what the original problem was and your proposed alternative in more detail?
@@SecondThread
Nvm, i figured it out. What i said was dumb
Please make a playlist on Graph
Please sir!!
please make a video on BITMASKING with DP
I LOVE THIS
Describing Euler as "some guys name". It's true, but he's a pretty important guy.
That's it for this thread....!!
What is the editor you are using to draw the diagrams ?
hey, isn't your LCA O(logN*logN) per query? logN for binary search and logN for moving up by that much. How do you bring it down to O(logN)?
Only one log because the “binary search” value only goes down, it never increases.
That is, if you jump up 2^12, you start checking 2^12 next time, then 2^11... so you only do 20 jumps total, and it amortizes to O(1) per jump
Gr8.....quality stuff....thanks a ton....
in path isloation idea why the height of 3 subtree is atmost 2 it should be 1 11:10
Can't we path tour using binary lifting? just like we processed lift, we could also process operations on path queries. No hating, just asking
So first of all binary lifting had an extra log factor so it'd be slower.
Next, paths can do subtrees, but lifting can't.
Finally, binary lifting can't process things with updates. When you update 1 node, you'll have to update O(n) nodes' lift arrays. So essentially it's just not possible to support non-static trees if the queries and mutations are arbitrary.
@@SecondThread I got it. Thanks !!!
Your playlist really helped me a lot in trees
Next up : CF DP gym contest like AtCoder ?
You are doing great job man.....while(true){ respect++;}
Hey, sorry for asking this but I am kinda new to your channel . I know the basics about graphs like bfs,dfs,SCC,shortest paths like Dijkstra, Floyd Warshall etc fairly well. Can you please tell if this video and the gym contest on tree basics is suitable for a pupil like me on Codeforces? NO offence but I just don't want to start this only to find out later that it is too hard for me yet. -Please say yes.-
I explain the prereqs required for it to be helpful in the beginning of the video
@@SecondThreadok. Thanks for reply 😀
You shouldn't be a pupil if you know all these fairly well...
great video
Could plz participate and explain google kickstart solutions also🙏
when will you add the tutorial for your cf gymset? waiting for it!
It's added now
thank you :)
Which laptop model are you using?
Good morning. I get TLE on the second problem, even though my complexity is O(n) #90389036
somehow i figured out that one dfs takes 0.3 secs(on the 4th test case), but i run it 4 times :(
Please make the test cases public now, the contest is already over.
Given some queries on a weighted tree:
1) U, V: find this value
max(max weight of an edge which lies on the shortest path between U and V, min weight of an edge which is not a part of the shortest path between U and V)
How to solve this?
The max weight of an edge on a path can be done with binary lifting. Min weight of an edge not in the path seems tricky to me. It's possible to do it in n*log^(2) with a persistent segment tree and Version 2 of tree flattening, but it's tricky at least. There might be a better, way that I can't think of right away though.
Nice problem flattening wouldn't work bfs will work but time complexity is not good I guess binary lifting will work with some modification
I am doing cp for 8 months,still,I didn't knew this idea of finding diameter🤭.
Love You Bro
What about Global round stream ?
It should be up on my channel already
@@SecondThread what about round 1 hackercup?
@@fastio8489 No hackercup participation from me allowed since I work for Facebook
@@SecondThread would be really helpful if you could make videos on solution though.
@@fastio8489 th-cam.com/video/vW4UbjBs3Jo/w-d-xo.html
please go through your code once, I have stared cp in java and looking at your videos for help. thanks.
why dont you post tutorial video for your contest - It will be useful for beginners
posting now
@@SecondThread you are a true inspiration...thanks🔥
Will this be helpful in Codeforces, CodeChef, or USACO competitions?
I thought you'd cover all the topics that you made problems on in your gym set :(
The general topics are all there: diameters, binary lifting, and subtree aggregates. For some problems you need to use a little math knowledge, but mostly it’s all just a short extension of this video
@@SecondThread Can't seem to really understand how to actually implement E from your gym set. I tried looking for some good tutorial on the web but couldn't find something. Do you plan to make a solution video too? If not, can you share some resources for the same? Thanks :)
doing Euler proud
this format is reaaally usefull like so much thanks a lot man ily :orz: :orz: :orz: :orz: but other videos also suits me lol dw
26:36 lol so cute :3
0:00 midnight for me lmao
Lets take a moment to thank David aka Secondthread for his hard work and time by liking this comment.
th-cam.com/video/jCHy8PEgIUI/w-d-xo.html
"I know how to find diameter of a tree, I didn't start programming last week "
No way ngl, I didn't know that tree's got diameter too, forget finding the diameter. Also, I didn't start programming last week 😭😭
Second Thread -
undoable = undo + able , simple guyz
Linguistics - Are we a joke to you
Actually, that's really funny. I just now noticed that it could mean "impossible to complete" as well
@@SecondThread Ahh you were right, I didn't cross check dictionary and thought you made up your own word. nm : )
damn ogs really cooked
1.1k vs 8 dislikes.
So if one person uses eight different accounts...
There is too much knowledge in this lecture.