CODEWITHSUNDEEP
arraysalgorithmoptimization
Mr.HITMAN
Mr.HITMAN

Reputation: 157

Hill climbing problem requiring Dynamic programming

So, basically the problem is that there is a series of hill points. we can only move from one hill point to the next greater hill point.

Please see the below image to get an idea.

enter image description here

On above image black points are hill tops, each hill top has some spices with some taste value. we can move from one hill top to another tasting spices in them.

Please See below image to know valid movements. green lines gives valid movements. enter image description here

So, Now we will be given a query with 2 integers b,c and for each query we need to find if moving from b hill point to c is possible. if it is then we have to output the total tastiness of journey.

Suppose a query comes in which b = 1 , c = 10.

So we need to find if moving from hill 1 to hill 10 possible and if it is we have to output the tastiness of journey.

The problem is simple if there are very low queries, as for each query we can just iterate in loop and find if reaching from 1 to 10 is possible or not and if it is then we will sum the taste.

for this particular problem our path will be 1-->2-->6-->7-->9-->10.

But if a query comes such that b = 1 , c = 11.

so we cant go from 1 to 11, hence no path is possible and answer is -1.

But when there are very large queries we can iterate in loop for every query. I mean we have to pre-process the data, so that in each query we just calculate the result in constant time.

What particularly i want to know ?

How can i know if reaching from b to c is possible or not in constant time.

If path is possible than how to calculate the sum of path in constant time.

Upvotes: 3

Views: 638

Answers (2)

captainLevi
captainLevi

Reputation: 31

Yes you can solve this in O(nlogn) Time.

Algorithm

  • First find next greater hill (if exists) for every hill. You can do this in O(n) using stack.
  • Now create a tree with the next greater hills you found on step-1 and to check if a has path from a to b or not you can use Lowest common ancestor with binary lifting to answer in O(logn) or sparse table to answer in O(1) time. if LCA(a,b) = c there exists a path from a to b.
  • To calculate path sum you need to store the sum at every height of tree node from root node. This can also be done in O(n) using DFS or BFS.
  • Finally your whole program would run in O(nlogn) even in worst case

Upvotes: 1

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

You can solve this with O(n) space and O(n+q) time where q is the number of queries using a lowest common ancestor algorithm. Here is a topcoder algorithm tutorial that explains the algorithm.

To convert the problem into this form, define a node for each hill, and let the parent of a node be the hill we can move to from this point. Introduce one extra root node that is the parent of any hills that have no valid move.

Then to determine if there is a path from b to c, you simply check whether LCA(b,c) is equal to c.

You can also precompute in O(n) the sum of spices on a path starting at each node and ending at the root node. To compute the sum along a path, you simply subtract the sum starting at c from the sum starting at b.

It may seem a bit hard to construct the graph in the first place, but this can also be done in O(n) using a next greater element algorithm.

Upvotes: 4

Related Questions