FLY - Editorial

PROBLEM LINKS:

Practice
Contest

DIFFICULTY:

Medium

PREREQUISITES:

[Connected Graphs][3], [Linear Functions][4] and Math

QUICK EXPLANATION:

Clearly when M=0 the optimal graph with N-1 edges is the star graph with edges [1,
2], [1, 3], …, [1, N]
. Its time penalty can be easily found. When we try to add edge to
this graph time penalty will decrease by 2 but the construction cost will increase by
C. Hence if C>=2 the star graph is optimal and if C<2 the complete graph is optimal.
Next when M=1 or M=2 but free edges have a common vertex, free edges already forms a subgraph of star graph, so we have the same cases as for M=0 but need to decrease construction cost by M*C.

Finally consider the case when M=2 but all ends of edges are different. So, for
example, edges are [1, 2], [3, 4]. Now it can be proved that the optimal tree should
have edges [1,2], [1,3], [1,5], [1,6], …, [1,N], [3,4]. It is clear that the best graph
with N edges is obtained from this tree by adding edge [1,4]. The difference of time
penalty for these two graphs can be easily calculated and is equal to 2(N-2). Hence
if C>=2(N-2) the optimal graph is tree, if 2(N-2)>C>=2 the optimal graph is the
tree with an extra edge [1,4] and for C<2 the best graph is again complete graph.

Next comes the part where we want to calculate the answer with high precision. For further details, please refer to the end of the detailed description.

DETAILED EXPLANATION:

Let us look at the problem from the perspective of graphs. Let every restaurant be a vertex in the graph and let a flyover between two restaurants be represented by an edge. Hence, we have N vertices and we need to determine the flyovers in the optimal model. Also, we have M flyovers being constructed for free. So let’s start with the case of M = 0.

In this problem, it is clear that the restaurants are all similar to each other.
The first and foremost necessity for this problem is that the graph must be connected i.e. there must be a path from each vertex to every other vertex. This is because the Chef travels only through flyovers. So, from the basic knowledge of graphs, we know that the minimum number of edges that required for a graph with N vertices to be connected is N-1. This leads to the conclusion that no matter what, the edges(flyovers) in our graph can never be less than N-1. There can be many ways to make a connected graph using N-1 edges:

alt text

OR

Fly2.jpg

It is evident that the time penalty between the pairs of vertices(i.e. the sum of lengths of the path between all the pairs) is different in both the cases above. To find the optimal solution, we must consider a graph that minimizes this sum. If we observe carefully, we can have a graph with the minimum sum of time penalties as the following graph:

alt text

A star graph as seen above is perfectly symmetrical. The vertex(0) at the center is at a distance of 1 from every other vertex i.e. T(0,i)=1 for all i!=0. And all the other vertices are at a distance of 2 from every other vertex i.e. T(i,j) = 2 for all i!=0 and j!=0. It’s easy to show that this is the optimal graph for the case of N-1 nodes i.e. there is no other graph which has a lesser sum of distances. Let us suppose the star graph having edges [0,1],[0,2]…[0,N-1] is modified to get a new graph. It is clear that we cannot add any edge as there are already N-1 edges. So we try to remove an edge and add it somewhere else. Let us assume that the edge [0,i] is changed to [i,j]. In this case, the distance of i from 0 changes to 2 (via j) and distance of i from j changes to 1 from 2. Also, the distance of i from every other vertex increases from 2 to 3. So, the overall sum increases. In case we changed the edge [0,i] to [j,k], it will no longer be a connected graph. Hence we stick to the previous change for now. Now let’s modify another edge. We can modify an edge [0,a] in the following ways:

  1. Change it to [b,a] : Same as the
    above case. The sum of distances
    increases further. Here b!=i.

  2. Change it to [i,a]: Clearly, the
    sum of distances increases a lot
    more than that for the previous
    change.

Thus we see that it’s not possible to get a lesser sum of distances by modifying the star graph.
We have the optimal case for N-1 edges. Let’s determine how many edges in all we need to construct so that the model is optimal. Let us suppose we need ‘x’ extra edges in the graph for the graph to be optimal. The center is already connected to all the N-1 vertices. So we use these edges to connect other pairs. Note that these ‘x’ edges can join any ‘x’ pairs of vertices(since all the vertices except the center one are similar). Also, it doesn’t make sense to connect the same pair twice. Thus we have (N – 1) + x pairs of cities connected with edges directly. Remaining ((N (N-1)) / 2) – (N -1 + x) pairs are connected through an intermediate vertex i.e. the center. Let’s call this number Y.

