***********************
Stage 1 Solution Answer
***********************

http://codersblock.net/ccc/2007/bowling/stage1_equation.gif


Let P(g, b) define the subproblem "What is the most number of points we can get if we are on our b'th ball, and only able to hit pins from g .. n?"

Then  P(g+1, b) gives us a smaller version of the same subproblem. 
Also, P(g+w, b+1) gives us the next subproblem if we decide to hit the current pins (g .. g+w).

The maximum of these subproblems is the best solution for P(g, b).

Translating this to C, it's really this simple:

    max(solve(g+1, b), solve(g+w, b+1)+sums[g])

Where "sums" is an array of each possible group of pins.

The results need to be cached in a two dimensional array, to prevent repeated subproblems. This will run in O(pins*balls) time.

Otherwise, if you let the same subproblems repeat, it will take exponential time.

Finally, the base case of the recursion is when either g >= n, or b >= balls. In which case we're solving an empty subproblem, and thus return 0.


***********************
Stage 2 Solution Answer
***********************

http://codersblock.net/ccc/2007/bowling/stage2_equation.gif


Adding penalty pins makes the subproblems much more difficult to identify. There are many ways you could consider the additional options you now have.

The way I took them into account, is I decided to solve an additional set of subproblems that tell us how many points we would get if we changed our next ball's move to hit "k+1" pins right of the current ball's move instead.


Let P(g, b) define the subproblem "What is the most number of points we can get if we are on our b'th ball, and only able to hit pins from g .. n?"

Then     P(g+1, b) gives us a smaller version of the same subproblem. 
Also,    P(g+w, b+1) gives us the next subproblem if we decide to hit the current pins (g .. g+w).
Finally, P(g+w+k+1, b+2), where (k = 0..w-1), gives us the best case, if we decide to hit the current pins (g .. g+w) and the additional pins (g+w .. g+w+k) with the next ball.

The maximum of these subproblems is the best solution for P(g, b).

The reason it's "b+2", is because we are changing the NEXT ball's move, and therefore want to see the best case after THAT ball's move.
This creates a new restriction, where (b+1) must be (< balls), or else we would be adjusting a ball that can not be used.

"g+w+k+1" is the first pin AFTER the additional pin(s) we took down. That is the start of the next subproblem (because we haven't yet touched those pins).

Therefore, it takes the following code to repeteadly max each sub-subproblem:

    for(add=0, k=0; (k < w-1) && (b+1 < balls); k++) {
        add += pins[g+w+k];
        score = max(score, sums[g] + add + solve(g+w+k+1, b+2));
    }

That needs to be maximized on top of the initial subproblems.

One more thing must be added to the stage 1 solution. We need to add "w" extra pins, with point values of 0, to the start of the set. This implicitely allows the algorithm to hit the left-most pins, in the event that there are penalty pins we don't want to touch there.

Note: We can keep our cache's NIL value set to -1, because we will never cache anything below 0. 
      A best result is never less than zero, because we can always chuck a ball off to the side if it were going to get us a negative score.
      Our algorithm already supports the "gutter ball" strategy by returning 0 for each empty subproblem. 

That was a toughy... :)


---------------------------
One more thing: Something's wrong with the test data from the official site for 2007. 
There are error messages written in plaintext in the 5th data file... For this reason, I did not include that file on this website.
---------------------------