Sunday, December 2, 2012

NEERC 2012 Results

NEERC 2012 Results (full results at official site: http://neerc.ifmo.ru/information/standings.html). Teams at 2nd and 3rd places got their last problem accepted 3 seconds before the end and 24 seconds before the end, respectively :)

RankTeamABCDEFGHIJKL=Time

1SPb NRU ITMO 1 (Kever, Korotkevich, Nigmatullin)+
14:14
+3
105:18
+1
42:11
+3
238:02
+
30:36
+
205:53
+
9:45
+
19:13
+
183:46
+
78:00
-10+1
146:06
111229
2Moscow SU 1 (Fedorov, Kaluzhin, Rogulenko)+
18:17
+1
80:33
+
142:36
+4
299:57
+
54:18
+
183:44
+
12:10
+
36:50
.+
143:55
.+1
254:43
101341
3Belarusian SU 1 (Malevich, Udavichenka, Zhgirovski)+
16:39
+
170:35
+
116:29
.+3
108:38
+
214:43
+
24:26
+
29:59
+6
299:36
+
182:16
.+
153:35
101491
4SPb SU 4 (Egorov, Kunyavskiy, Suvorov)+
13:02
+
94:29
+
74:20
+4
295:35
+1
45:00
+1
278:39
+
9:04
+1
23:24
+2
253:34
+3
259:24
..101583
5SPb NRU ITMO 4 (Bardashevich, Kucherenko, Vedernikov)+
11:22
+3
180:24
+
110:13
.+
92:41
+
233:45
+2
33:57
+
44:46
.+
164:04
.+
290:50
91257
6Moscow SU 4 (Kumok, Permin, Tikhomirov)+
16:59
+1
76:58
+
176:44
.+
108:56
.+1
41:12
+
47:44
+4
291:35
+
144:07
.+
278:57
91297
7Moscow SU 5 (Artuhin, Ignatev, Paramonov)+1
32:19
+2
159:37
+
127:49
.+
91:53
+
183:37
+
51:06
+
64:24
-2+
207:09
.+5
278:21
91352
8Ural FU 2 (Dolgorukov, Shchelkonogov, Soboleva)+
16:34
+3
221:44
+1
137:18
.+1
281:08
+
85:51
+
43:21
+1
68:16
.+1
172:57
.+
238:00
91401
9Moscow SU 3 (Evstropov, Ivlev, Pyaderkin)+
24:49
+4
194:06
+4
76:55
.+
97:13
+
289:16
+
37:03
+1
61:52
-1+1
196:58
.+1
261:24
91455
10Moscow SU 2 (Dubinin, Mokin, Sadkov)+1
14:12
+1
182:00
+3
146:59
.+3
125:17
+1
246:48
+1
21:42
+5
179:22
.+1
223:09
-1+
287:01
91743

NEERC 2012 - Комментарии

15:16 - Контест закончен. Результаты будут известны сегодня вечером, через 4-5 часов. Я напишу про это отдельный пост, на английском. Трансляция на этом завершена, но если у вас остались вопросы, пишите их в комментарии, постараюсь ответить.

15:08 - ИТМО 1 стали посылать задачу K. Цитата из их первого решения:

if (rand.nextBoolean()) {
  out.println("Aastria and Abstria intersect");

15:07 - Во втором решении команды МГУ 1 по D (с тех пор уже пришло третье) была та же ошибка, что и у всех остальных команд в этой задаче - не хватает промежуточной вершины в замыкании Клини.

15:00 - Осталось 10 минут. В последние минуты посылают в основном задачу B.

14:55 - В предпоследнем решении команды Saratov SU 1 в задаче B не разобран крайний случай - когда нужно набрать вес 0. С тех пор, как я это обнаружил, пришёл ещё один сабмит, поэтому я могу теперь написать о результате предпоследнего :)

14:53 - А самое большое решение тем временем тоже у команды ИТМО 1, последний сабмит по задаче D, 10016 байт.

14:47 - Результаты конкретных посылок я не буду писать, но изменений очень много. Такое впечатление, что после заморозки команды стали делать меньше ошибок.

14:39 - Осталось полчаса до конца контеста. Уже многие команды-лидеры послали решения, и некоторые из них прошли :)

