nikhil_vaibhav_17's blog

Help me out with this question
By nikhil_vaibhav_17, history, 3 years ago, In English

Hello Everyone,

I have been stuck at a question for quite some time. I came up with an approach but that's not working for me. Maybe the idea can be correct and implementation can be wrong. So I need some help with an approach. I will add necessary piece of code for showing my approach.

The question is exactly the same and has no typing errors.

Question
My Approach
Main computation part

I just want to know what can be a good approach for this and I will try to implement this on my own.

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

Comments Comments (2)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi. I don't know the constraints of the problem! But i think its better to make the DP like following:

State: (position ,remainingTime); Trans: 1. Take the restaurant in the current position and update the remainingTime. 2. Ignore the current restaurant (do nothing). 3. Always update the remainingTime when move from (position) to (position + 1).

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

The problem with your approach is — how do you account which shops Joel stays in and which he pass by? This can end up in O(N*М) complexity. You see this and trying to add some logic (if’s) to your DPs. But this logic still cant connect previous shops and future shops. It doesn’t save any history.

Can you think of some approach, where you remember shops that you visited and if you meet a shop with less time spent in it, you throw some slow shops away?

Or maybe you could think of approach when Joel goes T/2 steps forward and then thinks: if I was an optimal Joel — I would stayed in shops number i1, i2, i3,.. and so on?

And a little observation: if you need to go back anyway, then your travel time is just twice normal and you can forget about “getback” time.

→ Reply