ECOO 2013 Round 2 Solutions
How Difficult Was This Question Set? (No ending time set) 
1  Very Easy 

16% 
[ 1 ] 
2  Somewhat Easy 

16% 
[ 1 ] 
3  Neither Easy nor Difficult 

33% 
[ 2 ] 
4  Somewhat Difficult 

16% 
[ 1 ] 
5  Very Difficult 

16% 
[ 1 ] 

Total Votes : 6 

Author 
Message 
SamScott

Posted: Sat Apr 27, 2013 6:18 pm Post subject: ECOO 2013 Round 2 Solutions 


The attached zip contains the questions, data files, solutions, and notes from the second round of the ECOO (Educational Computing Organization of Ontario) programming competition, held today. We welcome discussion, suggestions, alternate solutions, etc.
Sam Scott
Sheridan College, Ontario
Description: 

Download 
Filename: 
ECOO 2013 Round 2  Solutions.zip 
Filesize: 
640.81 KB 
Downloaded: 
496 Time(s) 






Sponsor Sponsor



crossley7

Posted: Sat Apr 27, 2013 11:14 pm Post subject: RE:ECOO 2013 Round 2 Solutions 


Just did a quick look at the questions and a few quick comments, first I love the first 3 problems. A nice easy one if you understand the question for Q1 and can format text easily, a graphing problem, and a simulation that may or may not have required some optimization. Didn't look close enough to test case sizes and possibilities for that one.
Q4 Looks like a nice challenging problem and simulation is the only solution that came to mind immediately, but instinct tells me that is too slow of an approach for that problem. N!/P! options will kill you once N gets remotely high. Didn't look at the solutions pdf so not sure if these are on the right track but I am curious to see how many teams got Q4 perfect if a pure simulation didn't work.
Overall, it looks like a top team could get 3 in an hour, and a good team probably 3 in under 2 hours for sure probably closer to an hour and a half. Medium difficulty on the problem set as a whole, probably right where you want it for regional level with Q4 separating the contenders from pretenders there.






SamScott

Posted: Sun Apr 28, 2013 5:56 am Post subject: Re: RE:ECOO 2013 Round 2 Solutions 


crossley7 @ Sat Apr 27, 2013 11:14 pm wrote: Just did a quick look at the questions and a few quick comments, first I love the first 3 problems. A nice easy one if you understand the question for Q1 and can format text easily, a graphing problem, and a simulation that may or may not have required some optimization. Didn't look close enough to test case sizes and possibilities for that one.
Q4 Looks like a nice challenging problem and simulation is the only solution that came to mind immediately, but instinct tells me that is too slow of an approach for that problem. N!/P! options will kill you once N gets remotely high. Didn't look at the solutions pdf so not sure if these are on the right track but I am curious to see how many teams got Q4 perfect if a pure simulation didn't work.
Overall, it looks like a top team could get 3 in an hour, and a good team probably 3 in under 2 hours for sure probably closer to an hour and a half. Medium difficulty on the problem set as a whole, probably right where you want it for regional level with Q4 separating the contenders from pretenders there.
In the Central Regionals, only 3 teams out of 55 got problem 4 correct (2 teams got all four correct), with another 7 teams getting part marks. The test cases were constructed so you needed a more efficient approach for the last two or three to finish in under 30 seconds.
Sam.






crossley7

Posted: Sun Apr 28, 2013 10:38 pm Post subject: RE:ECOO 2013 Round 2 Solutions 


Ok, that's a bit fewer than I would have expected but that would out it at a very quality contest overall






ishiney

Posted: Sat May 11, 2013 11:45 pm Post subject: RE:ECOO 2013 Round 2 Solutions 


Disliked the diagram for #3, since it was somewhat misleading (it was a losing position, and we confused it with (2,4), which was winning). An orientation arrow (which direction increases x, which direction increases y) would clarify this. (We had dx[] and dy[] arrays, but failed quite a bit before realizing (postcontest) that we could've won by switching the dx[] with dy[], and negativeing one of them. Yeah, go figure. )
Couldn't really think of an efficient solution for #4. However, we (theoretically) could've came up with the radix3 solution, then precompute R<=80 and P<=10 into a text file, then read that for some easy marks. Didn't feel like it was fair or worth the effort though
Overall, nice contest. Had lots of fun!






ishiney

Posted: Sat May 11, 2013 11:46 pm Post subject: RE:ECOO 2013 Round 2 Solutions 


Would a possible DP solution work for #4 (by computing which combos can generate which weights, then somehow transitioning between these states)?






SamScott

Posted: Sun May 12, 2013 6:09 am Post subject: Re: RE:ECOO 2013 Round 2 Solutions 


ishiney @ Sat May 11, 2013 11:45 pm wrote: Disliked the diagram for #3, since it was somewhat misleading (it was a losing position, and we confused it with (2,4), which was winning). An orientation arrow (which direction increases x, which direction increases y) would clarify this. (We had dx[] and dy[] arrays, but failed quite a bit before realizing (postcontest) that we could've won by switching the dx[] with dy[], and negativeing one of them. Yeah, go figure. )
Couldn't really think of an efficient solution for #4. However, we (theoretically) could've came up with the radix3 solution, then precompute R<=80 and P<=10 into a text file, then read that for some easy marks. Didn't feel like it was fair or worth the effort though
Overall, nice contest. Had lots of fun!
We were relying on the standard computer science interpretation of the words "row" and "column" where rows are numbered from the top down and columns from right to left. But I agree that we should have stated that explicitly. Also, I just noticed that the statement "if Robot 2 had started out just one square to the left and used the same set of moves, it would have won" seems to be false. The first sample test case matches the diagram, but the starting position (4,3) does not appear in the list of winning positions for robot 2. Sorry about that!!!
Glad you had fun anyway
Sam.






SamScott

Posted: Sun May 12, 2013 6:13 am Post subject: Re: RE:ECOO 2013 Round 2 Solutions 


ishiney @ Sat May 11, 2013 11:46 pm wrote: Would a possible DP solution work for #4 (by computing which combos can generate which weights, then somehow transitioning between these states)?
It's possible some kind of DP could be made to work. My solution just uses a backtracker to generate the splits, always generating the smaller rocks first, but I found a tighter upper bound on the size of the next piece that let me finish in time.
Sam.







