# BICLIQUE - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

Easy Medium

# PREREQUISITES:

Graphs, Implementation, Pigeonhole Principle

# PROBLEM:

Given a graph G, check whether K(2,k) is a subgraph of G for a given k. Here by K(2,k) we refer to complete bipartite graph with partition sizes 2 and k respectively.

# EXPLANATION

The problem boils down to checking if any pair of vertices share atleast k neighbours. We will try to go over all the paths x-y-z (assuming x \lt z) and update count[x][z] by 1 for every such path. In order to iterate over all such paths, we will iterate over all the possible values of y from 1 to n and now x and z must be neighbours of y. So we iterate over all the unordered pairs of neighbours of y and update the count[x][z] accordingly.

Key Step: We need to stop the program as soon as we meet some count[x][z] which is equal to k.

# TIME COMPLEXITY :

In each step of the algorithm, for some (x,z) pair the count value will get increased by 1. We have O(n^2) pairs of distinct (x,z). And each pair can reach a value of atmost k. So we will find a biclique in atmost O(n^2* k) steps or will have completed the program without finding a biclique. Hence, Time complexity is O(n^2* k).

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2010;

int t, n, m, k, cnt[MAXN][MAXN];

int main() {
ios::sync_with_stdio(0);
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
}
bool ans = false;
for (int i = 1; i <= n; i++) {
if (ans)
break;
if (ans)
break;
if (x < y) {
cnt[x][y]++;
cnt[y][x]++;
if (cnt[x][y] >= k) {
ans = true;
break;
}
}
}
}
}
if (ans)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
``````
Tester's Solution
``````//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int cnt[2123][2123];
int deg[2123];
int main(){
//std::ios::sync_with_stdio(false); cin.tie(NULL);
int n,m,kk;
//cin>>n>>m>>kk;
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&kk);
int i,u,v,j,k;
rep(i,m){
//cin>>u>>v;
scanf("%d",&u);
scanf("%d",&v);
u--;
v--;
deg[u]++;
deg[v]++;
}
int cnt1=0;
rep(i,n){
if(deg[i]>n/2+k+4)
cnt1++;
}
if(cnt1>=2){
printf("YES\n");
return 0;
}
int val1,val2;
int ans=0;
rep(i,n){
if(ans)
break;
if(ans)
break;
if(val1>val2)
swap(val1,val2);
cnt[val1][val2]++;
if(cnt[val1][val2]>=kk)
{
ans=1;
break;
}
//cout<<cnt[val1][val2]<<" "<<val1<<" "<<val2<<endl;
}
}
}
if(ans){
printf("YES\n");
}
else{
printf("NO\n");
}
return 0;
}
``````

Feel free to Share your approach, If it differs. Suggestions are always welcomed.

2 Likes

@teja349 since you are the tester as well, can you please tell me whatâ€™s wrong with this approach:
We obtain the complement of the graph and now note that we may add any no. of edges in this graph since we may remove any no. of edges from the original graph.
Now, the answer exists if there exist 2 disjoint components of vertices (possibly formed by joining other components) s.t one is of size 2 and another of size k. In this way, we can construct a 2-clique and a k-clique by adding more edges and the cliques will not share an edge with one another in the complement graph.
I got WA using this approach. Is it something wrong with the approach or is it just some implementation mistake ?

2 Likes

What I did was check intersection of neighbours for every pair of nodes in 1 to n
If size of anyone intersection is \ge k then print yesâ€¦ Otherwise print noâ€¦
I got ACâ€¦ But whatâ€™s wrong in this approach ??
I use algorithm for merging two sorted arrays for counting intersectionâ€¦
Time complexity : I am confusedâ€¦
O(n^2+n*m+m*log(m))
So O(n^3) XD
But I guess if m is large then loop will break soon so thatâ€™s a trade off while making test casesâ€¦
So I think it passesâ€¦

1 Like

How about using bitsets to solve it in O(n^3)

4 Likes

The idea seems fine to me. Maybe implementation mistake.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
ll n,m,k;
cin>>n>>m>>k;
ll ans=n*(n-1)/2;
if(m>=n && m<=ans)
cout<<â€śYESâ€ť;
else
cout<<â€śNOâ€ť;
cout<<endl;
}

This solution is submitted by @maheswari7778, and in O(1) complexity.

Thanks. I tried a number of test cases but my submission was yielding correct answers on them. Still not able to figure out whatâ€™s missing.

1 Like

This is not the exact approach, due to weak test cases during the contest it got accepted.
I think they added few more test cases after moving to the practice section, now it is showing WA.

https://www.codechef.com/viewsolution/24330261

This is exactly like your solution, but giving TLE:sweat_smile:

They might have added some test cases

Thatâ€™s weird.

Sorryâ€¦ my code still passesâ€¦ Maybe avoid using â€śllâ€ť and use Fast i/o
And it will pass

Yup, it passed with fast IO.

1 Like

I wonder why were you not using fast i/o when u had it in your templateâ€¦

Deleted that line by mistake while trying different approaches:stuck_out_tongue:

1 Like

Can somebody please explain me why setter is checking (x<y) (why it is required).
Thank you.

you can see how much lucky this guy is as his approach checks if m is less than or equal to ans(i.e. n*(n-1)/2) which is actually the constraints of the question
it shows that how much he actually understood the question.
one simple testcase in which his approach will fail is when n is 2000 and m is 2 and k is 1
edges are as follows (1,2),(1,3), ans should be â€śyesâ€ť but his code will give ans â€śnoâ€ť.

https://www.codechef.com/viewsolution/24331051

I know this can be done with bitsetâ€¦but initially i tried set_intersection() methodâ€¦it gives tleâ€¦
Any thoughts on this?

1 Like

I think you need to sort those vectors before using set_intersection
Mine passes in 0.23 using set_intersection
https://www.codechef.com/viewsolution/24332547

1 Like

lol. I thought subgraph meant choosing only some vertices and all edges in that vertices.
learnt something new