# BICLIQUE - EDITORIAL

Now i think about it, Is there any good way to solve this problem. I could not solve it though out the contest?

Your logic is wrong I think
Try the following case :
5 5 2
1 2
1 4
3 2
3 4
4 5

1 Like

The method specified in the editorial is really bad for Java, in terms of Time limit. Even after using Fast IO, it kept on giving TLE. In the end, deeper language-specific optimisations had to be used to get AC. Please try to keep less tight Time Limits next time, so that at least the correct solutions pass.

If this would have happened with me during the contest, it would have cost me quite many penalties

Time limit is too strict, even setterâs solution is failing without Fast I/O

Thanks a lot for the test case . Now I realize what is wrong with the algorithm. It only considers that edges may be inserted in the graph leading to components being merged together. But, it does not consider the fact that vertices may be removed which may also split the components. I think incorporating this new idea into the algorithm is gonna be slightly difficult implementation wise.

@r_k_p I think its just to distinguish between x and y so that we donât end up getting something like cnt[4][4] or any other number.
I solved it with (x!=y) condition and it passed.

How is its time complexity is o(n^2*k) ?

As you need to find k different âyâ b/w two nodes say âxâ and âzââŚ So we have total nC2 pairs of x and zâŚ
Now we break loop when we find k "y"s b/w any one âxâ and âzâ and hence we can visit at max
k+(k-1)*(nC2-1) "y"s
And hence complexity is
O(k+(k-1)*(nC2-1)) == O(n^2*k)
As n^2*k is dominantâŚ

1 Like

yes ! someone used it here and even got AC. I wonder how a O(n3) got an AC. Is it technical fault ? Or the time complexity is less than O(n3) ???

1 Like

what optimization techniques do you use to get the answerâŚ because i got TLE when i used java.

I used Fast IO reader class. Other than that, I used ArrayDeque to store the edges, as opposed to Arraylist, etc.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool check(vector a,vector b,int k)
{
sort(a.begin(),a.end());
sort(b.begin(),b.end());

``````vector<int> v(a.size());
``````

auto it = set_intersection(a.begin(),a.end(),b.begin(),b.end(),back_inserter(v));
if(it-v.begin()>=k)
return true;
else return false;

}

int main()
{
int n,m,k;
cin>>n>>m>>k;
vector v1[n];
int x,y;
for(int i=0;i<m;i++)
{
cin>>x>>y;
v1[x-1].push_back(y-1);
v1[y-1].push_back(x-1);
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(check(v1[i],v1[j],k)){
cout<<âYESâ;
return 0;}
}
}
cout<<âNOâ;
}
Can you tell what wrong with this solution?? it is giving TLE.

1 Like

it passed when i used fast i/o.

1 Like

I too made the same mistake.

Can someone please tell me, why âPigeonhole Principleâ is in the tag?

Or please let me know the approach to solve the problem using Pigeonhole Principle.

2 Likes

Yes, using bitsets its possible to get AC. It probably shouldnât get accepted.

I donât know how hard is to generate tcs especially because of smaller k. I did saw many bitset solns. I didnt bothered to do a rigirous analysis.

P.S. - @l_returns soln is also O(n^3) without the use of bitsets and his time taken is almost same as my bitset soln.