Dynamic Programming on Trees with Modifications

Question

Recently I read a problem on trees But I was finding difficulty in approaching this problem. Here is problem:

There is country with n cities (2 to 10^5) and (n-1) bidirectional roads, such that It is possible to travel between any pair of cities. We have 1 magic Truck which can travel between cities but It will take 1 unit of time (if it's loaded) and 0 unit time (if not loaded) in traveling between adjacent cities, and can hold at max 1 unit of product.

Now You can have a customer in any city who requires exactly 2 units of products and cannot wait more than 2 units of time.

Now question is, we have to minimise total number of storages with given restrictions:

1. A city cannot have more than one storage.
2. A storage can only store 1 unit of product.

Assign Storages in country so that you can fill atleast first order on time. Given that order can be placed in any city.

Time Limit: 1sec

What I have tried:

1. Worst approach I can think is Brute force. Try to place storage in every city(2^n possibilities) and check if every city order can be fulfilled with help of neighbouring cities. But Time Complexity of this will be (n*2^n). So will not work at all.

2. Second approach I am thinking is using DP on trees somehow. And I am also not sure If this will be optimal. From above problem I can ensure that leaves should have 1 storage for sure. And I was thinking DP like, start from root and check if children can help in fulfilling it's order and assign storage to that city accordingly, With base case on leaves. But problem Here is that children can also fulfil order from parent so it's making circular loops. So, It did not help me too.

3. Last approach I was thinking to apply binary search on answer itself. As answer can lie between(1,n) then answer may be found in nLog(n) order. But again problem is, I could not think an optimal way to assign storages in cities with given number of storages.

So, Thats it.. I was trying hard but could not solve this. Any help would be appreciated. :)

Note: I don't know why they make problem statement so complicated like this. They could easily explain problem in much simpler way. Resulting I cannot find this problem on web any more. It was somewhere on codeforces I guess.

Answer 1

The important thing to note about the graph is that there are n cities and n-1 roads and all cities are reachable; this means that:

• There are no cyclic paths.
• There are at least 2 singly-connected cities (end-points).

There are two possibilities for every city; either:

• The city has a storage facility and another storage facility is a maximum of 2 cities away.
• The city has no storage facility, and is connected to at least two cities that have a storage facility.

This also means that a singly-connected city (end-point of a road) always has a storage facility, and a string of doubly-connected cities should (optimally) alternatingly have a storage facility or not, which will give us a starting point when deciding where to put the storage facilities.

^{blue: current node; green: storage; orange: no storage; +: needs another neighbour with storage; ?: visited but not yet solved}

That gives us the following algorithm:

• Find an end-point first: start at any city and move in any direction until you come to a singly-connected city.
• Put a storage facility in the singly-connected city, then go back to the previous city, and mark the road to the city you came from as visited.
• If this city has only one other unvisited road, proceed down the unvisited road, leaving a trail of adjacent cities with and without storage facility.
• If you come to a city that has more than one unvisited road, wait to decide whether to put a storage facility and take any of the unvisited roads; later when you come back to this city and it has only one unvisited road, you will know whether any of the already visited neighbouring cities requires this city to have a storage facility.
• Do this until you end up in a city with no unvisited roads; this means you have gone through the whole graph.

This is basically a "travel down all roads and backtrack again" algorithm, so the number of visited nodes is 2×N and the complexity is linear or O(N).

---

It's worth noting that the order in which cities are visited will not change the result, i.e. the number of storage facilities, but it may change some of their locations. Consider these two solutions for 4 cities:

S - / - S - S   (solved left to right)  
S - S - / - S   (solved right to left)  

---

Moving closer to actual code, let's see what to do once you've identified an end-point. The graph consists of nodes like e.g. this:

NODE "city" C1
- neighbours: [C2, C4, C7]
- has_storage: undefined          <- at first; will be set to true/false
- needs_more_storage: true/false  <- we'll add this property as we go
- visited: true/false             <- we'll add this property as we go

We start at an end-point, and then for each node, we'll:

• Mark the node as visited.
• Look at the neighbouring nodes: if you find only one that is undefined, determine has_storage for the current node: if all of the neighbours' has_storage are false or any of the neighbours' needs_more_storage is true, set the current node's has_storage to true; if not, set has_storage to false and set needs_more_storage to true if there is only one neighbouring city with storage; then move to the one undefined neighbour.
• If several neighbouring nodes are undefined, move to any of them that is unvisited.
• If none of the neighbouring nodes are undefined, you have reached the last node; this is always an end-point, so set its has_storage to true; the algorithm has now finished.