ECOO 2013 Round 2 Solutions

[SamScott]

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

[crossley7]

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]

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]

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

[ishiney]

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

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

Overall, nice contest. Had lots of fun!

[ishiney]

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

[SamScott]

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

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

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]

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.