UNIONSET - A Simple Approach

editorial
, , ,
4

My approach is little different link to solution

1 Like
5

Could someone please explain the time complexity of this approach? I could see that the constraint “1 ≤ len1 + len2 + … + lenN ≤ 10000” and the condition “if k<= length[i] + length[j]” is related. But how do you infer from the constraint that using such a if condition will pass the time limit?

1 Like
6

Here is my approach : Link.
I just represented each bit vector into integer number and did an OR operation to get the answer.

2 Likes
7

"Basic Logic" doesn’t explain why solution is quick even though it runs in O(N^2K). Editorial should have explained that this solution only works because of the constraint: 1 ≤ len_1 + len_2 + .. + len_N ≤ 10000

2 Likes
8

Link…AC in one go!!!

9

It can be solved in O(n * totalLen). This the main idea:

    int c[2505];
    int res = 0; // final answer
    for(int i = 0; i < n; ++i){
       for(int j = 0; j <= 2500; ++j){
          c[j] = 0;
       }
       for(int l = 0; l < a[i].size(); ++l){
          c[a[i][l]] = 1;
       }
       for(int j = i + 1; j < n; ++j){
          int c1 = a[i].size();
          for(int l = 0; l < a[j].size(); ++l){
              if(c[a[j][l]] == 0){
                 ++c1;
              }
          }
          if(c1 == k) ++res;
       }
    }

Runtime: 0.09s

Memory: 3.2M

Complete solution: https://www.codechef.com/viewsolution/14155554

5 Likes
10

I tried to use Java BitSet with the Basic Logic included, But it was giving a TLE. Here is the link to that submission.

I also tried @ayushagg solution approach (merging the subsets because they are sorted) in Java again, this was also giving a TLE. Here is the link.

I think these implementations works only with C++. There might be a better approach.

11

Another O(N^2 K) solution using set_intersection in C++ STL CodeChef: Practical coding for everyone

12

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
13

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

14

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

15

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

16

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
17

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
18

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.

19

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

20

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

21

crux of the solution is same, thanks anyways !

22

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:

23

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