NEERC 2008

26 ноября проводился полуфинал ACM ICPC в регионе северовосточной Европы. В этот регион входят все страны постсоветского пространства (кроме Украины и Молдовы), поэтому проведение соревнования в одном месте было бы несколько проблематично. Так что организаторы предпочитают сталкиваться с трудностями другого плана, проводя соревнование синхронизированно в четырёх местах одновременно: Санкт-Петербурге, Барнауле, Ташкенте и у нас на Кавказе, что из последних четырёх лет три раза было в Батуми.

В Батуми обычно приезжают команды из Грузии, Армении и Азербайджана. Учитывая, что на задачах полуфинала у нас проводится и Открытый командный чемпионат Южного Кавказа, с отдельным зачётом и иногда призовым фондом, каждый год у нас бывала гостевая команда, которой до сих пор обычно и доставалось первое место. В 2005 году это была Moscow x13, которая умудрилась не пройти из своего четвертьфинала, но тем не менее решила то ли 10, то ли 11 из 11 задач, предложенных на полуфинале. В 2007 году это была Lviv NU, которая впоследствии была награждена золотыми медалями на финале ACM ICPC. В 2008 году у нас было целых три гостя из Украины, и более того - две команды (NTUU KPI и Sumy SU) боролись за право учавствовать в финале именно из нашего региона. Третья же, Taurida NU, к тому моменту уже была финалистом, так как полуфинал их региона проводится раньше, чем NEERC.

Команды из Киева и Сум (Сумы, Сумов, не знаю как правильно склонять) приехали в Тбилиси 23-го числа, под вечер. Киевляне решили уехать в Батуми сразу ночным поездом, а Sumy SU остались, чтобы уехать с потоком команд из Тбилиси следующей ночью. Так что 24-ого у нас было время показать ребятам город.

Стоим слева направо: Гиоргий Сагинадзе (какой-то он тут грозный), я, тренер Sumy SU Сергей, Боря, а присевший - Саша. Фотографировал нас Виталий.

Как уже говорилось, в ночь с 24-ого на 25-ое большинство команд на поезде переместилось в Батуми (может, я с датами на день ошибаюсь, но да ладно). В первый день было открытие и пробный тур. Ничего особо интересного там на моей памяти не происходило.


Главное событие состоялось 26-ого. Проблемсет NEERC состоял из 11 задач, среди которых впервые присутствовала необычная для ACM-контестов интерактивная задача. То есть вместо стандартного "введи данные - выведи ответ" была целая череда "введи - выведи", причём входные данные подавались программе в зависимости от её предыдущих аутпутов. На этот раз задача была довольно простая - обойти некоторый граф DFS-ом. Но в принципе в будущем, я думаю, будут приносить в качестве интерактивной интересные задачи на теорию игр.

Как это часто у нас получается, начали мы с не самой лёгкой задачи, поэтому когда мы её провели на 28-ой минуте, у нескольких команд было уже по две, а SPb IFMO 1 вообще умудрилась решить 4ую на той же минуте, что мы первую. Но за следующие 40 минут мы решили ещё 4 и оказались среди лидеров. За следующий час мы расправились ещё с двумя задачами и с 7 задачами продолжали уверенно оставаться в первой десятке. Ещё более часа нам потребовалось на задачу K, которая, как выяснилось позднее, и вывела нас в финал. После этой задачи мы 100 минут безуспешно маялись с остальными задачами, долго писали D, но она так и не поддалась. Хуже получилось только у Бурундучков, Ижевска и Петрозаводска: у них не было AC последние 170 (!) минут. На мой взгляд, неуравновешенный получился проблемсет.

Как выяснилось позднее, NTUU KPI также решили 8 задач, и как выяснилось ещё позднее, 8 задач как раз и гарантировали попадание в финал для команд, обошедших своих конкурентов из того же университета. Что касается других команд Тбилисского Университета, две из них решили по 6, задач, заняв 46-ое и 56-ое места, а последняя решила 5 задач. В совокупности с достижением TSU1 это является лучшим результатом команд ТГУ на протяжении периода выступления наших команд в NEERC.

Можете посмотреть окончательные результаты NEERC и чемпионата Южного Кавказа.


27-ое число было посвящено спортивным соревнованиям, был проведён чемпионат по футболу и пинг-понгу. В футболе второй год подряд победу одержала команда учителей, а в настольном теннисе, если я не ошибаюсь, первое место занял Сергей Канищев.


В формате чемпионата Южного Кавказа, кроме командного первенства на задачах NEERC, бывает также личное первенство. Проводится оно по обычным правилам ACM, а задачи берут с в теории неизвестных в наших краях контестов. В прошлом году задачи были с South American Regional Contest 2007. Как ни странно, в этом году задачи взяли с этого же контеста, соответственно 2008 года. Боле того, на этих задачах проводился контест на uva.onlinejudge.org. Некоторые из участников личного первенства его даже писали. И ещё - эти задачи выложили на архиве spoj.pl (№№3405-3415) 23 ноября, а наше-то первенство проводилось 28-го числа... Так или иначе, можете взглянуть на результаты соревнования.


Ну а 29-ого числа состоялся банкет, на котором, несмотря на некоторую напряженность, в итоге было очень весело.

Open All-Siberian Olympiad 2008

