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.
The 2013 Ural Championship will take place between May 1 and May 3 in Ekaterinburg. This is an annual contest held using ACM ICPC-like rules, but this year the organizers have stepped up to make it a top-notch event, inviting many teams of the highest level. I'm currently waiting to board a plane to Ekaterniburg in the cloudy Moscow, pictured on the left.
