UNIONSET - A Simple Approach

editorial
, , ,
27

To solve the general case, you need something like deepak_13’s solution, by representing each set as bits and performing efficient bitwise OR to achieve O(N^2\frac{K}{32}) time.

28

Yea i followed that, looked more effecient, that’s why i asked for suggestions to know a better solution than mine.

29

Update:
the solution only works since k<=sum of lengths of all sets.

30

Awesome solution man :slight_smile:

31

Amazing solution~

32

My second method seems to be wrongly implemented. Please ignore it.

33

The approach that works in c++ will definitely work in java. Having said that, I think addition to bitset is costly and thus exceeding time.

34

No problem mate :slight_smile:

35

Be mindful of using Java Scanner, gives a lot of overhead when reading large input. Try using BufferedReader or similar.

36

Try a faster input method for all competitive questions as we need to be cautious of not exceeding the time constraints.

37

Right, inbuilt STL functions suffices too ^^

38

Right, thanks for pointing that ^^

39

I am trying to code a O(n^2*k) C/C++ solution using scanf for reading inputs. Still it is passing the small test cases, and TLE for large inputs. Please help me find where the performance issue is. Here is the link to latest solution CodeChef: Practical coding for everyone

40

Redirect your question here- "I want to ask a question" - Ask them all here! - meta - CodeChef Discuss

Asking for upvotes is against rules.

1 Like
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: