### PROBLEM LINK

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