Why am I getting TLE and WA

general
1

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

My Code

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

My code 1

My code 2

2

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.
CodeChef: Practical coding for everyone 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
3

For the second question your solution fails the case

10 10 1

10 10

Ans is 0

4

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.

5

My code 1 is giving 0 for it. But still wrong answer.

6

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