Ecoo 2011

[Cyril]

#1 was brute force! : D

[crossley7]

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]

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]

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]

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]

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]

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

[A.J]

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

[A.J]

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]

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]

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]

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]

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]

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]

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.