PROBLEM LINK:
Setter: Erfan Alimohammadi
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
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];
vector<int> adj[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;
adj[x].push_back(y);
adj[y].push_back(x);
}
bool ans = false;
for (int i = 1; i <= n; i++) {
if (ans)
break;
for (auto x: adj[i]) {
if (ans)
break;
for (auto y: adj[i]) {
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
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// 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];
vector<vi> adj(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]++;
adj[u].pb(v);
adj[v].pb(u);
}
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;
rep(j,adj[i].size()){
if(ans)
break;
f(k,j+1,adj[i].size()){
val1=adj[i][j];
val2=adj[i][k];
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. 
