Dynamic programming algorithm

Question

I'm attempting to solve the following problem:

Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which will the ball reach the ground. We are trying to catch them into a ball net, which we can move left or right, but each movement costs 1 second. The initial position of a ballnet is always on the left (position 0). We are allowed to > drop (not catch) $k$ number of balls.

What is the highest score we can achieve?

My first attempt at solving this was a greedy algorithm:

if the |next ball position - current position of the ball net| > (time of the next ball - current time) 
     then attempts++
     if attempts>$k$
           print game over
else
     current ball net position = next ball position
     current time = time of the next ball
     score++

however my algorithm doesn't take into consideration that sometimes it's better to sacrifice some number of balls in order to reach a higher score in the long run. This needs an approach via dynamic programming, I think.

Is this problem a known one so I can find some help? Could you help me with this problem? I can solve this in a greedy way, however I am failing to do it dynamically.

Thanks!

Answer 1

I'll denote $x[i]$ as the position of the ith point, and $T[i]$ as the time needed for ball $i$ to fall.

Think about a solution to this problem. You're trying to save as many balls as possible. Your solution would be an ordered set of indices $i_1, i_2, ..., i_S$ (that you save in order) That must satisfy (necessary conditions) the following:

1) $T[i_1] \leq T_[i_2] \leq ... \leq T[i_S]$. This is because if you save index $i_l$ first, then you have to wait until it dropes (which takes $T[i_l]$ and THEN move to the next index).

2) $x[i_l]-x[i_{l-1}] \leq T[i_l] - T[i_{l-1}]$ for all $i_l$, as you need time to move from your index $i_l$ to the next index of the ball you save.

3) For any index $a$ in the sorted time array, the set $\{1,2, ..., a\}-\{i_1, i_2, ..., i_S\}$ must have cardinality $\leq k$. You can't drop more than $k$ points at all times.

So here is the algorithm:

1) Sort the times given to you in ascending order, while also rearranging the location array.

2) Define $DP[i,k]$ as the maximum number of points we can save satisfying those necessary conditions from time T[1] to T[i] where we can drop at most $k$ balls. Let $B[i,k]$ be the index of the last ball (right most) we save in this case [In case of ties, choose right most].

3) Fix $(i,k)$. Now we will calculate $DP[i,k]$. For every index $i$, we can either save index $i$ ball, or not save it.

• If we do save it. Then look back at $B[i-1,k]$ and make sure you can arrive from that index to index $i$ in time. The solution is $1+DP[i-1, k]$ Set $B[i,k]=i$. However, if we cannot arrive from $B[i-1,k]$ to $i$ in time, then you cannot include this case, and you cannot save the ball.
• If we don't save it, then the solution is $DP[i-1,k-1]$. Set $B[i,k]=B[i-1,k-1]$. However, if $i - DP[i-1,k-1] > k$ then you cannot leave this ball, and you must save the ball.
• If you cannot leave the ball (due to restriction of $k$) AND you cannot save the ball (can't reach from previous index in time), return $-\infty$ for this case as it's impossible to solve the problem without dropping $k$ balls.

Taking the maximum of all your decisions for every index would give you the DP recurrence. The solution is $DP[n,k]$.

This would take $O(nk)$ time and $O(nk)$ space (although I think you can optimize the space as you're only looking at $n-1, k-1$ at most.