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. 
