Лучшая команда НГУ
Речь идёт о «Поттосинке». Скажу сразу же наш результат - седьмое место в общем зачёте и второе по Сибири - нас обошла команда ТГУ, занявшая четвёртое место, - примерно это я и имел в виду, когда говорил, что у них далеко не самый низкий уровень. Между прочим, в предыдущие два года лучшая команда Сибири оба раза была в общем зачёте восьмой. Наш регион поднимается? Это не может не радовать. А если кто-нибудь скажет, что мы облажались, что ж - «иди и сыграй лучше». Просто у Томска есть Миша Колупаев, который на данный момент явно сильнее меня. А у нас нет. Но это, как и все проблемы подобного рода, конечно же, поправимо.
Почему название поста выполнено в стиле Кэпа? О, это не моя идея. Раньше была такая славная традиция, что компания Parallels - один из спонсоров - вручает лучшей сибирской команде специальный приз. Но в прошлом году у «Пакетов» (2/3 которых ныне со мной) что-то пошло наперекосяк, и поэтому ВНЕЗАПНО получилось так, что этот приз должен был отойти чужим людям, - тогда-то наши тренеры и подкинули Parallels славную идею - вручить два приза: лучшей команде Сибири и лучшей команде Новосибирска. А в этот раз на лежащей сейчас у меня на тумбочке памятной доске с сертификатом на 60 к. р. почему-то красуется и вовсе скромная надпись: «Лучшей команде НГУ», - а приз томичам, уж не знаю какой, вручила компания APC.
Во втором, основном, туре, у нас всё шло более или менее стандартно. Разве что был такой интересный момент: раньше писать поиск наименьшего контролирующего множества в двудольном графе за O(VE) мне не доводилось никогда, даже на тренировках. Однако я каким-то чудом сумел во время контеста адекватно восстановить в памяти некогда виденную краем уха презентацию этого алгоритма. Ну а под конец мы не сдали свою седьмую задачу (и оказались на 14 строчке вместо 9) из-за того, что наш теоретик проявил фееричный идиотизм, сумев представить двумерную вообще-то геометрию как трёхмерную, а наш капитан проявил не менее фееричный идиотизм, сумев ему поверить. Мы продемонстрировали настоящий командный дух! И это не настолько шутка, как может показаться: когда команда впустую теряет полчаса времени из-за ошибки одного человека - это демонстрация справедливо наказуемого непрофессионализма в организации teamwork’а, а вот когда только из-за одновременной ошибки двоих - это прокол уже всё-таки не в земном менеджменте.
А вот не первом туре всё было куда веселее. Задача в этот раз там была не игровая, а скорее марафонская. Мы долго пытались придумать хоть сколько-нибудь приличный алгоритм, но ничего не получалось. В середине тура я, чтобы проверить хотя бы интерфейс программы, взял да и отослал тупейшее решение, генерировавшее ответ чуть лучше чем случайно, - и оно набрало 11 баллов, поместив нас в середину таблицы. Из этого факта стало ясно, что большинство команд находится сейчас примерно в том же положении, что и мы. А после этого мы догадались глянуть в топ: у лидеров было порядка сотни баллов, что составляло около одного процента от теоретически возможного максимума. Но ведь тогда… тогда, чтобы подняться высоко, достаточно использовать хотя бы какие-то, хотя бы чуть-чуть разумные эвристики! Следующая пара часов ушла у меня на то, чтобы написать самый простой алгоритм, сколько-нибудь претендующий на разумность. Результат - 18 баллов. Исправить в коде баги, ужасаясь, как это вообще смогло оказаться лучше рандома, - и получить около той самой сотни баллов и место в топе. Наконец, в последние полчаса упорото подкручивать разные от фонаря выбранные константы, добиваясь наилучшего результата, - 270 баллов и второе место (а до последних правок решения команды МГУ долго было даже и первое). Но во время тура, конечно, проводилось только предварительное тестирование. Окончательное же тестирование показало, что мы таки действительно на втором месте. Отставание от первого - двукратное. Отрыв от третьего - трёхкратный, от четвёртого - шестикратный, от пятого - одиннадцатикратный. Неслабо, верно? Я в очередной раз, как и в предыдущие два года, подумал, что, скажем, в TopCoder Marathon мог бы показывать результаты намного лучше, чем в TopCoder Algorithm. Видимо, у меня к формату соревнования, когда надо за пять часов решить не шесть-десять средней сложности задач полностью, а один нереальный гроб - частично, какой-то, как это ни прозвучит банально, талант. Но - нет и ещё раз нет. Я тренируюсь для ACM.
Вот, собственно, и весь рассказ. Действительно, интегрально - ничего особо выдающегося. Тебя это не вдохновляет - оно и понятно, меня и самого не очень. Всё те же, всё то же, а ночь всё холодней. Но полуфинал, между тем, уже через три недели.
Почему название поста выполнено в стиле Кэпа? О, это не моя идея. Раньше была такая славная традиция, что компания Parallels - один из спонсоров - вручает лучшей сибирской команде специальный приз. Но в прошлом году у «Пакетов» (2/3 которых ныне со мной) что-то пошло наперекосяк, и поэтому ВНЕЗАПНО получилось так, что этот приз должен был отойти чужим людям, - тогда-то наши тренеры и подкинули Parallels славную идею - вручить два приза: лучшей команде Сибири и лучшей команде Новосибирска. А в этот раз на лежащей сейчас у меня на тумбочке памятной доске с сертификатом на 60 к. р. почему-то красуется и вовсе скромная надпись: «Лучшей команде НГУ», - а приз томичам, уж не знаю какой, вручила компания APC.
Во втором, основном, туре, у нас всё шло более или менее стандартно. Разве что был такой интересный момент: раньше писать поиск наименьшего контролирующего множества в двудольном графе за O(VE) мне не доводилось никогда, даже на тренировках. Однако я каким-то чудом сумел во время контеста адекватно восстановить в памяти некогда виденную краем уха презентацию этого алгоритма. Ну а под конец мы не сдали свою седьмую задачу (и оказались на 14 строчке вместо 9) из-за того, что наш теоретик проявил фееричный идиотизм, сумев представить двумерную вообще-то геометрию как трёхмерную, а наш капитан проявил не менее фееричный идиотизм, сумев ему поверить. Мы продемонстрировали настоящий командный дух! И это не настолько шутка, как может показаться: когда команда впустую теряет полчаса времени из-за ошибки одного человека - это демонстрация справедливо наказуемого непрофессионализма в организации teamwork’а, а вот когда только из-за одновременной ошибки двоих - это прокол уже всё-таки не в земном менеджменте.
А вот не первом туре всё было куда веселее. Задача в этот раз там была не игровая, а скорее марафонская. Мы долго пытались придумать хоть сколько-нибудь приличный алгоритм, но ничего не получалось. В середине тура я, чтобы проверить хотя бы интерфейс программы, взял да и отослал тупейшее решение, генерировавшее ответ чуть лучше чем случайно, - и оно набрало 11 баллов, поместив нас в середину таблицы. Из этого факта стало ясно, что большинство команд находится сейчас примерно в том же положении, что и мы. А после этого мы догадались глянуть в топ: у лидеров было порядка сотни баллов, что составляло около одного процента от теоретически возможного максимума. Но ведь тогда… тогда, чтобы подняться высоко, достаточно использовать хотя бы какие-то, хотя бы чуть-чуть разумные эвристики! Следующая пара часов ушла у меня на то, чтобы написать самый простой алгоритм, сколько-нибудь претендующий на разумность. Результат - 18 баллов. Исправить в коде баги, ужасаясь, как это вообще смогло оказаться лучше рандома, - и получить около той самой сотни баллов и место в топе. Наконец, в последние полчаса упорото подкручивать разные от фонаря выбранные константы, добиваясь наилучшего результата, - 270 баллов и второе место (а до последних правок решения команды МГУ долго было даже и первое). Но во время тура, конечно, проводилось только предварительное тестирование. Окончательное же тестирование показало, что мы таки действительно на втором месте. Отставание от первого - двукратное. Отрыв от третьего - трёхкратный, от четвёртого - шестикратный, от пятого - одиннадцатикратный. Неслабо, верно? Я в очередной раз, как и в предыдущие два года, подумал, что, скажем, в TopCoder Marathon мог бы показывать результаты намного лучше, чем в TopCoder Algorithm. Видимо, у меня к формату соревнования, когда надо за пять часов решить не шесть-десять средней сложности задач полностью, а один нереальный гроб - частично, какой-то, как это ни прозвучит банально, талант. Но - нет и ещё раз нет. Я тренируюсь для ACM.
Вот, собственно, и весь рассказ. Действительно, интегрально - ничего особо выдающегося. Тебя это не вдохновляет - оно и понятно, меня и самого не очень. Всё те же, всё то же, а ночь всё холодней. Но полуфинал, между тем, уже через три недели.