computer_jock's blog

how to approach this problem ??
By computer_jock, history, 17 months ago, In English

you have been given tree, find a shortest path to travel from 1 to N, such that you visits some given set of nodes in your path from 1 to N. you are allowed to visit same node multiple times.

eg — N = 5 


      1  
    /  \ 
  2     3
      /   \ 
    4      5

node_to_visit_in_path = { 2 ,4 }

solution — 6 ( 1 -> 2 -> 1 -> 3 -> 4 -> 3 -> 5)

CONSTRAINTS; 
N UPTO ( 2 * 1e5 ) 
size of {node_to_visit_in_path}  : upto N-1

is this a famous kind of problem ?, i think similar problem i have see somewhere.

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

Comments Comments (10)
| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u specify the constraints pls?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what about the size of node_to_visit_in_path? How big can that get.

→ Reply
»
17 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Oh its a tree. I didn't realise it was a tree. Lets say u root the tree at 1, and u start at 1. Notice if u do a simple dfs, to visit all nodes in node_to_visit_in_path, and nothing more, and end up back at 1, u will get the minimum path for that route. (a route which starts at 1, visits all necessary vertices, and ends up back at 1). So now, instead of ending up at 1, u need to end up at N. This means, u just need to choose the last necessary vertex that u visit. I think the optimal choice is over all vertices which are either ancestors of N, or are in the subtree of N, the one with the highest depth. Call this node, opt_node. So the path is

Do a trivial dfs which starts at 1, and goes to all necessary nodes, but ends at opt_node. Then, go from opt_node -> N. This shldn't be too hard to implement which simple techniques like in/out time.

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

    Im not 100% sure im right tho. So do double check.

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

    Also notice, if there is no necessary vertex which is an ancestor, or in subtree of N. U do trivial dfs to visit all necessary nodes, end up back at 1, then go to N.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

just dfs and check the path when you reach node N

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is equal to 2*(total weight of edges in the smallest subtree that contains all nodes from the set, including 1 and N)-distance(1, N)

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/problemset/problem/1666/L How to approach this

→ Reply
»
12 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Yes, this is a very good question. See the algorithm: - First, find the path from 1 to N. (Here 1->3->5) - Make new visited array with visited[node]=1 for node in path and rest 0. - For each node in the path: Get the minimum distance needed to be traversed to visit all nodes in node_to_visit_in_path individually.

Answer: (size of path — 1) + minimum distances from all nodes traversed above.

In the given test case, after finding path, you will traverse for a minimum distance for nodes 1, 3, and 5 individually. Answers of individual minimum distance will be: Node 1: 2 (Going to 2 and coming back to 1) Node 3: 2 (Going to 4 and coming back to 3) Node 5: 0 (No way out)

To find minimum distances from all nodes in path: See this. Just consider your current node as 0 w.r.t. problem given in the link. (Remember to mark nodes of path as visited before doing this) Thanks :)

→ Reply
»
12 months ago, # |
← Rev. 4   Vote: I like it -16 Vote: I do not like it

While there is a leaf that doesn't need to be visited, delete it. You can do this using a single DFS or using a queue.

Now we must find the shortest 1--N path that visits every leaf.

An euler tour does this but is not the shortest. On it, the simple path from 1 to N is visited twice. We can easily piece the solution together out of substrings of the euler tour.

→ Reply