-----------------------------------
jli1
Sat May 21, 2011 2:03 pm
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.
-----------------------------------
A.J
Sat May 21, 2011 3:00 pm
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).
-----------------------------------
d310
Sat May 21, 2011 6:29 pm
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!
-----------------------------------
Cyril
Sun May 22, 2011 3:57 am
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. >_>)
-----------------------------------
A.J
Sun May 22, 2011 4:45 am
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 :P). 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).
-----------------------------------
jli1
Sun May 22, 2011 4:44 pm
Re: RE:CCC Stage 2 Problem Solutions
-----------------------------------
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.
-----------------------------------
A.J
Mon May 23, 2011 3:40 am
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.
-----------------------------------
Cyril
Mon May 23, 2011 10:18 am
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?
-----------------------------------
A.J
Mon May 23, 2011 10:28 am
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.
-----------------------------------
Velocity
Thu Jan 12, 2012 12:23 am
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