Answers to: MAXDIST - Editorialhttps://discuss.codechef.com/questions/71403/maxdist-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/SNCK15EL/problems/MAXDIST">Contest</a><br>
<a href="http://www.codechef.com/problems/MAXDIST">Practice</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/iscsi">Istvan Nagy</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a> and <a href="http://www.codechef.com/users/stzgd">Gedi Zheng</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/kevinsogo">Kevin Atienza</a></p>
<h1>PREREQUISITES:</h1>
<p>Tree center, tree radius, tree diameter, breadth-first search</p>
<h1>PROBLEM:</h1>
<p>The diameter of an undirected graph is the largest distance between any two nodes in the graph.</p>
<p>Given an unrooted tree, is it possible to decrease the diameter by adding exactly one edge?</p>
<h1>QUICK EXPLANATION:</h1>
<p>Handle the special case $N = 2$ (the answer is "NO"). In the following, assume $N > 2$.</p>
<p>First, find the centers of the tree (in $O(N)$ time). There can be one or two centers.</p>
<ul>
<li>If there is only one center, root the tree at the center, and compute the height of each subtree. Let $H$ be the height of the tree. Print "YES" if the root has exactly two children with height $H-1$, otherwise print "NO".</li>
<li>If there are two centers, remove the edge connecting the centers to form two trees, root the two trees on the centers, and compute the heights of all subtrees. Let $H$ be the (common) height of both trees. Print "YES" if one of the roots has exactly one children with height $H-1$, otherwise print "NO".</li>
</ul>
<h1>EXPLANATION:</h1>
<p>Let us first define a few simple terms related to trees and graphs.</p>
<p>The <strong>eccentricity</strong> of a node is the largest distance from that node to any other node in the graph.</p>
<p>The <strong>diameter</strong> of an undirected graph has been defined already. It is the largest distance between any two nodes in the graph. Alternatively, it is the largest eccentricity of any node in the graph. We also call any longest path in the graph a diameter, so the term "diameter" can mean either a path or a number, and it will be clear in context which kind of "diameter" we are referring to.</p>
<p>The <strong>radius</strong> of an undirected graph is the smallest eccentricity of any node in the graph.</p>
<p>A <strong>center</strong> of an undirected graph is any node whose eccentricity is equal to the radius. Note that a graph can have many centers (in particular, in a complete graph, all nodes are centers).</p>
<p>Since unrooted trees are a special case of undirected graphs, all the above terms are also defined for them. However, in the case of trees, there are a few additional useful properties:</p>
<ul>
<li>If $R$ is the radius and $D$ is the diameter, then $R = \lceil D/2 \rceil$ (i.e. the radius is approximately half the diameter). </li>
<li>A tree has either one or two centers.</li>
<li>If there are two centers, then they are connected by an edge.</li>
<li>All diameters pass through the center(s).</li>
<li>The diameter is even if and only if there is one center.</li>
</ul>
<p>These are pretty standard facts and are easy to prove, so we leave this exercise to the reader. The following illustrates the two cases, depending on the number of centers. The blue-filled nodes are the centers, and the blue edges are part of some diameter.</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist1.png"></p>
<p>All in all, the facts above say that the circumstances are really nice for an unrooted tree.</p>
<h1>Computing the answer</h1>
<p>Let's see how the center, radius and diameter can help us in answering the question. Note that all diameters pass through the center(s), which means that we only have to care about decreasing the lengths of those paths. We handle two cases, depending on whether there are one or two centers.</p>
<hr>
<p><strong>Case 1: 1 center</strong></p>
<p>Suppose that the tree only contains one center, say $C$. It makes sense to root the tree on $C$. Since the graph has at least two nodes, $C$ has at least two children (it cannot have just one, otherwise it wouldn't be a center). Furthermore, the height of the rooted tree is equal to the radius $R$ of the whole tree, and there are at least two direct subtrees of $C$ whose height is exactly $R-1$. These facts are intuitive and can easily be proven. See the following for a better picture of the situation:</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist6.png"></p>
<p>Suppose there are <em>exactly</em> two direct subtrees of $C$ with height $R-1$, say $A_1$ and $A_2$. In this case, all diameters pass through the sequence of nodes $A_1$-$C$-$A_2$ (or the reverse), and we can decrease the lengths of all these paths by adding an edge from $A_1$ to $A_2$, as shown below. </p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist2.png"></p>
<p>The paths passing through $A_1$-$C$-$A_2$ can instead take a shortcut by passing directly through the new edge, bypassing $C$. So we conclude that the answer is "YES" if $C$ has exactly two children with height $R-1$.</p>
<p>What if there are more than two direct subtrees whose height is $R-1$? Then in this case, we can show that it is impossible to add one edge to decrease the lengths of all diameters. This is because each diameter passes through exactly two of these subtrees, but by adding an edge, we only influence paths that pass through two subtrees, so diameters passing through the remaining trees are not affected.</p>
<p>This is illustrated in the following image, where there are three such children, $A_1$, $A_2$, $A_3$. In all the following cases, try to figure out why there are diameters which are not affected by adding the dashed edge.</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist3.png"></p>
<p>In fact, it is straightforward to prove this fact rigorously. Therefore, we conclude that the answer is "NO" if $C$ has more than two children with height $R-1$ :)</p>
<hr>
<p><strong>Case 2: 2 centers</strong></p>
<p>We now turn to the case where there are two centers, say $C_1$ and $C_2$. In this case, there is an edge between $C_1$ and $C_2$. Let's ignore that edge first, and root the two resulting trees on $C_1$ and $C_2$.</p>
<p>Now, we're sure that $C_1$ and $C_2$ has at least one child each, unless the $N$ is exactly two. But if there are just two nodes, we can simply output "NO" (there is only one such case. In fact, this case is given as a sample input). Therefore, we can assume that $C_1$ and $C_2$ has at least one child each. We can also show that the heights of both trees are equal. Let $H$ be this common height (note that it is possible to show that $H = R-1$).</p>
<p>Proceeding as in the above, suppose that $C_1$ has <em>exactly</em> one child of height $H-1$, say $A$. Then in this case it is possible again to decrease the lengths of the diameters by adding an edge from $A$ to $C_2$, as shown in the following:</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist4.png"></p>
<p>All diameters pass through the node-sequence $A$-$C_1$-$C_2$, but by adding the new edge, the diameters can bypass the node $C_1$. Therefore, if $C_1$ has exactly one child of height $H-1$, then the answer is "YES". A symmetric argument applies if $C_2$ has exactly one child of height $H-1$.</p>
<p>Now, what if $C_1$ and $C_2$ both have more than one children of height $H-1$? Then, similarly as in the previous case, we can show that it is impossible. Consider for example the following case:</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist5.png"></p>
<p>No matter where we place the edge, there are still diameters that are not affected by the new edge. Therefore, the answer is "NO".</p>
<hr>
<p>We have handled all the possible cases, and our solution runs in $O(N)$ time (assuming we already know the centers of the tree). This is an optimal solution!</p>
<h1>Computing the center</h1>
<p>The above algorithm assumes that we have already computed the centers of the tree. How do we compute the centers? There are several well-known ways to do it, some of them running in optimal $O(N)$ time. We will discuss one here:</p>
<ul>
<li>Select an arbitrary node $X$.</li>
<li>Find the farthest node $Y$ from $X$. If there is more than one, pick any.</li>
<li>Find the farthest node $Z$ from $Y$. If there is more than one, pick any.</li>
<li>The path $Y$-$Z$ is now a diameter, so the centers are the centermost nodes on the path from $Y$ to $Z$ (there can be one or two such nodes).</li>
</ul>
<p>Clearly, this runs in $O(N)$ time. But why does it work? This algorithm relies on the following fact:</p>
<p><em>For any node, any farthest node from it is an endpoint of some diameter.</em></p>
<hr>
<p><em>Proof:</em> </p>
<p>Let $D(i,j)$ be the distance between nodes $i$ and $j$.</p>
<p>Let $X$ be any node, and $Y$ be any node with the maximum distance from $X$. We want to show that $Y$ is the endpoint of some diameter. There are two cases:</p>
<ul>
<li>The path $X$-$Y$ doesn't intersect any diameter.</li>
<li>The path $X$-$Y$ intersects some diameter.</li>
</ul>
<p>Let's handle them separately:</p>
<p><em>Case 1: The path $X$-$Y$ doesn't intersect any diameter.</em></p>
<p>In this case, let $A$-$B$ be any diameter. Let $W$ be the nearest node from $X$ that belongs in the path $A$-$B$, and let $V$ be the farthest node from $X$ in the path $X$-$W$ that still belongs in the path $X$-$Y$. Note that it's possible that the vertices described here are not distinct. However, we know that nodes $V$ and $W$ are distinct, by assumption. Therefore $D(V,W) = D(W,V) \ge 1$. The following image illustrates the situation:</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist7.png"></p>
<p>We will show that the path $B$-$Y$ is longer than the diameter, which is a contradiction (because the diameter is the longest path).</p>
<p>Since $Y$ is farthest from $X$, we have $D(X,A) \le D(X,Y)$. But we have $D(X,A) = D(X,V) + D(V,W) + D(W,A)$ and $D(X,Y) = D(X,V) + D(V,Y)$, therefore we have:
$$D(V,Y) \ge D(V,W) + D(W,A)$$
and
$$D(W,Y) = D(W,V) + D(V,Y) \ge D(W,V) + D(V,W) + D(W,A) \ge 1 + 1 + D(W,A) > D(W,A)$$
and finally
$$D(B,Y) = D(B,W) + D(W,Y) > D(B,W) + D(W,A) = D(B,A)$$
which shows that $B$-$Y$ is indeed longer than the diameter $A$-$B$. This is a contradiction, therefore this case is impossible.</p>
<p><em>Case 2: The path $X$-$Y$ intersects some diameter.</em></p>
<p>This time, let $A$-$B$ be a diameter that intersects the path $X$-$Y$, and let $V$ and $W$ be the nearest and farthest nodes from $X$ in the path $X$-$Y$ that are in the diameter $A$-$B$, respectively. We also assume that $D(W,A) \le D(V,A)$, i.e. $W$ is nearer to $A$ than $V$ is unless $W = V$. There is no loss of generality, because otherwise we can just swap $A$ and $B$. As in the previous case, these nodes are not necessarily distinct. The following image illustrates the situation:</p>
<p><img align="center" src="http://discuss.codechef.com/upfiles/Maxdist8.png"></p>
<p>We will now show that the path $B$-$Y$ is also a diameter, which shows that $Y$ is an endpoint of some diameter.</p>
<p>Since $Y$ is farthest from $X$, we have $D(X,A) \le D(X,Y)$. But we have $D(X,A) = D(X,V) + D(V,W) + D(W,A)$ and $D(X,Y) = D(X,V) + D(V,W) + D(W,Y)$, therefore we have:
$$D(W,Y) \ge D(W,A)$$
However,
$$D(B,Y) = D(B,W) + D(W,Y) \ge D(B,W) + D(W,A) = D(B,A)$$
On the other hand, $D(B,Y) \le D(B,A)$ because $B$-$A$ is a diameter. Therefore, $D(B,Y) = D(B,A)$, and $B$-$Y$ is also a diameter, and we have shown that $Y$ is an endpoint of some diameter.</p>
<hr>
<h1>Time Complexity:</h1>
<p>$O(N)$ </p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/downloads/Solutions/SNCK15EL/Setter/MAXDIST.cpp">Setter</a><br>
<a href="http://www.codechef.com/downloads/Solutions/SNCK15EL/Tester1/MAXDIST.cpp">Tester 1</a><br>
<a href="http://www.codechef.com/downloads/Solutions/SNCK15EL/Tester2/MAXDIST.cpp">Tester 2</a> </p>enThu, 20 Jul 2017 23:18:43 +0530Answer by sidy_97https://discuss.codechef.com/questions/71403/maxdist-editorial/106069<p>Amazing Editorial! Really helpful thanks! :)</p>sidy_97Thu, 20 Jul 2017 23:18:43 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/106069Answer by chunky_2808https://discuss.codechef.com/questions/71403/maxdist-editorial/90385<p>please upvote me i need to ask question</p>chunky_2808Fri, 20 Jan 2017 23:54:56 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/90385Answer by codepandit1https://discuss.codechef.com/questions/71403/maxdist-editorial/90381<p>i am working on this problem for 4 days and after reading the editorial i think i am not even close to the answer..and yet it is on easy category....can some someone guides me how can i solve these type of problems....
i am new to programming</p>codepandit1Fri, 20 Jan 2017 22:11:04 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/90381Answer by asvikrhttps://discuss.codechef.com/questions/71403/maxdist-editorial/72284<p>What is the answer for this graph
9
1 2
2 3
3 4
4 5
4 6
4 7
2 9
2 8</p>asvikrFri, 26 Jun 2015 16:07:29 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/72284Answer by mladia163https://discuss.codechef.com/questions/71403/maxdist-editorial/72243<p><a href="/users/17741/kevinsogo">@kevinsogo</a>
why solution of setters and testers are not opening ?</p>mladia163Thu, 25 Jun 2015 07:06:48 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/72243Answer by shubham201https://discuss.codechef.com/questions/71403/maxdist-editorial/71956<p>Nice editorial, Highly appreciate the work of editorialist. Thank you :)</p>shubham201Sat, 20 Jun 2015 19:45:46 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71956Answer by shubham201https://discuss.codechef.com/questions/71403/maxdist-editorial/71954<p><a href="/users/16516/vvneagleone">@vvneagleone</a>, please tell me one thing how your solution is O(n^2). It seems O(2*n) to me :(
By the way nice solution ;) Actually if we observe your solution minutely using diagrams of this editorial, it covers all the cases described in this editorial nicely :) </p>shubham201Sat, 20 Jun 2015 19:42:15 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71954Answer by thezodiac1994https://discuss.codechef.com/questions/71403/maxdist-editorial/71725<p>Can someone provide a failing tc for
<a href="http://www.codechef.com/viewsolution/7234246">http://www.codechef.com/viewsolution/7234246</a> <br>
Thanks. </p>thezodiac1994Mon, 15 Jun 2015 22:34:44 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71725Answer by sud210https://discuss.codechef.com/questions/71403/maxdist-editorial/71487<p>nicely written...................!</p>sud210Sun, 14 Jun 2015 00:12:11 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71487Answer by shubhamsinghhttps://discuss.codechef.com/questions/71403/maxdist-editorial/71478<p>'Page not found' on clicking at tester and setter's solution.</p>shubhamsinghSat, 13 Jun 2015 19:26:37 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71478Answer by vvneagleonehttps://discuss.codechef.com/questions/71403/maxdist-editorial/71471<p>My solution:</p>
<ol>
<li>DFS from vertex "1" and find any one vertex at max depth (say v1). v1 is now one end of any one diameter-path of the tree.</li>
<li>DFS from v1 and find any one vertex at max depth (say v2). This also finds the diameter D.</li>
<li>DFS from v1 and find all paths of length D. Let there be p1 such paths.</li>
<li>DFS from v2 and find all paths of length D. Let there be p2 such paths.</li>
<li>Count the number of vertices which occur in all (p1+p2) paths (there must be at least one, because if we have 2 disjoint D-length paths then there must be another path of length at least D+1).</li>
<li>If count > 2 print yes else print no. If there are 3 or more such vertices they must form a path subgraph, which can be bypassed with the single edge.</li>
</ol>
<p>Although this is O(n**2) worst case, and shows pretty terrible understanding of the subtree method in the editorial, I took the risk in favour of typing speed and got AC in fastest time by far (0.26) typing in around 10 minutes.</p>vvneagleoneSat, 13 Jun 2015 17:16:21 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71471Answer by phixymahttps://discuss.codechef.com/questions/71403/maxdist-editorial/71465<p>Awesome editorial indeed, the proof is amazing :-)</p>phixymaSat, 13 Jun 2015 14:16:06 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71465Answer by sagarpatelhttps://discuss.codechef.com/questions/71403/maxdist-editorial/71452<p>+1 for the editorialist, thanks for the great explanation.....:)</p>sagarpatelSat, 13 Jun 2015 11:17:50 +0530https://discuss.codechef.com/questions/71403/maxdist-editorial/71452