Ecoo

[crossley7]

Last round tomorrow. Good luck everyone, hopefully we all do our best and the best team wins

[jr5000pwp]

Good job to everyone who participated. It was a close call for the top few teams and a lot of fun. I'm excited to see some of you again next year.

[crossley7]

It was pretty close all the way down. We ran out of time to get a 3rd perfect submission in as we were debugging as time ran out and only got 10 points on it. Had it been perfect we would have had a top 10 but instead settled for 18th.

I screwed up #1 initially with a bunch of little index errors and then the pressure and heat in the room made it difficult to focus and get them out. By the time I did, we only had time to get 1 more submission in and we had to pick between questions 2 and 4 and just came up short.

[mirhagk]

Finally placed this year lol.

[crossley7]

What place did you get mirhagk?

I found that the problems didn't seem to be particularly hard as there were brute force algorithms to solve all of them in relatively quick time, but it just took forever to implement the algorithms because of the number of steps.

I wish luck to all those who get to come back next year for another try and can't wait to meet a bunch of the people who did well this week at U of W. I also need a chance to redeem myself for botching this contest

It is hard to believe that our team actually placed worse this year than last year after improving at every other contest and generally kicking ass at them aside for the small hiccup here and there

[mirhagk]

We came in 3rd place, and I agree, the problems weren't difficult, they were just lots of little things to consider. I found the lisp one funny, what if you had lisp installed on your computer lol?

[crossley7]

which problem was the lisp one? If it was #3 I didn't even read it as the rest of my team solved it. And congratulations on 3rd, Wish we could have gotten there and probably would have had a chance ad there not been so many small indexing issues.

I saw number 4 and kinda thought it was a joke actually. That it was a clear brute force recursion type of problem just by looking at it made me disappointed. The last problem shouldn't be brute forceable, yet it was. Makes me even more disappointed that we only got 2/4.

#1 might have actually been the hardest problem this year and the concept of it was really simple

[mirhagk]

Yeah the concept was simple, but it was a little tricky figuring where to draw the 2nd tree. I just tried to draw it, and if it found an overlap then I'd revert to an older state and move over one. The 2nd one I believe was the lisp one. It was the one where the input was like:
(+ (+ 4 5) (* 2 (- 9 4)))

[crossley7]

ok, that was Q3. I had seen it in passing so that would be it. #2 was the jewels problem

[trishume]

Our team (Bell High School) was second ... for about 10 minutes.
We were the second team to answer question 3 since it was really easy and we have a fast coder on our team.

Unfortunately we had bugs in #2 and #4 that wasted a lot of time.
While the rest of my team debugged the other problems I hand-wrote a solution to #1 on paper and got our teams fastest typist to type it in during the last 20 minutes of the contest.

It worked almost first try but it printed out the trees shifted left by one character. So we submitted, got 50, changed 3 characters of code, resubmitted, and got 100.

That put us at around 20th place but for our final submission at the end of the contest we submitted the buggy solution for #4 and got 80.

Our final place was 11th. Which is pretty good considering we were one of the youngest teams there. 1 grade 9, 2 grade 10s and 1 grade 12.

[A.J]

Does anyone remember the rankings well enough? I wanted to know how Waterloo did (I couldn't make it as I'm working at Seattle for the summer).

[crossley7]

I don't remember them clearly, but I believe Waterloo #2 was around 15th (they just beat us by a couple spots) and #1 I think was around 7th or 8th

[trishume]

Made this out of my answer for problem #1 except removed the size limitations:

http://treeeees.herokuapp.com/

Pretty cool!

[SamScott]

NeilV @ Mon Apr 30, 2012 6:32 pm wrote:

I believe I have a pretty simple solution for #4.
For a 3x3 grid, we determine the number of moves for every target grid. To determine the number of moves, there are a couple key observations:
1) This one's obvious. It's always optimal to begin by filling empty spots with the correct number, as long as the correct number isn't somewhere else in the board.
2) Once all the numbers are in place, determining the number of swaps can be done with a simple greedy algorithm: Go through every square, and if the current square contains the wrong number, find the square with the correct number and swap them.

So the algorithm is as follows:
Fill in all the empty spots with the correct numbers, where possible.
Try every permutation of the numbers that haven't been placed on the grid (this is also really easy with languages that have a permutations function), and place them on the grid in that order.
For each of these permutations, determine the number of swaps and take the minimum.

This algorithm runs very fast because in the worst case there are 4 unplaced numbers after filling in the empty spots, and 4! permutations is no big deal (and none of their test cases had more than 3 remaining numbers).
Unfortunately, my team only finished 5th in the centre region because we made the most trivial mistake imaginable on #3 - we forgot to convert the angle to radians (for the Python math module). So frustrating!

Actually you don't have to try any permutations. See my solutions and notes posted in my "ECOO 2012 Solutions & Materials" thread.

Sam.