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

Username:   Password: 
 RegisterRegister   
 Ecoo 2011
Index -> Contests
Goto page Previous  1, 2, 3  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Cyril




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

#1 was brute force! : D
Sponsor
Sponsor
Sponsor
sponsor
crossley7




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




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




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




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




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




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




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




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




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




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




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




PostPosted: 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? Razz
mirhagk




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




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

Page 2 of 3  [ 32 Posts ]
Goto page Previous  1, 2, 3  Next
Jump to:   


Style:  
Search: