Editorial for COI '15 #4 Torrent


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's first solve the simpler problem where there is only one source. Let's denote with f(i) the minimal time needed for a file to spread over the subtree of node i (if we already have the file in node i, but not in the other nodes of the subtree).

Let's denote the children of node i with c_1, c_2, \dots, c_m. If the file is spread over node c_1 first, then c_2 and so on, the total time will be \max_{j=1}^m \{f(c_j)+j\}. Therefore, we need to choose the optimal order of sending the file to the children. It's intuitively clear that it is best to first send the file to the node in which the further sending requires the most amount of time, so node c_j that maximizes f(c_j). This is easy to see, if we assume that we have a pair of children that are not in sorted order, in other words, f(c_j) < f(c_k) and j < k. Then they potentially contribute to the maximum with f(c_k)+k, which is strictly larger than \max\{f(c_j)+k, f(c_k)+j\}, so the substitution of these two nodes cannot worsen the total time. Therefore, it is truly optimal to sort the children.

We have the relation: f(i) = \max_{j=1}^m \{f(c_j)+j\}, where c_j are sorted descendingly by f(c_j). The direct implementation is of the complexity \mathcal O(N \log N).

Let's now return to the problem with two sources, a and b. Let's observe the path from a to b. It is clear that, in the optimal spreading of the file on it, there will exist an edge (c, d) such that the file will come to node c from a and to d from b. This is why the optimal spreading would carry out identically even if we erased the edge (c, d) and split the tree into two components. If we knew which edge we need to erase, we would just do it and solve the problem for a single source on both given components. The maximum of these two times would be optimal.

One solution is to try edge after edge on the path from a to b and take the best. The complexity of this algorithm is \mathcal O(N^2 \log N), because we use the \mathcal O(N \log N) algorithm to solve the task with a single source of complexity \mathcal O(N) times.

Let's denote the edge from a to b with numbers from 1 to L. Let's denote f_a(i) as the time required to spread over the component of a if we erased the edge i. Analogously, let's use f_b(i) for the component of b. The solution is then \min_{i=1}^L \{\max\{f_a(i), f_b(i)\}\}.

A crucial observation is that, as we traverse from a to b, the component in which node a is in (after erasing an edge) becomes larger, so the total time to spread the file over the component of a can't be reduced. For the component of b, the analogous observation applies, the time cannot increase.

Therefore, sequence f_a(i) is ascending, and f_b(i) is descending. So, if we have i for which f_a(i) < f_b(i), the lesser maximum can be found only for a larger i. The similar applies for f_a(i) > f_b(i). Therefore, the optimal edge can be found using binary search. The total complexity is then \mathcal O(N \log^2 N).

For the curious reader: Try to reduce the complexity of the algorithm for a single source. Solve the task if, initially, the file is located on three computers (using the same limitations).


Comments

There are no comments at the moment.