Всем привет!

Только что закончился четвертьфинал Южного подрегиона 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. Ой!

Итак, всем советую:

1. проверять, сколько ваша программа жрет памяти с помощью Task Manager (Ctrl+Shift+Esc) или опции запуска на сервере.

2. или хотя бы правильно считать размеры массивов на калькуляторе, считая, что тип 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.