Computer Science Canada CCC Stage 2 Problem Solutions

 Author: jli1 [ Sat May 21, 2011 2:03 pm ] Post subject: CCC Stage 2 Problem Solutions Did anyone do something especially unique for any of the day 2 problems? Also, did any Canadians get perfect on bigfoot? Yes, this has a misleading title.

 Author: A.J [ Sat May 21, 2011 3:00 pm ] Post subject: RE:CCC Stage 2 Problem Solutions How did the contest go? I wasn't able to make it, so I don't know. How were the questions generally solved by people (what about the 'vampire tunnels' one?) I am sorry if the story misled you; it's kind of hard to come up with a suitable title/story for a generic question. I recall there being a O(N log^2(N)) solution for that problem involving a divide-and-conquer algorithm and a few neat observations (I did this a few years back). However, not having completely remembered it, we reduced the bounds to allow for an O(N^2) algorithm to pass (with coordinate compression being required).

 Author: d310 [ Sat May 21, 2011 6:29 pm ] Post subject: Re: CCC Stage 2 Problem Solutions Well for vampire tunnels, I decided to keep n nodes, but add another dimension to my 'best' array. So now my best array is [node#][suntime]. Passes in 3.5 seconds, well below the 7 second time limit. As for the bigfoot problem, I'm not sure if any Canadians got perfect on it. (Cyril didn't solve it) As for unique, well someone solved discs!

 Author: Cyril [ Sun May 22, 2011 3:57 am ] Post subject: Re: CCC Stage 2 Problem Solutions AJ, are you sure? This paper gives O(n log^3 n) after much hassle with Voronoi diagrams. Or are you talking about this O(n log^2 n), worst case n^2 algorithm? If not, could you show me, please? Wait, which Canadian solved Disks? I got the algorithm, but failed a few cases, due to bugs and STL abuse. x_X (Also, the fact that I didn't solve something should mean nothing. >_>)

 Author: A.J [ Sun May 22, 2011 4:45 am ] Post subject: RE:CCC Stage 2 Problem Solutions The method I had in mind is the one described in the second paper (I guess the worst case O(N^2) wouldn't have really mattered with our current input data). Mr.Vasiga has yet to send me the results, so I am not too sure how many students got what problem right. Vampire Tunnels was one of the problems I suggested (hence it was one of the easier ones ). Abel actually had your solution in mind, d310, but then I pointed out to him that it was possible to implement Djikstra's with a cutoff (the cutoff being 'remove every state in the priority queue with > S time spent outside'). I guess he didn't increase the bounds as he wanted to allow the O(E*S log(E*S)) algorithm to pass (where 'E' is the number of edges and 'S' is the max amount of time allowed outdoors).

 Author: jli1 [ Sun May 22, 2011 4:44 pm ] Post subject: Re: RE:CCC Stage 2 Problem Solutions A.J @ Sat May 21, 2011 3:00 pm wrote: I am sorry if the story misled you; it's kind of hard to come up with a suitable title/story for a generic question. Nah it was a good problem and made a lot of sense. I was referring to the title of the thread. As for vampires, for some reason I couldn't remember how to implement Dijkstra's algorithm.. so I used Bellman-Ford and only got 7/15 test cases (also due to my incorrect way of handling the sunlight). Which was kind of sad. I wasn't aware that any Canadian got perfect on discs.. stupid 5D dynamic programming.

 Author: A.J [ Mon May 23, 2011 3:40 am ] Post subject: RE:CCC Stage 2 Problem Solutions Wait, Bellman-Ford passed 7/15 cases? I resent that (I thought we made the data a lot tighter than that). At any rate, knowing how to implement Djikstra's is helpful in many cases. Fixing Disks is a cool problem. It requires a bit of thinking and bookkeeping, but a nice question.

 Author: Cyril [ Mon May 23, 2011 10:18 am ] Post subject: RE:CCC Stage 2 Problem Solutions Apparently you could get 7/15 for Disks if you disregarded the master stack. This reduces to the incredibly difficult task of, er, adding up numbers. AJ, which problems were your brainchildren?

 Author: A.J [ Mon May 23, 2011 10:28 am ] Post subject: RE:CCC Stage 2 Problem Solutions Of the 6 problems on Day 1/2, 'Vampire Tunnels' was the only one suggested by me. Perhaps Mr.Vasiga is busy, as he still hasn't sent me the results.

 Author: Velocity [ Thu Jan 12, 2012 12:23 am ] Post subject: RE:CCC Stage 2 Problem Solutions did you say 5 dimensional array? Thats like inception and beyond, my brain would die, but i think i could handle it. My body will prolly stay intact

 :