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)$ ~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)$ ~\mathcal{O}(N)~ or $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~ (if sorting is used to find the two longest paths).

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

Comments

2

peatlo17 commented on Jan. 22, 2021, 8:27 p.m.

I personally find DFS works best for most tree problems, including this one.

1

DynamicSquid commented on Dec. 30, 2020, 9:32 p.m.

When finding the diameter of the 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

Could you clarify the second step about performing "another depth first search from the vertex found in the first step"?

6

BalintR commented on Dec. 30, 2020, 9:58 p.m.

First, you pick an arbitrary vertex and find the vertex farthest away from it. Let's call the vertex we just found A. Then, you use the same algorithm to find the vertex that's farthest away from A. Let's call this vertex B. The diameter of the tree is equal to the distance between A and B.

-1

beibeizhu commented on Sept. 13, 2020, 11:35 p.m. ← edited →

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

-1
DynamicSquid commented on Dec. 25, 2020, 12:01 a.m.
Yes, I think.

I tried to draw it out. So for the second test case, the tree would look like this:

0 2 1 3 5 6 7 4

If we remove the unvisited nodes, and then "stretch" it out, we get this:

[7] - 3 - 2 - [0] - 1 - [6] | [4]

So the length of the tree would be 5, and then we add 2 because we have 1 path that we visited twice (the path to get to the 4).

At least I think that's how it works. I'm still not sure on how to construct the actual tree

1

4fecta commented on Dec. 25, 2020, 2:30 a.m.

First of all, the longest path in a tree is known as its diameter, not its length. Secondly, to learn how to represent graphs in a program, I would recommend you read the article here, paying special attention to the adjacency list section (since that's what most competitive programmers use).

1

DynamicSquid commented on Dec. 26, 2020, 8:33 p.m.

Oh okay. But for the adjacency list, I can find the distance between 2 nodes, but how do I do it for 3 or more nodes?

Reading the question, it says to remove all nodes which aren't a part of the path, and then find the diameter of the tree. But how do I remove all unused nodes?

2

ross_cleary commented on Dec. 26, 2020, 9:43 p.m.

To find the distance between nodes that are not directly connected by an edge, you need to use an algorithm like breadth first search. I would recommend starting with problems that only test breadth first search first (there are a lot of them mostly 7 to 10 point problems tagged as graph theory), and then trying a problem like this. This is because this problem requires special implementations of a breadth first or depth first search that would be extremely difficult to implement if you're not really familiar with the underlying algorithms.

7

peatlo17 commented on July 14, 2020, 4:09 p.m. ← edited →

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

$valid[c_1] \parallel valid[c_2] \parallel \dots \parallel valid[c_n]$

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

0

DynamicSquid commented on Jan. 1, 2021, 7:13 p.m.

Would BFS work as well?

6
cabbagecabbagecabbage commented on Jan. 1, 2021, 10:30 p.m.
I think the reason that DFS is suggested for this specific approach of pruning the tree is that with recursion, when we reach a node and then proceed to traverse the subtree rooted at the node, each child of the node returns a boolean value back to the parent indicating whether there is a pho restaurant in the subtree rooted at that child; and if at least one of those booleans is true (indicating there is a pho restaurant at the subtree), then this parent node must be kept, and otherwise it can be pruned. This specific approach is easier to implement with a recursive traversal than a queue-based traversal because it's much harder to return a value to the parent (and the parent's parent and so on) with a queue based traversal.

The method of pruning using BFS suggested by the editorial is different. First you would loop through each node and determine whether it is a leaf (hint: what would be the size of the adjacency list of a leaf?). If it is a leaf and it isn't a pho restaurant, then you would add this node to your BFS queue because it can be pruned - you don't need to visit that node. Note that we are starting this BFS from more than one node in the graph instead of just one, but the implementation of the traversal isn't too different from a standard BFS from this point on. After putting the prune-able leaves into the queue, you (try to) traverse from every node in your queue: remove the current node by removing it from its neighbor's adjacency list, and add the neighbor into the queue if

they are also a leaf after the current node is removed

they are not a restaurant

Once the BFS finishes (the queue becomes empty) then the pruning is done - nothing else can be pruned, everything that remains must be traversed. Then we can proceed with the rest of the solution.

I'm not an expert so take this with a grain of salt. Please correct me if I said anything incorrect.

11

noYou commented on July 9, 2020, 2:27 p.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.

13

noYou commented on March 14, 2020, 8: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.