aloo_parantha's blog

Decomposition of Paths
By aloo_parantha, history, 3 years ago, In English

You are given a tree that contains vertices and queries. Each query is determining the number of decompositions of the tree into paths and the path from to that is one of the paths in the decomposition modulo 998244353.

A tree decomposition in paths is valid if each vertex belongs to exactly one path. A path can be a single vertex. Two decompositions are different if there are two vertices and that belong to the same path in one of the decompositions but two distinct paths in the other.

Sample Input:

5 2 3 1 4 1 1 5 2 5 3 3 2 5

Output :

8 4

Can anyone please explain this problem with an example... Problem Link : https://www.hackerearth.com/problem/algorithm/path-decomposition-ii-ad4b4a0c/

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aloo_parantha (previous revision, new revision, compare).

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

A tree decomposition is just a splitting of the tree into vertex-disjoint paths. So here's one possible decomposition of the sample case: https://ibb.co/dLyFzNc

The paths in that image are $$$4-4, 1-3, 2-5$$$.

The queries simply ask you to count the number of tree decompositions that contain $$$u - v$$$ as one of the paths.

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

    If I say to answer each query I'll just erase the path from u to v and the tree will break into many trees now ,so no of ways to break the remaining tree, is our required answer. Is it equivalent to what u just said?? For second query 2 5 of the given example, if we erase the path from 2 to 5 Now we will be left with a tree with 3 nodes, we have 2 edges in it, so no of decompositions possible is equal to 2^(remaining edges after erasing the u — v path) that equals to 2^(2) = 4 in this case.... Can u please explain it with a good example.

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

      Well your formula for number of path decompositions ($$$2^\text{number of edges}$$$) isn't exactly right, but yes, if the query was the path $$$u - v$$$, then you can think of it as erasing the path and multiplying the number of path decompositions of the remaining trees.

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

        And the path u-v that I am erasing,I am assuming that we can't attach anything to it, while breaking it. Is it Correct?? I spent a lot of time on this problem , but still couldn't figure out what's going wrong. Can u please explain it with an example other than the sample case, because what I am assuming gives correct answer on those cases, so any good example on which my logic of removing paths fails. Thanks :)

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

          Yes, you cannot attach anything to the path $$$u - v$$$. Your interpretation of the problem is fine, I recommend you check the way you're calculating the number of path decompositions of a tree, as I have a hunch that might be the culprit.

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

            I tried to implement the brute force soln. Using normal traversal we can store the parents, and for every query pushed all the elements in the path of u to v in the set, and then called dfs keeping the check that I don't traverse any of the node in the set. And my answer is 2^(no of edges I traversed) https://ideone.com/Cve3z3. Can u please have a look on it. Thanks :)

            → Reply