Computer Science Canada Ccc 2009 |
| Author: | michaelp [ Tue Feb 24, 2009 4:29 pm ] |
| Post subject: | Ccc 2009 |
Well, I'm back from school today, and wrote the 2009 junior CCC. Thought it would be a good time to get the 2009 CCC topic going. I'm assuming all schools write it on the same day, as that is what it says the Waterloo website? I only got #1-3 for the junior division. 
My first year though, and I'm only in grade 9. 
Used Turing. |
|
| Author: | Tony [ Tue Feb 24, 2009 4:34 pm ] |
| Post subject: | Re: Ccc 2009 |
michaelp @ Tue Feb 24, 2009 4:29 pm wrote: I'm assuming all schools write it on the same day
That is not necessarily the case. Lets give it a few days before discussing the specifics of CCC 2009's content. |
|
| Author: | saltpro15 [ Tue Feb 24, 2009 4:35 pm ] |
| Post subject: | RE:Ccc 2009 |
we probably should not discuss the solutions or questions for a few days, just in case some schools haven't written yet, but good job  |
|
| Author: | michaelp [ Tue Feb 24, 2009 4:37 pm ] |
| Post subject: | RE:Ccc 2009 |
Okay. I'll be waiting patiently. I really wanna see how #4 could be done. (Even though for some people it wouldn't be that hard.  ) |
|
| Author: | saltpro15 [ Tue Feb 24, 2009 5:01 pm ] |
| Post subject: | RE:Ccc 2009 |
I got 1-3, my dwite teammate got 1,3 and 5 i think, props paul |
|
| Author: | corriep [ Tue Feb 24, 2009 5:05 pm ] |
| Post subject: | RE:Ccc 2009 |
I personally found #2 harder than #4. Im really proud that I got #5 too! |
|
| Author: | SJ [ Tue Feb 24, 2009 5:08 pm ] |
| Post subject: | RE:Ccc 2009 |
i did all 5 on senior. realized i had a bug in 4 T.T and 5's prob gonna time out on bigger cases T.T so overall, T.T |
|
| Author: | saltpro15 [ Tue Feb 24, 2009 5:08 pm ] |
| Post subject: | RE:Ccc 2009 |
i would like to see J4 as well, if someone could pm me it, or I can wait a few days i guess |
|
| Author: | saltpro15 [ Tue Feb 24, 2009 5:09 pm ] |
| Post subject: | RE:Ccc 2009 |
update : woo 300 bits! |
|
| Author: | Cyril [ Tue Feb 24, 2009 9:21 pm ] |
| Post subject: | RE:Ccc 2009 |
Okay, so I registered just to discuss the CCC. I should probably introduce myself, then? I'm Cyril Zhang, a Grade 10 student attending Don Mills Collegiate Institute. I got a perfect score in Grade 8 on the 2007 Junior CCC, which really doesn't mean much, as the problems were extremely easy that year... but I suppose it will do as an introduction. You might also find me on Project Euler, as #3 in Canada. I finished the Senior contest five hours ago, and we got them marked immediately. (spoilers will be filled in within a day or so) The problems were so hard this year- really caught me off guard. Any thoughts on whether 61/75 would make the Stage 2 cutoff this year? To those who have completed the contest already (I hope this is vague enough): if you think you've solved #4 and/or #5, be aware that a working solution is far from an optimal solution. The test cases were very IOI-esque. Be prepared to be disappointed. #5 has an optimal solution that is beyond my imagination (at least for now). |
|
| Author: | saltpro15 [ Tue Feb 24, 2009 9:25 pm ] |
| Post subject: | RE:Ccc 2009 |
Cyril, congrats, that's an amazing score and I do believe you'll make the cutoff, although I am not a CCC judge :p |
|
| Author: | DanielG [ Tue Feb 24, 2009 9:28 pm ] |
| Post subject: | RE:Ccc 2009 |
I thought (or more like hoped) on making stage two, and yes, the questions were much harder. I personally hope 61 gets into stage 2 since I probably got around 58-60 (just estimating) |
|
| Author: | Analysis Mode [ Tue Feb 24, 2009 9:30 pm ] |
| Post subject: | Re: Ccc 2009 |
lol, the last problem was ... yeah, let's not talk about it. I did S1, 3, 4 and I have no idea why, but I failed to get S2 :'(. as for cutoff, definitely won't be a 68 like last year. maybe 55 to 65. |
|
| Author: | Analysis Mode [ Tue Feb 24, 2009 9:31 pm ] |
| Post subject: | Re: Ccc 2009 |
btw cyril, did you get the highest score at your school? |
|
| Author: | Analysis Mode [ Tue Feb 24, 2009 9:36 pm ] |
| Post subject: | Re: Ccc 2009 |
For S4 and S5, the time limits were ridiculously high. dunno if I can say them out loud though. |
|
| Author: | saltpro15 [ Tue Feb 24, 2009 9:36 pm ] |
| Post subject: | RE:Ccc 2009 |
I think I might have gotten one of the highest from my school, but I wrote junior so I'm not counting it |
|
| Author: | Briggs [ Tue Feb 24, 2009 9:54 pm ] |
| Post subject: | RE:Ccc 2009 |
I wrote the Senior contest at my school and got 41/75. (Should actually be 40, but let's not do anything about it because S3 was accidentally marked out of 16...) S1: easy as usual. S2, I thought I got the right algorithm, but I failed 3 of the cases. I messed up some of the algorithms for S3, implementing an adjacency table to calculate degrees of separation. It worked properly for all except 2 of the cases, but hey, what can you expect from my first attempt at dynamic programming? S4 I ran out of time for, and my S5 definitely worked but it took way too long for the last 3. I might as well introduce myself too. I'm Joe Zeng, a tenth-grader from Don Mills CI. I like math, math, and DDR. I registered on these forums on request of Cyril, also to discuss results. Alright, on with the actual discussion. What might be an efficient algorithm for doing S5? (Please don't answer before the spoiler alert level goes below orange.) |
|
| Author: | Analysis Mode [ Tue Feb 24, 2009 9:58 pm ] |
| Post subject: | Re: Ccc 2009 |
S3? WEll for one part, it was DP, if you used the method i used. most of it were just basic operations on .... certain things of utmost secrecy. |
|
| Author: | Cyril [ Tue Feb 24, 2009 10:12 pm ] |
| Post subject: | RE:Ccc 2009 |
Yeah, I did. I was pretty lucky to (immense spoiler). And I thought the time limits were universally one minute...? Oh well- I think my approach for #5 was way off. |
|
| Author: | Briggs [ Tue Feb 24, 2009 10:24 pm ] |
| Post subject: | Re: Ccc 2009 |
Analysis Mode @ Tue Feb 24, 2009 21:58 wrote: S3? Well for one part, it was DP, if you used the method i used. most of it were just basic operations on .... certain things of utmost secrecy.
Well, then again, the basic operations based on your certain things of utmost secrecy are part of DP. All I did was store my partial results. and use them to ... do things that shall not be told of. |
|
| Author: | SJ [ Wed Feb 25, 2009 9:05 am ] |
| Post subject: | RE:Ccc 2009 |
*edit: nvm, i take everything back in case of spoiler* |
|
| Author: | A.J [ Wed Feb 25, 2009 9:27 am ] |
| Post subject: | Re: Ccc 2009 |
I didn't use DP for #3 at all...I used : (I won't say it now, maybe tomorrow after I can be SURE that everyone has written this contest) If #4's testcases were huge, then I am screwed...I used an inefficient algorithm |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 9:31 am ] |
| Post subject: | RE:Ccc 2009 |
A.J., just out of curiosity, what language did you use for CCC ? |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 9:34 am ] | ||
| Post subject: | Re: RE:Ccc 2009 | ||
corriep @ Tue Feb 24, 2009 wrote: I personally found #2 harder than #4
well, that's because you fail at life paul, because it wasn't that hard nice job getting 5 though, I think my solution for 5 was along the lines of:
lol |
|||
| Author: | A.J [ Wed Feb 25, 2009 9:38 am ] |
| Post subject: | Re: Ccc 2009 |
saltpro15 wrote: A.J., just out of curiosity, what language did you use for CCC ? I used C++ for all but #2 |
|
| Author: | phleet [ Wed Feb 25, 2009 12:57 pm ] |
| Post subject: | RE:Ccc 2009 |
50/76 (49/75) #1:Generate all of the cool numbers before getting input, run through list of cool numbers, adding to a counter if the number is within the given range. #2: If you remembered to to convert the 1 0 1 etc grid into a single integer, you could just xor the number with the one above it, then bruteforce works fine (16 seconds for the longest test case) #3: Typing in all the edges was a bitch =_= Used BFS with a table of still valid friendships (there's probably a simpler method, but I knew the algorithm off the top of my head. #4: Didn't do due to time restraints resulting from having to type out all the edges in #3. I knew the algorithm, but didn't think I'd have time to do it. Easy using prim's algorithm. #5: Had a working solution, but it was too slow for the larger test cases, so I got 4/15. My method was just to boost the signal of all the coordinates for all the intersections in the range of each cafe. Does anyone know the intelligent algorithm for it? |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 1:03 pm ] |
| Post subject: | RE:Ccc 2009 |
EDIT : why is my code not in c++ syntax? :S EDIT: EDIT: figured it out, nvm |
|
| Author: | SJ [ Wed Feb 25, 2009 4:19 pm ] |
| Post subject: | RE:Ccc 2009 |
i got 6/15, 15/15, 15/15, 0/15, 7/15 so thats 43 total. im gonna go kill myself now. first one i didnt generate enoguh numbers... careless mistake. fourth one i had a small bug reading in data and i had the whole algorithm coded -_-. and the last one i prob coded something wrong... i think it all ran in time but some didnt have the correct answer. i have no one to blame but myself, and since this is my last chance and i ****ed up, its time to drive into a lake. |
|
| Author: | A.J [ Wed Feb 25, 2009 4:30 pm ] |
| Post subject: | RE:Ccc 2009 |
hey, don't be too hard on yourself... 43 is actually a good mark for this year's CCC. You might not make stage 2, but you will DEFINITELY be getting a certificate for getting into top 20%! It was weird CCC this year...#2 in particular....it took me the longest to code/solve.....bashing would have worked, but I used DP to solve it....but I might have gotten it wrong.... |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 5:15 pm ] |
| Post subject: | RE:Ccc 2009 |
wonder how ppl did in junior, any1 here? |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 5:18 pm ] |
| Post subject: | RE:Ccc 2009 |
I wrote the junior, i think i got around a 35, 40 if i'm lucky. Man I hope next year's isn't as hard as this one, J2 was harder than J3 or J4! I think i got it though |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 5:21 pm ] |
| Post subject: | RE:Ccc 2009 |
is 70 a good enough mark to have a chance at the plaque u think? =oo and iunno i've done quite alot of J2-ish problems actually, these comes useful when you have to bruteforce =o (ie how i bruteforced Stage 2 Number Matrix). and number 3 was a b!tch... seriously... i left out the consideration of going over for St.Johns (hope this is not too much a spoiler). |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 5:32 pm ] |
| Post subject: | RE:Ccc 2009 |
j3? i found that quite easy actually, that was the second question I got |
|
| Author: | Insectoid [ Wed Feb 25, 2009 5:33 pm ] |
| Post subject: | RE:Ccc 2009 |
Really? Number 3 was easy. Just add the time difference, if it's a negative number, add 2400. for example, t = 100, Saskatchewan time diff is -300 (not really), add -300 to 100, get -200, add 2400, get 2200. I really hope that wasn't a spoiler. |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 5:35 pm ] |
| Post subject: | RE:Ccc 2009 |
yeah it was easy... but for St.John's, you do +130, so when you have something like.. 245, adding 130 would produce 375... which should be 415... i forgot about that catch... |
|
| Author: | DanielG [ Wed Feb 25, 2009 5:35 pm ] |
| Post subject: | RE:Ccc 2009 |
actually, I think you could just use mod functions which should result in positve number. |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 5:38 pm ] |
| Post subject: | RE:Ccc 2009 |
@chopperdudes, there is a way around the st.john's catch, and I don't really care about spoilers anymore, I'm sure everyone's written it by now or waterloo won't accept their results anyway. |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 5:42 pm ] |
| Post subject: | RE:Ccc 2009 |
nonono i mean it would've been easy to code had i seen that catch... since everythign else was by the 100's, i didn't see that coming... yes quite sad of me 3 marks gone right there... |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 5:44 pm ] |
| Post subject: | RE:Ccc 2009 |
that sucks man. i had 15/15 on J1, 15/15 on J3, maybe like 3 or 4/15 on J4 and I'm hoping for more than 5 or 6/15 on J2 |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 5:47 pm ] |
| Post subject: | RE:Ccc 2009 |
15/15, 15/15, 12/15, 15/15, 13/15 |
|
| Author: | phleet [ Wed Feb 25, 2009 5:54 pm ] |
| Post subject: | RE:Ccc 2009 |
Too bad you guys didn't get to write the Junior from 2007. Easiest thing ever. Me + one of my friends finished in 1.5 hours, got 100% and tied for the plaque. Good thing we didn't do senior that year too - bowling for numbers is an incredibly beastly problem. |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 6:02 pm ] |
| Post subject: | RE:Ccc 2009 |
yeah i know 2007 was extremely easy... i did it for practice in very little time... but i didn't know programming that year. how would you guys rate this year's CCC difficulty level? both junior and senior? |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 6:06 pm ] |
| Post subject: | RE:Ccc 2009 |
junior this year was close to last year's senior from what i've read of last year's questions, and senior this year was insane |
|
| Author: | DanielG [ Wed Feb 25, 2009 6:08 pm ] |
| Post subject: | RE:Ccc 2009 |
actually, senior wasn't insane (though it was much harder than expected), I just spent too long on Q2 (rewrote it twice before it actuall worked) and didn't get any time to think about 5 (bashed, in the LEASE efficient way), didn't get a chance to check any of the problems either (so missed the output message if there is no path). Also, bowling for numbers is NOT a hard question, it is very simple 2d dp. |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 6:15 pm ] |
| Post subject: | RE:Ccc 2009 |
last year's senior 24 was what'd take most of the time. Nukit was rather straight forward once you can define a winning and loosing position. you can even just basic recursion and memorization along the way. This year's junior wasn't that hard i don't find... just tiny mistakes here adn there... |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 6:16 pm ] |
| Post subject: | RE:Ccc 2009 |
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? |
|
| Author: | DanielG [ Wed Feb 25, 2009 6:21 pm ] |
| Post subject: | RE:Ccc 2009 |
I think you can if this is your first year writing the CCC, but you would have to check the cemc website. |
|
| Author: | A.J [ Wed Feb 25, 2009 6:25 pm ] |
| Post subject: | Re: Ccc 2009 |
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) |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 6:29 pm ] |
| Post subject: | Re: Ccc 2009 |
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. |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 6:31 pm ] |
| Post subject: | RE:Ccc 2009 |
chopperdudes, want to post that please? I would like to see a way to do it efficiently |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 6:34 pm ] | ||
| Post subject: | Re: Ccc 2009 | ||
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. |
|||
| Author: | chopperdudes [ Wed Feb 25, 2009 6:41 pm ] |
| Post subject: | RE:Ccc 2009 |
and when can we full out discuss CCC 09? |
|
| Author: | A.J [ Wed Feb 25, 2009 6:55 pm ] |
| Post subject: | Re: Ccc 2009 |
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 |
|
| Author: | bbi5291 [ Wed Feb 25, 2009 7:26 pm ] |
| Post subject: | Re: Ccc 2009 |
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. |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 7:31 pm ] |
| Post subject: | RE:Ccc 2009 |
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. |
|
| Author: | michaelp [ Wed Feb 25, 2009 7:34 pm ] |
| Post subject: | RE:Ccc 2009 |
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? |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 7:44 pm ] |
| Post subject: | RE:Ccc 2009 |
chopperdudes, thanks man! |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 7:49 pm ] |
| Post subject: | RE:Ccc 2009 |
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 |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 8:33 pm ] |
| Post subject: | RE:Ccc 2009 |
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. |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 8:50 pm ] |
| Post subject: | RE:Ccc 2009 |
well, scratch 5 and call it 0 :p I wasn't expecting a lot anyway |
|
| Author: | A.J [ Wed Feb 25, 2009 8:50 pm ] |
| Post subject: | RE:Ccc 2009 |
The solutions and testcases to all the junior questions and 3 of the senior questions are up on the unofficial website (http://access.mmhs.ca/ccc/index.htm) |
|
| Author: | saltpro15 [ Wed Feb 25, 2009 8:53 pm ] |
| Post subject: | RE:Ccc 2009 |
thanks A.J.! |
|
| Author: | chopperdudes [ Wed Feb 25, 2009 10:16 pm ] |
| Post subject: | RE:Ccc 2009 |
any1 here (or any1 you know) got over 70 for junior? |
|
| Author: | Cyril [ Wed Feb 25, 2009 11:08 pm ] |
| Post subject: | RE:Ccc 2009 |
Okay, so we can discuss now. #1 - trivial: powers of 6 (not sure why the MMHS website's solution writer hasn't thought of this) #2 - somewhat trivial: bitwise XOR shortcuts #3 - trivial: easy array stuff + BFS for 's' function (MMHS thing uses Warshall. Why?) The solution to #4 obviously uses Dijkstra's algorithm- use that to find the minimal path from the source to each vertex, and find the minimal sum of a vertex's pencil cost and edge cost. If I'm not mistaken, EVERY test case in the set had 5000 vertices, so a lot of people faced memory agony. Mine used too much memory for the second case, which was a huge tree- should have used a triangular array. I think the test case size specifications were pretty unfair. A suboptimal solution would most probably get 0/15. A language with any memory overhead (VB or Turing, for example) would be doomed either way. Finally, for C/C++ programmers, we had to remember to dynamically allocate short ints, or we would run out of memory. John (Stage 2 last year) used 32-bit integers, giving him a totally unexpected zero score. What's worse is that some solutions that would crash one computer could get 15/15 on another. As it is, this problem would have been fantastic in Stage 2, but we can't hope to have the same kind of regulation in Stage 1. ...Unless there's a really clever data structure that I'm overseeing. In that case, sorry; I'm just stupid. Keeping an adjacency list rather than a matrix would not help much, as the problem statement says that there are at most 25,000,000 edges. For #5, I think I see an approach now (at least, one that should score higher than 4/15). I just created a 2-dimensional array and added bitrates within the circles. I just forgot to terminate after reaching the boundary of the box, so my program performed a lot of unnecessary looping outside of the area. Shame! Could have done a lot better! |
|
| Author: | SJ [ Wed Feb 25, 2009 11:32 pm ] |
| Post subject: | RE:Ccc 2009 |
here's what i did for 5, maybe similar to Cyril's way: for all the rows that this circle spans to (from top to bottom) find the leftmost point in that row that's contained in the circle, +bitrate on that point. on the right side of that row (center+distance to leftmost point), -bitrate. After all the circles are added, just go through each row and sum all the bitrates for each row. finally go through all the rows again counting how many has the highest bitrate. so overall it has about K*R*(some small number) + 2*M*N operations. |
|
| Author: | A.J [ Wed Feb 25, 2009 11:44 pm ] |
| Post subject: | Re: Ccc 2009 |
For #4, I coded Djikstra, but made a stupid mistake while coding it....so at the last minute, I coded Warshall for #4  ....
I looked at the testcases, and Warshall should work for 2 (or 3) of them (as not all the testcases have 5000 cities). |
|
| Author: | Analysis Mode [ Thu Feb 26, 2009 12:08 am ] |
| Post subject: | Re: Ccc 2009 |
MMHS uses warshall's cuz it's easier to code (4 lines) and the graph is small (50 edges at most). (so did I) (but I forgot not to count friends of friends more than once and I hardcoded the graph wrong) For #4, I used dijkstra's but instead of starting at the dstination city, i started at every pencil-selling city :'(. dijkstra's with a priority_queue (what I used) apparently may time out if done inefficiently. (I didn't see with this observation though, btw). the test case with the most edges has 5 000 000 and 5000 cities. damn, the stupidest mistake I made on this contest came on teh first questoin. I outputted all teh numebrs that were cubes and squares in additio nto the numberof them :'((((( lost 9 marks. |
|
| Author: | Chiki [ Thu Feb 26, 2009 12:23 am ] |
| Post subject: | Re: RE:Ccc 2009 |
Cyril @ Wed Feb 25, 2009 11:08 pm wrote: EVERY test case in the set had 5000 vertices, so a lot of people faced memory agony Is 130MB of memory too much to ask for? If a triangular array was used, 65 MB? Quote: I think the test case size specifications were pretty unfair. A suboptimal solution would most probably get 0/15. A language with any memory overhead (VB or Turing, for example) would be doomed either way. I coded up S4 using Turing and for the largest cases it took around 135MB of memory using a square array (5000x5000). Quote: Finally, for C/C++ programmers, we had to remember to dynamically allocate short ints, or we would run out of memory. short ints = same amount of space as the triangular array Quote: What's worse is that some solutions that would crash one computer could get 15/15 on another. The contest assumes you are judging it on a P4 2.0 Ghz machine, that hopefully has the 128MB of ram needed for #4. I guess I should feel bad for those writing the CCC on an 80386 or something. The bottleneck for S4 in Turing is the IO which took around two minutes for the largest case. The actual computation once the IO was in took less than 5 seconds in each case. |
|
| Author: | Cyril [ Thu Feb 26, 2009 12:35 am ] |
| Post subject: | RE:Ccc 2009 |
Ah, then it might be the old version of GCC (supplied with DevC++) and its poor Windows memory management. Sorry for making assumptions and creating such a big fuss. It's probably too late now to try re-marking our school's S4 solutions with Borland...? |
|
| Author: | bbi5291 [ Thu Feb 26, 2009 4:21 pm ] |
| Post subject: | Re: Ccc 2009 |
My solution for S5 is essentially the same as SJ's (SJ, who are you, anyway?) Hanson had a faster solution - it has basically the same idea, but using coordinate compression so that the overall time changes from O(C(R+K)) to O(C(K log C)). Does anybody think they got perfect on the senior contest? One coder at my school thinks there will be no more than 4 perfect scores in Canada this year (and our school has two.) Also, we think the cutoff for stage 2 will be between 55 and 60 this year, what do you guys think? |
|
| Author: | CodeMonkey2000 [ Thu Feb 26, 2009 4:34 pm ] |
| Post subject: | RE:Ccc 2009 |
Wow what school do you go to? Massey? |
|
| Author: | Analysis Mode [ Thu Feb 26, 2009 4:46 pm ] |
| Post subject: | Re: Ccc 2009 |
heck no, bbi5291 and I are from woburn. (lol, but I brought shame to our school by my lacklustre score) you can see the types of errors i made in this thread and "got owned on CCC 2009". (some really stupid ones). |
|
| Author: | SJ [ Thu Feb 26, 2009 4:53 pm ] |
| Post subject: | RE:Ccc 2009 |
is the cutoff really going to be that low? I didnt find the problems hard algorithmically (no dp, max flow, computational geometry, etc) .. personally i had small implementation errors that took away massive marks, but i mean, if you know dijkstra you're basically set, cuz all the other questions are ad hoc. |
|
| Author: | bbi5291 [ Thu Feb 26, 2009 5:08 pm ] |
| Post subject: | Re: Ccc 2009 |
Funny how Massey seems to be a more elite coding environment than Woburn. *feigns outrage* Anyway, last year we had 4 perfect scores at our school. This year one of our strongest programmers got only 60/75, and he's made it to stage 2 for the past few years in a row. Robin Cheng, who was on the IOI team last year, didn't get perfect either (I'm not telling you his score, in case he would not want it to be disclosed.) If the contest wasn't hard, it must have been slightly tricky (note that if you use a priority queue for the Dijkstra's in problem 4, and an inefficient implementation, you will use too much time or memory). And problem 5 seems to have been more challenging than last year's Nukit - the solution is easier to understand, but during the contest itself the notion that it was a geometry problem might have made it difficult to see how to solve it. (This happened to me, so I had only 10 minutes left when I had finished it.) Overall, people seem to have done more poorly this year than last year. My school's base of coders appears to be much more balanced than last year's (i.e. there are a lot of good coders, as opposed to a few exceptional ones and the rest lacking dedication), I really expect more than 2 of us to advance to stage 2. For these reasons I expect quite a low cutoff. (The third highest score at Woburn is a 64.) |
|
| Author: | DanielG [ Thu Feb 26, 2009 5:09 pm ] |
| Post subject: | RE:Ccc 2009 |
that's exactly why they were hard, most people who are good tend to be more algorithmically inclined, so the ad hoc, which were unusual, where a challange (for the 3h period). |
|
| Author: | bbi5291 [ Thu Feb 26, 2009 5:12 pm ] |
| Post subject: | Re: Ccc 2009 |
I highly recommend SPOJ as a training website. Most of the problems there are ad-hoc, and they cover a wide range of difficulty (some, even Hanson can't solve). It doesn't ever let you see the testdata or tell you how many cases you got right, so it promotes bug-free coding as well. |
|
| Author: | DanielG [ Thu Feb 26, 2009 6:24 pm ] |
| Post subject: | RE:Ccc 2009 |
thanks, but it's a bit too late now (though I could try for acm next year) |
|
| Author: | saltpro15 [ Thu Feb 26, 2009 6:48 pm ] |
| Post subject: | RE:Ccc 2009 |
thanks bbi5291! (I assume you're Brian Bi?). Those questions are good practice, except the first one is ridiculously easy |
|
| Author: | bbi5291 [ Thu Feb 26, 2009 8:05 pm ] |
| Post subject: | Re: Ccc 2009 |
That would be I. It feels strange to have people actually know who I am; I was just starting to get used to the relative obscurity  . Hanson never let any of his achievements get to his head, I hope I can follow his example. I guess almost everybody here does DWITE, that must be the explanation.
Yes, the first problem is ridiculously easy, but there are things about online judges that confuse a lot of people who are new to SPOJ, this is probably why that problem is there. For example, those who had been using USACO might think that one needs to read from test.in and write to test.out. People who have never used online judges before might not understand that the states of the input and output files are independent, i.e. one can read the input data one at a time and print answers one at a time, rather than loading all test cases into memory and then processing them (for those who have only used screen I/O this confusion is understandable). I am shamelessly posting just so I can increase my post count. |
|
| Author: | saltpro15 [ Thu Feb 26, 2009 8:23 pm ] |
| Post subject: | RE:Ccc 2009 |
I thought you were the guy who was kicking my ass in every DWITE my team is the The Awesome Swatcats, although it will probably change next year. and I know what you mean about the I/O, i failed TEST the first time because of that  got it second time of course though, and I too am shamelessly posting in the hopes of one day reaching NewBe God rank  |
|
| Author: | chopperdudes [ Thu Feb 26, 2009 10:34 pm ] |
| Post subject: | RE:Ccc 2009 |
by when will we know the results? |
|
| Author: | Analysis Mode [ Thu Feb 26, 2009 10:36 pm ] |
| Post subject: | Re: Ccc 2009 |
you mean the official reesults from waterloo? maybe in a couple of weeks. |
|
| Author: | konnetikut [ Fri Feb 27, 2009 1:51 am ] |
| Post subject: | Re: Ccc 2009 |
I did the junior contest but screwed up St. John's (-3 marks)
I got everything else though. So I'm trying senior problems..S4 to be exact. How do I store 25 000 000 trade routes?... i'm getting OutOfMemory errors.  |
|
| Author: | DemonWasp [ Fri Feb 27, 2009 8:54 am ] |
| Post subject: | RE:Ccc 2009 |
Could you link to the problem description (or repost here, don't know if that's allowed...)? I'm having a hard time finding the actual CCC problem sets - even Google seems unhelpful. |
|
| Author: | Analysis Mode [ Fri Feb 27, 2009 1:36 pm ] |
| Post subject: | Re: Ccc 2009 |
you use a adjacency list. if you're using C++, you can implement it using an array of vector of pairs. vector <pair<int, int> > adj[5001]; adj[i] holds all nodes that i can reach, as well as the weight of the edge (hence the pair). to push onto adj[i] do this: adj[i].push_back(make_pair(weight,neighbour_id)); |
|
| Author: | chopperdudes [ Fri Feb 27, 2009 3:50 pm ] |
| Post subject: | Re: Ccc 2009 |
konnetikut @ Fri Feb 27, 2009 1:51 am wrote: I did the junior contest but screwed up St. John's
(-3 marks)
I got everything else though. So I'm trying senior problems..S4 to be exact. How do I store 25 000 000 trade routes?... i'm getting OutOfMemory errors. heyy, we got the exact same mark then! =oo (and i screwed up at the exact same place... i had 275 for st john's for the last case... edit: oh and demonwasp, you can find the problem sets here: http://access.mmhs.ca/ccc/index.htm |
|
| Author: | konnetikut [ Fri Feb 27, 2009 9:19 pm ] |
| Post subject: | Re: Ccc 2009 |
Analysis Mode @ Fri Feb 27, 2009 10:36 am wrote: you use a adjacency list. if you're using C++, you can implement it using an array of vector of pairs.
vector <pair<int, int> > adj[5001]; adj[i] holds all nodes that i can reach, as well as the weight of the edge (hence the pair). to push onto adj[i] do this: adj[i].push_back(make_pair(weight,neighbour_id)); thanks, but unfortunately i have no idea what you just said since i'm using java
im making use of a triangular array + djikstra to solve this - i think it worked! takes 10 seconds to solve s4.4. hmmm. i think there might be an error in the input/output provided by mmhs (http://access.mmhs.ca/ccc/index.htm) take for example s4.2.in: clearly states: 5000 cities, 4999 trade routes. but theres 5000 trade routes! and the 5000th one connects to city 5001, which doesnt even exist. furthermore, output says minimum cost is 9257. my program output 1419: destination is city 1. city 1 sells pencils for 1419. there is no way minimum cost is 9257.  |
|
| Author: | Analysis Mode [ Fri Feb 27, 2009 9:44 pm ] |
| Post subject: | Re: Ccc 2009 |
well I looked on google and JAva does indeed have a vector class. you shoudl take the time to familiarize yourself with it. as for pairs, it's a C++ container which allows you to store two variables in one, they can be the same or different. the nice thing is that I can sort them (using the sort function, of course). i.e. (1,3), (5, 6), (6, 8), (3,5), (1,4) becomes (1,3), (1,4), (3,5), (5, 6), (6, 8). yeah there is an error in s4.2.in. |
|
| Author: | konnetikut [ Fri Feb 27, 2009 9:49 pm ] |
| Post subject: | Re: Ccc 2009 |
Analysis Mode @ Fri Feb 27, 2009 6:44 pm wrote: well I looked on google and JAva does indeed have a vector class. you shoudl take the time to familiarize yourself with it.
as for pairs, it's a C++ container which allows you to store two variables in one, they can be the same or different. the nice thing is that I can sort them (using the sort function, of course). i.e. (1,3), (5, 6), (6, 8), (3,5), (1,4) becomes (1,3), (1,4), (3,5), (5, 6), (6, 8). yeah there is an error in s4.2.in. i see. ive only been using java for all of 2 weeks, actually. my cs knowledge isnt too advanced, so i just find a way to solve these problems without special classes. thanks for the tip though. |
|
| Author: | Cyril [ Fri Feb 27, 2009 9:57 pm ] |
| Post subject: | RE:Ccc 2009 |
Ah! So this is why I couldn't get that case to work. Evidently, it wasn't anything memory-related; I probably should have been more cynical. I spent about half an hour today staring at my Dijkstra code, trying to find an error. Anyone want to contact the U of W about this? |
|
| Author: | Analysis Mode [ Fri Feb 27, 2009 10:49 pm ] |
| Post subject: | Re: Ccc 2009 |
that won't be necessary. they've caught it already. as of yesterday. |
|
| Author: | konnetikut [ Fri Feb 27, 2009 11:33 pm ] |
| Post subject: | Re: Ccc 2009 |
can't solve 4.3, 4.5. could someone tell me where the pencils are shipped from in these two cases? |
|
| Author: | Analysis Mode [ Sat Feb 28, 2009 12:05 am ] |
| Post subject: | Re: Ccc 2009 |
you use dijkstra's algorithm in this problem. you don't need to know where they're shipped from. |
|
| Author: | konnetikut [ Sat Feb 28, 2009 1:16 am ] |
| Post subject: | Re: Ccc 2009 |
i realize that. you start at destination and work backwards, right? it would help my debugging to know where the pencils begin. destination is 0. for 4.3 i got 271 min cost @ city 213 for 4.5 i got 112 min cost @ city 1387 |
|
| Author: | Cyril [ Sat Feb 28, 2009 1:42 am ] |
| Post subject: | RE:Ccc 2009 |
konnetikut, 4.3: cost 135 822 -> 1927 -> 1392 -> 1603 -> 1622 -> 1266 4.5: cost 35 3830 -> 2736 -> 3819 -> 4612 |
|
| Author: | konnetikut [ Sat Feb 28, 2009 2:33 am ] |
| Post subject: | Re: RE:Ccc 2009 |
Cyril @ Fri Feb 27, 2009 10:42 pm wrote: konnetikut,
4.3: cost 135 822 -> 1927 -> 1392 -> 1603 -> 1622 -> 1266 4.5: cost 35 3830 -> 2736 -> 3819 -> 4612 thank you so much. i checked cost at these points: 4612: 0 3819: 8 2736: 10 3830: 279???? obviously something went wrong here. hmmm edit: FIXED!!!: it was a bug searching next node to visit. so how long is the program allowed to run? 4.5 takes almost 10 seconds for me. |
|
| Author: | A.J [ Sat Feb 28, 2009 1:13 pm ] |
| Post subject: | Re: Ccc 2009 |
konnetikut wrote: so how long is the program allowed to run? 4.5 takes almost 10 seconds for me. There is a 1 minute time limit to all the questions. |
|
| Author: | Analysis Mode [ Sat Feb 28, 2009 6:45 pm ] |
| Post subject: | Re: Ccc 2009 |
one minute time limit for hte first one? That seems ridiculous. For looping from 1 to 10^8 takes about 10 seconds (assuming 10 million operatinos per second, a good benchmark for most online judges and contests). |
|
| Author: | DanielG [ Sat Feb 28, 2009 8:13 pm ] |
| Post subject: | RE:Ccc 2009 |
it's to be fair to slow languages such as turing |
|
| Author: | McKenzie [ Sat Feb 28, 2009 11:25 pm ] |
| Post subject: | Re: Ccc 2009 |
Analysis Mode @ Sat Feb 28, 2009 6:45 pm wrote: one minute time limit for hte first one? That seems ridiculous. For looping from 1 to 10^8 takes about 10 seconds (assuming 10 million operatinos per second, a good benchmark for most online judges and contests).
Actually only S4 and S5 have time limits. In S1-S3, according to the marking guidlines, you can write stupid inefficient code that takes 10-20 min to run and you will get full marks. Mind you, if you get over 40 and your code goes to Waterloo for re-marking I think they take marks off for things like that so you should use 1 min as a guide for all of your programs. |
|
| Author: | konnetikut [ Tue Mar 03, 2009 11:57 pm ] |
| Post subject: | Re: Ccc 2009 |
results were fairly disappointing at my school. highest mark in senior: about 28 nobody got J5/S3 except for me  |
|
| Author: | A.J [ Wed Mar 04, 2009 12:27 am ] |
| Post subject: | RE:Ccc 2009 |
yay, the unofficial solutions guy accepted my solution to s4 |
|
| Author: | konnetikut [ Wed Mar 04, 2009 2:05 am ] |
| Post subject: | Re: RE:Ccc 2009 |
A.J @ Tue Mar 03, 2009 9:27 pm wrote: yay, the unofficial solutions guy accepted my solution to s4
I shouldve sent mine. oh well. Just trying out S5 here. got an inefficient solution that solves 1+2, 3 takes too long 4+5 heap space error. any tips? |
|
| Author: | konnetikut [ Sun Mar 08, 2009 8:03 pm ] |
| Post subject: | Re: Ccc 2009 |
A <a href="http://access.mmhs.ca/ccc/2009/CCC2009S5Wireless.txt">solution</a> was posted for S5, if anyone is interested. Quote: ...
// that concludes the HARDEST program yet in the CCC because without // having access to the final test data, why bother going to // the lengths necessary to tweek a WORKING PROGRAM // sufficiently to get in under the wire? |
|
| Author: | A.J [ Sun Mar 08, 2009 9:46 pm ] |
| Post subject: | Re: Ccc 2009 |
I emailed him a better solution for #5 from Daniel Galperin (DanielG on this forum) and myself. He said that it'll take him some time before he looks into it since he is busy. |
|
| Author: | A.J [ Tue Mar 10, 2009 8:10 pm ] |
| Post subject: | RE:Ccc 2009 |
yay, he accepted our solution (by ours, I mean DanielG's and mine). Brian's method is similar, nice! |
|
| Author: | konnetikut [ Wed Mar 11, 2009 12:13 pm ] |
| Post subject: | Re: Ccc 2009 |
how do you manage to create a 30 000 x 1000 array without getting an OutOfMemory error? |
|
| Author: | A.J [ Wed Mar 11, 2009 1:45 pm ] |
| Post subject: | RE:Ccc 2009 |
You don't run out of memory...and don't use turing 
Declare it publically...not inside your main function (or 'a' function) |
|
| Author: | konnetikut [ Wed Mar 11, 2009 3:11 pm ] |
| Post subject: | Re: RE:Ccc 2009 |
A.J @ Wed Mar 11, 2009 10:45 am wrote: Declare it publically...not inside your main function (or 'a' function)
how?? im using java, not turing.. it's java heap space that's limiting me. |
|
| Author: | dc116 [ Thu Mar 12, 2009 10:18 pm ] |
| Post subject: | RE:Ccc 2009 |
Does anyone know how to find out your score? |
|
| Author: | nike52 [ Thu Mar 12, 2009 11:11 pm ] |
| Post subject: | Re: Ccc 2009 |
if your teacher marked it already and mailed the marks in, it might be on quest in the test results tab |
|
| Author: | konnetikut [ Fri Mar 13, 2009 1:40 am ] |
| Post subject: | Re: RE:Ccc 2009 |
dc116 @ Thu Mar 12, 2009 7:18 pm wrote: Does anyone know how to find out your score?
run the test cases yourself if you have a copy of your programs |
|
| Author: | bbi5291 [ Tue Mar 31, 2009 5:37 pm ] |
| Post subject: | Re: Ccc 2009 |
The unofficial results booklet is now available here. The document doesn't state the cutoff - because the group below the stage 2 invitees is labelled "Honourable Mention". Still, I can gather some information - I do believe I was quite wrong - the cutoff is no more than 53. Breathe your sighs of relief, or exclaim your joy... |
|
| Author: | A.J [ Tue Mar 31, 2009 5:55 pm ] |
| Post subject: | RE:Ccc 2009 |
so, what was the cutoff mark? |
|
| Author: | bbi5291 [ Tue Mar 31, 2009 6:00 pm ] |
| Post subject: | Re: Ccc 2009 |
If I had known the cutoff mark, I would have stated it, rather than simply saying that it is no more than 53. The cutoff is not explicitly stated, and the table of ranks isn't up - thus I don't have any means of determining it. But someone from my school got 53 and is invited. |
|
| Author: | A.J [ Tue Mar 31, 2009 6:18 pm ] |
| Post subject: | RE:Ccc 2009 |
sry brian ...I didnt read your previous post (I only read the first line)...
someone from my school got 48 and didnt get invited so it is between 49 - 53 |
|
| Author: | Farnak [ Tue Mar 31, 2009 7:39 pm ] |
| Post subject: | Re: Ccc 2009 |
Good job for Tahriiiiiiiiiiiiif!!! |
|
| Author: | DanielG [ Tue Mar 31, 2009 8:04 pm ] |
| Post subject: | RE:Ccc 2009 |
I got 48... and wasn't invited (messed up question 1 and friend of friend in Q3). )= |
|
| Author: | Foundation [ Wed Apr 01, 2009 6:08 am ] |
| Post subject: | Re: Ccc 2009 |
The cut off was 49, inclusive. You can find the complete results on the results page with all the past contests. And congrats, Tahrif, see you there! Brian, it seems that you guys are the only two 75's, and there is one more person with 67. Good job. |
|
| Author: | phleet [ Wed Apr 01, 2009 5:14 pm ] |
| Post subject: | RE:Ccc 2009 |
Got in with a 49! Woo! See you guys there. |
|
| Author: | divad12 [ Sat May 02, 2009 3:11 pm ] |
| Post subject: | Re: Ccc 2009 |
I will be taking the VIA train 85 to Kitchener on Monday (May 4th). Who else is going to UW via that train? |
|
| Author: | bbi5291 [ Sat May 02, 2009 3:26 pm ] |
| Post subject: | Re: Ccc 2009 |
All five Woburn invitees are taking this train, including me. |
|
| Author: | divad12 [ Sun May 03, 2009 9:08 pm ] |
| Post subject: | Re: Ccc 2009 |
Let's bring ping pong paddles, and play ping pong! |
|
| Author: | Cyril [ Sun May 03, 2009 11:07 pm ] |
| Post subject: | RE:Ccc 2009 |
See you all in ~14 hours! |
|
| Author: | Cyril [ Fri May 08, 2009 9:38 pm ] |
| Post subject: | RE:Ccc 2009 |
Hey. Wow. Never been with so many smart people in my life- it was quite an amazing week. I'm glad to have met these like-minded (if I may say so without being pretentious) people. First of all, congratulations to Brian, Hanson, Peter, and Robin. This year's Canadian IOI delegation is very strong. Perhaps you guys can beat the Chinese team this year! (not) If you were there, you probably know what happened to me a few hours ago. That was pretty funny. If you weren't- basically, fate player a horrible prank on me and convinced me for 10 seconds that I was a gold medallist. Ah, there's always next year for fantastic IOI travel. >_> See some of you tomorrow at ECOO! |
|
| Author: | DanielG [ Sat May 09, 2009 5:16 pm ] |
| Post subject: | RE:Ccc 2009 |
Cyril, you do know next year IOI is in Waterloo, you wouldn't get to travel much. |
|
| Author: | bbi5291 [ Sat May 09, 2009 6:38 pm ] |
| Post subject: | Re: Ccc 2009 |
I suspect that he did know that and he was being sarcastic. |
|
| Author: | DanielG [ Sat May 09, 2009 6:58 pm ] |
| Post subject: | RE:Ccc 2009 |
true, should have realized that. |
|
| Author: | Cyril [ Sat May 09, 2009 7:48 pm ] |
| Post subject: | RE:Ccc 2009 |
Sorry, sarcasm does not carry well on a computer science forum. |
|
| Author: | Cyril [ Sat May 09, 2009 8:58 pm ] |
| Post subject: | RE:Ccc 2009 |
Hahaha, my dad took a video of said horrible prank. I might release this. (Also, I made a typo earlier that I can't fix, so: sentences[9].words[5][5] = 'd'; ) |
|
| Author: | bbi5291 [ Sat May 09, 2009 9:31 pm ] |
| Post subject: | Re: Ccc 2009 |
I actually thought that Troy pulled this on purpose because I had said something earlier to the effect that computer science was a subset of mathematics, which seemed to displease him (and he was sitting at my table), and also because I mentioned that I thought I wasn't going to be on the IOI team, but that I wasn't exactly sure. I felt really bad for you though... |
|
| Author: | Cyril [ Sat May 09, 2009 10:10 pm ] |
| Post subject: | RE:Ccc 2009 |
Oh, there's no reason to feel bad. I never felt bad for myself. I went to the banquet knowing that my placement would be somewhere in the middle of silver. I'm simply not "IOI material" this year. (You are.) This will probably give people the misconception that I was the runner-up, but I think that was Jon. Time to start doing SPOJ stuff! |
|