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
another simple approach…done using adjecancy matrix !!
here is d link to my code …CodeChef: Practical coding for everyone
1 Like
disappointing … i spend last 4 days to figure out how to do this question in o(n2)
My approach is little different link to solution
1 Like
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
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
"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
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
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.
Another O(N^2 K) solution using set_intersection in C++ STL CodeChef: Practical coding for everyone
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
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
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! 
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 