Frank Underwood is running for the post of "President of the United States of America". He is now in his home state South Carolina for campaigning. Today, he is visiting the city he grew up in, Gaffney.
Houses in Gaffney are arranged in the form of a tree with N nodes. Houses are denoted by the nodes, and roads (each of length 1 unit) are denoted by the edges of the tree. At present, Frank is at his house, which also happens to be the root of the tree. He plans on visiting each and every house in the city. It will be very late by the time Frank finishes visiting all the houses and he will have to spend the night in the last house he visits.
Given the map of Gaffney, can you state the minimum distance he has to travel today to visit each and every house in the city? Let us look at an example:
Houses in Gaffney are arranged in the form of a tree with N nodes. Houses are denoted by the nodes, and roads (each of length 1 unit) are denoted by the edges of the tree. At present, Frank is at his house, which also happens to be the root of the tree. He plans on visiting each and every house in the city. It will be very late by the time Frank finishes visiting all the houses and he will have to spend the night in the last house he visits.
Given the map of Gaffney, can you state the minimum distance he has to travel today to visit each and every house in the city? Let us look at an example:
If Frank travels as shown in Fig 1, the distance traveled by him will be 3 + 3 + 2 = 8 units. However, if he travels as shown in Fig 2, the distance traveled by him will be 2 + 2 + 3 = 7 units. Clearly, Fig 2 depicts a better way of visiting the houses.
View Solution: Solution to "House of Cards"
No comments:
Post a Comment