NeverSayNever's blog

STANDARD DP APPROACH

By NeverSayNever, 10 years ago, In English

Hello all,

I am trying to solve this problem

https://www.hackerrank.com/contests/101hack19/challenges/journey-scheduling

Editorial for this problem mentioned that the query for the longest distance for any given node in a tree can be performed with standard DP approach ... I am not familiar with the approach and also unable to find content regarding this on internet so please can anyone help me understanding this .. or provide me link for good tutorial for this standard approach with reference to some more problem ...

Thanx in advance ..

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Hi, with second time distance is diametr of tree.

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

    Yes you are absolutely correct but actually i need to query first for the longest distance that i can traversed from current position / current node . I want to know approach of finding that .. Please help if you can ..

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

      the longest distance from any node is always to travel to one of diameter ends ,if there are more than one diameter choose any one of them

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

        @kingofnumbers

        Can you please elaborate this a bit more.. I am getting whatever you are saying .. but still need more clarification ..

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

          This is what i have understood that we can first find the diameter of the tree which can be calculated using a single call to DFS easily (also maintain the start point and end point right)then for each node i will find the distance of this to both of the end point and end point which will give me maximum answer is the answer to the query right.. For this purpose i can use DP LCA ...

          Each query taking log(n) time so the total complexity is Q(log(N))..

          I understood this ... But i read in the editorial that this can be done V+E. Is the idea first find the two end points and then do DFS two time one for each point..

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

            Or even easier , you don't need LCA here's what you should do:

            1. find the diameter of the tree , this step needs doing dfs twice.

            2. now suppose the end points of the diameter are nodes v and u , do dfs from u to calculate the distance to u from all other nodes. do dfs from v to calculate the distance to v from all other nodes

            3. now for each node you have two values , the distance from it to v and to u , so for each node take the maximum of these two values , this is what you need.

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

              Thanx i mentioned this at the end of the above comment and i dont think we need twio dfs to find the diameter with start point u and v we can do that using only one dfs isn't it ??

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

                yes if you used the dp way for finding the diameter,

                there's another way to find the diameter by picking some random node v then go to farthest node from v call it u then go to farthest node from u call it w , now u and w are ends of diameter.

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

              @kingofnumbers

              Can you please post some related problem or some good tutorials related to tree terminologies... my mean such kinds of terminologies .. :D

              thanx

              → Reply