14:11 - Результаты заморожены, но видно, какие команды отправляют решения. Я где-то на полчаса ухожу обедать, но обязательно буду комментировать конец соревнования.

14:10 - Мы прорешивали эти задачи вместе с Андреем Халявиным, у нас было на момент заморозки 10 задач - не была решена задача J :) (ну и K).

14:08 - ИТМО 1 сдаёт D, им осталась только задача K. В ней основная сложность - за O(NlogN) проверить, есть ли самопересечения у ломаной, кроме этого нужно просто аккуратно всё написать.

14:06 - Тем временем, у ИТМО 1 10 задач, они по-прежнему не могут найти ошибку в D. У БГУ 9 задач, у МГУ 1, ИТМО 4, МГУ 5 по 8 задач.

14:00 - Из комментариев: "Что у СПБ ГУ 2 с В? И есть ли сабмиты на Delphi? Спасибо" Delphi на полуфинале нет с 2007 года. Решение СПб ГУ 2 не работает на тесте из условия - приходит в 2, а не в 5.

13:57 - Из комментариев: "Что у ижгту в B?" Не очень понятно. Они находят не максимальный возможный вес, само решение похоже на правильное.

13:56 - Из комментариев: "Сколько команд проходит в финал? спасибо" Это ещё не объявлено.

13:48 - Из комментариев: "Что с сабмитом СПбГУ 4 по J?" Что-то очень странное. Оно не работает на первом тесте, падая на строчке "assert(0)", и это выглядит, как будто они не разобрали один из случаев, и оставили там заглушку. Но если это происходит на первом тесте, то зачем посылать? В любом случае, очень странно что они уже очень долго ничего не посылают.

13:46 - Из комментариев: "Насколько близки БГУ2 к сдаче B?" Сдали :)

13:45 - Из комментариев: "А сколько сейчас решений на С++ у команды ИТМО 1?" A, B, F, G, I, L.

13:43 - Из комментариев: "Насколько близки MIPT 2 к сдаче I?" Мне кажется близки, решение очень похоже на верное. У них выдаётся 130 букв Q на тесте, где правильный ответ 400 букв Q.

13:41 - Из комментариев: "What can you say about difficalties in problem I? Are there some "underwater stone"?". Да, там требуется очень много аккуратности, чтобы не посчитать некоторые пики два раза.

13:39 - Из комментариев: "Петя, а не подскажешь, что с командой БГУИР 1 (Belarusian SUIR 1) - у них уже 6 неверных попыток в задаче C". У них ошибка в тесте с большим ответом, видимо проблемы с eps. Само решение похоже на правильное.

13:36 - ИТМО 1 сдали F. Теперь, видимо, Миша Кевер будет писать K, а Гена и Нияз будут искать ошибку в D.

13:32 - Может быть, вы хотите узнать ещё что-нибудь о сабмитах? Пишите в комментариях.

13:27 - Команда МГУ 3 досдала 2 задачи за 3 минуты, теперь у них 7. Пока что всё равно кажется, что составить конкуренцию МГУ 1 за выход в финал никто не сможет.

13:22 - От СПбГУ сейчас проходит в финал третья команда.

13:20 - В этом году командам приносят шарики, если они первыми сдали какую-то задачу. Пока что 6 таких шариков у ИТМО 1, один у МГУ 4, один у СПбГУ 4, и один у УрФУ 2.

13:14 - ИТМО 1 сдают I. Не очень радостная необходимость писать решение для K всё ближе. МГУ 1 сдали F, вернулись на второе место. ИТМО 1 тут же исправили проблему с пустой строкой в D - но теперь у них та же проблема, что и у СПбГУ 4.

13:11 - Тем временем МГУ 4 и ИТМО 4 сдали по 7 задач. СПбГУ 4 уже на 6 месте. У БГУ 1 уже 8 задач, они вышли на второе место.

13:05 - Первая посылка по I в Санкт-Петербурге от команды МФТИ 2. Решение у них идейно верное, но видимо есть мелкие ошибки. Идея там такая: сначала найдём, какие линейные комбинации P и Q у нас есть, потом идём динамическим программированием одновременно с двух краёв, где состоянием является сколько P мы поставили слева, и сколько справа. O(N^3) состояний и такое же время работы. Нужно идти одновременно с двух краёв, чтобы можно было посчитать всего один раз, если какой-то префикс и какой-то суффикс дают одну и ту же массу.

