askhelper's blog

By askhelper, 4 weeks ago, In English,

Hello, all! I am thinking about the following problem:

Given a tree with N vertices and some constant D. You are to find maximum number of vertices you can color if distance between any two colored vertices should be at least D.

How to solve this problem better than $$$O(N^2)$$$? I think for $$$O(N^2)$$$ we can use greedy approach; choose the farthest available vertex from the root.

Any helps are appreciated.

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't see how your greedy approach is working. I have dp solution: root tree in 1 and calculate dp[i][j] for every vertex i and every deep 0<=j<=D recursively, where dp[i][j] is answer for subtree of i where the closest colored vertex is on deep j. Dp equations aren't really hard in that case, something like dp[i][j]=max(dp[u][j-1]+sum_on_children(dp[v][D-j])-dp[u][D-j]) and dp[i][0]=sum(dp[u][D-1])+1. For every node we need O(D*deg_of_node) operations so it work in O(D*sum(deg))=O(N*D) and answer is max(dp[1][j]). Sorry for bad English. EDIT: for j>=D/2 dp[i][j] is just sum(dp[u][j-1])

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$d \leq n$$$, so it is same as $$$O(n^2)$$$ when d is big enough.

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

Very nice problem. Your greedy is correct and that can be used for $$$O(n\cdot\sqrt{n})$$$ solution.

Firstly, let's think about "brute-force" solution. Sort all vertices for its depth from root in descending order. Then iterate these vertices and if current vertex is available then increment the answer and start dfs from that vertex. dfs may go at most $$$O(n)$$$ vertices and we do dfs for each "answer vertex". Notice that answer can be at most $$$O(\frac{n}{d})$$$. So, overall complexity is $$$O(\frac{n^2}{d})$$$.

Now, the tricky part. If we use two dimensional used array such that used[v][d] means we are currently in the vertex v and we will go d more vertices; then we can stop if used[v][d] is already true in the dfs. So, the complexity becomes $$$O(n\cdot d)$$$.

Finally, we combine above solutions. If $$$d \leq \sqrt{n}$$$ then do the second, otherwise do the first one. It can be coded neatly with only one dfs.

Code