need help with Golf Problem... not from this website

dimroed · Post by **dimroed** » Thu Dec 27, 2001 3:34 am

This is a problem from another contest.

You have a set of N(1<=N<=32) clubs, each of which can hit the ball a given length. You are also given a certain distance (1<=d<=5280). You must find the minimal combination of clubs in order to get to that distance, but you CANNOT go past the distance.

Anyway, I tried just cycling through the data and keeping track of the minimum # of clubs it takes to get to a certain distance, so that it doesn't keep longer if it took more to reach that distance on another iteration; this is too slow for n=32. I also tried another approach in which I sorted the clubs by the distance each hit the ball, and then started out by finding the maximum number of times that the biggest clubs goes into the distance, then the second biggest, and so on. Still too slow.

Any suggestions? sorry if this is a newbie question...

I'm not sure this is the right place to post this question. Does anybody know any other forums where I can post these types of questions?

THanks in advance

bolster · Post by **bolster** » Tue Jan 15, 2002 6:14 am

Ah I remember that one. I believe it was from the CCC in 2000, correct? You can solve this using dynamic programming.

Place a ball at the start. Now, note that from this point, the ball can go to 32 locations... label each of those locations with "1" since it takes one swing to get there... Now, go to all these new locations (in order of distance from start), and repeat the process. DO NOT re-label something that has already been labeled, since the original label is the optimal solution to get to that point. In the end, if the end point has a label, then that is the answer. If it does not, then there is no solution.