BICLIQUE - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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. :slight_smile:

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… :stuck_out_tongue::stuck_out_tongue_closed_eyes:
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) :stuck_out_tongue:

4 Likes

The idea seems fine to me. Maybe implementation mistake.

And how about this code : -

#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.
Link : https://www.codechef.com/viewsolution/24323626

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.
@teja349 please check on this?

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.:roll_eyes:

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… :stuck_out_tongue:

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 :joy: :joy: :joy:
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 :stuck_out_tongue:
https://www.codechef.com/viewsolution/24332547

1 Like

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