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

crux of the solution is same, thanks anyways !

4

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

5

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:

6

My approach is little different link to solution

1 Like
7

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

8

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
9

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
10

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

1 Like
11

Probably O(k*N^2)

12

"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
13

Link…AC in one go!!!

14

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

15

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.

16

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

17

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
18

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

19

Awesome solution man :slight_smile:

20

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.