Editorial for CCC '16 S3 - Phonomenal Reviews


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: FatalEagle

First, remove all vertices from the tree that are not a part of the vertex-induced subgraph formed from the Pho restaurants. This can be done with a breadth-first search from the leaves of the tree inwards, at each step adding all neighbors of the currently processing vertex that are not processed yet and are not Pho restaurants into the queue. This process does not change the answer for the problem, as those vertices will never be visited in the optimal solution. From here on, we will assume that all leaves of the tree are Pho restaurants (i.e. we must visit all the leaves at least once).

To visit all the leaves at least once, you must visit all vertices of the tree at least once. This is similar to a depth first search. If we add the condition that Jo should return to where she started, then no matter how Jo visits the vertices she will traverse each edge twice, taking exactly 2 \cdot (N-1) time. However, in the real problem, Jo does not have to return to her starting vertex. Therefore, there will be exactly one path in the tree where each edge is traversed once instead of twice (if there are edges not on this path that are traversed only once, then Jo must have somehow teleported between vertices, which is impossible). Obviously, to minimize the time Jo takes, we should maximize the length of such a path. This path is called the diameter of a tree. There are many ways to compute the diameter of a tree. The simplest way is to perform a depth first search from any vertex, find any of the farthest vertices from this vertex, then perform another depth first search from the vertex found in the first step. The distance between the vertices found at the end of both steps will be the diameter of the tree (proof is left as an exercise to the reader). Another way is to find the diameter recursively: the diameter is either in a subtree of the root, or it is formed by joining the two longest paths in different subtrees passing through the root. This method may be implemented in either \mathcal{O}(N) or \mathcal{O}(N \log N) (if sorting is used to find the two longest paths).

Complexity: \mathcal{O}(N) or \mathcal{O}(N \log N)


Comments


  • -1
    beibeizhu  commented on Sept. 13, 2020, 7:35 p.m. edited

    So the answer should be whatever a diameter's length + those edges visited twice * 2?


  • 7
    peatlo17  commented on July 14, 2020, 12:09 p.m.

    DFS and dynamic programming allows you to prune the tree quite nicely. Just keep some boolean array valid[x] which evaluates to true if there is at least one pho restaurant in the subtree of x and false otherwise. Thus valid[x] is true if

    valid[c_1] \ || \ valid[c_2] \ || \ \dots \ || \ valid[c_n]

    Where c_1, c_2, \dots, c_n are the child nodes of x.


  • 6
    noYou  commented on July 9, 2020, 10:27 a.m. edited

    The editorial suggests BFS, a queue based algorithm for inducing the subgraph. I tried for a few days to get this to pass but to no avail in java. Looking at the slowest AC java 8 submissions, even they do not use BFS to induce the subgraph, indicating that it probably is not possible, or at the very least not worth your time to try and prune the tree using BFS in java.

    That being said, if you're scared of c++ like me, an alternative approach to the pruning is to use DFS.

    Root the tree at a pho restaurant, and go down the levels of the tree using DFS, passing the total amount of pho restaurants in each subtree to the top. If there are no pho restaurants in any given subtree, this indicates that an optimal solution would never visit this subtree, and it can be safely ignored.

    This works because the root node is a pho restaurant, and if there is a pho restaurant in the subtree, it would probably be used because of the 1 path property between every 2 nodes of a tree.

    The rest of the java solution can be achieved by following the rest of the editorial.


  • 4
    noYou  commented on March 14, 2020, 4:17 p.m.

    remove all vertices from the tree that are not a part of the vertex-induced subgraph formed from the Pho restaurants. This can be done with a breadth-first search from the leaves of the tree inwards, at each step adding all neighbors of the currently processing vertex that are not processed yet and are not Pho restaurants into the queue.

    What does this mean? I don't understand.