Hi
I am getting TLE using this solution for this codeforces question.
I have used union find and getting TLE for nodes = 200000 and edges = 50000.
Isn’t the complexity for union find O(n), why am I getting TLE ? How do I improve its complexity?
Somebody please help.
Use UNION-FIND with Rank and compression techinique.
But I have done that only, haven’t I?
why? i’ve used a straight up recursive dfs and i have used this in several questions earlier also, it never has created problem.
also it’s not getting WA, it’s TLE, and the DFS is taking O(nodes) only.
i think do_union has to be optimized but i have already used path compression with rank and not able to understand what to do now
In the loop in which you are traversing minmax, you have another loop inside it which traverses from the minval to maxval, this part is causing TLE as you are approaching a time complexity of O(n^2) due to this. Consider you have components whose min max values are (1,7), (2,4), (5,10), then for 1,7 you traverse all the numbers from 1 to 7 and you do this for each min max pair, you can see that this will result in O(n^2) time complexity.
5 Likes
thanks a lot for this clear explanation!!!
finally got it.
1 Like
@raunaqroxx i tried implementing that but i’m getting TLE on a case but rest all cases are passing in this code. If I uncomment the commented code I get accepted otherwise I get TLE on test with n=200000, m = 50000.
Although it’s not TLE for several cases with n= 200000 and m =200000.
Can you please help with that?
Umm, you still have some nested loops but if they are working on every test case except the most extreme one, I think it is not resulting in O(n^2), so a normal tweak to save TLE you can do is, that while traversing maxmin vector, in the for loop do not write i<maxmin.size(), instead store the size in a variable and use that variable, because calling this function again and again causes TLE sometimes.
Not really related to your question but a better way to solve this problem using DSU would be to simply iterate from vertex 1 to n-1, and increment answer by 1 everytime
find_set(i)>i+1 and find_set(i)!=find_set(i+1)
You can check out my solution.
1 Like
Okay i saved the size in a variable and also removed the sort function as it was redundant, here is that solution, still its ending up in TLE for that one case and has 0 improvement in time for other cases as well.
Also apart from that 1 TLE there’s a case on which it is running in 975ms.
I am not able to understand why it’s taking so much time when after this implementation it should be O(n) only, and n is also less than 2*1e5 plus there are no test cases.
thanks for sharing.
pretty elegant way of traversing in a go and setting parent as larger node which doing union.