Bear and Forgotten Tree 3

Introduction

Problem located at http://codeforces.com/problemset/problem/639/B

Limak the Bear cannot remember his tree but can tell you three values n, d and h:

• The tree had exactly n vertices.

• The tree had diameter d. In other words, d was the biggest distance between two vertices.

• Limak also remembers that he once rooted the tree in vertex 1 and after that its height was h. In other words, h was the biggest distance between vertex 1 and some other vertex. The distance between two vertices of the tree is the number of edges on the simple path between them.

The goal is to help Limak restore his tree:

• Check whether there exists a tree satisfying the given conditions.
• Find any such tree and print its edges in any order.
• If there is no suitable tree, print "-1".

Solution

For this problem, we first check when a tree would be impossible. Since the tree is not binary, the main restriction that we must focus on is when height and diameter constraints contract each other. We know that the diameter can at most be 2 * height, since height denotes the max depth in the tree, and since 1 <= h <= d <= n-1, as long as the height-depth relationships are satisfied, and number of n nodes can follow. The only exception to this rule is when d = 1 and n > 2.

If all these are satisfied, then we can build the specified tree. We start by building the main “chain” for the tree based upon the given diameter. It is given that diameter must be at least as large as height, so we first build the chain for height from the first node 1 to the hth node. Then we build another chain of d-h length and connect that to the root.

The remaining nodes can now just be connected directly onto the root. The only situation where they cannot be connected to the root is when h = d, since attaching anything even of length 1 to the root will result in a diameter of greater than d. For this instance, instead of attaching to the root, we attach all remaining nodes to the 2nd level node (note that the diameter = 1 case has already been covered above).

Code

Solution - Java

import java.util.Scanner;

/**
 * Created by callie on 4/18/16.
 */

public class BearAndForgottenTree3 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int d = in.nextInt();
		int h = in.nextInt();

		if (d > 2 * h || (n > 2 && d == 1)) {
			System.out.println("-1");
		} else {

			for (int i = 1; i <= h; i++) {
				System.out.println(i + " " + (i + 1));
			}

			for (int i = h + 1; i <= d; i++) { 
				if (i == h + 1)
					System.out.println("1 " + (i + 1));
				else
					System.out.println(i + " " + (i + 1));
			}
		
			for (int i = d + 1; i < n; i++) {
				if (h == d)
					System.out.println("2 " + (i + 1));
				else
					System.out.println("1 " + (i + 1));
			}
		}

	}
}