13:02 - Довольно странно, что задачи F и I кажутся сложными - F сдали две команды (Ural FU 2 и Saratov SU 2), I вообще никто не сдал. Мне кажется, что I проще L, а F проще D.

13:00 - Самая высокая команда, у которой нет неверных попыток - Ульяновский ГТУ, 3 задачи.

12:57 - На первых двух местах нет изменений - 8 задач у ИТМО 1, 7 задач у МГУ 1. Дальше 6 команд по 6 задач.

12:55 - 515 решений на C++, 77 решений на Java всего среди петербургских решений.

12:48 - У ИТМО 1 тоже есть неудачная попытка по D - они не заметили, что ответ должен быть непустой. Когда я тестировал задачи, я сделал ту же ошибку.

12:45 - Команда Белорусского ГУ 1 тоже сдала L. Основная идея решения этой задачи такая: для того, чтобы заблокировать все пути из левого верхнего угла в правый нижний, необходимо и достаточно заблокировать два крайних пути: тот, что получается, если все время держаться рукой за левую стену, и такой же для правой стены.

12:43 - Проблема в решении задачи L у ИТМО 1 была просто мелкой ошибкой. Из-за того, что у них есть "if" вместо цикла, они забыли одинаково обработать момент прихода в правый нижний угол в обеих ветках.

12:40 - У СПбГУ 4 проблема с построением автомата для замыкания Клини: они забывают добавить отдельное состояние для "прочли очередное повторение", и поэтому их автомат для (cb*)* принимает строку "b", сначала переходя по переходу "не брать ничего" для (cb*)*, а потом возвращаясь по переходу "взять еще одну" для b*.

12:38 - ИТМО 1 сдали L. СПбГУ 4 прошли чуть дальше, до такого теста:

(cb*)*
b

12:36 - Оба решения команд МГУ по J - конструктивное построение ответа.

12:33 - МГУ сдаёт C и J за две минуты, и выходят на второе место. МГУ 4 сдаёт J и выходят на четвёртое место.

12:31 - Задача D основана на стандартном построении автомата, который принимает только строки, удовлетворяющие заданному регулярному выражению. Чтобы автомат получится маленьким, в нем нужно сделать eps-переходы. Дальше у нас есть два автомата, и мы делаем граф, вершины которого - пары состояний автоматов, и есть переходы стоимости 0 и 1, и запускаем модифицированный поиск в ширину.

12:30 - СПбГУ послали D, но не проходит такой тест:

b*a*
a

12:27 - Как-то не очень решают сегодня команды Саратова - не больше 3 задач у них. Надеюсь, ускорятся :)

12:23 - Вот тест, который у них не работает. Похоже, у них не работает, когда ответ 1?..

15 12
....#.......##.
###.##.#.##..#.
..#..###..##...
.###..#..####.#
.#.##.##..#.#..
....#..##...##.
#.####.#..#..#.
..#....#.###.#.
#...######.#.#.
..###.##.....##
.##.#.#..#.#..#
........##.##..

12:19 - У ИТМО 1 неудачная попытка по L. Главная идея в решении у них есть, но вот детали видимо не доделаны.

12:15 - 201 команда сдала хоть одну задачу (все они сдали задачу A), 114 команд сдали задачу G.

12:14 - Самое большое решение из уже отправленных - решение команды Ижевского ГУ 2 по задаче G на С++ - 4110 байт. Довольно мало.

12:00 - Не открыты четыре задачи: D, I, K, L. D и K - стандартные алгоритмы, но много писать, I и L нужно придумать, но писать меньше.

11:59 - У команды ИТМО 1 три задачи из семи сданы на C++: A, B, G - видимо, их писал Гена. Давно ничего не сдаёт МГУ.

11:56 - ИТМО 1 сдали B, избавившись от приближённой части. 60 штрафных минут потрачено на 3 неверные попытки, плюс довольно много времени за компьютером.

11:49 - у ИТМО 1 третья неудачная попытка по B, проблема с 1000 команд остаётся.

