0
$\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$
  • 2
    $\begingroup$ This looks like a competition or homework problem. Could you provide a link to the competition, so we know it's no longer active? Thanks. $\endgroup$ – j_random_hacker Mar 7 at 20:57
  • $\begingroup$ @j_random_hacker it's not a competition, it's a problem from my advanced algorithms class. $\endgroup$ – Daniel Mar 7 at 22:00
  • $\begingroup$ OK, hint: See if you can compute the largest number of balls that you can catch given that you are at position $i$ a few milliseconds before time $t$. $\endgroup$ – j_random_hacker Mar 7 at 22:04
  • $\begingroup$ Try dynamic progtramming. $\endgroup$ – vonbrand Mar 7 at 22:25
  • 1
    $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Mar 8 at 5:08

Your Answer

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

Browse other questions tagged or ask your own question.