Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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.

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

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

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

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

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

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 10 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: