I didn’t do anything special to handle such a case, and when I tested my solution on a test case constructed like this with N and M both in the order of 1000, it ran for more than two minutes and I had to quit it eventually… So I’m pretty sure my solution is N^2*M^2. Yet, it passed with 100 points in the contest which may mean the test cases were weak?
agree… I found it medium…
Update: You are correct @akamoha. The test cases were weak. Thanks for a similar test case. Have updated the editorial with a warning too.
can you share the input file ? (like on a G drive or dropbox)
This pointed out in the editorial. Please check again.
ya, seen that, thank you!!
I will have to ask the Codechef team and author to share the counter test case.
Union-find algorithm works in amortised O(n) only if it is implemented by “Rank” algorithm, i.e. merging smaller sets to larger ones. But in practice, even random merging works fine and it is tough to generate a test case against it.
2 Likes
i converted editorialist’s solution to java Code… but in java same code is giving TLE… Here is link:- CodeChef: Practical coding for everyone
You may want to check out my code xD
You can optimise the code. Obvious things are reducing function calls, replacing Math.max() etc. by ternary operator. Also, remember that usually, constant associated with hashing is high. You can have a look at my code for reference.
1 Like
I was talking about akamoha’s test case, the one which is mentioned in the comment above.
We perform one DSU per edge and reset only those values that have been affected when processing a set of edges.
Yeah, you are right.
Corrected.
@smartnj, you are correct. My implementation would give TLE, because I traverse each component the number of elements it has in it. Thus the test case provided above have similar idea where a lot of 1's are clustered close to each other.
getWho is the “find” while who is the “parent” array compared to the usual DSU implementation.
Hi @akamoha, Could you please elaborate on how you determined the worst case to be O(n^2 * m^2) considering this particular case? Also if you could explain a little bit about how the editorialist’s initial estimation was 8mn? Thanks!
1 Like
hi @smartnj , i don’t know why but when i submitted same solution of yours , i am getting tle in some of the cases , is it happening because of constant factor or is the time complexity analysis wrong ?