PROBLEM LINK:Author: Sergey Kulik PREREQUISITES:Graphs, eccentricity, central nodes PROBLEM:Given a connected undirected graph of $N$ nodes and $M$ edges, add at most $2N$ nodes and $N(N1)$ edges such that:
Some of the terms I used in the previous sentence are standard and I'm sure you can search them online if you're unfamiliar :) QUICK EXPLANATION:It's always possible to do so within the given constraints. Here's one way to do it:
EXPLANATION:Here we first define some terms. The eccentricity of a node $v$, denoted $\epsilon(v)$, is the greatest shortest path from $v$ to any other node. (Note: $\epsilon(v)$ coincides with $d(v)$ in the problem statement, but $\epsilon(v)$ but seems to be a more standard notation after a bit of internet searching :D) The radius $r$ of a graph is the minimum possible $\epsilon(v)$ among all nodes $v$. A node $v$ is called a central node if its eccentricity is the minimum possible, i.e. $\epsilon(v) = r$. The eccentricity can be very large (even in connected graphs). In path graphs of $N$ nodes for example, the eccentricities of the nodes at the ends of the path are $N1$. However, we can introduce some nodes and edges to the graph to force the eccentricity to be at most $2$. Let A be a new node. If we connect A to all the $N$ historical nodes, then it can be shown that the eccentricity of each node is at most $2$, because we can always pass through A to reach any other node, for a total of two edges! This makes our task a bit easier, because our goal is to make the eccentricities of the $N$ historical nodes equal. The following illustrates this: The problem with this is that some historical nodes may still have eccentricities of $1$. But we can fix this! We add another node, B, connected to A, so all historical nodes will have eccentricities of $2$ (because they are $2$ edges away from B). Here's an illustration: But there is still a problem. The eccentricity of A is $1$ while the eccentricity of B is $2$, but we want them to exceed $2$. But we can still fix this! We add two nodes C and D, connect all $N$ historical nodes to C, and connect C and D. The following illustrates this: This will force A and B (as well as C and D) to have eccentricities at least $3$, because there are nodes at the other side of the fence. Therefore, this construction is now valid! Also, note that we didn't actually require the edge information, because they don't really matter in this construction! Now, let's see how many nodes and edges we used. It's easy to see that we have only added $4$ nodes and $2N+2$ edges. Now, we have a constraint to use at most $2N$ additional nodes and $N(N1)$ additional edges, but we have $4 \le 2N$ iff $N \ge 2$, and $2N+2 \le N(N1)$ iff $N \ge 4$, so the construction above will work for all cases where $N \ge 4$ :) We still have to consider the cases $N \le 3$ though. Thankfully, there are only four such cases, because the original graph is connected. If $N < 3$, or if $N = 3$ and $M = 3$, it can be seen with some trial and error that the graph is complete, i.e. all pairs of nodes are connected by an edge (remember that the original graph is connected), so there is nothing needed to be done (the graph is totally symmetric and thus eccentricities are the same. In fact it is equal to $1$ for $N > 1$ and $0$ for $N = 1$ :D). The only remaining case is $N = 3$ and $M = 2$, and there is only one such kind of graph: a simple path graph of length $2$. Let's call the three nodes in the path order as R, S and T (i.e. S is the middle). We cannot do the construction above because we are limited to $6$ additional nodes and $6$ additional edges. You can try to find a good construction in paper, but you can also do a bruteforce search to find a valid construction. The first construction that came up in the editorialist's bruteforce search is what we will call the umbrella graph (:D :D), i.e. the following where the nodes A and B are new. It can be seen that the eccentricities of R, S and T are $2$, while the eccentricities of A and B are $3$. Moreover, there are only $2$ additional nodes and $3$ additional edges. Therefore, this is valid! The time complexity of the whole algorithm is $O(N+M)$, which is dominated by reading the input and writing the output. Also, since we didn't miss any case, we have just shown that there always exists a solution. Note: there are other constructions aside from what is described in this editorial. We have just shown you one possible way. We'd be happy to hear what you did :) Time Complexity:$O(N+M)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 23 May '15, 16:29

Okay @ankitbisla21, my idea is like this. Assume n >= 3. Let A = {1} and B = {2, .., n}. Now, partition B into two sets C, D such that 1 is adjacent to all of C and none of D. If D is empty, I call my easy() function which constructs takes two paths l1, l2 of length n2 and connects one end of l1 to A and one end of l2 to all of B. This can be seen to work. If D is non empty, I call my hard() function which again take two paths l1, l2 of length n2 and connect one end of l1 to A and one end of l2 to all of C. Now, add 2 more vertices u, v and connect u to one end of l1 and v to one end of l2(the same ends that are connected to the old vertices). Then connect both u, v to all of D. Finally, when D is non empty, the above algorithm doesn't work for n = 3, m = 2(it gives 7 edges when only 6 edges are allowed) which I deal separately with my supa() function(which means supa hard because that cost me a WA xD). answered 23 May '15, 22:57

Nice problem! Let me explain my (another unnecessary complicated) solution.
It works, unless there exists a vertex v which satisfies d(v) = 1. Even so, we can correct the solution above with
Here is my solution. Thanks. answered 24 May '15, 09:54

@ahujamoh @asvikr The first example adds new edges and vertices to the already valid graph just to clarify that this would still result in a correct answer even though it isn't minimal. This means that your solution can be simplified to the one explained in the "Quick Explanation" of the editorial, and that you do not have to bother to check if the graph is already valid, or if there is a solution with fewer vertices or edges. answered 11 Jun '15, 14:15

Nice Explanation! :D