Editorial for COI '15 #4 Torrent
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 the minimal time needed for a file to spread over the subtree of node (if we already have the file in node , but not in the other nodes of the subtree).
Let's denote the children of node with . If the file is spread over node first, then and so on, the total time will be . 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 that maximizes . This is easy to see, if we assume that we have a pair of children that are not in sorted order, in other words, and . Then they potentially contribute to the maximum with , which is strictly larger than , 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: , where are sorted descendingly by . The direct implementation is of the complexity .
Let's now return to the problem with two sources, and . Let's observe the path from to . It is clear that, in the optimal spreading of the file on it, there will exist an edge such that the file will come to node from and to from . This is why the optimal spreading would carry out identically even if we erased the edge 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 to and take the best. The complexity of this algorithm is , because we use the algorithm to solve the task with a single source of complexity times.
Let's denote the edge from to with numbers from to . Let's denote as the time required to spread over the component of if we erased the edge . Analogously, let's use for the component of . The solution is then .
A crucial observation is that, as we traverse from to , the component in which node is in (after erasing an edge) becomes larger, so the total time to spread the file over the component of can't be reduced. For the component of , the analogous observation applies, the time cannot increase.
Therefore, sequence is ascending, and is descending. So, if we have for which , the lesser maximum can be found only for a larger . The similar applies for . Therefore, the optimal edge can be found using binary search. The total complexity is then .
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