Binary Lifting

Someone please suggest some practice problems on the topic “Binary Lifting”.

ROOTLESS

Finding kth ancestor of a node in a tree is very important use of binary lifting :slight_smile:

BARCEP problem has a part which involves binary lifting(kth-ancestor…) …(it is from October Long Challenge-2019)
.
Edit:-Link:–>https://www.codechef.com/OCT19A/problems/BACREP

3 Likes

I solved this problem during the long challenge using binary lifting and segment trees, but don’t you think the binary lifting part is too less for this problem to be considered as a practice problem for it. This problem requires coming up with other ds tricks and observations as well.

Better start with this recent one : https://www.codechef.com/COFN2019/problems/CFD020

1 Like

I agree with you, it was just on the top of my head!

Yeah, it’s a good problem.
I suggested that problem instead because on some other thread I can see someone confusing binary lifting with only being used in trees. But it’s a very general concept. I’ve seen lot of coders ignoring stuffs related to graphs and trees in their early phase (even I used to), so it’s better to introduce as many as concepts in more general way so it appears less scary.

Good to see that you are quite active on discuss. :slight_smile:

1 Like

Thank you for the suggestions !!

2 Likes