rhezo's blog

How to solve IOI 2011 RACE using Centroid Decomposition
By rhezo, history, 7 years ago, In English

Problem Link.

Can anyone explain the centroid decomposition solution?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Let's fix a current centroid (root).

So, if path v - u with length k exists and path contains vertex root, we can split it to the two parts: from vertex v to the root and from root to vertex u. Note: vertexes v and u must be in different subtrees of root.

Next, we process every subtreee of root from left to right (or another fixed order) by simple dfs(vertex, distance, edgecount), and collect map<distance, edgeCount> for each subtree (local), and one global map. Suppose now we are in vertex u, with distance D and edgeCount E, we should check, that global map contains k - D key, and update answer if can (answer = min(answer, E + global[k - D]), and update min in local map. After subtree processing, we merge local map to the global.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. This works because for the original centroid we would have to process N vertices in our DFS. And after splitting the tree, in the subsequent DFSs the number of nodes to process gets half. And therefore the complexity would be O(NlogN) excluding the map log factor. Right?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's enough to use an array of size k instead of a map if we are careful about reusing it. This way we can get O(N logN) without any hashing (if one wanted to use a hash map to remove the log factor from using a map). This is the official solution and it can be found here.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we submit the problem?

→ Reply