CDIT04 - Editorial

PROBLEM LINK:

Practice

Contest

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.