CCC Stage 2 Problem Solutions
Author 
Message 
jli1

Posted: 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.






Sponsor Sponsor



A.J

Posted: 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 divideandconquer 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

Posted: 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!






Cyril





A.J

Posted: 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).






jli1

Posted: 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 BellmanFord 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

Posted: Mon May 23, 2011 3:40 am Post subject: RE:CCC Stage 2 Problem Solutions 


Wait, BellmanFord 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

Posted: 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?






A.J

Posted: 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.






Velocity

Posted: 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







