BICLIQUE - EDITORIAL

editorial
, ,
22

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

23

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

1 Like
24

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 :cry:

25

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

26

Thanks a lot for the test case :smile:. 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.

27

@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.

28

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

29

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
30

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
31

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

32

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

33

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

it passed when i used fast i/o.

1 Like
35

I too made the same mistake. :stuck_out_tongue:

36

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
37

Yes, using bitsets its possible to get AC. It probably shouldn’t get accepted.

38

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.

39

@teja349 Please reply !!

40

He is busy in code gladiator maybe… he got very nice rank :stuck_out_tongue:

41

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