UNIONSET - A Simple Approach

editorial
, , ,
21

Another O(N^2 K) solution using set_intersection in C++ STL https://www.codechef.com/viewsolution/14006485

22

Amazing solution~

23

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

24

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.

25

Using a 2D array is a great idea, I had the logic correct, but was using Javaā€™s inbuilt Set operations, which TLEā€™d. Thanks for the editorial

1 Like
26

No problem mate :slight_smile:

27

one of the simple approachā€¦!
just declare the 2D array arr[n][10000] to store your elements with initializing all elements to zero,
as the array is of size n,10000, you can store values at their index positions which make searching of element easy.
now as we have to just search for the union of k, fix your ith row and see which elements are not there in that row, store those values of k which are not there in an ith row and search them in a jth row, for ex-taking 3rd test case
3 1 2 3
4 1 2 3 4
3 2 3 4
an ith row is 1 row so u have to search for 4 in j rows (that too on just index arr[j][4] if you found that value here increase your count else break and move to next row)
hereā€™s the soln https://www.codechef.com/viewsolution/14131774

28

I computed the bit vector associated with each set in decimal and then used the OR operator. Similar to @deepak_13 apprroach. However I still got TLE. Can someone please look into my code?
https://www.codechef.com/viewsolution/14229632

29

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

30

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

31

Right, inbuilt STL functions suffices too ^^

32

One Another Approach
just invert the set like if set contains 1 2 then in inverted set 1 and 2 should not present and vice versa then question will change to number of pairs of set such that their intersection(BITWISE AND) gives 0 ā€¦this can be done by trie ā€¦

My Solution : https://www.codechef.com/viewsolution/14020287

33

Iā€™m new here and want to ask questions. Can someone upvote my answer, so I can reach 3 karmas?
Also here is my solution in CPP for the problem. Thanks! :slight_smile:

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

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t,n,k;
	int i,j;
	cin>>t;
	while(t--)
	{
		int ans = 0;
		cin>>n>>k;
		vector<vector<long int>> make_pair(n);
		for(i=0;i<n;i++)
		{
			int num,curr;
			cin>>num;
			for(j=0;j<num;j++)
			{
				cin>>curr;
				make_pair[i].push_back(curr);
			}
		}
		int check = (k+1)*k/2;
		for(int i=0;i<n;i++)
		{
			vector<bool> done(k+1,true);
			int sum=0;
			for(auto j:make_pair[i])
			{
				done[j] = false;
				sum += j;
			} 
			for(int j=i+1; j<n; j++)
			{
				int sum2 = 0;
				for(int k=0; k<make_pair[j].size(); k++)
				{
					if(done[make_pair[j][k]]) 
					    sum2 += make_pair[j][k];
				}
				if((sum2+sum)==check)
				    ans++;
			}
		}
		cout<<ans<<"\n";
	}
}
1 Like
34

Isnā€™t this: if !(sets[i]||sets[j]) supposed to be: if !(sets[i][y]||sets[j][y]) ? to check the yth bit of the ith set?

1 Like
35

Right, thanks for pointing that ^^

36

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 https://www.codechef.com/viewsolution/14243805

37

Redirect your question here- https://discuss.codechef.com/questions/97820/i-want-to-ask-a-question-ask-them-all-here

Asking for upvotes is against rules.

1 Like
38

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
39

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
40

Its very disappointing, I wrote my code in python. My solution was O(total_length * (K/50)). Still it was TLE,
Only in C++ it works fine i guess. @admin Please look into the testcases constraints and set the limit based on the language used as well. Same solution might take different time in different languages. Just having hard limit of C++ x time, java 2x time, python 3x time is not going to work.