11:46 - СПбГУ 4 сдали B с первой попытки, у них тоже 6. Отставание 86 минут.

11:42 - ИТМО 1 исправили проблему со stop, но оставили приближенный поиск весов за 666 шагов, и теперь им не хватает 1000 шагов.

11:41 - Их перебор работает за 140 миллисекунд на самом медленном тесте.

11:36 - Открыта ещё одна задача: F, её сдала команда Ural FU 2. Сама задача - просто перебор, без особых ухищрений.

11:33 - МГУ 1 сдаёт B, теперь 6-5-5, СПбГУ обгоняет МГУ на 16 минут. Решение по B у всех успешных команд одинаковое: сначала уменьшаем вес до нуля, потом наращиваем до максимума, запоминая все n весов, потом перебором всех подмножеств находим нужный вес и уменьшаемся до него.

11:31 - Решение задачи J у ИТМО 1 конструктивное. Слева тратим почти все прыжки по 3 (туда-обратно-туда), справа тратим все прыжки по два (туда-обратно), получаются три случая в зависимости от количества оставшихся прыжка по 3 (0, 1 или 2).

11:28 - Открыты две новые задачи: ИТМО 1 сдали J, МГУ 4 досдали B. Единственное изменение в их решении - ответ на первый запрос :)

11:27 - МГУ 3 досдали C, избавившись от eps как ИТМО 1 - деля в конце на НОД.

11:26 - Две команды по 5 задач, отставание 70 минут.

11:25 - СПбГУ 4 сдали C. У них решение очень аккуратное - в целых числах.

11:22 - Что-то посылок стало очень мало, одна в минуту. Первые три места те же.

11:20 - У команды МГУ 4 по задаче B решение почти правильное, но они неправильно обрабатывают самый первый запрос - отвечают на него "decline", и поэтому вообще не знают, какое число является текущим.

11:18 - Проблемы с точностью продолжаются. Они уменьшили eps до 1e-14, и теперь выводят пустой файл - не находят никакого подходящего рационального приближения.

11:16 - У команды МГУ 3 ("Тапирёнок") по задаче C как раз, похоже, проблемы с eps - неправильный ответ в тесте с большим знаменателем.

11:11 - Теперь ИТМО 1 получили неправильный ответ по B. Я на этом уже один раз обжёгся, но опять скажу, что до правильного решения довольно далеко. Во-первых, они неправильно поняли формат обмена с проверяющей программой (говорят stop после accept, а не вместо него), во-вторых, у них приближённое решение для случая, когда есть совпадающие числа - пытаются по количеству раз, когда прибавляется какое-то число из первых 666 шагов, оценить количество таких равных чисел. Хотя, может быть, это и работает.

11:07 - Первые три команды те же, но теперь в другом порядке - из-за чистой сдачи МГУ вышли на второе место с четырьмя задачами.

11:04 - У первой команды Петрозаводского ГУ 1 странное решение по C - считают, что ответ либо целый либо полуцелый. На самом деле там знаменатели до ста тысяч. Собственно решение такое - отсортируем отрезки, бинарный поиск по ответу, пытаемся для каждого отрезка поставить его подотрезок как можно левее. Соответственно, возможные препятствия - сколько-то копий ответа влезло целиком между двумя целыми точками, а копий может быть до ста тысяч.

10:58 - Прошло 50 минут, первые три места 5-4-3 задач. Дальше должно идти помедленнее. Надеюсь. Иначе задач не хватит.

10:56 - У СПбГУ 4 задачи, сдали E. Решение стандартное: идём по возрастанию степени 10, для текущей степени 10 рассмотрим все мешки с достаточно мелкими монетами, и берём жадно от самого большого мешка к меньшему, пока не наберём достаточно, чтобы обнулить текущую цифру, потом переходим к следующей степени 10.

10:52 - Добавили модуль, прошло. У них решение проще, чем я видел раньше - вместо того, чтобы использовать eps и мучиться с подбором правильного значение для него, они без eps выбирают наилучшее рациональное приближение, а потом делят числитель и знаменатель на их наибольший общий делитель, чтобы выбрать нужное приближение из равных. Здорово!

