Questions Tagged With centreehttps://discuss.codechef.com/tags/centree/?type=rss&user=deadwing97questions tagged <span class="tag">centree</span>enMon, 19 Jun 2017 07:10:14 +0530CENTREE - Editorialhttps://discuss.codechef.com/questions/102432/centree-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/CENTREE">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/CENTREE">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Graph Theory</p>
<h1>PROBLEM:</h1>
<p>Construct a tree of <strong>N</strong> nodes such that the maximum distance between one of its centers and one of its centroids is exactly <strong>B</strong>.</p>
<p>A vertex <strong>u</strong> is a centroid if after removing <strong>u</strong> from the tree, the size of any of the resulting connected components is at most <strong>n/2</strong>.</p>
<p>Let <strong>f(x)</strong> be the greatest distance from u to any other vertex of the tree. A vertex <strong>u</strong> is a center if <strong>f(u) ≤ f(v)</strong> for any other vertex <strong>v</strong>. </p>
<h1>EXPLANATION:</h1>
<p>First of all let's create a tree consisting of a single node numbered <strong>1</strong> and assuming that it will be our centroid. </p>
<p>Now we should construct a chain consisting of <strong>B</strong> edges ending in a node representing our future center and this node is numbered <strong>B+1</strong>. Currently our tree is composed of a chain containing <strong>B+1</strong> nodes. Currently node <strong>B+1</strong> is not the center of our tree. So to make it our center we should extend this chain from this node by <strong>B</strong> extra nodes. Resulting a chain consisting of <strong>2*B+1</strong> node where the i<sup>th</sup> node and the (i+1)<sup>th</sup> node are connected by an edge for each <strong>0 < i < 2*B+1</strong></p>
<p>Now we assured that node <strong>B+1</strong> is our center. And clearly node <strong>1</strong> is not our centroid. So we must make use of the remaining nodes and attach each one of them directly to node <strong>1</strong> (Each of them connected to <strong>1</strong> by a directed edge so we keep our center unchanged). Of course we must have enough nodes to ensure that. Removing node <strong>1</strong> would leave us with a subtree consisting of <strong>2*B</strong> nodes, and subtrees made of single nodes (we attached). </p>
<p>As a conclusion we can say that for any <strong>N,B</strong> such that :</p>
<p><strong>2*B ≤ N/2</strong> <strong>-></strong> <strong>4*B ≤ N</strong> </p>
<p>A solution exists and can be constructed by this way. For cases where 4*B > N, constructing such a tree is impossible.</p>
<p>Of course we must handle this special case : </p>
<p>Case n = 2:</p>
<p>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</p>
<p>This image briefly describes the configuration of our tree:
<img alt="centree" src="https://codechef_shared.s3.amazonaws.com/download/upload/COOK83/centroid.jpg"></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Setter/CENTREE.cpp">Here</a><br>
<strong>TESTER's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Tester1/CENTREE.cpp">Here</a></p>deadwing97Mon, 19 Jun 2017 07:10:14 +0530https://discuss.codechef.com/questions/102432/centree-editorialcentreead-hocgraphtreeconstructivecook83editorial