Ecoo

[crossley7]

Does anyone happen to know when the ECOO Contests (all 3 rounds) are this year? I was trying to check today and their website is in maintenance right now so I couldn't find out. I know that board contests are normally shortly after March Break but I was curious to see if anyone knew the actual dates yet.

[A.J]

They contacted all the board convenors a while back regarding this year's ECOO. However, they haven't specified a date to us as of yet. I'll let you know if they do.

[Yves]

In general they give a range of dates during which the board-wide contest may be held; I've been told that the TDSB contest is going to be held on the 24th at York University.

[trishume]

How does one sign up for the board-wide ECOO? Contact someone?

[McKenzie]

http://ecoocs.org/boardwide.php

[crossley7]

Well, after the contest today, I think it is safe to discuss the problems. We came 5th today in the West Regional which was a bit disappointing but oh well, still get to move on. I felt like we should have had easily 20 more points which would put us in third and potentially could have done even better if we had a better approach timing wise, but then again, hindsight is always 20/20

Seemed like problems 1 and 3 were the easiest with 2 having a bunch of random cases you had to hard code in (I didn't code our solution so not sure of the details on the problem. Just know we spent 2 hours writing and then debugging the stupid thing)

Anyone have a solution for 4? We only had about 5 minutes once it came time so we couldn't implement our idea, but it wasn't the efficient solution that I know is there somewhere. There had to be a cool DP type solution for that one with the limited possible solutions and patterns

[Badsniper]

Not me specifically, but someone on my team did have a way to solve it. We spent a good hour and a half on 2, finally worked, and by then we had 3-4 minutes left. He said it was easy if you start at the end and work backwards. I didn't read the problem (I did 2), so I don't know what he meant.

[mirhagk]

Problem 4 was the soduku one right? After the competition me and one other teammate got together and solved it. Basically we made a function that expected a solution board and a list of places and numbers in the 3x3 cell. First we counted the number of 0's, that was the initial moves for the first round. Then we added a bunch of code to remove a bunch of the numbers (if they are in the right spot you can remove them right away, and if you can swap them with another one to get them both right you can remove both and add one to the moves list). Then we coded a recursive algorithm that just tried every combination that moved a number to it's correct place with a restriction on depth equal to the best sequence of moves found so far (and starting with n-1 where n is the number of numbers left)

[crossley7]

Ok, I think that sounds like a similar solution to the one our group was planning on implementing had we had time. Although it seems as though it is cleaner than ours was going to be.

[A.J]

Yes, the contest went fairly well. Our teams came 1st and 3rd, so I was pretty happy.

Regarding #4, you can treat each 3*3 grid in the given 9*9 grid separately. Then you place each of the target 3*3 grids (these were the special magical squares whose name I can't remember) on top, counting the number of moves required. Then place the one that requires the least number of moves.

The contest was at a right level (not too easy, and at the same time not too hard) this year. Congrats to the teams that made it through to the provincials.

[crossley7]

Yeah, way to go AJ. We were fighting your team beside us throughout the contest, but I guess they got the better of us in the end. Looking forward for another chance to beat Waterloo and Massey at York.

I enjoyed how the contest was so balanced at our regional this year. It seemed like a bunch of teams had a good chance to move on but in the end it was the usual suspects once again.

Hoping the next round doesn't have another hard code style question like #2 was as those problems generally come down to bugs in the code and how fast you can type rather than finding the correct algorithm.

[Don Victor]

crossley7 @ Sun Apr 29, 2012 8:22 pm wrote:

Yeah, way to go AJ. We were fighting your team beside us throughout the contest, but I guess they got the better of us in the end. Looking forward for another chance to beat Waterloo and Massey at York.

I enjoyed how the contest was so balanced at our regional this year. It seemed like a bunch of teams had a good chance to move on but in the end it was the usual suspects once again.

Hoping the next round doesn't have another hard code style question like #2 was as those problems generally come down to bugs in the code and how fast you can type rather than finding the correct algorithm.

i saw waterloo at the competition but i didn't see Massey at all. does massey even do computer science anymore?

[crossley7]

Yup. They had 2 teams qualify for York and I saw one of their teams beside us. We had Massey 2 and Waterloo 2 on the 2 sides of us.

I think the top 7 at our regional went
1 Waterloo CI
2 Vincent Massey
3 Waterloo CI
4 AB Lucas
5 EL Crossley
6 Vincent Massey
7 AB Lucas

I know 3-5 was within 20 points as we were a few little mistakes from top 3.

[A.J]

@crossley7 - Yeah, I wanted to judge in a room with one of my teams, but then realized that it wouldn't be too fair so I moved to the room that doesn't have WCI 1 or 2. I was looking at the rankings, and recall that you guys did fairly well, good job!

[NeilV]

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!