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

Errichto should be in the UN protected list ❤.

@teddq7210

3 жыл бұрын

😀❤️💯

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 💚💚

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

Errichto one of the best, I love his videos.

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

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

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

Thank you for these videos. Keep on making them

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

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

@GGxEpsilon

3 жыл бұрын

Tourist

your explanation is great, thank u

His voice and explanation both are soothing🙂

Your contents are awesome ❤️

Clear and concise. I love it.

Loved the explanation. Thanks a lot

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

@ani68

3 жыл бұрын

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

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

Great content 🙌💯

Thanks man. Astounded by your brain

Please do some tutorials on centroid and heavy light decomposition.

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

The preprocessing of vector

@pankaj2077

3 жыл бұрын

He meant every query is answered in O(logN)

You are an amazing teacher

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

@Errichto

3 жыл бұрын

Good luck!

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?

Thanks it was helpful.

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.

2 videos in a week. 🎉

Absolute beauty

which compiler are you using in this video?

Thanks you😊

Thank you so Much

Thanks!

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

@Errichto

3 жыл бұрын

Thanks :)

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

Жыл бұрын

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

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

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.

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

Nice :)

im guessing your using a PC, can you share what you are using to sketch, hardware and program?

@Errichto

3 жыл бұрын

github.com/Errichto/youtube/wiki/FAQ#hardware

May god bless you

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

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

You used to live in Suwałki?

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.

@Errichto

3 жыл бұрын

Codeforces (div2&3, edu), Atcoder (ABC), Leetcode and basically all the platforms.

@Harpreetsingh-qc8sf

3 жыл бұрын

Thanks Errichto hope you win codejam this tym

COME TO BRAZIL !!!

Geeeeezz...

Likes

is beutiful

hackercup T-shirt lol

T

Please heart me, i somehow arrived early