Sunday, December 2, 2012

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.

50 comments:

  1. Что с сабмитом СПбГУ 4 по J?

    ReplyDelete
  2. Посмотри, пожалуйста, что у Уфы было неверно по В?

    ReplyDelete
  3. How many schools can advance to the World Finals in NEERC 2012?

    ReplyDelete
  4. This is not announced yet. Last year, 16 teams advanced.

    ReplyDelete
  5. Ты не знаешь, в чем в итоге у нас была бага в I?

    ReplyDelete
  6. Привет, я не слежу очень уж сильно за спортивным программированием, поясни, почему ты был в жюри (?), а не среди участников?

    ReplyDelete
  7. Я уже не студент давно

    ReplyDelete
  8. I think tests will be published later today.

    ReplyDelete
  9. Can we see problem statements?

    ReplyDelete
  10. http://neerc.ifmo.ru/information/problems.pdf

    ReplyDelete
  11. Could you tell me what was the test number 83 in problem G? 

    ReplyDelete
  12. что у саратов су 1 по задаче C?

    ReplyDelete
  13. Первый сабмит - TL.

    ReplyDelete
  14. Петр, не скажите что у Perm SU 1 в B? Спасибо.

    ReplyDelete
  15. Либо Runtime Error либо не хватает 1000 команд в первых попытках.

    ReplyDelete
  16. Что у МФТИ1 в B, G?

    ReplyDelete
  17. В G TL на 35 минуте и больше нет посылок - очень странно, в B не укладывалось в 1000 операций, видимо не хватало какой-то идеи.

    ReplyDelete
  18. Что сдают маи в В и что они посылали в Л? На каком языке?

    ReplyDelete
  19. и в B и в L решения на Java, в B не укладывалось в 1000 операций, в L какая-то эвристика, правильной идеи нет.

    ReplyDelete
  20. Первый сабмит по задаче K от South Ural SU 1, насколько там все далеко от правильного решения ?

    ReplyDelete
  21. Довольно далеко. В правильном решении есть стандартный блок "найти во множестве из n отрезков два пересекающихся за O(nlogn)", у них я его не нашёл.

    ReplyDelete
  22. Узнаете после закрытия :)

    ReplyDelete
  23. Была ли сдана задача K ?

    ReplyDelete
  24. Узнаете после закрытия :)

    ReplyDelete
  25. K РЕШИЛИ ?!

    ReplyDelete
  26. Узнаете после закрытия :)

    ReplyDelete
  27. член двачаMay 10, 2013 at 1:34 PM

    Петя, естьли шанс пройти в финал у команд с 5 задачами?
    Где по-твоему будет граница выхода в финал:  количество задач и штрафных минут. 
    Хотя бы приблизительно, твоя оценка.

    ReplyDelete
  28. К сожалению, я знаю реальные результаты, поэтому не буду делать предположений :)

    ReplyDelete
  29. какие прогнозы жюри на Анжи-ЦСКА? :) первый тайм заканчивается

    ReplyDelete
  30. Что у СПБ ГУ 2 с В?
    И есть ли сабмиты на Delphi? Спасибо

    ReplyDelete
  31. Что у ижгту в B?

    ReplyDelete
  32. Петя, а не подскажешь, что с командой БГУИР 1 (Belarusian SUIR 1) - у них уже 6 неверных попыток в задаче C

    ReplyDelete
  33. Спасибо!

    ReplyDelete
  34. Сколько команд проходит в финал? спасибо

    ReplyDelete
  35. Насколько близки БГУ2 к сдаче B?

    ReplyDelete
  36. А сколько сейчас решений на С++ у команды ИТМО 1?

    ReplyDelete
  37. Насколько близки MIPT 2 к сдаче I?

    ReplyDelete
  38. What can you say about difficalties in problem I? Are there some "underwater stone"?

    ReplyDelete
  39. Что там у КБТУ-2 и КБТУ-4? 

    ReplyDelete
  40. можно поподробнее про конструктивное решение задачи J? не очень понятно как начинать тратить прыжки по 3 и 2 сначала

    ReplyDelete
  41. Будет ли продолжаться комментирование после заморозки таблицы ?)

    ReplyDelete
  42. Could you also post the solutions of the problems as teams solve them ?

    ReplyDelete
  43. В таблице результатов только те команды которые пишут в Питере ? или еще другие регионы ? 

    ReplyDelete
  44. Вроде все должны быть.

    ReplyDelete
  45. What's wrong with online translation ? ?

    ReplyDelete