LCA - Lowest Common Ancestor

Рет қаралды 63,423

Күн бұрын

Пікірлер: 85

@Errichto 3 жыл бұрын

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).

@pycz 3 жыл бұрын

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!

@prakash_77 3 жыл бұрын

@@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.

@lakshyamittal3098 3 жыл бұрын

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?

@exe2543 2 жыл бұрын

@@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).

@allwell8570 3 жыл бұрын

Generally, it is difficult to learn from extra-ordinary people like you. But you are exception to that also. Thank you so much.

@coefficient1359 3 жыл бұрын

Errichto should be in the UN protected list ❤.

@teddq7210 3 жыл бұрын

😀❤️💯

@mukulkumar2316 3 жыл бұрын

After watching numerous errichto videos , whenever I explain my code to anyone else I get errichto's accent. Your videos are awesome.

@ksg7882 3 жыл бұрын

I am simple man , i see Errichto is teaching something i will click it

@sonugupta147 3 ай бұрын

The analogy with binary search was a great hint what we are going to do here. Thanks Errichto

@alexandruhritcan9727 3 жыл бұрын

I know how to do LCA with RMQ, but this solution is something else I love it to bits 💚💚

@saitejaballa6759 Жыл бұрын

The way you explained the binary lifting is just awesome ❤❤

@desyfer1709 3 жыл бұрын

This guy doing a god's work...whoever is the god of cp

@GGxEpsilon 3 жыл бұрын

Tourist

@hydroUNI 3 жыл бұрын

YES! A THOUSAND TIMES YES! Thank you soooooo much for making a video on LCA!

@ShubhamKumar-me7xy 3 жыл бұрын

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.

@prathamkumar2968 3 жыл бұрын

The preprocessing of vector

@pankaj2077 3 жыл бұрын

He meant every query is answered in O(logN)

@glaucoa.9214 3 жыл бұрын

Errichto one of the best, I love his videos.

@RajatSingh-dg8ov 3 жыл бұрын

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

@itz_me_imraan02 3 жыл бұрын

His voice and explanation both are soothing🙂

@iPaperPlane 3 жыл бұрын

Can't believe this still *F R E E*

@bethsuni4011 3 жыл бұрын

Thanks for the lectures. I like this format a lot: short videos with explanation, code, and example.

@darkknight98-v 4 ай бұрын

best video on lca on the internet!!

@josephwong2832 3 жыл бұрын

awesome explanation of LCA and Binary Lifting

@srishtikdutta8946 3 жыл бұрын

Please do some tutorials on centroid and heavy light decomposition.

@saiprasadduduka2155 3 жыл бұрын

Some of your videos(like this one) are so well made. Thnx🔥

@simone8504 3 жыл бұрын

Thank you i was searching for this after the binary lifting video 👍

@luizeduardoreis7657 6 ай бұрын

You are an amazing teacher

@BelalMoawadOfficial 3 жыл бұрын

your explanation is great, thank u

@sunnyrawat931 Жыл бұрын

Clear and concise. I love it.

@nguyentrongvanviet 2 жыл бұрын

thank you so much I can finally solve the question on cses hope more video like this from you

@shivanshsrivastava9264 Жыл бұрын

Loved the explanation. Thanks a lot

@cp_freak 3 жыл бұрын

I am a beginner sir but really like your way hope i get green soon on cf

@Errichto 3 жыл бұрын

Good luck!

@ahbarahad3203 25 күн бұрын

Did you achieve your goal ?

@cp_freak 24 күн бұрын

@@ahbarahad3203I am a semi-retired expert now😅 became expert 3 years back... trying hard to become CM😢

@patrykwronski8476 3 жыл бұрын

Thank you Kamil for such a great explanation, keep up the good work:)

@dtrade4787 2 жыл бұрын

Thanks man. Astounded by your brain

@ani68 3 жыл бұрын

This was the video which I wanted....thanks😊😊

@ani68 3 жыл бұрын

I think these concepts are very easy for kamil....😅

@abdullahzaghmout5615 3 жыл бұрын

Thank you for these videos. Keep on making them

@AniketSingh-mt6zr Жыл бұрын

Absolute beauty

@GGxEpsilon 3 жыл бұрын

2 videos in a week. 🎉

@prasenjitmondal673 3 жыл бұрын

Very Nice explanation. Thanks. Can you do a tutorial on heavy-light decomposition?

@spicefiend Ай бұрын

When doing the lifting part (after equalizing depths), can we loop j from 0 to LOG (noninclusive) instead of LOG-1 to 0? Related, when we jump up by 2^i ancestors towards the LCA, why do we have to decrement i by 1? what if the remaining distance is still 2^i away?

@teddq7210 3 жыл бұрын

Your contents are awesome ❤️

@gitanshgarg3146 3 жыл бұрын

Great content 🙌💯

@manojmaurya9683 3 жыл бұрын

People have their own kind hero.I have you #the best❤️

@Errichto 3 жыл бұрын

Thanks :)

@vigneshs8738 2 жыл бұрын

The j iterator should only go reverse order from Log -1 to 0 and not the other which works in binary lifting?

@satyampal7235 2 жыл бұрын

Thanks it was helpful.

@wow4669 2 жыл бұрын

Thanks you😊

@GauravKumar-ue7nz 2 жыл бұрын

Thank you so Much

@mzmzgreen 3 жыл бұрын

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?

@Errichto 3 жыл бұрын

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.

@ananyapamde4514 3 жыл бұрын

May god bless you

@Kyanqy_Tarb3r Жыл бұрын

which compiler are you using in this video?

@bahabouali6886 2 ай бұрын

sublime text i believe

@miku6701 3 жыл бұрын

I'm tellin y'all, this guy is friends with Megamind

@seaorz 3 жыл бұрын

Thanks!

@mizel_almizel 3 жыл бұрын

I love you bro u help me a lot

@ramsankar585 3 жыл бұрын

can we move from lowest power to highest power? If not why?

@anonymoussloth6687 2 жыл бұрын

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

@notwatermango 2 жыл бұрын

for small cases maybe, for larger ones the linear is worse

@pavankumar-cy6mg 3 жыл бұрын

what if last for loop goes form 0 to n-1

@sumitrohilla1494 3 жыл бұрын

Which drawing software is that...plz someone tell me

@alexamish2020 3 жыл бұрын

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.

@allwell8570 3 жыл бұрын

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.