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.