A.K.Goharshady's blog

By A.K.Goharshady, 9 years ago, In English,
This one has two different linear-time solutions. Greedy and dynamic programming.

Greedy solution:
You should stop at the city with maximum distance from the root (city number 1). So all roads are traversed twice except for the roads between the root and this city.

Dynamic Programming:
For each city i we declare patrol[i] as the traverse needed for seeing i and all of it's children without having to come back to i (Children of a city are those cities adjacent to it which are farther from the root) and revpatrol[i] as the traverse needed to see all children of i and coming back to it. we can see that revpatrol[i] is sum of revpatrols of its children + sum of lengths of roads going from i to its children. patrol[i] can be found by replacing each of revpatrols with patrol and choosing their minimum.

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

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

please explain a bit about the dynamic programming approach for this problem...how can you traverse all the childs of i without traversing it again... suppose i has 2 branches then after travelling the first branch in graph, we must return to i to move to second branch.. thus how is patrol[i] is defined in those cases where the parent has more than 1 child.

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

It is not clear that how patrol[i] be calculated...Please explain in detail....

11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem is quite interesting
But i can't understand editorial
Can anyone explain both greedy and dp approach in detail?

  • »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    If you are talking about eternal victory — Observation 1 : Optimal traversal always stops at any leaf. Observation 2 : All the edges from path to optimal leaf is always visited once and all other edges are visited twice because at any step we enter the subtree containig opt leaf after visiting all other subtree rooted at same depth.

    Do DP[node] = max length of path from node to any leaf in its subtree or just to a bfs.