Thank you David for all the effort you put in making solution videos, screencast and lectures. Just a small suggestion or I should say Request, Kindly do lectures on not so advanced stuff with questions. Just like what you did for tree algorithms(problems on gym + explanation later), that was really helpfull. It would be really great if you could do for other topics as well(not so advanced topics) which can be helpfull and at the same time, frequently used in cf contests. Topics like:- Dp with bitmask Dp on segments Some dp problems which can be solved with recur + memo Graphs Tree dp Array problems increasing decreasing subsequence types. Etc Some gym questions + explanation later would be Great, just the way you did for tree algorithms. Thank you so much
Ohh Holy, I was wandering everywhere to understand this topic since months, pls do take some problems and pls let us walk through the code step by step ❤️
I have been waiting to learn one of the balanced search trees and treap seems like a good starting point, I will be thankful if you can mention that case you talked about where you might explicitly need splay trees ?
wow, I'm amazed at your intelligence, the speed you have in solving codeforces problems is wow too, it doesn't even seem you need to think hard about them at all
Great tutorial David. I had two questions though. 1) Since treaps are randomized, what would be some safe constraints in contest problems for which treaps won't reach a height much worse than log(N) and timeout due to that? 2) Since the left to right order is preserved, I guess the relative order of any split up treaps of a larger treap cannot be changed while merging as it won't remain a BST. So I was wondering is there any efficient way to shuffle the order of the elements in a segment (like cyclically shift the segment right by 1) and do range queries on the modified order of elements? EDIT: Nvm about 2. To cyclically shift l...r to one right, we can just mirror l..r and then mirror l+1...r
You don't need to maintain the BST property either. The left to right order is only based on how you merge things, the example in the beginning was just to explain why it was randomized. As for constraints, you're probably safe up to about 2*10^5 but you might need a big time limit depending on how costly your internal operations are.
@@SecondThread Oh okay. But now if we don't maintain the relative order, isn't it possible that the height of the tree changes from logn to something much worse over a lot of queries? For example, if we have n updates where we split treap T at first n - 1 positions getting T1 and T2 as the new treaps and then merge in the order T2 and T1 to form T again, wouldn't this become much worse than logn height eventually? EDIT: Solved the gym contest's A problem. I guess it doesn't.
The video is awesome.Clearly understood the concept. @second thread could you please provide solutions for codeforces 678 div2 round. It would be really helpful.Thanks in advance.
Hey brother if possible please make video on codeforces round 679(tecnicup once) specifically problem C div2 Perform Easily Kind of hard to understand from Tutorial part✌️ thank you
can treap do stabbing queries like segment tree? which is the problem that requires splay and not treap? why have the two children as `vector` rather than `Treap *left, *right` ?
1) What's a stabbing query? You can do a range query of width 1 if that's what you mean 2) Nothing with a splay tree is *impossible* with a treap, but some things are a log factor slower. An example of this is implementing a Link Cut Tree. That's like the main and only one I know of. 3) So that you can flip left and right really easily. If you access your kids as kids[0^flip], this will always access the *left* kid even when you need to propogate a flip still.
Awesome video! Thanks David! What laptop do you use? Is this the surface pro? Love how you can draw ideas and diagrams out to help you visualize difficult concepts.
I actually use a desktop and have a cheap drawing tablet on from Amazon. It doesn't have a screen or anything, so I'm looking at my monitor, but my hand is just on my desk
Just a general guestion about Java: why do you, while doing competitive programming, put all methods to static? Wouldn't be simpler to just run an instance of the class in the main method and then not need to set everything to static (or is the execution faster with everything on static?).
Yeah, it might be shorter to code. Conceptually I like to save objects for when they are actually in an object of something though; it just makes more sense to me.
I think he is. Even I find him mind boggling quick in seeing through the problem to the solution. And watching him in action inspires me to atleast try to emulate it. Feels similar to how I felt after watching the movie and tv series "Limitless".
I'm sorry! Ur MERGE explanation wasn't understandable at all! U shud've used names to the nodes, or some other style to narrate. U were talking about priorities but u didn't assign any priorities to the nodes while explaining the concept (as an illustration). I hope I'll understand better while watching ur code section.
The mirroring portion outside was an extremely nice touch.
What a day to be alive. Can't wait to watch!
Thank you David for all the effort you put in making solution videos, screencast and lectures.
Just a small suggestion or I should say Request,
Kindly do lectures on not so advanced stuff with questions. Just like what you did for tree algorithms(problems on gym + explanation later), that was really helpfull.
It would be really great if you could do for other topics as well(not so advanced topics) which can be helpfull and at the same time, frequently used in cf contests.
Topics like:-
Dp with bitmask
Dp on segments
Some dp problems which can be solved with recur + memo
Graphs
Tree dp
Array problems increasing decreasing subsequence types.
Etc
Some gym questions + explanation later would be Great, just the way you did for tree algorithms.
Thank you so much
Had this resource be available in my good ol' ICPC times 🔥 hahaha nice job!
Ohh Holy, I was wandering everywhere to understand this topic since months, pls do take some problems and pls let us walk through the code step by step ❤️
Great video SecondThread! Really looking forward to using treaps in my upcoming contests! :^)
Your videos are both funny and interesting. I absolutely love them!
Looking for a good treap tuto long ago. Nice video and gonna check out the problems! Thanks
I have been waiting to learn one of the balanced search trees and treap seems like a good starting point, I will be thankful if you can mention that case you talked about where you might explicitly need splay trees ?
Thanks for this great tutorial and codeforces problem set , appreciate what you are doing
8:43 Why will it get splitted into 1/3 and 2/3 on average?
You're the best I hope and one day compete with you why I know what will happen Nothing is impossible
wow, I'm amazed at your intelligence, the speed you have in solving codeforces problems is wow too, it doesn't even seem you need to think hard about them at all
"Host" David Harmeyer. Woooaahhhh, hold up
Tbh, I was kind of scared when you brought that axe!:)
Loved the video awesome!
He haven't uploaded yet 😂
@@tanishqgupta1071 doesn't matter my comment would have been same.
@@nuni_boyka7869 SecondThread orz
Sir please attend the Div 2 round🥺.Missing your post contest explanations now a lot.
Hey good morning.. 😊
Great tutorial David. I had two questions though.
1) Since treaps are randomized, what would be some safe constraints in contest problems for which treaps won't reach a height much worse than log(N) and timeout due to that?
2) Since the left to right order is preserved, I guess the relative order of any split up treaps of a larger treap cannot be changed while merging as it won't remain a BST. So I was wondering is there any efficient way to shuffle the order of the elements in a segment (like cyclically shift the segment right by 1) and do range queries on the modified order of elements?
EDIT: Nvm about 2. To cyclically shift l...r to one right, we can just mirror l..r and then mirror l+1...r
You don't need to maintain the BST property either. The left to right order is only based on how you merge things, the example in the beginning was just to explain why it was randomized.
As for constraints, you're probably safe up to about 2*10^5 but you might need a big time limit depending on how costly your internal operations are.
@@SecondThread Oh okay. But now if we don't maintain the relative order, isn't it possible that the height of the tree changes from logn to something much worse over a lot of queries? For example, if we have n updates where we split treap T at first n - 1 positions getting T1 and T2 as the new treaps and then merge in the order T2 and T1 to form T again, wouldn't this become much worse than logn height eventually?
EDIT: Solved the gym contest's A problem. I guess it doesn't.
Come on David ..come on 🔥🔥
Thanks.
The video is awesome.Clearly understood the concept.
@second thread could you please provide solutions for codeforces 678 div2 round. It would be really helpful.Thanks in advance.
C++ code was helpful
In C++, using a vector to store the nodes is faster than pointers.
My implementation: github.com/thallium/acm-algorithm-template/blob/master/code/DataStructure/Treap_split.cpp
That's pretty clean. I like the pass-by-reference so you don't forget to update your treap root
Goood morning everybody 😻😻although night is going on
Hey brother if possible please make video on codeforces round 679(tecnicup once) specifically problem C div2 Perform Easily Kind of hard to understand from Tutorial part✌️ thank you
Nice explanation! :)
very nice
Hey, what's up! Are planning to do solutions for last Techno Cup round 2021? If so, I can't wait to see that)
sir u are fine
Wow, thank you :3
can treap do stabbing queries like segment tree?
which is the problem that requires splay and not treap?
why have the two children as `vector` rather than `Treap *left, *right` ?
1) What's a stabbing query? You can do a range query of width 1 if that's what you mean
2) Nothing with a splay tree is *impossible* with a treap, but some things are a log factor slower. An example of this is implementing a Link Cut Tree. That's like the main and only one I know of.
3) So that you can flip left and right really easily. If you access your kids as kids[0^flip], this will always access the *left* kid even when you need to propogate a flip still.
Awesome video! Thanks David! What laptop do you use? Is this the surface pro? Love how you can draw ideas and diagrams out to help you visualize difficult concepts.
I actually use a desktop and have a cheap drawing tablet on from Amazon. It doesn't have a screen or anything, so I'm looking at my monitor, but my hand is just on my desk
@@SecondThread Interesting. Thanks David!
Just a general guestion about Java: why do you, while doing competitive programming, put all methods to static? Wouldn't be simpler to just run an instance of the class in the main method and then not need to set everything to static (or is the execution faster with everything on static?).
Yeah, it might be shorter to code. Conceptually I like to save objects for when they are actually in an object of something though; it just makes more sense to me.
Do more algorithms please
Please be my sensei David....orz....!!!!!
is it possible to get ur scanner class?
good everybody
YAYYAYYAYA
I thought the video said "meap"...whatever tho, good usage of time!
Please share your java template
"Finding daddy" hmm ok
how did you get so smart, are you naturally inclined
I think he is. Even I find him mind boggling quick in seeing through the problem to the solution. And watching him in action inspires me to atleast try to emulate it. Feels similar to how I felt after watching the movie and tv series "Limitless".
Bruh how tf do u do that palindrome problem
Yummy!!!
orz
I'm sorry! Ur MERGE explanation wasn't understandable at all! U shud've used names to the nodes, or some other style to narrate. U were talking about priorities but u didn't assign any priorities to the nodes while explaining the concept (as an illustration). I hope I'll understand better while watching ur code section.