Please read the new rule regarding the restriction on the use of AI tools. ×

just_chill_123's blog

Need Help in a Tree question.
By just_chill_123, history, 12 months ago, In English

Any approach for this question? Only approach i could think of was greedy around centroid. https://www.codechef.com/problems/ADMN?tab=statement

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

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

I am also not getting any approach. Anyone??

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

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.

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

    Yeah, weird! Makes me wonder where this question comes from.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Can you please elaborate your approach.

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
        ← Rev. 3   Vote: I like it +11 Vote: I do not like it

        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 of i. The second vector counter[i] is defined like this:

        • When we place a minister down, the counter becomes D+1. This means we can go up to D steps away with the counter being more than zero.
        • If the counter is more than zero, the current node is in range of a minister.
        • If the counter is zero or below, 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 of i.
        • All roots begin with a counter of 0, since they themselves are not in range of a minister.

        We know that once the counter reaches -D it is D + 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:

        if (counter[u] == -D) {
  dp[u] += 1;
  counter[u] = D+1;
}

        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 the counters is as follows:

        • Only the maximum and minimum counters matter: the extra range we have from one minister at the best case (maximum) and the 'deficit' of a minister at the worst case (minimum).
        • We need to come up with a condition that tells us whether the extra range will cover the deficits. The condition is: mx - 2 >= 1 - mn. This is because the steps away from being in range of the last minister is 1 - mn, and the minister's range will decrease by two by the time it enters the different subtree (mx - 2).
        • So, if the condition is satisfied we don't need to worry about those subtrees, and the counter of this node will be mx - 1. Otherwise, we do care about those subtrees and the counter becomes mn - 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.

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          nice sol

          → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          orzz..

          → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          "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 doing counter[u] = mn - 1. This could be negative but at the same time node u could be within d distance of a minister (perhaps along the child with the maximum counter value)

          What am I missing here?

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

            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.

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

              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 of i. That makes a lot more sense now, I hope? Thank you for pointing that out.

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

          Very nice soln,just one question we are always considering 0 as root,why would it always work ?

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply