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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
Great job :D Thank you :)
Here's a nice problem about Centroid Decomposition : Race (although it's from IOI '11 not codeforces)
Can't it be solved without CD?
It can be solved using DSU on Tree.
The complexity is always O(nlogn) ?
So it doesn't depend on the problem or on the requested queries ?
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).
Thanks a lot :D
Your reply here helps me a lot after 3 years.
Mahmoud and a xor trip usually fails with cd due to the tight time limit. O(nlognlogM) is sadly too much.
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.)
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.
if you want you can add these problems :
150E — Freezing with Style
293E — Close Vertices
Done
Thanks :D
your welcome
How is 183C - Cyclic Coloring related to centroid decomposition?
you are right :) sorry. repeating pls remove Cyclic Coloring
Auto comment: topic has been updated by repeating (previous revision, new revision, compare).
348E - Pilgrims
why just problems on CF ?
Because this blog's on CF !!
that doesn't make sense!
Tree2 from Timus can be solved using multiple techniques and Centroid Decomposition is one of them
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?
Can anyone help me with Centroid Decomposition approach to the problem 161D("Distance in Tree")(http://codeforces.me/contest/161/problem/D)
CD is so overkill. Subtree DP is faster and easier.
with subtree DP you achieve an NK solution?
18045256
Thanks
Sorry, may I ask if it is an official name? It is an awesome technique. I have seen it in USACO once but never thought that it would be applicable here :)
Subtree DP? Isn't that just the most basic DP on tree? I think I must have missed something.
Well, it is not like there exists an internationally standardized curriculum about DP in this world :v , all I know about what-so-called "DP on tree" is that the technique is DP and the problem involves tree.
Can you explain the "awesome technique"? Thanks!
If you want to read about "DP on Tree" here's a tutorial:
https://codeforces.me/blog/entry/20935
I haven't read all of it but it looks promising.
http://codeforces.me/contest/161/submission/31966570
Should be self explanatory i think.
http://codeforces.me/contest/161/submission/31470816 This is also the effecient way
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
It's OK
Thanks for your help
New problem with CD: http://codeforces.me/contest/914/problem/E
Can someone explain the solution of 766E — Mahmoud and a xor trip with Centroid Decomposition? Thanks in advance!
No.
Stop downvoting!!
Can anyone tell the centroid decomposition solution to 161D? I did it using a n*k dp.
see rumblefool solution.. he solved it using cd
766E , centroid decomposition is not fast enough..
While it might be easier to solve with DP instead of CD (Centroid Decomposition), it still can be done with CD pretty comfortably I think.
https://codeforces.me/contest/766/submission/32760352
Here's my solution for example using CD that takes less than 600ms where TL is 2s.
I am not saying that using CD here is a better idea, just showing that it's possible to do it with CD.
yeah, I 'll try to improve my code base on your code.
Thanks for share~
old one: https://codeforces.me/contest/766/submission/51847865
new one: https://codeforces.me/contest/766/submission/54057910
There was a flaw in my answer's rekoning part, which cause square time complex~.
Now it's fixed and fast enough.
1156D - 0-1-Tree also can be solved using Centroid Decomposition.
Here is my solution using CD: 54143834
cd is an overkill for this problem
A recent problem of CF 563 Div2 : F. Ehab and the Big Finale
khung
This is a nice one: https://codeforces.me/contest/914/problem/E
https://codeforces.me/problemset/gymProblem/100633/D?locale=ru
Interactive Question
Two from codechef:
https://www.codechef.com/MARCH21A/problems/RWALKS
https://www.codechef.com/COOK132A/problems/MAXJMP
If anyone have solved all the questions then please share the submission link.