It’s been a while since the last one, but today we’ll tackle a problem from the first day of the 2011 International Olympiad in Informatics called “Race”. If you don’t know the problem and want to read its statement, here’s the official one: http://www.ioi2011.or.th/hsc/tasks/EN/race.pdf . If you want to run your source code against the official test cases, you can download them along with the template here: http://www.ioi2011.or.th/hsc/testdata/race-test.zip and if you want to submit it on an online judge, try this one: http://wcipeg.com/problem/ioi1112 .
Before we start, I’d like to make a few comments. This problem is sort of a special one for me since I was a participant when it was presented at the IOI. At the time I did poorly on this problem, which wasn’t unexpected since it was the third most difficult problem from that year (judging from the overall scores) and I was still unexperienced and young. However, I don’t feel like this problem is harder than Ideal City, for example, so I’d rank it a 3.5 in a scale from 1 to 5. Having a partial score (even the maximum before 100) is rather easy, but the 100 points can be tricky if you don’t know the right techniques.
Small Disclaimer: The analysis I present here is original (I wrote it and code it independently), but the ideas and concepts have been established for a while. This solution is very similar to the official one you can find at the IOI website, but I wanted to do my own. Also, when I was training to the 2012 IOI I remember trying to implement this problem and had some difficulties with details that were ignored by the official solution as well as how to simplify my implementation.
Task Summary
We’re given an edge weighted tree with N nodes and an integer K. The problem asks us to compute the path with fewest edges such as the sum of the weights of the edges is exactly K.
Solution
As always, I’ll solve the problem incrementally. Even though the solutions for different subtasks are quite different, they give us some insight into the problem.
Subtasks 1 and 2
In the first two subtasks N is less than 100 and 1000, respectively. So a brute force approach is sufficient here. The idea is to perform a single depth first search starting on each node and find which of the found paths that sums to K has the fewest edges.
That said, this is a simple algorithm that can be easily implemented in O(N^2) (since the number of paths in a tree is of this order). The first subtask was made to accommodate solutions that were poorly implemented and ended up being O(N^3), for example, if one was to recompute the distances between each pair of nodes instead of calculating them incrementally.
Subtask 3
The third subtask was still a relatively standard one. For this subtask N can be as large as 200 000, but K is limited by 100. This means we can play around with K as long as we keep our solution linear on N. The idea is to apply a rather well known algorithm, dynamic programming on trees.
We start by rooting the tree in some node u, for example, on node 0. If you are unfamiliar with this concept, rooting here means setting u as the “start” of the tree (from where the rest of the nodes will branch out) and thus we calculate the children of each node and the parent of each node (where the root has no parent). Now we create a dynamic programming array of N by K dimensions. The idea is that for each node v, we have: DP[v][l] = min(DP[c][l – cost(v, c)] + 1) for all c, where c is a child of v and cost(v, c) is the cost of the edge from v to c. In other words, the path with the minimum number of edges that sum l and ends at node v is the minimum of the paths that sum to l – cost(v, c) over all children c of v plus one (the own edge {v, c}). We can easily fill this matrix in O(N * K) if we iterate the tree in a depth first search fashion starting from the root and for each node filling in all values from K to 0. Also, don’t forget the base case, that for all nodes v, DP[v][0] = 0 (and DP[v][x] = ∞ for all x different from 0, we will fill these with the above recurrence).
After we fill the dynamic programming matrix, our answer is the minimum of DP[v][K] for all nodes v. Thus our approach here is O(N * K) and is enough for subtask 3 (notice, however, that this approach doesn’t necessarily work for subtask 2, since K isn’t bounded by 100, so to get full marks on the first three subtasks you’d have to implement both approaches).
Subtask 4
The final subtask requires some more creativity. Now K is no longer bounded by 100, so our solution will have to be linear on both N and K. We could try to approach this in a bunch of different ways, but one way that works well is called centroid decomposition. Instead of simply describing the technique and then trying to apply it, we’ll progressively get there more organically throughout the rest of this analysis.
An initial important observation is that our first solution tries a lot of paths multiple times. I say so because when starting a depth first search on a certain node we are basically “shifting” our previous search one node further. To use this in our favor, we’re going to first select a node from the tree and consider all of the paths pass through that node. To calculate these it is not enough to do a simple depth first search like we did for subtasks 1 and 2, but rather something slightly more ingenious.
Let’s fix a node v and calculate all paths that cross v. If we do a depth first search starting on each neighbor of v (careful to not go back through v), we can store what’s the minimum number of edges necessary to make a path of length l, for all l between 1 and K. Now, if we keep an array A[] of K elements (initially all at infinity, but the element 0, that will be at 0), which we’ll fill with the minimum number of edges to get a path of sum l as A[l]. When we do a new depth first search starting on a new neighbor of v, if the current length of the search is l and we got here using p edges, then there is a path that sums K with p + A[K – l] edges. We have to be careful to not consider overlapping paths, so in practice we do two depth first searches from each neighbor of v, one to calculate the minimums and one to fill the array A[].
If we do the above calculation, we can divide the graph into separate components by removing the node v from the graph (along with all adjacent edges) and recursively calling our method to calculate the answer on each component. We can do so because all paths between components have been considered in the calculation of the above paragraph (since they have to use node v). So essentially we have found a way of dividing our original problem into smaller problems, in a sort of divide and conquer way. But now the question arises: which node should we select as v in order to have the best efficiency possible? Note that the method of the above paragraph is of complexity O(T), where T is the number of nodes in the component we are applying the method (initially this is N), so the better we divide the graph into smaller graphs, the better the complexity. Here is where the idea of centroid decomposition enters. The centroid of a tree is the node whose maximum subtree is minimum, or in other words, that when removed partitions the graph in components whose maximum size is the minimum possible (note that the centroid is not the same as the center, where the eccentricity is minimized instead of the maximum sized subtree). It is sort of the center of mass of the tree and can be generalized to weighted graphs, but here we are interested in the unweighted decomposition, to be able to take advantage of the following result. The following image shows an example of such (notice that 6 would be the center of the tree, but 4 is the centroid).
Why the centroid? Because there is a known result that says that if the original tree has N nodes, the centroid partitions the tree into subtrees each of size at most N/2. It is not very difficult to prove, if a certain node v partitions the tree into a subtree of size larger than N/2, then choose the node from that subtree that neighbors v as the new possible centroid. If we repeat this, eventually there is no subtree is larger than N/2. This helps us because if always select the centroid as the vertex from the previous paragraph, we always divide the tree into at most two trees of size N/2 (or a lot of trees of sizes smaller than N/2 that sum to N). Thus we can apply the divide and conquer idea and get a complexity similar to the merge sort O(NlogN) complexity, for the same reasons.
To find the centroid there are a number of different algorithms. The one I feel is the simplest, is to first root the tree in any node. Afterwards, pre-compute the size the subtree of each node (the subtree that contains all its descendants) using a standard depth first search. Finally, iterate through all the nodes and select the one where: max(T – size[v], size[c1], size[c2], …) is the least possible, where T is the number of nodes of the tree and c1, c2, … are the children of v. This corresponds to the size of all the subtrees starting on v.
So to summarize everything, the algorithm first computes the centroid of the tree in O(N), then calculates all paths that cross the centroid in O(N) and finally divides the tree intro subtrees by the centroid and recursively computes the same (unless the tree has size 1, which is the base case). The overall complexity of this algorithm is O(NlogN), which is enough for the full 100 points.
Implementation Details
I implemented a solution in C++ using the method described for subtask 4. I didn’t implement the methods of the previous subtasks since they are less interesting, but they are simpler. You can find the code here. The code isn’t very complicated, it is actually pretty much divided into the tasks described in the explanation of the algorithm. However, there are a few details I think I should highlight.
First of all, in order to simplify and shorten my implementation, I didn’t actually root explicitly any tree (meaning I didn’t calculate children or parents, like in my previous code for Ideal City 2012). What I actually did was keep an adjacency list and also a processed nodes list. Now, whenever I did a depth first search, I kept the previous node and used it as the parent of the next node in order to prevent infinite recursion. The processed nodes list was used in order to “close” the recursed subtree, that is, whenever I did any recursion after calculating a centroid, I marked the centroid as processed and made sure I never got there again in any of the next calculations, since this node is no longer required. That way, I didn’t have to do expensive operations or pass the graph as an argument to the function.
Another thing that I did and didn’t mention on the explanation above, was the way I dealt with the array with K elements that stored the minimum number of edges needed to make a path of size l for all l from 1 to K. After each recursion step, we need to clean up this array, but we can’t simply memset it or iterate through it, since that would be O(K) and would ruin our lovely complexity. What I did was use a standard (though clever) technique that considers an auxiliary array initially filled with 0. Then, we use an extra variable, initially at 0. Whenever we need to reset the array, we increment the extra variable and only if A_auxiliary[value] == extra variable do we consider the actual value on A[value], if not, we ignore the current value on A[]. Also, whenever we update the value of A[value], we place the value of A_auxiliary[value] = extra variable.
Obviously, another thing to look out are all kinds of overflow. If you implement it in the right way, you shouldn’t need more than a C++ int, but that means capping the depth first searches when the cost sum is larger than K (not on the centroid one, of course).
Concluding Remark
Alas, we have reached the end. This solution is a very specific application of the technique of centroid decomposition that, as you might have guessed by now, is the process of applying divide and conquer on the tree by using the centroid to divide it. There are not a lot of other applications, but I think this one is good enough to be worth learning. The problem is very interesting mainly because it looks much more difficult than it actually is (once you know how to solve it). There were a few 100s in the official contest, so it is a tractable problem, but at the same time it isn’t trivial.
As always, I’m open to comments and corrections you might have.








