Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 CCC Stage 2 Problem Solutions
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
jli1




PostPosted: 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
Sponsor
sponsor
A.J




PostPosted: 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).
d310




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




PostPosted: Sun May 22, 2011 3:57 am   Post subject: Re: CCC Stage 2 Problem Solutions

AJ, are you sure? This paper <http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf> gives O(n log^3 n) after much hassle with Voronoi diagrams. Or are you talking about this <http://iasl.iis.sinica.edu.tw/IASL/webpdf/paper-1984_On_the_maximum_empty_rectangle_problem.pdf> 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




PostPosted: 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 Razz). 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




PostPosted: 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.
A.J




PostPosted: 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.
Cyril




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




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




PostPosted: 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
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 10 Posts ]
Jump to:   


Style:  
Search: