Problem Link:
Setter: Misha Chorniy
Tester: Ke Bi
Editorialist: Rashad Mammadov
Difficulty:
HARD
Prerequisites:
Graph Theory, Trees, DFS and Similar, Data Structures
Problem:
Given a tree with N nodes (servers). Initially there are c_{i} citizens living on the i^{th} server (for each 1 \leq i \leq N). Each citizen can move to a different server through channels. Moving through a channel with ping 2w takes w nanoseconds. Everyone should receive exactly 1 Chefcoin. Chefcoins can only be received on certain servers containing cryptoexchanges. You can only create cryptoexchanges on two servers. Each citizen chooses the closest server with a cryptoexchange and moves to that server. The two servers containing cryptoexchanges can be chosen arbitrarily. Compute the minimum total time it takes all citizens to receive a Chefcoin!
Explanation:
Let’s first consider a simpler version where we have the problem with only one cryptoexchange. How to solve it?
The answer is \displaystyle\sum_{e|E} w \cdot min(size_{to}, S - size_{to}). Why? Here is a greedy proof:
We can root the tree in an arbitrary node, let’s take it 1. In the above expression e|E means for each edge in E. size_{to} shows the number of citizens in the subtree of "to", and S or size_{1} is the total number of citizens in the tree.
The total time for all citizens to receive a Chefcoin is clearly the sum of “w * number of citizens passing through this edge” for all edges in the tree. On the other hand, for each edge (v, to, w) we have 2 choices. Either all the citizens in subtree "to" will pass through the edge (in this case the cryptoexchange is above subtree "to") or all the other citizens will pass through this edge (in this case the cryptoexchange is in subtree "to"). Obviously, it is always better to choose the smaller part. Thus, the above solution for this simpler version is true.
This simplified version can be solved using DFS in O(N) time.
Now, let’s consider the original problem:
Consider the final placement of cryptoexchanges, then there is an edge where nobody will pass through it. This gives an idea to iterate over all edges and remove them from the tree and calculate the answers for two separate trees independently by the above algorithm. This gives us an O(N^2) solution.
It’s not the end, O(N \cdot logN) solution can be achieved.
Let’s define in_{v} (entering) and out_{v} (living) times for node v during the DFS. Then all the nodes in the subtree of v are placed in the interval [in_{v}, out_{v}].
If the problem would be for exactly one cryptoexchange we should find the sum over all edges (v, to, w): \displaystyle\sum_{e|E} w \cdot min(size_{to}, S - size_{to}), but with two cryptoexchanges, we don’t need to calculate something like w \cdot min(size_{to}, S - size_{to}). Here is a simple and beautiful trick in rewriting: w \cdot min(size_{to}, S - size_{to}) as w \cdot size_{to} if size_{to} \leq \frac{S}{2} and w \cdot S - w \cdot size_{to} if size_{to} > \frac{S}{2}.
Now, get back to the idea of O(N^{2}) solution. Let we remove an edge (v, to, w) in DFS from the tree. We get two subtrees with sizes X = size_{to} and Y = size_{1} - size_{to}. Then solve the problem for subtree "to" and subtree above.
For subtree "to":
We need to find the sum over all indices in the DFS-order for the interval [in_{v}, out_{v}] of w \cdot min(size_{to}, X - size_{to}). By that trick we need to find the sum w \cdot size_{to} (for all size_{to} \leq \frac{X}{2}) + w \cdot X (for all size_{to} > \frac{X}{2}) - w \cdot size_{to}(for all size_{to} > \frac{X}{2}).
The remaining part is related to finding the sum of numbers \leq K on an interval [l, r] and can be done offline with scanline and Fenwick trees by compressing coordinates "w \cdot size_{to}" and "w" for the intervals [in_{to}, out_{to}] and the number \frac{X}{2}.
Subtree above (all tree except subtree "to"):
Everything is similar, just we need to make these things at intervals [1, in_{to} - 1] and [out_{to} + 1, N] and with subtree size Y, except for the chain from the root (let’s call it 1) to "v"(subtree "to" includes to these subtrees). Fortunately, we can say that for this case by binary-search (or two pointers) and prefix sums as the function size_{u} decreasing on the chain from "1" to "v", we can subtract what we counted for \leq \frac{Y}{2}. Let’s make the same things but only for size_{1} - size_{u} and will add what we need to be > \frac{Y}{2}, this function is increasing from "1" to "v".
The overall complexity of this solution is O(N \cdot logN) with a hidden constant around 10-15.
Time Complexity:
O(N \cdot logN)
Space Complexity:
O(N \cdot logN)