Photo by Ян Ценч |

Here are the results of the top teams (full results here: http://acm.urfu.ru/chu/2013/standings.html):

Rank | Participant | A | B | C | D | E | F | G | H | I | J | Solved | Time |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | Moscow SU Unpretired | +0:14 | +2:32 | +12:35 | +1:28 | +31:17 | +23:47 | +94:43 | +0:49 | +0:37 | 9 | 1382 | |

2 | SPb NRU ITMO 1 | +0:11 | +1:33 | +1:11 | –194:59 | +14:45 | +42:31 | +13:36 | +0:48 | +0:23 | 8 | 1018 | |

3 | Moscow SU Trinity | +0:29 | +23:56 | +22:01 | +11:28 | +34:48 | +34:02 | –74:57 | +1:16 | +0:17 | 8 | 1317 | |

4 | Moscow IPT Unutterable Team | +0:34 | +3:28 | +4:41 | +11:29 | +11:10 | +1:26 | +0:26 | 7 | 834 | |||

5 | SPb SU Angry Muffin | +0:46 | +4:53 | +3:12 | +1:54 | +1:20 | –34:57 | +1:17 | +30:56 | 7 | 918 | ||

6 | SPb SU 4 | +0:27 | +14:12 | +3:41 | +10:37 | –22:43 | +43:47 | –14:46 | +0:48 | +0:16 | 7 | 948 | |

7 | SPb SU Canyon | +20:58 | +12:28 | +11:24 | +13:22 | +14:06 | +1:31 | +10:54 | 7 | 1023 | |||

8 | Moscow SU SG | +21:56 | +2:49 | +3:26 | +12:12 | +54:39 | –10:24 | +0:55 | +20:58 | 7 | 1215 | ||

9 | Warsaw U 1 | +21:02 | +14:43 | +11:19 | +82:52 | +104:58 | –24:55 | +0:33 | +10:34 | 7 | 1421 | ||

10 | SPb SU ITMO 2009 #1 | +0:44 | +13:52 | +1:46 | +0:59 | –54:57 | –44:23 | –44:50 | +0:48 | +0:15 | 6 | 524 | |

11 | SPb SU: Burunduchki | +10:32 | +12:38 | +0:40 | –34:54 | +12:29 | –64:59 | +1:15 | +1:09 | 6 | 583 | ||

12 | Moscow SU T@pirenock | +10:39 | +1:26 | +1:33 | –22:33 | +53:29 | –14:55 | +1:06 | +0:51 | 6 | 664 | ||

13 | Petr Team | +10:12 | +12:13 | +21:28 | +32:07 | –34:58 | –44:55 | +1:05 | +31:37 | 6 | 722 |

At 2:13 into the contest, we solved the 6th problem and were in the first place. As you can see from the last line of the above standings, we didn't solve anything in the remaining 2 hours and 47 minutes. What happened?

For problem C (statements of all problems), we couldn't come up with the simple solution, and wrote down an long expression that we needed to integrate. Since it was a polynomial, that was an easy task, but the answer didn't match the sample output. We've found a couple of bugs in the calculations, the expression was no longer a polynomial, and integrating it numerically still produced an answer that's far off the example output.

For problem F, again we couldn't come up with a O(n^2) solution - we had one that we expected to be O(n^2), but closer to the end of the contest we realized it required O(n^3) time AND memory, and couldn't come up with anything better. What made me feel bad about this problem is that a few teams have submitted 'incorrect' solutions (that sacrifice some search space to stay O(n^2)) that still passed the system tests. It might be that it's impossible to fail those under the constraints (integer coordintes up to 1000), but still that feels bad.

For problem G, we knew the solution all along but postponed writing it since it was complex and since we had 3 other solutions ready but not working. After the end of the contest, I sat down to write it and it took 40 minutes and got accepted from the first attempt.

And finally, for problem H, which is somewhat standard, our solution had a bug - it did not handle several equal vectors in the input correctly. We've discovered this bug after the contest ended, and the solution got accepted after fixing it. Again, this problem left somewhat strange feeling since at least one team managed to squeeze through an (at least theoretically) incorrect solution - just sorting along several thousand random directions. Maybe I'm just feeling grumpy because of our result :)

Still, I'd like to thank the organizers for the wonderful Ural Championship and for making it not "yet another contest" but an awesome event :) And congratulations to the Unpretired!

who was the 3rd member in your team ?

ReplyDeleteMy team was myself, http://community.topcoder.com/tc?module=MemberProfile&cr=14970299 and http://community.topcoder.com/tc?module=MemberProfile&cr=15881985

ReplyDelete