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

# BICLIQUE - EDITORIAL

Your logic is wrong I think

Try the following case :

5 5 2

1 2

1 4

3 2

3 4

4 5

The answer should be YES but your output is NO

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âŚ

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) ???

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.

it passed when i used fast i/o.

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.

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.

He is busy in code gladiator maybeâŚ he got very nice rank

If number of steps is more than O(n^2*k) then at least one of the count values must be greater than k (this is by pigeon hole principle).