0
$\begingroup$

I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:

In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.

  • Lap times last exactly a minute, and they are booked for the full minute.
  • If we use a free lap time slot, we must wait x seconds until we can use another.

We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.

Example:

With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.

So I tried hard and came up with this recurrence: $$X[i,m] = \max_{1 \leq j \leq i}\ (\min\ (X[j,m-1],\sum_{k=j}^{n-1}abs(s_{k+1} - s_k)))$$ Where X[i,m] means "the maximum distance that I can pick in the subset $\{s_1,s_2,...,s_i\}$ so that I lap at least m times".

Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested).

Any ideas or hints?

Thank you.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ "Any ideas" is not good question. What do you expect to find in the answer? $\endgroup$ – Evil Nov 21 '16 at 15:49
  • $\begingroup$ An answer that tells me if it's right or wrong and why. $\endgroup$ – lkese3ker Nov 21 '16 at 18:02
  • $\begingroup$ 1. Have you checked whether your recurrence gives the right answer on some small examples? that would be a good way to get a better feeling for it. If you've already done that, have you tried proving the recurrence correct? Those are the ways to tell whether your answer is right or wrong. 2. What do you mean by "come up with a good solution looking at the right bottom corner value"? I'm having a hard time understanding what you mean by that. Can you edit the question? $\endgroup$ – D.W.♦ Nov 22 '16 at 6:17
  • $\begingroup$ @D.W. Nevermind. The recurrence is wrong, it's a binary search problem. And by "corner" I meant looking at the X[n,m] value. Thanks for your help anyway . $\endgroup$ – lkese3ker Dec 8 '16 at 15:08
0
$\begingroup$

The solution was using a binary search on the time between laps and since every checking of the value is linear time, computing the solution is cheap. Thank you anyway.

Improve this answer
$\endgroup$

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.