PROBLEM LINKS:
DIFFICULTY:
Medium
PREREQUISITES:
[Connected Graphs][3], [Linear Functions][4] and MathQUICK 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:
OR
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:
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:
-
Change it to [b,a] : Same as the
above case. The sum of distances
increases further. Here b!=i. -
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:
- 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). - 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.
- 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:
-
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.
-
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:
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.