repeating's blog

Centroid Decomposition
By repeating, history, 7 years ago, In English

Hi

These are some problems about Centroid Decomposition , you can learn this algorithm here .

Its complexity is O(nlogn)

I hope these problems would be useful for you :)

If there are another problems on CF please put it on comment !!

UPD : The list has been updated

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

Comments Comments (56)
| Write comment?
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Great job :D Thank you :)

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

Here's a nice problem about Centroid Decomposition : Race (although it's from IOI '11 not codeforces)

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

The complexity is always O(nlogn) ?

So it doesn't depend on the problem or on the requested queries ?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +21 Vote: I do not like it

    Lol, don't try to memorize it. Understand why it is O(N*logN). You build the centroid-decomposition-tree. The tree has logN levels. From each level, you do a DFS and visit atmost N nodes in total. So, you perform NlogN operations. If you do other stuff while visiting the nodes, the complexity will change too. For example, if after visiting each node, you insert into some global set, you introduce another logN factor. So, yes, it depends on the problem and the requested queries. O(NlogN) is just the bound on the total number of nodes you visit during the DFSs (a particular node may be visited multiple times from different centroids).

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

      Thanks a lot :D

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

      Your reply here helps me a lot after 3 years.

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

Mahmoud and a xor trip usually fails with cd due to the tight time limit. O(nlognlogM) is sadly too much.

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

    I don't understand why you'd solve 766E - Mahmoud and a xor trip using CD anyway. In problems where simple dynamic programming suffices, there's no need to go through the hassle of implementing centroid decomposiotion. Reserve it for problems where all paths rooted at some vertex can't be represented by 2 integers total.

    (I guess practicing CD is a reason enough. Still, I'd explore simpler solutions.)

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

      I ain't gonna solve it using cd :D

      I'm just warning since I've seen many cd-oriented solutions failing with TLE here.

      → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

if you want you can add these problems :

150E — Freezing with Style

293E — Close Vertices

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

Auto comment: topic has been updated by repeating (previous revision, new revision, compare).

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

348E - Pilgrims

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

why just problems on CF ?

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

Tree2 from Timus can be solved using multiple techniques and Centroid Decomposition is one of them

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

    Can you elaborate on your approach? I solved it using CD, however my solution is a bit slow(0.3 seconds, there are submissions in less than 0.1)? What is your complexity?

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

Can anyone help me with Centroid Decomposition approach to the problem 161D("Distance in Tree")(http://mirror.codeforces.com/contest/161/problem/D)

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

Don't get angry if I mention this problem even if it's not on CF: I think is very interesting Centroid Decomposition problem, and it's pretty difficult. https://csacademy.com/contest/archive/task/flareon

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

New problem with CD: http://mirror.codeforces.com/contest/914/problem/E

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

Can someone explain the solution of 766E — Mahmoud and a xor trip with Centroid Decomposition? Thanks in advance!

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

Can anyone tell the centroid decomposition solution to 161D? I did it using a n*k dp.

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

766E , centroid decomposition is not fast enough..

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

1156D - 0-1-Tree also can be solved using Centroid Decomposition.

Spoiler
→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A recent problem of CF 563 Div2 : F. Ehab and the Big Finale

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

This is a nice one: https://mirror.codeforces.com/contest/914/problem/E

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

https://mirror.codeforces.com/problemset/gymProblem/100633/D?locale=ru

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

Interactive Question

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

Two from codechef:

https://www.codechef.com/MARCH21A/problems/RWALKS

https://www.codechef.com/COOK132A/problems/MAXJMP

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone have solved all the questions then please share the submission link.

→ Reply