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], но во второй день они были выше, а приоритет отдавался именно ему. Окончательная таблица выглядит так.