10:49 - У ИТМО 1 неудачная попытка по C. До правильного решения пока далеко. Текущая основная ошибка - забыт модуль. В задаче нужно из числа в double получить рациональное число, и при проверке, на сколько отличается приближение от самого числа, они просто их вычитают, забывая взять модуль.

10:47 - По задаче H очень чёткая картина - все решения на C++ которые используют квадратные скобки для чтения из map получают TL, все остальные решения проходят. Moscow SU 1 сразу написали нормально, вышли на третье место.

10:45 - Пока что наборы задач монотонны - у всех команд с одной задачей только A, две задачи - A и G, три задачи A, G, H.

10:43 - По три задачи у СПбГУ 4, БГУ 1 и КБТУ 1. МГУ отстаёт.

10:40 - И четвёртая задача у ИТМО 1 - задача E. Тоже на Java, значит Гена готовится писать другие задачи :)

10:39 - Тем временем есть посылки по задачам C, F, L - но проходят пока только те три, которые сдали лидеры.

10:38 - Тем временем две команды по 3 задачи, 5 команд по 2 задачи.

10:36 - Оказывается, дело было не просто в map - по умолчанию квадратные скобки создают новый элемент, и соответственно получалось слишком много элементов со значением 0. Исправили квадратные скобки на find() - прошло.

10:31 - По задаче H: У ИТМО 1 решение на Java, и использует HashMap (из маски четностей по каждому символу в количество), а у СПбГУ на C++ и использует map - и у них Time Limit Exceeded из-за лишнего логарифма!

10:29 - У ИТМО 1 третья задача - H.

10:29 - Условия: http://neerc.ifmo.ru/information/problems.pdf

10:27 - у ИТМО 1 тоже две задачи. G - 20 строк, A - 22 строки. Все четыре упомянутые задачи на C++ - значит у ИТМО 1 их писал Гена.

10:25 - Решение задачи G СПбГУ - 17 строк, решение задачи A СПбГУ - 26 строк (кроме шаблона).

10:23 - у СПбГУ уже 2 задачи. Вообще сегодня много не очень сложных задач, начало контеста будет интересным.

10:21 - ИТМО 1 тоже сдают G. Еще 8 команд сдали A.

10:18 - Первая посылка! СПбГУ 4 сдали задачу G - одну из самых простых.

10:10 - 12 задач.

10:09 - Начали!

10:04 - Контест пока не начался, последние команды рассаживаются.

09:59 - Полуфинал проходит в четырёх городах одновременно: Санкт-Петербург, Барнаул, Ташкент, Тбилиси. Участники: http://neerc.ifmo.ru/regional/teams.html.

09:56 - Результаты будут здесь: http://neerc.ifmo.ru/information/standings.html.

09:53 - Конкурс прогнозов на SnarkNews: http://srv.snarknews.info/~ejudge/showvote.cgi?data=neerc2012. ИТМО:СПбГУ:МГУ 24:5:0.

09:41 - Команды пока ещё рассаживаются по местам.

This post will contain the blog for NEERC 2012 - refresh it to get new comments. The comments will be in Russian, you can try Google Translate to read them.

Saturday, December 1, 2012

NEERC 2012

Tomorrow is the day of ACM ICPC Northeastern European Regional Contest - probably the strongest semifinal ACM ICPC contest of all, home for 7 of the last 13 world champion teams. Best teams from Russia and ex-USSR, except Ukraine, gather in St Petersburg to select those who will go to the world finals, which will happen in St Petersburg as well this time, in July 2013.

There are many strong teams this year, but there are three teams that stand out (in my opinion): SPb NRU ITMO 1 (touristmikhailOKniyaznigmatul, combined TopCoder rating 8957, tourist and niyaznigmatul on the picture above, taken today at the practice session), SPb SU 4 (Dmitry_Egorovkuniavskiyeputons, combined TopCoder rating 8197) and Moscow SU 1 (SergeiFedorovSergeiRogulenkow_AleX_w, combined TopCoder rating 7877).

I will be doing a live blog about the contest tomorrow, here at http://petr-mitrichev.blogspot.com/. The blog will be in Russian since most people watching the contest speak Russian, and I hope the Google translation won't be too bad :) Join me at 10am Moscow time tomorrow (Sunday, December 2, 2012). Time in other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=NEERC+2012&iso=20121202T10&p1=352&ah=5.