DistanceSumTree
SRM 820 · 2021-12-27 · by misof
Problem Statement
Time limit is 4 seconds.
You are given the
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
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.
Constraints
- S will be between 1 and 10^6, inclusive.
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.
1
Returns: {0, 1, 1 }
20
Returns: {0, 1, 20 }
21
Returns: {0, 1, 2, 1, 2, 3, 2, 3, 1 }
Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DistanceSumTree with a public method vector<int> construct(int S) · 120 test cases · 2 s / 256 MB per case