LCA - Lowest Common Ancestor
Вставка
- Опубліковано 5 кві 2021
- Tutorial on LCA algorithm. We use Binary Lifting to get O(N*log(N)) preprocessing and O(log(N)) to find the lowest common ancestor of two nodes in a tree.
Binary Lifting video • Binary Lifting (Kth An...
SPOJ problem www.spoj.com/problems/LCASQ/
code github.com/Errichto/youtube/b...
Two homework problems:
1) Answer queries "find distance between two given nodes U and V" cses.fi/problemset/task/1135
2) Given a tree with weighted edges (i.e. every edge has some value), answer queries "given two nodes U and V, find minimum weight along path U-V". (I don't have a source for this one).
Coding live streams - / errichto
FAQ - github.com/Errichto/youtube/w...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](http://i.ytimg.com/vi/vZxxksAP8yk/mqdefault.jpg)
Here are two homework problems for you:
1) Answer queries "find distance between two given nodes U and V" cses.fi/problemset/task/1135
2) Given a tree with weighted edges (i.e. every edge has some value), answer queries "given two nodes U and V, find minimum weight along path U-V". (I don't have a source for this one).
Oh, I tried to solve 1-st problem with python3, looks like I get it right, but on big input I stucked with TIME LIMIT EXCEEDED. But in Statistics sections I saw an accepted python solution. Any tips to speed up python code to fit into 1 second timeout?
I am already:
1) Used collections.deque for dfs
2) Used array.array for up (partially), parents and depth arrays.
3) sys.stdin.readline() instead of input()
I will appreciate any help!
@@pycz I did with C++. 2 or 3 were getting TLE. It's probably because i/o is slow. I added these three at start of main function.
1.) ios::sync_with_stdio(0);
2.) cin.tie(0);
3.) cout.tie(0);
in C++ and got AC. There'll be something similar to that in Python also.
Is the second question a little bit like Sparse Table (RMQ)? But complexity for each query will be O(Log(N)) only because we still need to find the LCA. Am I right?
@@pycz I got TLE with Java as well on the big inputs, but when I ran it locally I got the correct result. I tried using an iterative rather than recursive DFS but it still TLE's. I'm just going to assume it's an issue with reading the inputs because I have implemented the actual algorithm itself correctly and it produces the correct result (I'm using BufferedReader and PrintWriter).
Errichto should be in the UN protected list ❤.
😀❤️💯
Generally, it is difficult to learn from extra-ordinary people like you. But you are exception to that also. Thank you so much.
After watching numerous errichto videos , whenever I explain my code to anyone else I get errichto's accent.
Your videos are awesome.
I am simple man , i see Errichto is teaching something i will click it
It's a great initiative by you to teach algorithms. Looking forward for more such great videos. Also add some more practice problems of whatever you explain.
Thanks for the lectures. I like this format a lot: short videos with explanation, code, and example.
YES! A THOUSAND TIMES YES! Thank you soooooo much for making a video on LCA!
Some of your videos(like this one) are so well made. Thnx🔥
I know how to do LCA with RMQ, but this solution is something else
I love it to bits 💚💚
This guy doing a god's work...whoever is the god of cp
Tourist
Thank you Kamil for such a great explanation, keep up the good work:)
The way you explained the binary lifting is just awesome ❤❤
Errichto one of the best, I love his videos.
Thank you i was searching for this after the binary lifting video 👍
Thank you for these videos. Keep on making them
your explanation is great, thank u
thank you so much I can finally solve the question on cses
hope more video like this from you
awesome explanation of LCA and Binary Lifting
Loved the explanation. Thanks a lot
I know that these problems are very easy for you but trust me these are very hard for me.
And if you are making it, I will watch it!. You are literal GOD in coding!.
Please keep on making these very basic videos on concepts, I really liked your Binary Search video as well!.
Thanks
Clear and concise. I love it.
Can't believe this still *F R E E*
This was the video which I wanted....thanks😊😊
I think these concepts are very easy for kamil....😅
Your contents are awesome ❤️
Thanks man. Astounded by your brain
His voice and explanation both are soothing🙂
You are an amazing teacher
Great content 🙌💯
Thanks you😊
Very Nice explanation. Thanks. Can you do a tutorial on heavy-light decomposition?
Thanks it was helpful.
Please do some tutorials on centroid and heavy light decomposition.
2 videos in a week. 🎉
The preprocessing of vector
He meant every query is answered in O(logN)
Thank you so Much
Absolute beauty
I am a beginner sir but really like your way hope i get green soon on cf
Good luck!
Thanks!
I love you bro u help me a lot
The j iterator should only go reverse order from Log -1 to 0 and not the other which works in binary lifting?
which compiler are you using in this video?
People have their own kind hero.I have you #the best❤️
Thanks :)
What about time/space complexity of this algorithm? Is it logN like in a binary search? I guess worst case is O(N) when first node is a root and second node is the deepest leaf, right?
We only have for-loops of size log(N) so it's O(log(N)) per query.
Preprocessing takes O(N*log(N)) space & time.
In the case of finding lca just once, doesn't this perform worse than the linear solution? Not only does it take extra space, but we do a linear DFS to pre process all parents and then find the lca
for small cases maybe, for larger ones the linear is worse
I have noticed one thing whicle actually coding for the problem. In the second loop, from LOG - 1 to 0, if we change this to 0 to LOG - 1, the program gives WA for soms tcs. Can someone explain why ? if the LCA is xth ancestor of a and b (after equalizing the depths), does it matter how we access the bits of x. It can be either fromt MSB or LSB. Please clear this concept.
0 to LOG-1 in last for loop will not work. Because we are moving both nodes one by one to the level just below the lowest common ancestor.
Let us call this level as 'Limiting level'.
Suppose, we have to make 2 jumps to reach limiting level.
As you start for loop from 0, you'll check for 2^0 jumps from initial position, then it is allowed (as they will not be equal) , therefore you will make jump. From that position, you can check for 2, 4 ,8... jumps. But we are just 1 jump away from limiting level.
Therefore we can not reach limiting level here, that is why it is not working.
I'm tellin y'all, this guy is friends with Megamind
May god bless you
can we move from lowest power to highest power? If not why?
Which drawing software is that...plz someone tell me
I am not able to get ideas quickly for simple adhoc problems of A B problems please suggest me some idea where to practicr for these ques.
Codeforces (div2&3, edu), Atcoder (ABC), Leetcode and basically all the platforms.
Thanks Errichto hope you win codejam this tym
im guessing your using a PC, can you share what you are using to
sketch, hardware and program?
github.com/Errichto/youtube/wiki/FAQ#hardware
You used to live in Suwałki?
what if last for loop goes form 0 to n-1
Nice :)
Geeeeezz...
COME TO BRAZIL !!!
is beutiful
hackercup T-shirt lol
Likes
T
Please heart me, i somehow arrived early