Editorial for Yet Another Contest 3 P2 - Work Experience


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.

Author: Josh

Let X, Y, Z be the nodes with Josh, Nils, and Mike are at respectively. Let A be the selected building which minimises the sum of distances.

Subtask 1

The crucial observation is that A is the median of X, Y and Z. This means we can use combinatorics to calculate the number of combinations for each value of A. There are three cases:

  • X, Y and Z are all equal to A: there is one scenario in this case.
  • Exactly two of X, Y, and Z are equal to A: there are 3(N-1) scenarios in this case, as there are N-1 positions other than A that can be chosen, and 3 ways to allocate Josh, Nils and Mike to the positions.
  • All three of X, Y and Z are distinct: there are 6(A-1)(N-A) scenarios in this case, as there are (A-1) ways to choose which position is to the left of A, (N-A) ways to choose which position is to the right of A, and 6 ways to allocate Josh, Nils and Mike to these positions.

Hence, the answer for the building A is 3(N-1) + 6(A-1)(N-A) + 1.

Time complexity: \mathcal{O}(N)

Subtask 2

We can brute force over all \mathcal{O}(N^3) values of X, Y and Z. For each combination, we can find the optimal building in \mathcal{O}(N) time, by performing a DFS / BFS from X, Y, Z. We can alternatively precompute the distances between all buildings by performing DFS, BFS, or Floyd-Warshall.

Time complexity: \mathcal{O}(N^4)

Subtask 3

Root the tree arbitrarily. If we consider the list [LCA(X, Y), LCA(X, Z), LCA(Y, Z)], where LCA(a, b) is the lowest common ancestor of a and b, it can be seen that A 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 \mathcal{O}(1) time. Note that it may be easier and faster to precompute the LCA between all pairs of buildings.

Time complexity: \mathcal{O}(N^3)

Subtask 4

There are multiple solutions, one of which will be described below.

Let f(V) be the number of combinations where the optimal building lies in the subtree of X. Note that our observation from subtask 3 implies that A lies in the subtree of V if and only if at least two of X, Y and Z lie in the subtree of V.

Hence, f(V) = sz(V)^3 + 3sz(V)^2(N-sz(V)), where sz(V) is the size of the subtree of V.

Then, the answer to the problem for each building A is the difference between f(A), and the sum of all f(B) where B is a child of A.

Time complexity: \mathcal{O}(N)


Comments


  • 1
    bu  commented on June 2, 2022, 1:19 p.m.

    How can the approach in subtask 3 work?(I thought you also need to find the building with minimum index)


    • 2
      Josh  commented on June 2, 2022, 2:32 p.m.

      It can be shown that there is always exactly one building with the minimal total distance. So, the minimum index condition is irrelevant.