Now let’s calculate the cost of this model:

  1. Sum of T(u,v), where u and v are
    connected with direct edges : 2 (N
    – 1 + x)
    . We multiply by 2 because
    we need to include both T(i,j) and
    T(j,i).
  2. Sum of T(u,v), where u and v are connected through an intermediate vertex(the center of star): 2 * Y * 2. Here, T(u,v) = 2.
  3. Cost of flyovers: C (N – 1 + x)

If we simplify, we get the total cost to be:

(C-2).x + 2.N^2 + (C-4).N – (C-2)

We can see here that it is a linear equation in x. The coefficient of x is (C-2).
We know that the function will be a monotonously decreasing function if (C-2) < 0 , monotonously increasing function if (C-2) > 0 and constant if C - 2 = 0. (A monotonously increasing function means that the value of the function keeps increasing linearly as we keep increasing the value of x. Similarly a decreasing function decreases as we increase x.) Also, we know that x can vary between 0 and (N (N - 1)) / 2 – (N – 1).

a) Thus, for the case where C – 2 < 0 i.e. C < 2, we should choose x as maximum so that the cost can be minimum. This implies that x = (N (N - 1)) / 2 – (N – 1).
Hence, total cost: C (N (N-1))/2 + (N (N-1))

b) For the case of C – 2 > 0 i.e. C > 2, we should choose the minimum value of x. Thus, x = 0. Hence, total cost: 2N^2 + (C-4)N – (C-2)

c) For C = 2, we can choose x to be anything. The cost doesn’t depend on x. Cost will always be 2N^2 + (C-4).N – (C-2)

Thus, we have the answers when M = 0.

Next we come to M = 1.
Suppose an edge between x & y can be constructed for free. You only need N – 2 edges to get a connected graph. We again create a star graph with M – 1 edges to minimize the sum of distances. Make the center of the star graph described above to be either x OR y. Then we have the same problem at hand like for M = 0. The only difference here would be that we subtrace the cost of 1 edge i.e. C from the final answer as calculated above.

Next case to be considered is M = 2.
This again has 2 cases:

  1. Suppose the free edges are (x,y) and (x,z). We can make x as the center of the graph. And calculate the answer as we did for M = 0. We subtract 2C from the final answer.

  2. Suppose the edges are of the form (x,y) and (w,z). In this case, it is not possible to obtain a star graph with N – 1 edges. Suppose we make the center as x. We can connect x to every other (N – 3) vertices. Now the distances from x of every vertex apart from z is 1 and T(x,z) = 2. Thus we have a N -1 edged connected graph of the type for the minimum sum of distances:

alt text

Now, for this graph we have multiple cases again. We have clearly seen that for C <= 2 we connect all the edges. So, even in this case, we connect all the edges when C <= 2 and the cost is calculated like we did for M = 0. We subtract 2C from it.
When C > 2, we did not add an edge in the cases of M=0 and M=1. But here, we do not have a perfect star graph and hence the sum of distances is not necessarily minimum. The edge missing here is (x,z). If we have this edge, we have a star graph with an extra free egde which will reduce the cost by improving the time penalty for the pair (w,z) to 1 which would have been 2 in case of a perfect star graph. Now we should decide if we should add this edge in the optimal model or not.

If we had the edge, we would have paid A = 2( 2(N-3) + 1 + 1) as the time penalty to reach z and reach any other vertex from z i.e. sum of T(i,z) + T(z,i) for all i and C as the cost for one extra edge.
If we dont have the edge, we pay B = 2( 3(N-3) + 2 + 1) as the time penalty to reach z from other vertices and to reach any other vertex from z.

Thus, if A >= B i.e. C >= 2(N-2)*, we will not have the edge in the optimal model.
But if B > A, we have the edge in the optimal model. The costs can be easily calculated.

The other main challenge in this problem was to calculate the answer with precision. Using double will throw an error because we need much more precise calculations. So let’s go through a simple trick for calculating the answer.

Clearly the answer will be in the form

A+C.B where A, B are non-negative integers.

