s5 2007

[Integrate]

Hello. I've been practicing with some competition questions and I am having some problems with doing s5 from the CCC competition 2007:
http://compsci.ca/v3/viewtopic.php?t=15232

I've been trying to do the problem in turing, but my problem is that my answer is too slow. It works fine for smaller numbers and such, but as they start to get big, my program takes much longer to finish.

I tried to solve the problem by trying to find all the possible arrangements of ways to hit the pins. I have tried to increase the speed by making the program not go over the same arrangement twice, but for a case of 50 pins with 8 balls of size 4, I'm exceeding 4x10^13 arrangements.

I would like to know if there is a better way to do this (on turing), or if I am doing it wrong.

Here is my code (sorry, its uncommented since I was timing myself, plus I was using bits of code from s1 to s4 so some useless artifacts might be in there), the test data I'm having problems with, and the answers to the data. I decide to output my data onto the screen because it was easier for me to check the answers.

code:

var stream : int var str : string open : stream, "s5.in", get get : stream, str var t : int := strint (str) var scorearray : flexible array 1 .. 0 of int proc calc (w : int, balls : int, pin : array 1 .. * of int, score : int, mem : int)     var switch : boolean := false     var totalscore : int := score     var ballsLeft := balls - 1     var pinsLeft : array 1 .. upper (pin) of int     if mem + 1 <= upper (pin) then         for i : mem + 1 .. upper (pin)             for z : 1 .. upper (pin)                 pinsLeft (z) := pin (z)             end for             for h : 0 .. w - 1                 if (i + h) >= 1 and (i + h) <= upper (pinsLeft) then                     totalscore += pinsLeft (i + h)                     %put totalscore                     pinsLeft (i + h) := 0                 end if             end for             % if ballsLeft = 0 then             %     for h : 1 .. upper (pin)             %         put pinsLeft (h), " " ..             %     end for             %     put ""             %     put ""             % end if             %put ballsLeft             if ballsLeft > 0 then                 calc (w, ballsLeft, pinsLeft, totalscore, mem + 1)             else                 new scorearray, upper (scorearray) + 1                 scorearray (upper (scorearray)) := totalscore             end if             totalscore := score         end for     else         new scorearray, upper (scorearray) + 1         scorearray (upper (scorearray)) := totalscore     end if end calc for i : 1 .. t     get : stream, str     var n : int := strint (str)     get : stream, str     var k : int := strint (str)     get : stream, str     var w : int := strint (str)     %put n, " ", k, " ", w, " "     var data : array 1 .. n of int     for h : 1 .. n         get : stream, str         data (h) := strint (str)     end for     calc (w, k, data, 0, 1 - (w - 1) - 1)     var maxscore : int := 0     for h : 1 .. upper (scorearray)         maxscore := max (scorearray (h), maxscore)     end for     put maxscore end for

test data: save as s5.in

code:

3 25 3 2 8249 1216 4341 8292 320 4896 3368 4586 2520 5727 9129 9737 5831 802 8891 8966 193 6516 4504 4251 7426 5933 4301 6078 8954 50 2 10 6076 6781 636 7814 8848 7208 3461 9707 985 6264 1716 2833 8481 8738 2151 8065 742 3524 6227 6140 1020 5005 7773 6901 1693 381 415 5374 991 9102 9550 3419 2236 186 1234 7436 3747 1047 7143 4732 3663 5211 3917 2144 3950 2420 6562 4692 5945 9141 50 8 4 191 8138 3445 4190 4798 7973 8875 1104 9793 2614 2477 7191 7106 8378 2273 6021 2135 9318 1418 8230 7738 3364 7049 9839 57 6596 1482 3256 3463 4283 3041 3654 8773 6486 7845 3572 4459 3072 1028 4252 5686 3505 7796 9144 8235 6421 1517 370 5739 2936

answers to that set of data:
51755
107873
197422

Thanks for your time!

[Tony]

umm..

Quote:

for h : 1 .. upper (scorearray)
maxscore := max (scorearray (h), maxscore)
end for

You're calculating every possible score in there?

It's Pins nCr Balls combinations. Assuming Pins >>> Balls:

(Pins - Balls)^Balls will give you a conservative estimate of the value. So it could be over 29500^500. That's a lot.

So it should be clear that you're not supposed to try everything.

--------

A hint comes in a form of Bob's strategy for going after the highest scoring shot, one at a time. That's very easy to do, even in O(N^2) sort, 30,000^2 is <<< 29500^500. Supposedly this will give you the correct answer 20% of the time, and be fairly close the rest of the time. This should be your starting case, not 0.

I think that checking if any particular shot will improve/worsen Bob's strategy on the remainder, should give you the answer in O(N^3) time.