Editorial for Yet Another Contest 3 P2 - Work Experience
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Let be the nodes with Josh, Nils, and Mike are at respectively. Let be the selected building which minimises the sum of distances.
Subtask 1
The crucial observation is that is the median of , and . This means we can use combinatorics to calculate the number of combinations for each value of . There are three cases:
- , and are all equal to : there is one scenario in this case.
- Exactly two of , , and are equal to : there are scenarios in this case, as there are positions other than that can be chosen, and ways to allocate Josh, Nils and Mike to the positions.
- All three of , and are distinct: there are scenarios in this case, as there are ways to choose which position is to the left of , ways to choose which position is to the right of , and ways to allocate Josh, Nils and Mike to these positions.
Hence, the answer for the building is .
Time complexity:
Subtask 2
We can brute force over all values of , and . For each combination, we can find the optimal building in time, by performing a DFS / BFS from . We can alternatively precompute the distances between all buildings by performing DFS, BFS, or Floyd-Warshall.
Time complexity:
Subtask 3
Root the tree arbitrarily. If we consider the list , where is the lowest common ancestor of and , it can be seen that equals the least frequently occurring element in this list. The proof of this is left as an exercise to the reader.
This allows us to find the optimal building for each combination in time. Note that it may be easier and faster to precompute the LCA between all pairs of buildings.
Time complexity:
Subtask 4
There are multiple solutions, one of which will be described below.
Let be the number of combinations where the optimal building lies in the subtree of . Note that our observation from subtask implies that lies in the subtree of if and only if at least two of , and lie in the subtree of .
Hence, , where is the size of the subtree of .
Then, the answer to the problem for each building is the difference between , and the sum of all where is a child of .
Time complexity:
Comments
How can the approach in subtask 3 work?(I thought you also need to find the building with minimum index)
It can be shown that there is always exactly one building with the minimal total distance. So, the minimum index condition is irrelevant.