Ecoo 2011
Author 
Message 
Cyril

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


#1 was brute force! : D






Sponsor Sponsor



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 15 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)
FloydWarshall algorithm for allpairs 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.







