At 10:58 the binary number is 100 and you are jumping for the second bit even though it's not set. I didn't understand that. Don't we have to jump for a bit only when it is set ?
Once we initially bring the 2 nodes to the same level, can't we use binary search to find the LCA? Because it seems that there's a monotonic property in the search space. Let's say LCA is at height h from the 2 updated nodes. We know that if we check for parents at height h' >= h from the 2 nodes, they will always be equal, whereas for height h' < h, they are never equal. So, this way we could binary search to find the largest h' for which the parents are unequal, and then jump to those nodes. This process should take O(log log n) since the list of parents at heights 2^x is of size O(log n). I'm not sure about the overall complexity right now, but does this seem viable at all?
When the difference of height is 7 between the two nodes than how do we reach the seventh node? also what is the meaning of parent[node][0] ......... is the immediate parent of the node? another thing is that if the answer to above question is true than what is the meaning of parent[node][1] ?
@@gkcs yes, using dfs for decomposing the graph and segment trees for finding minimum level.BTW your videos explanations are lucid .Can u do more on system design.thanks www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/
Everybody is asking for a tutorial for PISHTY AND TREE but I would like you request you to post the tutorial of TWO COINS instead simply because it isthe coin problem that has to be implemented on dynamic programming on Trees where as the pishty problem is based segment tree which you covered earlier (even peristence one) BTW this is a nice tutorial
Hi, Nice video. Can you add links to some problems that uses LCA and not complicated topics like HLD? That would give a chance to practice LCA alone first and then other topics
What if A or B is the LCA of (A, B) means if B is a sub child of A, then when you make both at the same level, you are actually pointing both to the LCA. Now, second part also terminates as no jumps would be there to make giving us a wrong answer. I think invariants are not properly managed in this algorithm.
Hi Gagan, thanks for pointing that out. :-) Yes we should check if the two nodes are the same after bringing them to the same level. If so, return the node itself.
does this approach work on non-binary trees? and for that matter does it extend to directed acyclic graphs? I’m just now learning about LCA and binary lifting
i am looking for an algorithme that calculate LCAS{a,b,c,d} for example where a, b,c, d are nodes of a directed graph (and not a tree) I know thatLCA(a,b,c)=LCA(LCA(a,b),c) but the LCA(a,b) in a graph could be a set of node ( but in a tree it is a single node) and this complicate the algorithme. do you have any idea or links that could help me
We make sure that the two nodes never jump to the same node. That would be impossible to come back from. We know the level at which p and q are when we start jumping. So after making as many jumps as we can while maintaining this condition, they up just one level away from their lca.
Hey, Consider the difference between two nodes, A and B, whose LCA is needed to be found, which have a difference of diff in their levels (or depth), then the first thing we do is make that diff zero by going up to the diff'th parent of A (assuming depth(A)>depth(B)). So if diff = 14 = 1110, then we first go 8 steps up, then 4 steps from there, and then go up 2 steps again, from there. Cool. We're looking at th MSB, of the diff, and then removing it from the diff. But _what if_ we go the other way? From LSB to the MSB. The total would remain the same, and it gives us the benefit of fenwick trees like traversal. That is, we can simply find the LSB by diff&(-diff), and remove it by diff-=diff&(-diff). The problem with MSB to LSB path is that it might lead to more bugs. You first calculate the MSB by floor(log2(diff)), and decrease it by diff-=(1
Hello Sir Nice Video again. Can you please help me with the recurrence relation. int par_rec(int ele,int h) { if(h==1) { parent[ele][1]=pp[node]; } if(parent[ele][h]!=-1) { return parent[ele][h]; } parent[ele][h]=par_rec(parent[parent[ele][h/2]][h/2],h/2); /*for(int i=1;i
loved the explanation bro. scratching the youtube but finally found a gem here
I don't understand your explanation from 4:24 to 5:00. Can you please elaborate.
At 10:58 the binary number is 100 and you are jumping for the second bit even though it's not set. I didn't understand that. Don't we have to jump for a bit only when it is set ?
+Vaibhav Pal Have a look at Vaibhav's comment. I have answered it there now :-)
Once we initially bring the 2 nodes to the same level, can't we use binary search to find the LCA? Because it seems that there's a monotonic property in the search space. Let's say LCA is at height h from the 2 updated nodes. We know that if we check for parents at height h' >= h from the 2 nodes, they will always be equal, whereas for height h' < h, they are never equal. So, this way we could binary search to find the largest h' for which the parents are unequal, and then jump to those nodes. This process should take O(log log n) since the list of parents at heights 2^x is of size O(log n). I'm not sure about the overall complexity right now, but does this seem viable at all?
This is called binary uplifting right?
Yes, I have seen that term being used earlier. Binary Uplifting it must be.
Its Binary lifting
When the difference of height is 7 between the two nodes than how do we reach the seventh node?
also what is the meaning of parent[node][0] ......... is the immediate parent of the node?
another thing is that if the answer to above question is true than what is the meaning of parent[node][1] ?
we can solve these by segment trees which is easier and takes logn time per query
It's not easier. This is an important part of Heavy Light decomposition and other algorithms 🙂
@@gkcs yes, using dfs for decomposing the graph and segment trees for finding minimum level.BTW your videos explanations are lucid .Can u do more on system design.thanks
www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/
Thank you!
Everybody is asking for a tutorial for PISHTY AND TREE but I would like you request you to post the tutorial of TWO COINS instead simply because it isthe coin problem that has to be implemented on dynamic programming on Trees where as the pishty problem is based segment tree which you covered earlier (even peristence one)
BTW this is a nice tutorial
Why this way of finding LCA is used in hld and not the way using euler toor and RMQ, is that just because of lesser number of lines of code ?
Once again excellent work!!
Thanks Deepak!
Hi, Nice video. Can you add links to some problems that uses LCA and not complicated topics like HLD? That would give a chance to practice LCA alone first and then other topics
Please make tutorial on Pishty and Tree.
Looking into it :)
What if A or B is the LCA of (A, B) means if B is a sub child of A, then
when you make both at the same level, you are actually pointing both to the LCA.
Now, second part also terminates as no jumps would be there to make giving us a wrong answer.
I think invariants are not properly managed in this algorithm.
Hi Gagan, thanks for pointing that out. :-)
Yes we should check if the two nodes are the same after bringing them to the same level. If so, return the node itself.
does this approach work on non-binary trees? and for that matter does it extend to directed acyclic graphs? I’m just now learning about LCA and binary lifting
What about the algorithm to calculate the LCA of many nodes in a graph? do you have any idea of how to implement it?
Have a look at Centroid Decomposition
i am looking for an algorithme that calculate LCAS{a,b,c,d} for example where a, b,c, d are nodes of a directed graph (and not a tree)
I know thatLCA(a,b,c)=LCA(LCA(a,b),c) but the LCA(a,b) in a graph could be a set of node ( but in a tree it is a single node) and this complicate the algorithme. do you have any idea or links that could help me
Your code is totally different than the concept you are telling here , dp is not created in the same way for example!!
at last how we are deciding jumps? means how we know that the jump does not going to exceed the required LCA or vice-versa?
We make sure that the two nodes never jump to the same node. That would be impossible to come back from. We know the level at which p and q are when we start jumping. So after making as many jumps as we can while maintaining this condition, they up just one level away from their lca.
thanks i got it and no doubt once again a great video :)
Do you have a video on generics ?
Not yet :)
So is there a significance of 1 or 0 in the binary representation?
+Vishal Anand Only when putting the nodes on the same level. Not when moving up the tree after that.
least common ancestor in graphs having cycles?
Does that make sense to you? 😛
Ancestor of A is B. If they are in a cycle, we could also have ancestor of B is A.
So this means Pishty and Tree problem editorial is underway :)
I guess it wasn't :/
Nice explanation.. Would be amazing if you could do a video or more on Binary Indexed Trees and Suffix Trees!
I will be talking a about Suffix trees in the near future :-)
very nice explanation...thank you....
Hey,
Consider the difference between two nodes, A and B, whose LCA is needed to be found, which have a difference of diff in their levels (or depth), then the first thing we do is make that diff zero by going up to the diff'th parent of A (assuming depth(A)>depth(B)). So if diff = 14 = 1110, then we first go 8 steps up, then 4 steps from there, and then go up 2 steps again, from there.
Cool.
We're looking at th MSB, of the diff, and then removing it from the diff.
But _what if_ we go the other way? From LSB to the MSB. The total would remain the same, and it gives us the benefit of fenwick trees like traversal. That is, we can simply find the LSB by diff&(-diff), and remove it by diff-=diff&(-diff).
The problem with MSB to LSB path is that it might lead to more bugs. You first calculate the MSB by floor(log2(diff)), and decrease it by diff-=(1
Hello Sir Nice Video again. Can you please help me with the recurrence relation.
int par_rec(int ele,int h)
{
if(h==1)
{
parent[ele][1]=pp[node];
}
if(parent[ele][h]!=-1)
{
return parent[ele][h];
}
parent[ele][h]=par_rec(parent[parent[ele][h/2]][h/2],h/2);
/*for(int i=1;i
Thanks a lot, really useful
Thanks Subhadip!
Thank you so much man!
Thanks Diman!
complete code: goo.gl/uhtFUf
incoming pishty and treeeeee
Haha, hopefully soon :-)
thanks bro
anyone here for C4? just give up already :)
Thank you very much bro, I have been reading the editorial for 2 hours but could not understand.
Excellent Job!!!