AMAEXPER - editorial

PROBLEM LINK:

Practice
Contest

Author: Aleksandar Abas
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica

DIFFICULTY:

MEDIUM

PREREQUISITES:

Trees, Jump Pointers in a Tree

PROBLEM:

Chef has a rooted tree with lengths on edges. For every subtree (rooted at every vertex i) you must find the minimum maximum distance between any two vertices in the subtree.

QUICK EXPLANATION:

We will denote the minimum maximum distance between any two vertices in a subtree by the radius of that subtree. Let the diameter of the subtree be the longest path between any two vertices in the subtree. Then the radius is obtained between one of the endpoints of the diameter and one of the vertices close to the “middle” of the diameter.

Let’s assume that the diameter of the subtree consists of the vertices v(1), …, v(K). Let dist(i,j) be the distance between the vertices i and j in the tree. Let m be the maximum index such that dist(v(1),v(m)) <= dist(v(1),v(K))/2 and dist(v(1),v(m+1)) > dist(v(1),v(K))/2. The middle vertices of the diameter are v(m) and v(m+1), and the radius is min{dist(v(1),v(m+1)),dist(v(m),v(K))}.

We can compute the diameter (and its endpoints) for every subtree rooted at any vertex i in overall O(N) time. In order to find the vertices close to the “middle” of the diameter we can either use the jump pointers technique or we can use an approach similar to the “two pointers” technique. The first option leads to an O(Nxlog(N)) time complexity, while the second option leads to an O(N) time complexity.

EXPLANATION:

We can write a recursive function DFS(x), in which we compute all the needed information:

  • diameter(x)=the diameter of the subtree rooted at the vertex x
  • dmax(x)=the length of the longest path starting at x and going down in its subtree
  • end(x)=a vertex located below x (or equal x) on the longest path starting at x and going down the tree (it may be different depending on whether we use the jump pointers technique or not)
  • droot(x)=the distance from the root to the vertex x
  • radius(x)=the radius of the subtree rooted at the vertex x (the value that the problem asks us to compute)
DFS(x):
    dmax(x) = dmax2 = diameter(x) = radius(x) = 0
    end(x) = x
    for y child of x:
        droot(y) = droot(x) + length of the edge (x,y)
        DFS(y)
        if diameter(y) > diameter(x):
            diameter(x) = diameter(y)
            radius(x) = radius(y)
        if dmax(y) + length of edge (x,y) > dmax(x):
            dmax2 = dmax(x)
            dmax(x) = dmax(y) + length of edge (x,y)
            end(x) = end(y)
        else if dmax(y) + length of edge (x,y) > dmax2:
            dmax2 = dmax(y) + length of edge (x,y)
    if dmax(x) + dmax2 > diameter(x):
        diameter(x) = dmax(x) + dmax2
        Let z be the highest ancestor of end(x) such that (dmax2 + droot(z) - droot(x)) > (dmax(x) + dmax2) / 2.
        radius(x) = min{dmax2 + droot(z) - droot(x), diameter(x) - (droot(parent(z)) - droot(x)) - dmax2}

In order to compute z we can use the “jump pointers” technique. For every vertex x we compute its ancestor anc(x,j) located 2^j levels higher. Using this table we can start at end(x) and go as far as up the tree as possible, as long as the condition regarding the distances holds. Thus, we can find z in O(log(N)) time.

However, we can do better. We can start at end(x) and repeatedly set end(x)=parent(end(x)) as long as the condition involving distances holds. At the end of these iterations we will have end(x)=z. Although it seems that this approach may take O(N) time for each vertex, we can perform an amortized analysis of the algorithm to prove that it actually takes O(N) time overall.

AUTHOR’S, TESTER’S AND EDITORIALIST’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

@admin Links to solution not working.

CodeChef: Practical coding for everyone can some one provide me test case where it will fail?

The author’s solution won’t work for the large test case.

@Author, please give the proof for the amortized complexity.

2 Likes

The problem can be solve easily by observing few points-
On every sub tree for which we need to find out the required answer we have a corresponding root(all other are child of this node in sub tree). Now there are three type of branches it may have-

a) The branch which have maximum weight .

b) The branch which have second maximum weight.

c) All the other remaining Branches .

Now all the branches of type 3 is useless why?
The reason is simple the special value of node for root is the maximum distance to any leaf or simply
the weight of branch type 1 and thus the distance from any node in any branch of type 3 is always greater
the special value of root which is the weight of branch 1 plus distance of any node from branch 3 to
root so we discard branch 3 nodes as we are looking for minimum of such value .

For the same reason we can discard all node of branch 2.

Now we are left with branch one any of these node(including root ) can be the candidate for producing the minimum value this branch consist of two continous sections section start from root to node x and section 2 start from child of node x to leaf of branch 1 type .

The difference between these two type of segment is the type of node they consist of-

  1. nodes are of type who special value of node coming from the distance between this node and the leaf node of branch 1 .

  2. nodes are of type whose special value of node is not coming from leaf of branch one type but from the leaf of branch 2 type .Here the branch 2 need not be of root of this sub tree it may be of any node in the type 1 branch.

Now X and child of x are the candidate for answer , Minimum of two is the right answer.

Now we are left with the part of how to find out the Type X node of parent subtree by knowing the Type x node of child subtree . lets look at Type x of child now consider the child of X node we get, Start from this node
and move upward i.e toward root until the condition of type 2 segment is satisfied with respect to branch 2 of root .Wherever the conditon voialte is the X node also atmost once we have traverse each node for checking condition so complexity to find out X for all subtree can be maximum O(n).

Time complexity: O(n) for each test case.

Solution link:
https://www.codechef.com/viewsolution/9900857

4 Likes

hi ,
could some one explain why radius is our answer.
I think that radius of the diameter will be the minimum of all max , if diameter pass through the root of a subtree. But cann’t there be a possibility that the minimum could be somewhere in the subtree which could pass through diameter , and yet making a min of the max ?
I have not seen the solution , as i want to explore my answer through the editorial .

Thanks in advance…

Can anyone provide some explanation on author’s solution? I am not able to make any relation between author’s solution and the editorial. Thanks in advance!

@admin Links to solutions not working, redirecting to same page.

Apologies. Fixed it…

My Approach was also exactly the same.

Moreover, the author’s solution seems to have complexity of even more than n^2. So, I do not think it will pass all the subtasks.