Следующее событие - финал Открытой Всесибирской олимпиады им. Потоссина. В 2008 году эта олимпиада проводилась уже в девятый раз. Не знаю, как было сначала, но последние три раза перед onsite финалом проводился отборочный раунд через интернет. Можете посмотреть на результаты последнего.

Так вот, в 2008 году команда ТГУ в третий раз подряд прошла в финал этой олимпиады, но в этом году перспектива поехать была ещё более призрачной, чем когда-либо ранее, вследствие августовских событий. На этот раз организаторами олимпиады было допущено исключение по отношению к нашей команде - нам была представлена возможность учавствовать из Тбилиси, тем не менее оставаясь в конкурсе. К нам приехал представитель Новосибирского Государственного Университета, господин Николай Вячеславович Шилов, для контроля соблюдения нами правил во время соревнования.

Этот человек мне очень запомнился, он интересный собеседник и вообще приятная личность. Также он потряс меня своим умением вести беседу, вернее, одной особенностью. Я часто замечаю, что во время разговора человек, объясняя подробности чего-либо, вспоминает связанные с этим темы и постепенно разговор переходит в новое русло, а первоначальная идея теряется. Ну по крайней мере со мной так часто бывает, и я могу только позднее вспомнить, что на самом деле я хотел сначала досказать. А вот Николай Вячеславович умудрялся углубиться в детали, рассказать связанные с ними вещи, но сколь долго бы он не говорил, в итоге он возвращался к предыдущей теме и досказывал свои мысли до конца. Он мог так вспомнить что-то, затем что-то, связанное с этим чем-то, и так далее, а затем обязательно закончить каждую предыдущую мысль. Примечание ненасытного олимпиадщика: если представить все мысли как дерево, в котором каждая новая идея - вершина; ассоциация, приводящая от одной мысли к другой - ребро; а мысль, после которой тема исчерпана - лист, то этот человек обходил всё дерево поиском в глубину. Something like that :D

Ну чтож, может, в разговоре я и забываю первоначальную тему, но на бумаге я точно следую плану. Поэтому вернёмся к финалу Всесибирской олимпиады.

Формат финала подразумевал два дня соревнований. Первое соревнование было 5- или 6-часовым, точно не помню. Давалась одна страшная и неповоротливая задача в стиле Marathon Match, которая на этот раз была чем-то таким:

Дано некое пространство, в нём N треугольников и M точек (N<=10^5, M<=10^4). Найдите для каждой точки список всех точек, которые из неё видны. Видимость означает, что отрезок, соединяющий эти точки, не пересекается ни с одним из треугольников. Очки команда набирала за каждый правильно угаданный список. Time Limit был что-то вроде 10 секунд. К задаче прилагался визуализатор, с помощью которого можно было осмотреть это самое пространство для любого теста. Давалось около 5-6 example тестов, а всего их было что-то вроде 50.

Было ясно, что перебирать для каждой вершины все остальные и потом проверять все треугольники, т.е. O(M^2 * N), точно слишком медленно для больших тестов. Тем не менее, ничего лучше нам в голову так и не пришло, поэтому Ника имплементировал этот подход. Потом мы его максимально обрезали, не рассматривали треугольники вне какого-то интервала, определённого отрезком, и т.д. и т.п. В итоге мы вышли на четвёртое место по результатам этого дня, и по набранным командами очками было видно, что кроме первых двух команд (по-моему SPb IFMO и MSU Unpredictable), никто лучшего подхода к задаче не нашёл.

Второй день соревнований проводился по стандартным правилам ACM. Задачи были довольно сложные, мы в итоге только 7 решили и вышли на четвёртое место по результатам того дня. Задачи я особо не помню, из менее решаемых был вроде MCMF, FFT, ещё задача на нахождение мат. ожидания в довольно извращенных условиях.

По сумме двух дней мы вышли на третье место и уступили второму только по допольнительным показателям - т.е. мы имели с ними одинаковое среднее место, подсчитанное как [(PlaceDay1)/2+PlaceDay2], но во второй день они были выше, а приоритет отдавался именно ему. Окончательная таблица выглядит так.

ACM ICPC 1/4 Finals - Georgia Subregion

Первым в хронологическом порядке, вроде бы, следует четвертьфинал ACM ICPC, проведённый 1 ноября, который одновременно является этаким первенством Грузии, хотя никаких дипломов, титулов или призов на нём не раздаётся. Правда, в этом году, помимо грузинских команд, в нашем четвертьфинале участие приняли две команды из Украины (NTUU KPI и Sumy SU), которые в итоге успешно прошли в полуфинал.

Леква во время четвертьфинала был в Кутаиси, поэтому писали только Ника и я. Задачи, как и в прошлом году, представляли собой упрощенный вариант задач Северного четвертьфинального региона. Первые 50 минут у компа сидел я, а Ника читал задачи и говорил мне алгоритмы. Пустив так 6 задач, я уступил ему место и из оставшихся 5 задач 4 написал уже он. В итоге мы закончили за 126 минут и вскоре покинули место действия, окончательные результаты увидев уже дома. В полуфинал были допущены все команды, решившие хоть что-либо, за исключением Tbilisi SU 5 и 6, потому что квота на количество команд от одного университета для полуфинала в Батуми равна 4 командам.

Спустя несколько месяцев...

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