Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Ecoo 2011
Author Message
Cyril

Posted: Sat May 14, 2011 4:31 pm   Post subject: RE:Ecoo 2011

#1 was brute force! : D

crossley7

Posted: Sat May 14, 2011 4:55 pm   Post subject: RE:Ecoo 2011

really? I thought there may be a brute force solution, but didn't know how to get it partly because i didn't understand the question. Congrats on the first place though, under an hour for 4 problems is fast
mirhagk

Posted: Sun May 15, 2011 12:02 am   Post subject: RE:Ecoo 2011

I messed up on the last one, for some reason I thought it was like A* without the distance check (It's not, but could've been implemeneted similarily). My answers were always no more than 5 above the right answer, so we just subtracted a random number from 1-5 and submitted it lol.
Cyril

Posted: Sun May 15, 2011 12:31 am   Post subject: RE:Ecoo 2011

Basically, if you're given the boxes in some order b1, b2, ... bn, you can find the areas b1.x*b1.y, min(b1.x,b2.x)*min(b1.y,b2.y), min(b2.x,b3.x)*min(b2.y,b3.y), etc. Then, you can verify that they're decreasing, and find the sum of the areas of intersections. Just do this for every permutation. (psst... use C++'s next_permutation and turn on -O2 for magical compiler optimization hax)

You could probably do some backtracking with pruning for larger cases... but this is equivalent to finding the longest path in a complete weighted graph with descending weights. The longest path problem is known to be intractable, so there's not really any hope of getting a solution that would work for 1000 books.

Thanks! It went unexpectedly smoothly today. We were lucky enough to have been in a nice mindset.
Cyril

Posted: Sun May 15, 2011 1:10 am   Post subject: Re: Ecoo 2011

Code is horrifically unclear... I would be a pretty fail software engineer. If pseudocode helps:

1.
for each permutation of boxes:
- area of contact between first and floor is width*height
- area of contact between two boxes is (min width)*(min height)
- if areas are not decreasing, disregard this permutation
- otherwise, find the sum of areas
output the valid permutation with the max sum of areas

2.
for each letter x:
- find the cylinder configuration
- find which position in cylinder 2 maps to x; let the letter corresponding to this position be p
- find which position in cylinder 1 maps to p; output the letter corresponding to this position

3.
keep and work with the map in the format given in input
BFS from interior point (stopping at 'a') to find interior area, marking visited points
for each letter L, go through grid:
- if a point is currently marked with '.', visited by BFS, and adjacent to a letter L, change that point to L+1
- break when you don't make any updates in this way
output the updated map at the end

4.
make a graph out of this (vertices = squares, weighted edges = time to travel between two adjacent squares)
Floyd-Warshall algorithm for all-pairs shortest paths
output shortest path length from start to end
A.J

Posted: Sun May 15, 2011 3:51 am   Post subject: RE:Ecoo 2011

Sounds like ECOO to me. I couldn't make, so I guess I'll ask the WCI team how it went. I am assuming that the questions and rankings should be up at some point.
mirhagk

Posted: Sun May 15, 2011 2:09 pm   Post subject: RE:Ecoo 2011

Yeah I can post them once he sends them to us.
A.J

Posted: Mon May 16, 2011 4:19 am   Post subject: RE:Ecoo 2011

Its ok, I already received them (they send all the rankings and problems to the coaches).

A.J

Posted: Mon May 16, 2011 7:03 am   Post subject: RE:Ecoo 2011

Well, I just wrote the contest on my own, and I wasn't able to beat Don Mills. I was 5 points from them (keep in mind that I didn't have to type out some of the test data onto my computer, as I had electronic copies of the questions. This would have added on some time).

Good job on finishing it blazingly quickly. Overall a pretty good contest. I believe that the average score was higher than usual (for a provincial).
mirhagk

Posted: Mon May 16, 2011 7:55 am   Post subject: RE:Ecoo 2011

Actually test data was all electronic this year, which was nice (test data for problem 4 and 3 would've taken WAYY too long to type out). I really think that all test data should be given electronically, we should not be marked on how quick we can type test data.
A.J

Posted: Mon May 16, 2011 9:25 am   Post subject: RE:Ecoo 2011

Yeah, I agree (well in that case, I guess that would be my final score). The problems were a bit disappointing, as they were on the easy side (most of the problems didn't really require much thinking, unlike last year's problems). But a good contest nonetheless.

Also, regarding Cyril's analysis for #3, isn't it easier to floodfill (i.e. DFS) instead? I mean, my typing speed isn't too quick, so that extra code required for the BFS would have slown me down. Nonetheless, you guys did manage to beat most people on time bonus.
saltpro15

Posted: Mon May 16, 2011 5:32 pm   Post subject: Re: RE:Ecoo 2011

crossley7 @ Thu May 12, 2011 wrote:
Sorry, couldn't remember what place they got exactly. I know they had 2 teams beat us though. It will be a good contest this weekend with lots of really strong teams. hopefully we can do better than our school did last year after that last place mess

[quote = "AJ"]The problems were a bit disappointing, as they were on the easy side (most of the problems didn't really require much thinking, unlike last year's problems). [/quote]

ahem...
crossley7

Posted: Mon May 16, 2011 5:40 pm   Post subject: RE:Ecoo 2011

I have looked at last year's contest in preparation for this one and I think they are both easier than prior contests, but for the most part these were easier than last year. I was surprised to see a cypher on it, but was excited too. My teammate and I haven't found a cypher we can't code between the 2 of us yet. And saltpro, are you mad that we beat your placing from last year?
mirhagk

Posted: Mon May 16, 2011 6:23 pm   Post subject: RE:Ecoo 2011

There's always a cipher lol, well at least in my experience. It's always a dead easy problem, a cipher, a out there problem, and one that can't be brute forced. I think that that set up works very well, diverse, yet consistent.
crossley7

Posted: Tue May 17, 2011 8:22 pm   Post subject: RE:Ecoo 2011

I see a cipher in most every contest, but looking through past contests I hadn't seen a cipher in the final round which is why it surprised me.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 2 of 3  [ 32 Posts ]
Goto page Previous  1, 2, 3  Next
 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: