PROBLEM LINK:Author: Alei Reyes DIFFICULTY:Easy PREREQUISITES:Graph Theory PROBLEM:Construct a tree of N nodes such that the maximum distance between one of its centers and one of its centroids is exactly B. A vertex u is a centroid if after removing u from the tree, the size of any of the resulting connected components is at most n/2. Let f(x) be the greatest distance from u to any other vertex of the tree. A vertex u is a center if f(u) ≤ f(v) for any other vertex v. EXPLANATION:First of all let's create a tree consisting of a single node numbered 1 and assuming that it will be our centroid. Now we should construct a chain consisting of B edges ending in a node representing our future center and this node is numbered B+1. Currently our tree is composed of a chain containing B+1 nodes. Currently node B+1 is not the center of our tree. So to make it our center we should extend this chain from this node by B extra nodes. Resulting a chain consisting of 2*B+1 node where the i^{th} node and the (i+1)^{th} node are connected by an edge for each 0 < i < 2*B+1 Now we assured that node B+1 is our center. And clearly node 1 is not our centroid. So we must make use of the remaining nodes and attach each one of them directly to node 1 (Each of them connected to 1 by a directed edge so we keep our center unchanged). Of course we must have enough nodes to ensure that. Removing node 1 would leave us with a subtree consisting of 2*B nodes, and subtrees made of single nodes (we attached). As a conclusion we can say that for any N,B such that : 2*B ≤ N/2 > 4*B ≤ N A solution exists and can be constructed by this way. For cases where 4*B > N, constructing such a tree is impossible. Of course we must handle this special case : Case n = 2: if B = 1 the tree made of 2 nodes connected by an edge is the solution, for other values of B the answer is NO This image briefly describes the configuration of our tree: AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Jun '17, 07:10

I was damned on the n=2, b=0 case in which the answer must be "NO" and all other things were correct. Sad :( answered 19 Jun '17, 16:42

Answer is hidden as author is suspended. Click here to view.
answered 19 Jun '17, 15:50

Can someone explain me the definition of centeroid and center in simple words, i'm not getting it...!!! answered 23 Jun '17, 14:40

Here is the link to my editorial with little detailed explanation of centroid and center, i too faced quite a problem in understanding these definations. Hope it helps. answered 02 Jul '17, 23:36

Author and Tester solution links are invalid, please update