UNIONSET - A Simple Approach

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

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 : CodeChef: Practical coding for everyone

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

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

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.

A basic brute force kind of approach worked as well. here is the solution.

Can anyone please tell me how to increase karma points? I can’t even ask questions :frowning:

crux of the solution is same, thanks anyways !

Yea I was surprised too that this can be accepted in o(kn2), infact o(kn2) doesn’t work if you don’t take set length into consideration. :stuck_out_tongue:

I see that you are maintaining a max variable throughout check whether it equals k, nice one mate !

I’m confused for that too, it’s just that i was trying many solutions and this was what worked for me.

1 Like

Probably O(k*N^2)

Thanks for the suggestion, I’ll make the adjustments, new to posting solutions so bear a bit. :slight_smile:

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.

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

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

Awesome solution man :slight_smile:

Amazing solution~

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

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.