Thursday, May 9, 2013

Ural Championship - aftermath

Photo by Ян Ценч
The best team in the world right now, SPb IFMO 1, has only managed to get the second place at the Ural Championship, that was according to my plan :) However, my team has only got 13th place - and the winner was Moscow SU Unpretired, another veteran team that has 5 ACM ICPC medals between them - 2 gold, 1 silver, and 2 bronze - all in different teams. Congratulations Ilya (ilyakor), Jacob (Dlougach) and Ivan (Jedi_Knight)!

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

RankParticipantABCDEFGHIJSolvedTime
1Moscow SU Unpretired+
0:14
+
2:32
+1
2:35
+
1:28
+3
1:17
+2
3:47
+9
4:43
+
0:49
+
0:37
91382
2SPb NRU ITMO 1+
0:11
+
1:33
+
1:11
–19
4:59
+1
4:45
+4
2:31
+1
3:36
+
0:48
+
0:23
81018
3Moscow SU Trinity+
0:29
+2
3:56
+2
2:01
+1
1:28
+3
4:48
+3
4:02
–7
4:57
+
1:16
+
0:17
81317
4Moscow IPT Unutterable Team+
0:34
+
3:28
+
4:41
+1
1:29
+1
1:10
+
1:26
+
0:26
7834
5SPb SU Angry Muffin+
0:46
+
4:53
+
3:12
+
1:54
+
1:20
–3
4:57
+
1:17
+3
0:56
7918
6SPb SU 4+
0:27
+1
4:12
+
3:41
+1
0:37
–2
2:43
+4
3:47
–1
4:46
+
0:48
+
0:16
7948
7SPb SU Canyon+2
0:58
+1
2:28
+1
1:24
+1
3:22
+1
4:06
+
1:31
+1
0:54
71023
8Moscow SU SG+2
1:56
+
2:49
+
3:26
+1
2:12
+5
4:39
–1
0:24
+
0:55
+2
0:58
71215
9Warsaw U 1+2
1:02
+1
4:43
+1
1:19
+8
2:52
+10
4:58
–2
4:55
+
0:33
+1
0:34
71421
10SPb SU ITMO 2009 #1+
0:44
+1
3:52
+
1:46
+
0:59
–5
4:57
–4
4:23
–4
4:50
+
0:48
+
0:15
6524
11SPb SU: Burunduchki +1
0:32
+1
2:38
+
0:40
–3
4:54
+1
2:29
–6
4:59
+
1:15
+
1:09
6583
12Moscow SU T@pirenock +1
0:39
+
1:26
+
1:33
–2
2:33
+5
3:29
–1
4:55
+
1:06
+
0:51
6664
13Petr Team+1
0:12
+1
2:13
+2
1:28
+3
2:07
–3
4:58
–4
4:55
+
1:05
+3
1:37
6722


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!

2 comments:

  1. who was the 3rd member in your team ?

    ReplyDelete
  2. petrmitrichev10 May, 2013 11:33

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

    ReplyDelete