UNIONSET Doubt

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.

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

Probably take a bit vector or array to make insertion and escape from extra set insertion time.