A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are under construction and will be available soon. We get an array C of length N, where the value of C[i] describes the petrol station at location i in the following way:

  • If C[i] = -1 there is no station.
  • If C[i] = 0 there is a station at location i
  • If C[i] = x there is a station at location i which will be
    available at in x days.

Assume that flying from point a to point b takes no time. But if jet runs out of petrol on a point x of array, it should wait x days to refill and then continue its way. If x=-1, jet is stuck. The task is to find the minimal number of days the jet can get from point 0 to N+1, refilling on the way when necessary.

Is it a TSP variant with an extra condition? I am new to these.

P.S.The task is the same as "compute the maximum value of minimum values for each range of length R".

UPD. I looked at all types of dynamic programming questions, it is not close to them. I was given this problem in the university, as one in the miscellaneous set of problems.

  • 1
    $\begingroup$ This looks much easier than TSP. $\endgroup$ – Yuval Filmus Sep 8 '17 at 16:13
  • $\begingroup$ Implementations are off-topic here. Where did you encounter the question? Can you credit the source? If it came from a course or textbook, what topics were being taught at about that time? Have you tried looking for an algorithm using dynamic programming? What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Sep 8 '17 at 20:44
  • $\begingroup$ @D.W. thank you for your comment! Okay I'll update my question and provide an answer also, as I have found it:) I am new to here, so I needed a comment like this. Regards! $\endgroup$ – jazz_mine Sep 8 '17 at 21:11
  • $\begingroup$ @YuvalFilmus, this looks like some weighted problem, so, I'm unsure here. $\endgroup$ – rus9384 Sep 8 '17 at 22:18
  • 1
    $\begingroup$ @rus9384 In some sense, any NP problem is TSP in disguise. $\endgroup$ – Yuval Filmus Sep 9 '17 at 6:14

TSP assumes you go through a hamiltonian path.

This problem looks more like a simple a path search with some added restrictions and it's solvable with A*.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.