Ccc 2008

[Sane]

Yeah, but I meant for fun. That's what these contests are for: Fun.

[klopyrev]

Yes, they are for fun. However, winning contests and getting to travel the world because of that is very fun.

ACM finals will be held in Stockholm, Sweden next year. I'm somewhat excited to go there. However, one of you guys can steal my spot if you try hard enough.

[bugzpodder]

tell you what, beating klopyrev is fun I managed to beat richard two years ago and that was really fun (and almost beat malcolm, only 5 penalty points short for the black team, doh)
but these guys schooled me last year

[thegoose]

bugzpodder @ Fri Jun 13, 2008 12:58 pm wrote:

tell you what, beating klopyrev is fun I managed to beat richard two years ago and that was really fun (and almost beat malcolm, only 5 penalty points short for the black team, doh)
but these guys schooled me last year

....and klopyrev won. http://plg1.cs.uwaterloo.ca/cgi-bin/cgiwrap/acm00/score2.cgi

GG

[saltpro15]

ha this is a necro but I refuse to start a new topic for the same topic. Did anyone ever get J5 of the 2008 CCC in Turing? I'm doing the 2008 questions as prep. for the 09 CCC and so far I'm 4/4 , any help with the 5th would be great though, thanks

[CodeMonkey2000]

I don't have a turing solution, but I know that the problem was a DP. Let [i][j][k][l] be the amount of chemical a,b,c and d you have. If you know that [i][j][k][l] is a loosing spot for Patric, then if Ronald has any reactions that leads to that state, Ronald is the winner, and vise versa. By default you know that [0][0][0][0] is a loosing state for Patrick since he goes first. Infact there are a bunch of loosing states you can deduce.

[DanielG]

quad for loops, that's how I did senior last year in turing and it worked (I don't have my solution anymore though).
You could also try to use memoization, using 4d array again, but using recursion instead of dp to build the table.

[saltpro15]

I got it today using DP, and memoization , thanks guys

[chopperdudes]

hmm saltpro, i would like to see your code in turing, and possibly explain the reason behind your dynamic programming. I've not done more than filling an array with recursion, then looking it up later on during the recursion (ie. fib numbers), but i don't really get how to fill the table of values with just for loops alone. so i would really like to see your solution. I also solved mine in turing, junior i did basic recursion, and senior with direct recursion filling up a 4D array. here's the code:

junior:

Turing:

type reaction :     record         a, b, c, d : int     end record /*  This will fail on senior test data 3 and 4 due to inefficiency,  but is a simple solution for the junior test data.  */ /*  -if at anytime you have a negative number of particles, it is a loosing position.  -if any of the moves leads to a winning position, this currently is a loosing position.  -if none of the moves leads to a winning position, this currently is a winning position.  */ fcn win (a, b, c, d : int) : boolean     if a < 0 or b < 0 or c < 0 or d < 0 then         result false     else         if win (a - 2, b - 1, c, d - 2) or win (a - 1, b - 1, c - 1, d - 1) or                 win (a, b, c - 2, d - 1) or win (a, b - 3, c, d) or win (a - 1, b, c, d - 1) then             result false         else             result true         end if     end if end win var f : int var temp : int open : f, "nukit.txt", get get : f, temp var particles : array 1 .. temp of reaction for i : 1 .. temp     get : f, particles (i).a, particles (i).b, particles (i).c, particles (i).d     if win (particles (i).a, particles (i).b, particles (i).c, particles (i).d) then         put "Roland"     else         put "Patrick"     end if end for close : f

senior:

Turing:

type reaction :     record         a, b, c, d : int     end record /*  This includes a 4D table to look up calculated values  instead of recaculating them as was done in junior due  to large test cases.  since initializing a 4D table do take some time, I also  output the actual time used for calculation after each answer.  */ /*  -if at anytime you have a negative number of particles, it is a loosing position.  -if any of the moves leads to a winning position, this currently is a loosing position.  -if none of the moves leads to a winning position, this currently is a winning position.  */ var values : array 0 .. 30, 0 .. 30, 0 .. 30, 0 .. 30 of string for i : 0 .. 30     for j : 0 .. 30         for k : 0 .. 30             for l : 0 .. 30                 values (i, j, k, l) := ""             end for         end for     end for end for fcn win (a, b, c, d : int) : boolean     if a < 0 or b < 0 or c < 0 or d < 0 then         result false     end if     if values (a, b, c, d) = "t" then         result true     elsif values (a, b, c, d) = "f" then         result false     else         if win (a - 2, b - 1, c, d - 2) or win (a - 1, b - 1, c - 1, d - 1) or                 win (a, b, c - 2, d - 1) or win (a, b - 3, c, d) or win (a - 1, b, c, d - 1) then             values (a, b, c, d) := "f"         else             values (a, b, c, d) := "t"         end if         if values (a, b, c, d) = "t" then             result true         elsif values (a, b, c, d) = "f" then             result false         end if     end if end win var f : int var temp : int open : f, "nukit S.txt", get get : f, temp var particles : array 1 .. temp of reaction for i : 1 .. temp     get : f, particles (i).a, particles (i).b, particles (i).c, particles (i).d     var y := Time.Elapsed     if win (particles (i).a, particles (i).b, particles (i).c, particles (i).d) then         put "Roland" : 10 ..     else         put "Patrick" : 10 ..     end if     put (Time.Elapsed - y) / 1000, " sec"     for x : 0 .. 30         for j : 0 .. 30             for k : 0 .. 30                 for l : 0 .. 30                     values (x, j, k, l) := ""                 end for             end for         end for     end for end for close : f

anyone thinks my solution for junior is easier to understand than the indirect recursion in the unofficial solution? (and of course in senior the real DP approach should be better i take it.)