CCC Stage 2 Problem Solutions

[jli1]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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