Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 ECOO 2013 Round 2 Solutions
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

How Difficult Was This Question Set?
(No ending time set)
1 - Very Easy
16%
 16%  [ 1 ]
2 - Somewhat Easy
16%
 16%  [ 1 ]
3 - Neither Easy nor Difficult
33%
 33%  [ 2 ]
4 - Somewhat Difficult
16%
 16%  [ 1 ]
5 - Very Difficult
16%
 16%  [ 1 ]
Total Votes : 6

Author Message
SamScott




PostPosted: 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



ECOO 2013 Round 2 - Solutions.zip
 Description:

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

Sponsor
Sponsor
Sponsor
sponsor
crossley7




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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 (post-contest) that we could've won by switching the dx[] with dy[], and negative-ing one of them. Yeah, go figure. Wink )

Couldn't really think of an efficient solution for #4. However, we (theoretically) could've came up with the radix-3 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 Wink

Overall, nice contest. Had lots of fun!
ishiney




PostPosted: 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




PostPosted: 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 (post-contest) that we could've won by switching the dx[] with dy[], and negative-ing one of them. Yeah, go figure. Wink )

Couldn't really think of an efficient solution for #4. However, we (theoretically) could've came up with the radix-3 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 Wink

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 Smile

Sam.
SamScott




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 8 Posts ]
Jump to:   


Style:  
Search: