KDIAMS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter:
Tester: Rahul Dugar
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Observation

PROBLEM

Given N and K, find an unweighted undirected connected graph with N nodes such that there are exactly K pairs of nodes which have distance same as the diameter of the graph.

The diameter of a graph is given as the maximum of shortest distance between any pair of nodes.

QUICK EXPLANATION

  • If we have K = N*(N-1)/2, we can simply add edge between all pairs of nodes, leading diameter 1 and all pairs having same distance.
  • Otherwise we have diameter \geq 2. Since there are atleast N-1 edges, the pairs of nodes connected with direct edge cannot be pair with maximum distance.
  • If K > N*(N-1)/2 - (N-1), no graph is possible. Otherwise Let’s connect node 1 with all other nodes. It has exactly (N-1)*(N-2)/2 pairs with distance 2.
  • We can add an edge between (N-1)*(N-2)/2 - K pairs of nodes to make distance between them 1, making them bad pair.

EXPLANATION

In most constructive problems, we have a couple of corner cases, and then a couple of main cases. It’s often useful to cover the corner cases first, as they sometimes provide constraints on main case. This is what is gonna happen in this editorial.

One case to think of would be when K = N*(N-1)/2. We need all pair of nodes to be equidistant. We can simply add edge between all pairs of nodes, leading to diameter 1.

Now, what happens if K < N*(N-1)/2? We need to have diameter at least 2. Since the graph is connected, there are at least N-1 edges. For all pairs of nodes having direct edges between them, shortest distance is 1 and hence, they cannot have distance same as diameter.

So there can be at most N*(N-1)/2 - (N-1) = (N-1)*(N-2)/2 good pairs.

If we have K > (N-1)*(N-2)/2, there cannot exist a graph, so we print -1.

There’s a simple construction, just connect all nodes with node 1. It’ll give exactly (N-1)*(N-2)/2 pair of nodes with distance 2. Now say R = (N-1)*(N-2)/2-K, we need to reduce number of good pairs by R. We can add edges between R pair of nodes (excluding node 1), as we can see that adding one direct edge will reduce number of good pairs by exactly 1.

For example: N = 5, K = 4
Since 4 <= (4*3)/2, answer exists.

Adding edges from 1 to every other nodes, we get (4*3)/2 = 6 pairs. We need to remove 2 good pairs. So let’s add edge 2 3 and 2 4.

Final answer becomes

6
1 2
1 3
1 4
1 5
2 3
2 4

TIME COMPLEXITY

The time complexity is O(M) per test case, where M can be upto N^2 depending upon value of K.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			if(!(l<=x && x<=r))cerr<<l<<"<="<<x<<"<="<<r<<endl;
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
template<class T>
vector<T> readVector(int n, long long l, long long r){
    vector<T> ret(n);
    for(int i = 0; i < n; i++){
	ret[i] = i == n - 1 ? readIntLn(l, r) : readIntSp(l, r);
    }
    return ret;
}


int main(){
    int t = readIntLn(1, 100);
    while(t--){
	int n = readIntSp(2, 100), k = readIntLn(1, (n * (n - 1)) / 2);
	vector<pair<int, int>> edges;
	for(int i = 2; i <= n; i++) edges.push_back({1, i});
	int cnt = (n * (n - 1)) / 2 - (k == (n * (n - 1)) / 2 ? 0 : k);
	if(cnt < n - 1){
	    cout << -1 << endl;
	    continue;
	}
	for(int i = 2; i <= n; i++){
	    for(int j = 2; j < i; j++){
	        if(sz(edges) < cnt) edges.push_back({i, j});
	    }
	}
	assert(sz(edges) == cnt);
	cout << edges.size() << endl;
	for(auto it : edges) cout << it.first << " " << it.second << endl;
    }
}
Tester's Solution
Editorialist's Solution
import java.util.*;
import java.io.*;
class KDIAMS{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni(), K = ni();
	    if(N*N-N == 2*K){
	        pn((N*N-N)/2);
	        for(int i = 1; i<= N; i++){
	            for(int j = i+1; j<= N; j++){
	                pn(i+" "+j);
	            }
	        }
	    }else if(K*2 <= (N-1)*(N-2)){
	        int remove = ((N-1)*(N-2))/2 - K;
	        int M = N-1 + remove;
	        pn(M);
	        for(int i = 2; i<= N; i++)pn("1 "+i);
	        
	        for(int i = 2; i<= N; i++){
	            for(int j = i+1; j<= N && remove > 0; j++, remove--){
	                pn(i+" "+j);
	            }
	        }
	    }else pn(-1);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new KDIAMS().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

9 Likes

Thanks for uploading such an awesome and easy-to-understand editorial! :slight_smile:

2 Likes

In the question it is given graph distance is the largest distance between two nodes and here in editorial it says graph distance is the maximum of shortest distance between any pair of nodes. Aren’t these two different in meaning?

You are write technically. But in graph theory both means same.

1 Like

So do you mean distance is equal to shortest distance?
Edit : I got it, in graph theory distance means shortest distance. Thanks @satyam_656

Thanks nice editorial :slight_smile:

This is by no means an easy problem.

1 Like

How to get this part ?K>(n-1)*(n-2)/2 not possible —> how to conclude that?

Let us build a Complete Graph first. The diameter of the complete graph is 1. Also we can see that the distance of any node to any node is 1. Hence there will be (N*(N-1))/2 pairs whose distance between them will be 1.

What happens when we remove a single edge from the Complete Graph ?

The diameter of the graph becomes 2. And now there will be only 1 pair whose distance between them will be 2, and that pair is the one from which we had removed the edge.

To increase such pairs whose distance between them equals the diameter of the graph which is 2, we keep on removing the edges and each time we remove a edge the number of such pairs get increased by 1.

Keep in mind that after removing any edge the graph should always be connected. To make a graph of N vertices connected we need atleast (N-1) edges.

Initially there were (N*(N-1))/2 edges so you can remove max x edges, such that:

  • (N*(N-1))/2 - x = (N - 1).

We can see the value of x comes out to be ((N-1)*(N-2))/2. The number of edges removed is equal to the number of pairs we get whose distance between them equals the diameter of the graph. So we see that the maximum number of pairs we can get is ((N-1)*(N-2))/2. So the answer doesn’t exist for K>((N-1)*(N-2))/2

2 Likes

Wowww, what a great derivation!!!Simply Awesome

Yeah Bhi Theek hai!!

1 Like

Nice explanation. Can somebody please provide the code in python. I got the logic but dont know how to implement.