Editorial for COCI '14 Contest 1 #6 Kamp

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.

Let us observe the case when the camp is placed at house number $1$ ~1~. Because the village is represented as a tree graph, the path from the camp to any individual house to which the volunteers must go is unique. Let us assume that Mirko must return back to camp after he drives all the teams.

When he drives one team to their house and it turns out that another team has to go to a house that is on the way to the first house, Mirko will of course drive both teams in order to save time. Because of the assumption that Mirko has to return back to camp, the solution would then be twice the sum of all edges that connect the camp and all the houses the volunteers go to.

Since the task condition is that Mirko has to stay and help the last team (so, not going back to camp), the best solution is to always drive the farthest team last because that way we drive only once through the tree edges that connect the farthest house. Now the final solution is twice the sum of all edges that connect the camp and all the houses the volunteers go to minus the length of edges in the longest branch.

Finding the edges that connect the camp and houses the volunteers go to can be done in complexity $\mathcal O(N)$ ~\mathcal O(N)~, and when we apply this algorithm in a way that we try to place the camp in every house, the final complexity would be $\mathcal O(N^2)$ ~\mathcal O(N^2)~ and that solution is good enough for half of total points.

Let $K$ ~K~ be the minimal subtree of the given tree that contains all houses the volunteers have to go to and possibly some other houses that are in the way between the volunteers' houses. Let $S$ ~S~ be the sum of all edges of subtree $K$ ~K~. Then the solution for a house $X$ ~X~ is:

$\displaystyle solution[X] = distance[X] + 2S - farthest[Y]$

where $distance[X]$ ~distance[X]~ is the minimal distance between house $X$ ~X~ and subtree $K$ ~K~ or, more specifically, some house $Y$ ~Y~ from subtree $K$ ~K~. Additionally, $farthest[Y]$ ~farthest[Y]~ is the length of the longest chain from house $Y$ ~Y~ in subtree $K$ ~K~. This formula assumes that we know the maximal length of the longest chain for each house in $K$ ~K~, which is possible to calculate by a careful DFS traversal of the tree. The complexity of this solution is $\mathcal O(N)$ ~\mathcal O(N)~ and gives total points.

Comments

There are no comments at the moment.