Ccc 2009

[saltpro15]

hang on, if I'm in gr12, which I'm not but I'm just hypothetically speaking, I can still write the junior CCC if i want?

[DanielG]

I think you can if this is your first year writing the CCC, but you would have to check the cemc website.

[A.J]

chopperdudes wrote:

Nukit was rather straight forward once you can define a winning and loosing

I think the easiest way to do Nukit was DP...it runs in constant time (30^4)

[chopperdudes]

A.J wrote:

chopperdudes wrote:

Nukit was rather straight forward once you can define a winning and loosing

I think the easiest way to do Nukit was DP...it runs in constant time (30^4)

i think the way i did it, was AT MOST it takes 30^4 since i calculate all the necessary values, store them, and reuse them when necessary, i don't calculate unnecessary abcd combinations.

[saltpro15]

chopperdudes, want to post that please? I would like to see a way to do it efficiently

[chopperdudes]

Turing:

/*  -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

i don't actually think it's more efficient since i'll need to first initialize the 4D array, but during calculations i actually don't think i do extras.

"" means not calculated, t means it's a winning position, f means it's a loosing position.

[chopperdudes]

and when can we full out discuss CCC 09?

[A.J]

For Nukit, my solution was the one posted on the unofficial web site...it fills up all possible starting positions (upto 30 A's, B's, C's and D's) before getting the input, then gets the # of A's, B's, C's, D's and just looks up the winner in the array at dp (numA, numB, numC, numD). The basic idea is that of gametheory : if a position leads to at least one winning position, then it is a losing position....if it doesn't lead to any winning positions, then it is a winning position...

memoization works too, but I prefer DP

[bbi5291]

At 11:25 AM today (ON time, GMT-5:00), Troy Vasiga from the CCC committee wrote:

Quote:

Brian,

If you hold off until this afternoon (i.e., day after contest date) at the earliest, that would be great. We actually have kids in Hong Kong and Beijing writing the contest, and they wrote it last night (while you were sleeping) at 4am or so.

I am glad you got some solutions. Perhaps there will even be Woburnite or two that makes it to Stage 2.

Troy (t.v.)

You may feel free to start discussing solutions.

[chopperdudes]

okay i was just wondering how people did J4... all i did was hardcode up to 30, which then it'll all be in one line, and then soft coded it.

[michaelp]

I couldn't do J4. It was... BAH!
I just replace the spaces with periods, and fixed got the formatting of the lines working. The words would still screw up and stuff.
And in difficulty, compared to most years, what would the junior CCC be considered? Hard? Average? Easy?

[saltpro15]

chopperdudes, thanks man!

[saltpro15]

and I started J4, hit a substring index is greater than length of string error that I couldn't fix, tried some lame bs solution that probably got like 5/15 and called it a day

[chopperdudes]

lol saltpro were you trying to loop thru the string with a for loop and change the string at the same time? there were 5 test cases for that question if i rmbred correctly. 3 marks each.

[saltpro15]

well, scratch 5 and call it 0 :p I wasn't expecting a lot anyway