Блог пользователя rhezo

How to solve IOI 2011 RACE using Centroid Decomposition
Автор rhezo, история, 7 лет назад, По-английски

Problem Link.

Can anyone explain the centroid decomposition solution?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where can we submit the problem?

→ Ответить