Algorithm

E. Tree Constructing
time limit per test
4 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1003/problem/E
input
standard input
output
standard output

You are given three integers n�, d� and k�.

Your task is to construct an undirected tree on n� vertices with diameter d� and degree of each vertex at most k�, or say that it is impossible.

An undirected tree is a connected undirected graph with n−1�−1 edges.

Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.

Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex u� it is the number of edges (u,v)(�,�) that belong to the tree, where v� is any other vertex of a tree).

Input

The first line of the input contains three integers n�, d� and k� (1≤n,d,k≤4⋅1051≤�,�,�≤4⋅105).

Output

If there is no tree satisfying the conditions above, print only one word "NO" (without quotes).

Otherwise in the first line print "YES" (without quotes), and then print n−1�−1 lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from 11 to n�. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1

Examples
input
Copy
6 3 3
output
Copy
YES
3 1
4 1
1 2
5 2
2 6
input
Copy
6 2 3
output
Copy
NO
input
Copy
10 4 3
output
Copy
YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7
input
Copy
8 5 3
output
Copy
YES
2 5
7 2
3 7
3 1
1 6
8 7
4 3

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 4e5 + 1;
int n, d, k, fr[N], p[N];
vector<pair<int, int> > edges;

int main() {
#ifndef ONLINE_JUDGE
  freopen("in", "r", stdin);
#endif

  scanf("%d %d %d", &n, &d, &k);

  if(n < d + 1) {
    puts("NO");
    return 0;
  }

  for(int i = 1; i <= n; ++i)
    fr[i] = k;

  int s = 1, e = d + 1;

  for(int i = 1; i < e; ++i) {
    if(fr[i] > 0 && fr[i + 1] > 0) {
      edges.push_back({i, i + 1});
      --fr[i], --fr[i + 1];
      p[i] = max(i - s, e - i);
    } else {
      puts("NO");
      return 0;
    }
  }

  int cnt = e;
  for(int i = s + 1, cur, node; i < e; ++i) {
    cur = min(i - s, e - i), node = i;
    while(cnt < n && cur > 0 && fr[node] > 0) {
      if(fr[cnt + 1] < 1) {
        puts("NO");
        return 0;
      }

      edges.push_back({node, ++cnt});
      --fr[node], --fr[cnt];
      --cur;
      p[cnt] = p[node] + 1;
      node = cnt;
    }
  }

  for(int i = 1; i <= n; ++i) {
    if(i == s || i == e || p[i] == d)
      continue;
    while(cnt < n && fr[i] > 0) {
      if(cnt + 1 == i || fr[cnt + 1] < 1)
        break;
      edges.push_back({i, ++cnt});
      --fr[i], --fr[cnt];
      p[cnt] = p[i] + 1;
    }
  }

  if(edges.size() != n - 1 && cnt  <  n) {
    puts("NO");
    return 0;
  }

  puts("YES");
  for(int i = 0; i < edges.size(); ++i)
    printf("%d %d\n", edges[i].first, edges[i].second>;

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
6 3 3

Output

x
–
+
cmd
YES
3 1
4 1
1 2
5 2
2 6
Advertisements

Demonstration

Codeforces Solution-E. Tree Constructing-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+