PROBLEM LINK:
Author: Ankit Kathuria
Tester: Akshay Sharma
Editorialist: Ankit Kathuria
DIFFICULTY:
MEDIUM
PREREQUISITES:
Recursion ,Tree traversal
PROBLEM:
Given a tree, find the weight of shortest path that exist between any two nodes…
QUICK EXPLANATION:
for each node calculate the shortest path that starts from that node. This calculation can be done recursively starting from the leaf nodes in a bottom to top manner. The least of these values will be the answer,
EXPLANATION:
Naive approach:
for each pair calculate the difference of destruction factor and find the minimum.The time complexity is O(N^2) and hance will not be accepted for higher test cases…
Better approach
We are given a tree
Edge length between two nodes will be the difference of destruction factors between the nodes.
Difference of destruction factor between two nodes can be seen as a sum of edge lengths(weight of path) in a path connecting the two nodes.
i->j->k
E[i,k]=D[i]-D[k]=(D[i]-D[j])+(D[j]-D[k])=E[i,j]+E[j,k]
for each of the node N we calculate the weight of the shortest path that starts from N
F(N)= weight of shortest path that starts from N to K(any predecessor of N)
we have to calculate F(N) for every N and find the minimum of all those values.
Calculate F(N):
To calculate F(N), we can either iterate from 1 to n and then getting the weight of the shortest path but that would take O(N) time. and we have to repeat it n times i.e for each node. so The time complexity would be O(N^2) which would be fairly large when N<=100000.
Better method:
calculate the value of F(N) for each of the children of the N.lets say K1,K2,K3…
and then calculate F(N) using all those values.
F(N)= min(E[N,K1]+F(K1), E[N,K2]+F(K2) , E[N,K3]+F(K3),… )
where E[a,b] = edge length from a to b
code would look something like this.
int F( N ) //stores and return the value of F(N)
{
if(N is leaf node)
a[N]=INFINITY;
return INFINITY;
min=INFINITY;
for each children K of N
if(getf(K)+D[N]-D[K]<=min)
min=getf(K)+D[N]-D[K]
a[N]=min;
return min;
}
calling F(root) will fill the array completely for each of the nodes,now we have to just iterate the array a and get the minimum value that will be the answer
Time Complexity : O(N) as we have to just traverse the whole tree once to get the F(N) for each node.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.