UNIONSET - A Simple Approach

editorial
, , ,
41

Hey! Can you help me here? I also thought on similar lines, but i am getting TLE, while your solution is an impressive 0.09s. Can you point out the mistake?

https://www.codechef.com/viewsolution/14226695

1 Like
42

Your solution is not O(n * totalLen). It’s O(n^{2}*k). Observe that ind vector stores k-1 elements in worst case. And in the else statement, for every i + 1 to n, you are iterating ind vector each time. Which gives complexity of O(n^{2}*k). If ind vector stores positive elements:

if(arr[i][j]==1)
{
  ind.push_back(j);
}

then it would be O(n * totalLen).

And as a side note, never use

arr[n+1][k+1]={0};

arr may not be initialized by 0 completely. I guess only arr[0][0] will be initialized to 0.

1 Like
43

looks good ^^

44

Thanks for your feedback! I see, i missed things in implementation. Thought process was same, but yes, i was at fault in implementation. I will make sure to give it another shot with your explanation in mind, THANKS!! :slight_smile:

(Regarding array, i heard it gives a warning but initialises elements to 0. Nonetheless, its better to avoid risky things, undefined behaviour in program is a HUGE headache to debug…)

45

@vijju123 Nope, it doesn’t initialize all elements to zero. You can check here: Sv7wK2 - Online C++0x Compiler & Debugging Tool - Ideone.com

I believe there was discussion on this in codeforces.

1 Like
46

Thanks for the reference! I will keep that in mind in future!! Thanks again dear :slight_smile: