repeating's blog

By repeating, history, 23 months 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  

»
23 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Great job :D Thank you :)

»
23 months 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)

»
23 months 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 ?

  • »
    »
    23 months 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).

»
23 months 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.

  • »
    »
    23 months 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.)

    • »
      »
      »
      23 months 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.

»
23 months 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

»
23 months 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).

»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it
»
22 months ago, # |
  Vote: I like it -10 Vote: I do not like it

why just problems on CF ?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

uva 12772

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4625

I only came up with O(n*sqrt(n)*lg(n)) complexity, which will get tle...

»
22 months 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

  • »
    »
    22 months 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?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks :)

»
22 months 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://codeforces.com/contest/161/problem/D)

»
22 months 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

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it
»
13 months 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!

»
4 months 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.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

766E , centroid decomposition is not fast enough..