PraveenDhinwa's blog

Any hint/idea to solve CNTTREE spoj
By PraveenDhinwa, 11 years ago, In English

Hi, I am unable to find some idea to solve problem http://www.spoj.com/problems/CNTTREE/. I think that this is a dp problem. But no idea how can I find it's states of dp. Could anybody help me with just the state part??

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

Comments Comments (8)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This problem seems interesting, I'll try to solve it.

but why there is no modulo number? do we have to output the exact number?

then we should use some bignum and that's annoying specially for C++ coders

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

    The input is a tree. A naive implementation of the subsets of all edges in the graph is 2^(N-1) where N is the number of vertices in the tree. So the answer will easily fit into a 64 bit signed integer without much analysis.

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I didn't solve it, but this is my idea. Fix the diameter between every two nodes (i,j). Then, try counting how many subtrees have that diameter. You can attach new nodes to any of the nodes between i and j (exclusive, because attaching a node to i or j would increase the diameter). There are some details that still need to be figured out. I'll try to solve it in the near future.

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

select a root node, let it be first vertex.
during DFS calculate for each vertex x values d[x][MaxDepth][MaxDiameter] (0 <= MaxDepth <= n, 0 <= MaxDiameter <= n) — how many subtrees with root x there is, with maximal depth MaxDepth and maximal diameter MaxDiameter. Inside a DFS function you know all matrices of childs of root x. There is simple dp to combine results for childs dd[indexOfAChild][MaxDepth][MaxDiameter]
UPD: Code

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

    I wrote the same solution, but it gets TLE.
    http://ideone.com/4mBo1w

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

      The solution can be improved in n times. you can divide cycles into several ones. In each of this cycles there will be no any if's and max. Then we can reduce number of operations in n times just replacing one of for by sum on some submatrix of d[child[i]][...][...]

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

    @Alias what if we modify the statement a bit. Like given a tree, if we have to find the number of subtrees with atmost k edges connected to the complement of the subtree.

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

      I hope you're not referring to the problem from the currently active hackerrank.com contest :-/

      → Reply