CCC 2006

[gvc]

MysticVegeta wrote:

What happens to people who use java to advance to Stage 2? They are pretty much forced to use C++

That's right. C++ or Pascal. Same for people who write the first stage in Turing, Perl, Python, Basic, PGP, and so on.

[thegoose]

gvc wrote:

The key observation is that the grid has a maximum of 20 locations, so there are only 2^20 = 1 million possible configurations. For every possible configuration you can compute and record the successor. I'll leave it for you to figure out how to convert that information into what's required for S5.

What would be the time limit for S5 be? It is possible for a program to enumerate all gardens of Edens, then see what their successors are (iterating until a state is repeated). Would this solution receive full marks as well?

The test data for no.2 brought back the nightmares of tring to get a ACM problem accepted.....

[gvc]

thegoose wrote:

gvc wrote:

The key observation is that the grid has a maximum of 20 locations, so there are only 2^20 = 1 million possible configurations. For every possible configuration you can compute and record the successor. I'll leave it for you to figure out how to convert that information into what's required for S5.

What would be the time limit for S5 be? It is possible for a program to enumerate all gardens of Edens, then see what their successors are (iterating until a state is repeated). Would this solution receive full marks as well?

The test data for no.2 brought back the nightmares of tring to get a ACM problem accepted.....

There are only a million configurations. It is easy to find all the gardens of edens by marking all successors (anything unmarked at the end is a garden of eden). But you'd be silly to do separate forward searches from each garden of eden. You can do an all-points search considering all gardens at the same time - that takes linear time with a BFS. (Linear in the number of configurations, that is.)

Whether or not the separate searches would run in our lifetimes, I'm not sure. Depends on the number of edens and the length of the paths. Perhaps people with the naive method got lucky. CCC tries to ensure that the actual time limit is not a big factor, but sometimes they don't do so well. In spite of the guidelines, some teachers let the solutions run for hours. I know only one or two of last year's full-mark S5s actually used the correct algorithm.

What did you do?

[thegoose]

gvc wrote:

What did you do?

I did BFS and its runtime was 1.38 seconds a Pentium 4. I know at least one other person who also did BFS.

[cool dude]

does somebody have the answers for the juniour competition? its a lot easier than the senior.

[MysticVegeta]

Here is a detailed analysis by me on the junior set:
http://www.compsci.ca/v2/viewtopic.php?t=11477

[Chinchilla]

Paul: funny because that's the only question where I managed to get all the test cases

I made alot of stupid mistakes in the problems but my approach to each problem at the time of the contest was as follows

1st: I just built a string that contained all the letters that are possible for the 2 flies, and for each baby I just did a lookup whether that letter was there, not sure where I screwed up but I didn't get all the test cases

2nd: Simple, I used STL and a map as a "letter lookup"

3rd: I made a table of edges and made a "function" (mathematical) to get a certain y value depending on the x. Than I checked whether or not the line touched or passed through an edge in my table.

4th: I treated the inverse property as a special case of identity (from what I could tell that's the truth). Than I recursed through the whole table.

5th: Time was running short. This question was similar to one I did awhile ago, I forget the exact name monkey paradise or something, monkeys can plant trees at different corners, and if a tree is to stay alive it needs a monkey tending to it, I dunno, maybe you guys know. I was working on a n OOP solution for it, making a global "garden" and than each cell in the garden can point to a blank or an object which would be the "live cell." and they would have member functions that controls it's life. I ended up running out of time, so I commented out all the code and made it output '2' (I ended up getting one of the test cases right )


in short, I fucked up alot. I only got about 47 points D:.. what pisses me off was that the problems were so easy, I just make alot of mistakes. I'll win next year

[bugzpodder]

u should never do OOP on an algorithm contest, unless its like tree nodes or something.

[Chinchilla]

Why not, it's alot easier to visualize and code when you have a simple structure to it. Solving problems doesn't necesarilly demand a procedural view on the code.

[Cervantes]

Agreed. OOP is wonderful, even for contests. I wrote the CCC in Ruby and wrote my own classes to solve every problem. (Well, every problem that I solved, that is. )