2
$\begingroup$

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!

$\endgroup$
5
  • 1
    $\begingroup$ Is it possible that two balls drop simultaneously, or do all the balls drop at different times? $\endgroup$ Commented Mar 7, 2020 at 20:55
  • 1
    $\begingroup$ Dynamic programming would be easy were it not for the rule that the game stops when you miss $k$ balls. I have trouble seeing how to incorporate this. $\endgroup$ Commented Mar 7, 2020 at 21:02
  • $\begingroup$ @saulspatz Balls can drop at the same time. $\endgroup$ Commented Mar 7, 2020 at 21:59
  • $\begingroup$ @saulspatz Is there any other way you would try? $\endgroup$ Commented Mar 7, 2020 at 22:00
  • $\begingroup$ So far, I can't see how to do it. $\endgroup$ Commented Mar 8, 2020 at 1:25

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.