Всем привет!
Только что закончился четвертьфинал Южного подрегиона NEERC, и я хотел бы немного рассказать, что происходило сегодня и вообще на этой неделе в Саратове.
Часть 1: читайте инпут, посоны!
Hohol, как обычно, решил выиграть пробный тур. Как это делать, Hohol прекрасно помнил, ведь на его счету два выигранных пробных тура в 2011 году :) На сей раз, как выяснилось на открытии, жюри четвертьфинала решило добавить интерактивную задачу, поэтому на пробном туре нас тоже ждали интерактивные задачи.
Порешили на том, что Hohol садится за клавиатуру и пишет две стандартные задачи саратовского пробного тура, я слежу, как он это делает, а craus решает интерактивку. Посабмитив две первые задачи примерно на 2:10 и 3:30, мы обнаружили, что первая из них получила WA 1 (забыли считать инпут), а вторая — TLE 11 (инпут был слишком большой для cin). Так что мы забили на идею победить в пробном туре, открыли студию и начали спокойно писать две интерактивные задачи.
Сдав эти интерактивные задачи, мы с удивлением и смехом обнаружили себя на первом месте (одна из интерактивок была довольно неплохой сложности и многим не поддавалась). На следующий день нас ждало Code Game Challenge.
Часть 2: не оставляйте known issues, посоны!
Code Game Challenge заключался в следующем: дано игровое поле с двумя большими препятствиями в центре и четыре танка машинки, управляемые программами участников. Машинки должны были ездить по полю, собирать флаги (которые давали очки) и лечиться на своей ремонтной станции. Особенностью этого Code Game Challenge было то, что машинки погибали навсегда — поэтому осторожное объезжание препятствий, стен, других игроков было важной частью стратегии. Еще можно было стрелять друг в друга шинами, правда, кажется, это было не очень эффективно — шины просто отталкивали соперников, но не наносили им урона непосредственно.
Code Game Challenge полностью писал я по указаниям craus, который вечером раздумывал над особенностью стратегии. В итоге наша машинка на тестах против случайных машинок была примерно в серединке. К тому же у нас был баг, проявлявшийся примерно в 1 случае из 15. Я не буду раскрывать всех подробностей Code Game Challenge. Вы можете посмотреть видео, понаблюдать за нашим багом своими глазами и вообще насладиться великолепной атмосферой этого шоу.
Часть 3: не сабмитьте ML 1, посоны!
Контест довольно неплохой, так что советую всем его порешать (на acm.sgu.ru, задачи 542-553 или на Codeforces-тренировках). А если при решении возникнут трудности, специально для вас есть разбор задач с места событий.
Вероятно, вы уже видели финальную таблицу и наше отставание на 5 минут от третьего места. Сейчас я расскажу, как так получилось.
В один из предыдущих дней I_love_natalia толкнул в жюри байку о том, что в мишку встроен голосовой передатчик, а обратная связь прикручена к ноге Hohol. Вроде бы они там сильно посмеялись, но, оказывается, волонтеры поглядывали, чтобы мы не говорили с медведем :D
В начале контеста мы довольно серьезно тормозили. craus прочитал задачу E и мы начали ее писать. Мы ее написали и обнаружили, что задача была решена неправильно: craus пошел думать дальше, а Hohol сел за задачу L.
Задачу L Hohol писал по ощущениям минут 15, один раз полностью переписывая решение заново. После этого я сел писать задачу J, а Hohol за мной наблюдал. Ее мы написали довольно быстро. Посмотрев на монитор, мы увидели один AC по задаче E от нашей второй команды (Slamur, Sinner, Jeg) и несколько AC по задаче F. Читаю задачу F — да это же халява! Пишем сдаем, AC.
После этого craus придумал (видимо, не очень оптимальное — можно было сэкономить на этой задаче минут 20-30) решение по задаче E, требующее дерево отрезков — я пошел ее писать, распечатал, Hohol нашел в ней пару багов, а в это время мы дописали остальное решение. Получив AC, мы посмотрели на монитор — мы были на 4 месте, а на 3 месте расположилась наша вторая команда, очень быстро сдавшая четыре задачи. На первых двух местах были команды из Саратова.
Следующей нашей задачей стала задача G. Hohol и craus придумали основную идею, а я пошел писать. Написав эту задачу (правда, потеряв, по ощущениям, минут 10), мы решили ее посабмитить. Вердикт: Memory limit exceeded on test 1. Ой!
Итак, всем советую:
проверять, сколько ваша программа жрет памяти с помощью Task Manager (Ctrl+Shift+Esc) или опции запуска на сервере.
или хотя бы правильно считать размеры массивов на калькуляторе, считая, что тип int занимает 4 байта, а не 1.
Через три минуты мы получили AC, но штрафная попытка, к сожалению, уже была получена.
Затем я и craus пошли думать над задачей B, которую к тому времени сдала команда Saratov SU 1, а вскоре Hohol придумал решение задачи H, которую я перед этим неправильно прочитал и посчитал гробом. Hohol сел за комп и вскоре сдал нашу шестую задачу H. Открыв монитор, мы с грустью увидели отставание в 5 минут от третьего места, на котором расположилась команда Saratov SU 4.
В оставшиеся полтора часа мы пытались написать задачу C (по которой у Saratov SU 2 к этому времени было несколько штрафных попыток) и додумать задачу B (потом оказалось, что мы были на правильном пути и немного недопридумали).
Наша вторая команда в это время пыталась сдать задачу G. Оказалось, что они примерно в течение двух часов слали очевидно TL-ящееся решение. Сразу после заморозки Sinner придумал-таки нормальное решение и они сдали пятую задачу. Потом они написали задачу H, получили по ней WA 16, но ошибки до конца контеста так и не нашли. На NEERC, впрочем, наша вторая команда попала, причем за счет быстрых четырех первых задач у них было даже не последнее место среди тех, кто сдал пять задач.
Итак, сегодня у нас было чуть менее, чем 100500 возможностей занять 3 место, но что-то не сложилось :(
Заключение
Собственно, две команды Samara SAU едут на NEERC, где мы со многими из вас встретимся. Пожелаем нам удачи, ибо это последний сезон и последний шанс попасть на финал. Ждем 2 декабря и спасибо за внимание.
P.S. Вроде бы монитор на сайте соревнования не открывается уже открывается: http://contest.sgu.ru/monitor/?id=1
На NEERC прошли команды вплоть до 19 места, из них из Саратова — только три первых говорят, что четыре, так как проведение контеста дает +1 к квоте.
P.P.S. Видео Code Game Challenge выложено на Youtube. Разбор задач выложен на Youtube.
Это лучший пост из серии «Спортивное программирование и…»
Все было так! Я гарантирую это!
Жду видео с CGC)
Выложил на Youtube, ссылка в посте
Найс, щас заценю как Уркаган снова выиграл)
Эх, посоны, что же вы в тройку-то не попали. Плохой старт подвел. Удачи на полуфинале, посоны!
Это нормально, мы, когда стали финалистами, тоже в Саратове заняли четвертое место, после трех Саратовых. Родные стены Саратову очень помогают, на полуфинале мы были 9е, а Saratov SU #3 22е без двух задач от нас.
Всем минусовавшим смотреть результат NEERC.
Какое совпадение, только теперь разница в три задачи.
а Снарк считает по-другому.
Там, кстати, опечатка: у команды Кудасов, Фролов, Свечников номер 4, а не 3.
Скоро будет 3 :)