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

Rank	Participant	A	B	C	D	E	F	G	H	I	J	Solved	Time
1	Moscow SU Unpretired	+ 0:14	+ 2:32	+1 2:35	+ 1:28	+3 1:17	+2 3:47		+9 4:43	+ 0:49	+ 0:37	9	1382
2	SPb 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	8	1018
3	Moscow 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	8	1317
4	Moscow IPT Unutterable Team	+ 0:34	+ 3:28	+ 4:41	+1 1:29	+1 1:10				+ 1:26	+ 0:26	7	834
5	SPb SU Angry Muffin	+ 0:46	+ 4:53	+ 3:12	+ 1:54		+ 1:20		–3 4:57	+ 1:17	+3 0:56	7	918
6	SPb 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	7	948
7	SPb SU Canyon	+2 0:58	+1 2:28		+1 1:24	+1 3:22	+1 4:06			+ 1:31	+1 0:54	7	1023
8	Moscow SU SG	+2 1:56	+ 2:49	+ 3:26	+1 2:12	+5 4:39	–1 0:24			+ 0:55	+2 0:58	7	1215
9	Warsaw 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	7	1421
10	SPb 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	6	524
11	SPb SU: Burunduchki	+1 0:32	+1 2:38		+ 0:40	–3 4:54	+1 2:29	–6 4:59		+ 1:15	+ 1:09	6	583
12	Moscow SU T@pirenock	+1 0:39	+ 1:26		+ 1:33	–2 2:33	+5 3:29	–1 4:55		+ 1:06	+ 0:51	6	664
13	Petr Team	+1 0:12	+1 2:13		+2 1:28	+3 2:07	–3 4:58		–4 4:55	+ 1:05	+3 1: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!