link to question : https://www.codechef.com/JUNE17/problems/UNIONSET
My code gives only 40 pt for Unionset when i do it using set based approach in which i take union of two set
by putting element of both set in a single set(new set) and if size of set(new set) equals to K then i do
sum++ but it shows TLE
even when set insert take O(lg n).
On the other hand using hashing approach gives 100 pts .
Cant understand why set based approach is not working.
link to set based approach : https://www.codechef.com/viewsolution/14160598
link to hashing based approach : https://www.codechef.com/viewsolution/14160764
Time complexity : O(T*(N^2)*K)) (HASHING BASED APPROACH)
I faced the same condition when i did it that way.
Try adding a check to take union only when the sum of number of elements in the chosen pair of sets is greater than k.
I think this should work.
Insertion in a set takes logn for each element, so when you are inserting n elements, it will take logn time.
Your set based solution has a complexity of n^2*(summation of (len(i)log(len(i)))
which will give TLE for second case.
Probably take a bit vector or array to make insertion and escape from extra set insertion time.
This is because insertion and creation of new sets take time. In every interation out of N^2 iteration, you are building new set. So its complexity becomes more than N^2.
Here is my implementation similar to that of your 1st approach. LINK
1 Like