Блог пользователя PraveenDhinwa

Any hint/idea to solve CNTTREE spoj
Автор PraveenDhinwa, 11 лет назад, По-английски

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??

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, # |
← Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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]][...][...]

      → Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    @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.

    → Ответить