Note that for C>2 we have B < N so C.B<10^9.N<10^18
and for C < 2 we have B = N(N-1)/2 so we still have C.B < 10^18.

Let C = C1+C2/10^d, 0 <= C2 < 10^d (where d=9)
and B = B1.10^d + B2, 0 <= B2 < 10^d then
C.B = C1.B1.10^d + C2.B1 + C1.B2 + C2.B2/10^d
C2.B2 < 10^18 since d=9.

Let C2.B2/10^d = D1 + D2/10^d, 0 <= D2 <10^d.
Then
ans = A + C.B = A + C1.B1.10^d + C2.B1 + C1.B2 + D1 + D2/10^d.

Since C.B < 10^18 then
C1.B1.10^d + C2.B1 + C1.B2 + D1 will fit in long long and D2 is int.
Also it is clear that A<10^18 so
X = A + C1.B1.10^d + C2.B1 + C1.B2 + D1 will fit in long long
and we can print the correct answer in C++ as
printf("%lld.%09d\n", X, D2);

Solution using above approach takes ~0.1 seconds in C++ to clear ALL test files as compared to using BigInt library which takes ~5 s in Java

SETTER’S SOLUTION

Can be viewed here.

APPROACH

The setter used the above approach in his solution.

TESTER’S SOLUTION

Can be viewed here.

APPROACH

The tester used the above approach in his solution.

5 Likes

very good explanation

There’s a simpler proof that star tree has the minimal sum of distances. Consider distances between all pairs of nodes. In star graph 2*(N-1) pairs have distance 1, and all other pairs have distance 2. In any other tree 2*(N-1) pairs have distance 1 (because there are N-1 edges) and all other pairs have distance at least 2. It’s clear that star tree gives minimal sum of distances.

1 Like

As you may noticed guys we currently have no proof that in the case when M=2 and edges cover 4 different vertices the optimal graph with N-1 edges is exactly that graph that was described in the editorial. The correct mathematical statement for this is the following. Let tree T is not a star tree then the time penalty for this tree is at least 2 * (N-1 + 3 * (N-3) + 2 * (N * (N-1)/2 - (N-1) + (N-3))), that is, the time penalty for the tree with edges (0,2),(0,3),…,(0,N-1) and (2,1). This statement seems quite clear intuitively but I could not find the full proof for it even after an hour of thinking. We will really appreciate if someone will prove this statement and post its proof as an answer here.

Why is the near-star-Tree optimal for M = 2 and the two edges are on 4 different vertices.

EDIT: Discussed this with a friend and we came up with 2 proofs.

Proof 1: For each edge (u,v), ask yourself: how much does this edge contribute to the cost? Since the graph is a tree, (and consequently every edge is a bridge), this edge contributes 2 * n1 * (N-n1) to the cost :- where n1 is the number of nodes in the component containing u. Hence, the following holds:

Summation (over all unordered pairs(x,y)) d(x, y) = Summation (over all edges (u,v)) 2n1(N-n1).

Now, note that (a) there are N-1 edges. (b) each edge contributes a cost of atleast 2 * 1 * (N-1), © Since it is not a star, atleast one edge contributes a cost of 2 * 2 * (N-2). From the preceding, and the fact that the near-star-Tree has exactly one edge of cost 2 * 2 * (N-2) while all others are 2 * 1 * (N-1), we get that the near-star-Tree is optimal.

Proof 2: Since the diameter (maximum distance between any 2 pairs of vertices) is atleast 3, we consider a 3-length path a-u-v-b. Now, each node in the component of u to each node in the component of v (after deleting uv) would contribute to a path of length atleast 3. Lets say the number of nodes in the component-of-u = n1. So number of atleast-length-3 paths is atleast (n1-1)(N-n1-1). This means that the number of length-2 paths is atmost N(N-1)/2 - (N-1) - (n1-1)*(N-n1-1). This is maximized for n1-1 = 1. Further, in the near-star-Tree, all the other paths are of length equal to 3.

I think that with trees it’s clear, but I wasn’t convinced about the fact that it has to be tree - I didn’t know for sure if there doesn’t exist some “special” graph that is not tree, but the sum of distances is better…

To state that in another way - suppose the optimal graph has k edges. Then the total sum has k ones, with all others at least 2. k must be at least N-1, and the star graph achieves that bound.

1 Like