Any approach for this question? Only approach i could think of was greedy around centroid. https://www.codechef.com/problems/ADMN?tab=statement
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Any approach for this question? Only approach i could think of was greedy around centroid. https://www.codechef.com/problems/ADMN?tab=statement
Название |
---|
I am also not getting any approach. Anyone??
O(N) solution
I dont really want to descriminate the problem: I submitted an O(nd) solution that shouldnt pass and it AC in 0.07s. This means that the test data is very weak. Hence, I will assume that d is small.
In fact, this problem is similar to a problem on luogu.com.cn
Here is the link: https://www.luogu.com.cn/problem/P3267
This is kind of a similar problem but with more limitations. You will have specific nodes that you have to "administer" and different prices of putting a minister at different nodes.
My solution is with O(nd), which I dont think I will discuss it here because its time complexity doesn't match and the author clearly didnt generate strong test data.
Yeah, weird! Makes me wonder where this question comes from.
Weird that NeoYL's code passes with O(ND). Here's an O(N log N) solution: https://www.codechef.com/viewsolution/1025837353 (I apologise that it's very messy, I would make it more readable but I've got to go now. Essentially it's a rerooting tree DP)
Oh wait, it works even without the rerooting LMAO, I just assumed the question was difficult enough to require rerooting without thinking, oh well. Here's the O(N) solution then: https://www.codechef.com/viewsolution/1025839057
Can you please elaborate your approach.
Imagine drawing the tree downwards, then the principle of the program is that we need to place the ministers as high as possible on the tree whilst still reaching the leaves at the very end of the tree. The first vector
dp[i]
represents the number of ministers in the subtree ofi
. The second vectorcounter[i]
is defined like this:D+1
. This means we can go up toD
steps away with the counter being more than zero.-counter[i]
is the longest distance to any node that doesn't have a minister in range of it, in the subtree ofi
.0
, since they themselves are not in range of a minister.We know that once the counter reaches
-D
it isD + 1
steps away from being in range of the last minister. Meaning that if we put a minister down here the range that the minister has control over will go exactly up to the end of the range of the previous minister. That's what this code does:Let's talk about merging the results for different subtrees in the DFS. Obviously, we need to do
dp[u] += dp[v];
since the number of ministers in one subtree includes the ones in the children's subtrees. Now, the way we merge thecounter
s is as follows:mx - 2 >= 1 - mn
. This is because the steps away from being in range of the last minister is1 - mn
, and the minister's range will decrease by two by the time it enters the different subtree (mx - 2
).mx - 1
. Otherwise, we do care about those subtrees and the counter becomesmn - 1
.We continue to merge like this up to the root. Lastly, to calculate the answer we need to take
dp[0]
. However, if the root itself is not in range of any ministers (that is,counter[0] <= 0
), we need to place a minister down there, adding one to the answer.Hope that makes sense! Please ask for clarifications if you don't understand something.
nice sol
orzz..
"If the counter is zero or below, the current node is 1 — counter steps away from being in range of the last-placed minister on its subtree"
You are not really maintaining this invariant, are you? When merging the results of children of node
u
, if the condition you mention isn't satisfied you are doingcounter[u] = mn - 1
. This could be negative but at the same time nodeu
could be within d distance of a minister (perhaps along the child with the maximum counter value)What am I missing here?
You're right — it's hard to explain what the counter variable is xD
The reason I set counter to
mn - 1
is to account for the nodes along the subtree of its child which don't have a minister assigned to them. I'll try to revise my explanation later tonight.I just thought of the following description of
counter[i]
: the value of-counter[i]
is the longest distance to any node that doesn't have a minister in range of it, in the subtree ofi
. That makes a lot more sense now, I hope? Thank you for pointing that out.Yeah, thanks for the clarification
Very nice soln,just one question we are always considering 0 as root,why would it always work ?
Simply because of how the DP is defined. The minimal solution is always maintained in the DP. One example of where we need rerooting is a question which requires us to find the node which has the lowest maximum-distance-to-any-other-node in a weighted tree. We would need rerooting there since the DP is defined in such a way where the answer isn't guaranteed to appear in it from using a single root.