Computer Science Canada Ecoo 2011 |
| Author: | mirhagk [ Mon May 09, 2011 11:32 am ] |
| Post subject: | Ecoo 2011 |
So my team is heading to the finals, we came 4th at York regionals, so we're confident we can do decently. And if woburn and Don mills don't go we'll for sure win lol. But we want to know what the prizes are/are there any? |
|
| Author: | A.J [ Mon May 09, 2011 12:02 pm ] |
| Post subject: | RE:Ecoo 2011 |
The teams that finish in the top 3 get a monetary prize (I am not too sure what the amounts are though). I helped out as a judge at the Western regionals; it was pretty fun, as I had to run about checking team's output. |
|
| Author: | mirhagk [ Mon May 09, 2011 12:36 pm ] |
| Post subject: | RE:Ecoo 2011 |
Yeah, my team also doesn't have a coach anymore (our compsci teacher can't go), we're trying to scramble to find a replacement lol. Like we have rides there and everything, we just need a teacher. If anyone knows a HWDSB teacher that'd be willing to give up next Saturday please message me. Also I heard someone mention something about scholarships? I'm assuming it's a rumour, but could it be true? |
|
| Author: | crossley7 [ Mon May 09, 2011 4:32 pm ] |
| Post subject: | RE:Ecoo 2011 |
I doubt you need a proper coach. Our team didn't have one at the second round and a parent who knows nothing about comp sci is our coach for provincials. I'm looking forward to it, we were tied second at Western until 3 teams passed us in the last 5 minutes as question 4 screwed us over on setting some arrays and crap. I'm looking forward to having a chance for our small town team to take down one of the powers from Toronto area (Massey, Woburn etc). Right now I'm just hoping we get 3 of the questions at this contest. I think it is possible looking at last year's contest, but will be hard with only 3 hours. |
|
| Author: | A.J [ Tue May 10, 2011 2:09 am ] |
| Post subject: | RE:Ecoo 2011 |
Well, technically WCI hasn't had a computer science teacher for the past 2 years. However, it is good to have a coach alongside you to help judge the contest at the regionals/provincials. Schools like Woburn and Massey have a huge CS program (with teachers, and students alike, helping out to enrich extracurricular CS). I guess once some schools, like WCI, get teachers who actually care about extracurricular CS, we'll have a shot at doing well at the Provincials. Having said that, some of the smaller schools, like E.L Crossley, Ressurection, etc..., have done well on their own as well. |
|
| Author: | mirhagk [ Tue May 10, 2011 7:22 am ] |
| Post subject: | RE:Ecoo 2011 |
Well it's not that we needed an actual coach, it was the issue of teacher supervision, but we worked it out alright now, fortuneatly. And crossley, which regionals were you at? (the one with the queen and knight question as 4?) |
|
| Author: | A.J [ Tue May 10, 2011 8:13 am ] |
| Post subject: | RE:Ecoo 2011 |
Crossley was at our regionals, i.e. the Western regionals (yes, the one where #4 was a DFS/BFS problem). |
|
| Author: | mirhagk [ Tue May 10, 2011 8:20 am ] |
| Post subject: | RE:Ecoo 2011 |
Actually interestingly enough you could ignore the queen and get 80 points on the question. (with both the test case and the actual answers) |
|
| Author: | coolgod [ Tue May 10, 2011 9:12 pm ] |
| Post subject: | Re: RE:Ecoo 2011 |
crossley7 @ Mon May 09, 2011 4:32 pm wrote: I doubt you need a proper coach. Our team didn't have one at the second round and a parent who knows nothing about comp sci is our coach for provincials. I'm looking forward to it, we were tied second at Western until 3 teams passed us in the last 5 minutes as question 4 screwed us over on setting some arrays and crap. I'm looking forward to having a chance for our small town team to take down one of the powers from Toronto area (Massey, Woburn etc). Right now I'm just hoping we get 3 of the questions at this contest. I think it is possible looking at last year's contest, but will be hard with only 3 hours.
massey is located in windsor. Small city i'd say. |
|
| Author: | mirhagk [ Wed May 11, 2011 8:31 am ] |
| Post subject: | RE:Ecoo 2011 |
It's Don Mills and Woburn that concern me. I mean we came first right after them, and that made me extremely excited, but I don't think any humans can take down Don Mills and Woburn |
|
| Author: | crossley7 [ Wed May 11, 2011 10:54 pm ] |
| Post subject: | RE:Ecoo 2011 |
Massey was at our regional and it was a small accomplishment for us to be ahead of them even if it was only for a few minutes with 3 solutions. They worry me as they got 1st and second from our regional. We realized after the contest that we should have coded the knights first instead of the queen, but oh well. I tested our logic after the contest and it worked perfectly. Unfortunately we didn't figure this out in the last 40 minutes of the contest that we had to solve it... and we were using a language that I am unfamiliar with to code it at the contest. Windsor is pretty large in comparison to Pelham that has all of 20000 people |
|
| Author: | A.J [ Thu May 12, 2011 4:53 am ] |
| Post subject: | RE:Ecoo 2011 |
Wait. Massey didn't get first and second. Waterloo Collegiate got 2nd (I would know as I was the teacher accompanying them). |
|
| Author: | crossley7 [ Thu May 12, 2011 8:13 am ] |
| Post subject: | RE:Ecoo 2011 |
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 |
|
| Author: | mirhagk [ Fri May 13, 2011 8:30 am ] |
| Post subject: | RE:Ecoo 2011 |
I won't be able to sleep tonight I'm so excited. It's gonna be so awesome lol. Someone take out Don Mills and Woburn, and you will actually be the best programmer to ever exist. |
|
| Author: | crossley7 [ Sat May 14, 2011 4:23 pm ] |
| Post subject: | RE:Ecoo 2011 |
Congrats to everyone was there. I was shocked to see how competitive it was. We only got 17th but have next year to try again. Just wondering, was #1 a dynamic solution??? Our group thought it was dynamic but didn't know how to code it. If anyone is willing to, could they post a solution on here for some of the questions? |
|
| Author: | Cyril [ Sat May 14, 2011 4:31 pm ] |
| Post subject: | RE:Ecoo 2011 |
#1 was brute force! : D |
|
| Author: | crossley7 [ 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 |
|
| Author: | mirhagk [ 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 1-5 and submitted it lol. |
|
| Author: | Cyril [ 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. |
|
| Author: | Cyril [ 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) Floyd-Warshall algorithm for all-pairs shortest paths output shortest path length from start to end |
|
| Author: | A.J [ 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. |
|
| Author: | mirhagk [ Sun May 15, 2011 2:09 pm ] |
| Post subject: | RE:Ecoo 2011 |
Yeah I can post them once he sends them to us. |
|
| Author: | A.J [ 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). |
|
| Author: | A.J [ 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). |
|
| Author: | mirhagk [ 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. |
|
| Author: | A.J [ 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. |
|
| Author: | saltpro15 [ 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... |
|
| Author: | crossley7 [ 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?  |
|
| Author: | mirhagk [ 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. |
|
| Author: | crossley7 [ 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. |
|
| Author: | Cyril [ Sun May 22, 2011 3:33 am ] |
| Post subject: | RE:Ecoo 2011 |
AJ, we got the sample test data files too. So, accounting for the 4 vs. 1 difference, you win. Haha, I don't know. I always get paranoid when using DFS instead of BFS for things like this... probably more comfortable firing off a BFS now, even if it uses more code. |
|
| Author: | A.J [ Sun May 22, 2011 4:47 am ] |
| Post subject: | RE:Ecoo 2011 |
Regardless, congrats on two wins in a row. |
|