Собственно, только что закончился третий раунд SNWS 2014. Хотелось бы узнать 2 вещи:

1) Можно ли как-нибудь решить E без использования длинной арифметики?

2) Кто-нибудь может объяснить вот это? Всегда думал, что Java 7 x32 самая быстрая, а тут наоборот оказалось.

По традиции один из участников СГАУ после любого крупного соревнования пишет пост о нем. На сей раз в связи с тем, что традиционный блоггер нашего университета dalex не поехал на ЧФ, эта честь досталась мне. Я являюсь участником команды Samara SAU 1 и это мой второй сезон ACM ICPC.

Пробный тур

Так как то, что происходило до пробного тура, не особо интересно, начну, пожалуй, с него. Первые две задачи на нём были стандартные — количество нечетных чисел на интервале [a,b] и реверс массива. Третья и четвертая задача были интерактивными с одинаковым условием, но разными ограничениями на количество запросов. Интерактивку читал я, пока Slamur кодил А и B, каково же было мое удивление, когда я узнал, что игра "Быки и коровы", которая описывалась в ней, является общеизвестной. Если кому интересно, надо было отгадать четырехзначное число, в котором все цифры различны, сами правила игры можно легко найти в гугле. Быстро сдав С, в которой ограничение на количество запросов было равно 50, мы попытались придумать, как отгадать число за 7 запросов (задача D). В итоге это привело к тому, что мы стали играть друг с другом в эту игру и ушли минут за 25 до окончания пробного тура. Нас сразу же встретил I_love_natalia и объяснил как это решать, но возвращаться и писать это мы, естественно, не стали. Насколько я помню, решить её смогла только первая команда Саратовского ГУ и команда Южного ФУ.

Code Hockey

По традиции, в день перед основным контестом проводилось соревнование ботов, написанных участниками — Code Game Challenge. Однако вместо того, чтобы как обычно кодить AI для танчиков (волшебников, машинок — одна суть) участникам предлагалось написать бота для хоккейной команды, состоящих из двух полевых игроков и вратаря, бот для которого уже был написан и менять его было нельзя. В отличии от предыдущего года мы почти не обсуждали в вечер перед кодгеймом варианты стратегий, я же просто перед сном стал играть в FIFA 14, правда не думаю, что это нам помогло.

Первые почти полтора часа контеста мы пытались написать бота, который хотя бы не проигрывает одной из дефолтных реализаций. Когда нам это более менее удалось, мы решили всё-таки послать его играть с ботами других команд и не особо сильно удивились тому, что проигрывали всем подряд. Поиграв немного с ботом нашей второй команды (Samara SAU 2), мы решили скопировать у них тактику ударов и, успешно это сделав, стали более-менее стабильно забивать шайбы. Позже эта тактика была немного усовершенствована после игр с ботом ZBS команды Саратовского СУ 1, и после этого атаку мы больше не улучшали, решив сосредоточиться на защите собственных ворот. Основная суть защитной тактики была в том, что один из полевых игроков стоял в противоположном от своего вратаря углу ворот. При хорошей реализации это позволяло практически не пропускать, однако выловить все баги мы так и не смогли. Свои шансы мы оценивали довольно скромно, но тем не менее решили всё-таки поменять название нашей хоккейной команды с "Samara Aero DNO" (предложено Slamur) на более приличное. После одной победы и одного поражения в первом этапе мы заняли 19 место, что давало нам выход во второй этап, где участвовало 24 команды. В нем мы внезапно умудрились одержать 2 победы, одну, кстати, над ботом нашей второй команды, и заняли 3 место. В третьем этапе(8 команд) нам снова повезло с противниками и, выиграв одну игру у "I_am_coach" и проиграв "Uncrashable", мы снова заняли 3 место. В финале же из 4 команд по круговой системе мы проиграли абсолютно всем и, соответственно, заняли 4-ое место. Это нас не сильно расстроило, так как мы даже не предполагали забраться так далеко. Плюс ко всему, мы вспомнили, что в прошлом году Teddy Bears также заняли 4 место в кодгейме, а потом это же 4 место на основном туре. Кто же знал, что история повторится...

Контест

Набор задач нам показался несколько несбалансированным, однако сами задачи были предельно понятны и довольно интересны. Сразу же хочу извиниться перед командами в нашей комнате, так как мы наряду с сидящей рядом с нами саратовской командой иногда довольно громко говорили.

В начале контеста Слава (Slamur) сел за клавиатуру набивать шаблон, пока мы с Егором (Petruchcho) читали задачи. Найдя халявку, мы достаточно быстро ее закодили и получили АС. После этого, мы с Егором придумали какую-то фигню в M, однако оказалось, что она не проходит сэмплы. Подумав над ней еще минут 5, мы забили на нее и к примерно к 1:40 сдали еще 3 легких задачи. Взглянув после этого на таблицу, мы увидели, что у Saratov SU 1 6 задач, а у нас и Saratov SU 2 по 4. Сдав в следующий час 2 задачи, мы вышли на 2 место с гигантским отставанием по штрафному времени от Saratov SU 1. К сожалению, мы получили +3 по B из-за довольно тупых WA, и вторая и третья команды Саратова обходили нас по штрафу после сдачи ими своих 6-х задач. Saratov SU 4 же отставал от нас на 3 минуты штрафного времени. Оставшееся время до заморозки мы провели за неудачными попытками придумать решение к остальным задачам и просмотром положения других самарских команд. В последний час я придумал более-менее адекватную(как выяснилось позже всё-таки неправильную) идею к задаче M, однако сдать мы ее не смогли. К концу контеста мы так и остались на 4-ом месте с шестью задачами, 7 задач на момент заморозки сдали только Saratov SU 1.

Награждение

До награждения мы узнали, что Saratov SU 4 в последний час ничего не сдали, вследствие чего наши шансы на 4-ое место сильно повысились. В итоге только Saratov SU 2 сдали в последний час седьмую задачу, так что история повторилась, и мы как и Teddy Bears годом ранее заняли первое непризовое место с отставанием в 18 штрафных минут от третьего. Вторая и третья команды СГАУ сдали 2 и 1 задачи соответсвенно и на выход в полуфинал не претендовали. Шансы пройти в Санкт-Петербург оставались только у одной самарской команды — Samara SU 2, сдавшей 4 задачи. После разморозки результатов они оказались на 20 месте, которое при квоте в 15 команд от региона и 6 саратовских командах впереди, являлось первым невыходящим. Но всё-таки была расширена квота на одну команду, которой как раз и стала Samara SU 2, последняя из решивших 4 задачи. C чем я их собственно и поздравляю. Забавно, что в прошлом году квота также была увеличена на одну команду и тогда ей оказалась Samara SU 1.

Хочу также поздравить тех, с кем мы постоянно тусовались в Сазанке, а именно Mordovia SU 1, и Kazan FU 2, с которыми мы сегодня неплохо отметили выход в полуфинал.