ayushrocker92's blog

problem hiking

By ayushrocker92, 10 years ago, In English

how to solve this problem??

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

»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

You can do this by binary searching the answer which is checked valid by:

1.making a graph with cost sqrt(|x_j-x_i-L|) — R * b_j and always x_j > x_i.

2.In this graph,find shortest path from x0 to xn (take x0 as a dummy start).

i)if this value is -ve this means the mid(of binary search) is greater than the optimal value.

ii)if +ve this is opposite the above,thus take the necessary steps in else of binary search.

3.Once you get the optimal value you backtrace the waiting pts you took.

For further reading Editorial's comment

His submission for this method Submission

EDIT:Congrats for becoming the Training and Placement Representative

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

    What is R? and why is the cost taken as sqrt(|x_j-x_i-L|) — R * b_j

    → Reply