Problem Statement
Time limit is 4 seconds.
You are given the int S.
We are interested in trees with the following properties:
- The tree has between 1 and 50 vertices, inclusive.
- The vertices are connected by undirected edges.
- The length of each edge is between 1 and 20, inclusive.
- If we take all unordered pairs of vertices, for each of them compute their distance, and add up all those distances, the result will be exactly S.
If such a tree exists, construct any such tree and return a int[] with the list of its edges as specified below. Otherwise, return the int[] {-1}.
Suppose you want to return a tree with N vertices. Number the vertices from 0 to N-1. The return value should be a concatenation of N-1 triples, each of the form {x, y, d} where x and y are the vertices connected by one of the edges and d is the length of that edge.
Definition
- Class:
- DistanceSumTree
- Method:
- construct
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] construct(int S)
- (be sure your method is public)
Constraints
- S will be between 1 and 10^6, inclusive.
Examples
96
Returns: {0, 1, 3, 3, 1, 10, 3, 4, 1, 1, 2, 5 }Returned tree (numbers in brackets are edge lengths) 0--[3]--1--[10]--3--[1]--4 | [5] | 2 The pairwise distances for this tree are 3 for the pair {0,1}, 8 for the pair {0,2}, 13 for the pair {0,3}, and so on. Their sum is 3 + 8 + 13 + 14 + 5 + 10 + 11 + 15 + 16 + 1 = 96, which is exactly what we needed.1000000
Returns: {-1 }Within the given constraints there is no tree for which the sum of pairwise distances equals 10^6.