UNIONSET - A Simple Approach

editorial
, , ,
#1

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: admin2

DIFFICULTY

EASY

PROBLEM

Given N sets whose elements range from 1 to k, find the number of pairs among those N sets which contain all elements ranging from 1 to k.

EXPLANATION

This solution only runs due to the constraints: 1≤len1+len2+…+lenN≤10000
This problem can be solved by making pairs among only the ones whose sum of set length is greater than k in a boolean 2D vector.
For each input set mark the values as true from 1 to k which are appearing in the set, refer below pseudo code.

    2D vector sets
	vector length  
	for(i from 1 to k){
		input length of set and push this length in length vector
		bool vector temp
		for(j from 0 to len){
			input individual set element
			set the corresponding index as true in temp vector
		}
		push the temp vector in sets
	}

We will now have a 2D vector representing all the sets.

Input part in complete!
Now all that remains in the problem is to make pairs among different sets of only those whose sum of length of sets exceeds or equals k since only then there is possibility of having the union equal k elements. (basic logic :P)

Pairs are made!
Now for each pair we need to check whether their union will contain all the elements ranging from 1 to k.
With each pair what we do is iterate from 1 to k and check whether at least one of those set has a set bit in each iteration, if not we strictly break as that element is not present in both the set and thus the pair we chose can never have all k elements.
If there is no such condition where both chosen pairs have false bit then all elements are present from 1 to k in the union of the chosen pairs and thus we increment our answer count!
Refer pseudo code below on how to check for each pair

bool check = true
for(i from 0 to n-1)
   for(j from i+1 to n)
      if k<= length[i] + length[j]
         for(y from 1 to k)
             if !(sets[i][y]||sets[j][y])
                check = false
         if check
            ans++

Feel free to share your approach below !
If you forget to take into account the set length vector, it will result in exceeded time

SOLUTION

My AC
Execution Time: 0.21 s
**Memory:**3.3M

3 Likes
#2

another simple approach…done using adjecancy matrix !!
here is d link to my code …https://www.codechef.com/viewsolution/14055300

1 Like
#3

disappointing … i spend last 4 days to figure out how to do this question in o(n2)

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

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

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

#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: