View Problem: House of Cards
Let us assume that instead of spending the night in the last house he visits, Underwood returns to his house the same day. Clearly, in such a case, the distance he travels will be 2 x (Number of Edges in the Tree) = 2(N-1). Now, if he does stay back in the last house he visits, it will be best if the distance between his own house and this last house (say D) is as large as possible. This is because the distance traveled by him in this case will be 2(N-1) - D. Hence, the minimum distance traveled by Underwood will be 2(N-1) - (Length of the longest path between the root to a leaf).
Let us assume that instead of spending the night in the last house he visits, Underwood returns to his house the same day. Clearly, in such a case, the distance he travels will be 2 x (Number of Edges in the Tree) = 2(N-1). Now, if he does stay back in the last house he visits, it will be best if the distance between his own house and this last house (say D) is as large as possible. This is because the distance traveled by him in this case will be 2(N-1) - D. Hence, the minimum distance traveled by Underwood will be 2(N-1) - (Length of the longest path between the root to a leaf).
No comments:
Post a Comment