Computer Science Canada

Ecoo

Author:  crossley7 [ Sun Mar 04, 2012 10:18 pm ]
Post subject:  Ecoo

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.

Author:  A.J [ Mon Mar 05, 2012 12:40 am ]
Post subject:  RE:Ecoo

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.

Author:  Yves [ Sun Mar 11, 2012 12:13 am ]
Post subject:  RE:Ecoo

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.

Author:  trishume [ Wed Mar 14, 2012 8:16 am ]
Post subject:  Re: Ecoo

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

Author:  McKenzie [ Wed Mar 14, 2012 9:40 am ]
Post subject:  RE:Ecoo

http://ecoocs.org/boardwide.php

Author:  crossley7 [ Sat Apr 28, 2012 11:39 pm ]
Post subject:  RE:Ecoo

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

Author:  Badsniper [ Sun Apr 29, 2012 10:04 am ]
Post subject:  Re: Ecoo

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.

Author:  mirhagk [ Sun Apr 29, 2012 4:17 pm ]
Post subject:  RE:Ecoo

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)

Author:  crossley7 [ Sun Apr 29, 2012 4:24 pm ]
Post subject:  RE:Ecoo

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.

Author:  A.J [ Sun Apr 29, 2012 8:00 pm ]
Post subject:  RE:Ecoo

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.

Author:  crossley7 [ Sun Apr 29, 2012 8:22 pm ]
Post subject:  RE:Ecoo

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.

Author:  Don Victor [ Mon Apr 30, 2012 2:32 am ]
Post subject:  Re: RE:Ecoo

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?

Author:  crossley7 [ Mon Apr 30, 2012 3:01 pm ]
Post subject:  RE:Ecoo

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.

Author:  A.J [ Mon Apr 30, 2012 6:10 pm ]
Post subject:  RE:Ecoo

@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!

Author:  NeilV [ Mon Apr 30, 2012 6:32 pm ]
Post subject:  RE:Ecoo

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!

Author:  crossley7 [ Fri May 11, 2012 3:30 pm ]
Post subject:  RE:Ecoo

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

Author:  jr5000pwp [ Sat May 12, 2012 4:21 pm ]
Post subject:  RE:Ecoo

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.

Author:  crossley7 [ Sat May 12, 2012 5:37 pm ]
Post subject:  RE:Ecoo

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.

Author:  mirhagk [ Sat May 12, 2012 5:41 pm ]
Post subject:  RE:Ecoo

Finally placed this year lol.

Author:  crossley7 [ Sat May 12, 2012 5:47 pm ]
Post subject:  RE:Ecoo

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 Very Happy

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

Author:  mirhagk [ Sat May 12, 2012 7:26 pm ]
Post subject:  RE:Ecoo

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?

Author:  crossley7 [ Sat May 12, 2012 9:16 pm ]
Post subject:  RE:Ecoo

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

Author:  mirhagk [ Sun May 13, 2012 8:35 am ]
Post subject:  RE:Ecoo

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)))

Author:  crossley7 [ Sun May 13, 2012 12:02 pm ]
Post subject:  RE:Ecoo

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

Author:  trishume [ Sun May 13, 2012 7:37 pm ]
Post subject:  Re: Ecoo

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.

Author:  A.J [ Tue May 15, 2012 10:07 pm ]
Post subject:  RE:Ecoo

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).

Author:  crossley7 [ Wed May 16, 2012 7:26 am ]
Post subject:  RE:Ecoo

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

Author:  trishume [ Sat May 26, 2012 10:43 am ]
Post subject:  Re: Ecoo

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

http://treeeees.herokuapp.com/

Pretty cool! Very Happy

Author:  SamScott [ Wed Dec 05, 2012 10:49 am ]
Post subject:  Re: RE:Ecoo

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.


: