I am getting TLE for this . The approach is union find algorithm and everyone else’s similar approach got AC.

Also, for this , I am getting WA. It works for all my test cases but I am not able to find the problem.

I am getting TLE for this . The approach is union find algorithm and everyone else’s similar approach got AC.

Also, for this , I am getting WA. It works for all my test cases but I am not able to find the problem.

while doing union find you are supposed to have the length of the set as small as possible.

in your worst case you may be merging two sets like this

1->2->3->4->5->6

thus when you have to find the parent of 1 you have to traverse through 5 elements

but optimally you can do

1------>2,

3------>2,

5------>2,

etc…

thus your find() will take O(n) time when it should be done in O(log(n)) time

This can be done by also storing an extra variable as the height.

http://www.codechef.com/viewsolution/6046989 This is my solution. In the pair I have stored the first element as the parent and the second element as the height.

1 Like

For the second question your solution fails the case

10 10 1

10 10

Ans is 0

Sorry, I didn’t get you. I understood the part where my code runs in O(n) but but how to change it to O(log n). Please clarify a little bit.

finally AC. Took me a long time to focus on this one