?

Log in

No account? Create an account
Ferlon [userpic]

Лучшая команда НГУ

November 7th, 2011 (10:35 pm)
current song: Ария – Король дороги

Речь идёт о «Поттосинке». Скажу сразу же наш результат – седьмое место в общем зачёте и второе по Сибири – нас обошла команда ТГУ, занявшая четвёртое место, – примерно это я и имел в виду, когда говорил, что у них далеко не самый низкий уровень. Между прочим, в предыдущие два года лучшая команда Сибири оба раза была в общем зачёте восьмой. Наш регион поднимается? Это не может не радовать. А если кто-нибудь скажет, что мы облажались, что ж – «иди и сыграй лучше». Просто у Томска есть Миша Колупаев, который на данный момент явно сильнее меня. А у нас нет. Но это, как и все проблемы подобного рода, конечно же, поправимо.

Почему название поста выполнено в стиле Кэпа? О, это не моя идея. Раньше была такая славная традиция, что компания Parallels – один из спонсоров – вручает лучшей сибирской команде специальный приз. Но в прошлом году у «Пакетов» (2/3 которых ныне со мной) что-то пошло наперекосяк, и поэтому ВНЕЗАПНО получилось так, что этот приз должен был отойти чужим людям, – тогда-то наши тренеры и подкинули Parallels славную идею – вручить два приза: лучшей команде Сибири и лучшей команде Новосибирска. А в этот раз на лежащей сейчас у меня на тумбочке памятной доске с сертификатом на 60 к. р. почему-то красуется и вовсе скромная надпись: «Лучшей команде НГУ», – а приз томичам, уж не знаю какой, вручила компания APC.

Во втором, основном, туре, у нас всё шло более или менее стандартно. Разве что был такой интересный момент: раньше писать поиск наименьшего контролирующего множества в двудольном графе за O(VE) мне не доводилось никогда, даже на тренировках. Однако я каким-то чудом сумел во время контеста адекватно восстановить в памяти некогда виденную краем уха презентацию этого алгоритма. Ну а под конец мы не сдали свою седьмую задачу (и оказались на 14 строчке вместо 9) из-за того, что наш теоретик проявил фееричный идиотизм, сумев представить двумерную вообще-то геометрию как трёхмерную, а наш капитан проявил не менее фееричный идиотизм, сумев ему поверить. Мы продемонстрировали настоящий командный дух! И это не настолько шутка, как может показаться: когда команда впустую теряет полчаса времени из-за ошибки одного человека – это демонстрация справедливо наказуемого непрофессионализма в организации teamwork’а, а вот когда только из-за одновременной ошибки двоих – это прокол уже всё-таки не в земном менеджменте.

А вот не первом туре всё было куда веселее. Задача в этот раз там была не игровая, а скорее марафонская. Мы долго пытались придумать хоть сколько-нибудь приличный алгоритм, но ничего не получалось. В середине тура я, чтобы проверить хотя бы интерфейс программы, взял да и отослал тупейшее решение, генерировавшее ответ чуть лучше чем случайно, – и оно набрало 11 баллов, поместив нас в середину таблицы. Из этого факта стало ясно, что большинство команд находится сейчас примерно в том же положении, что и мы. А после этого мы догадались глянуть в топ: у лидеров было порядка сотни баллов, что составляло около одного процента от теоретически возможного максимума. Но ведь тогда… тогда, чтобы подняться высоко, достаточно использовать хотя бы какие-то, хотя бы чуть-чуть разумные эвристики! Следующая пара часов ушла у меня на то, чтобы написать самый простой алгоритм, сколько-нибудь претендующий на разумность. Результат – 18 баллов. Исправить в коде баги, ужасаясь, как это вообще смогло оказаться лучше рандома, – и получить около той самой сотни баллов и место в топе. Наконец, в последние полчаса упорото подкручивать разные от фонаря выбранные константы, добиваясь наилучшего результата, – 270 баллов и второе место (а до последних правок решения команды МГУ долго было даже и первое). Но во время тура, конечно, проводилось только предварительное тестирование. Окончательное же тестирование показало, что мы таки действительно на втором месте. Отставание от первого – двукратное. Отрыв от третьего – трёхкратный, от четвёртого – шестикратный, от пятого – одиннадцатикратный. Неслабо, верно? Я в очередной раз, как и в предыдущие два года, подумал, что, скажем, в TopCoder Marathon мог бы показывать результаты намного лучше, чем в TopCoder Algorithm. Видимо, у меня к формату соревнования, когда надо за пять часов решить не шесть-десять средней сложности задач полностью, а один нереальный гроб – частично, какой-то, как это ни прозвучит банально, талант. Но – нет и ещё раз нет. Я тренируюсь для ACM.

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

Comments

Posted by: Anton Dubovik (Anton Dubovik)
Posted at: November 8th, 2011 01:34 pm (UTC)
Первая номинация

Какой у вас алгоритм в большой задаче?
По рейтингу четко видно, что только top-4 команд сдали что-то небессмысленное, остальные соревновались в параолимпиаде на лучший рандом.
Мы тоже поздно сообразили (за 40 минут до конца), что если решить задачу чуть лучше, чем рандом то будет уже очень хорошо. А до этого пытались написать хорошее решение с перебором направления взгляда со звезды и сопоставлением видимой картинки с данным созведием. Но так и не смогли поднять этого монстра. Я уверен, что у большинства команд ровно та же история - попытка поставить на ноги сложное достаточно точное решение с закономерной неудачей.
Такой тип задачи был действительно неожиданен. Следовало бы как-нибудь намекнуть участникам, мол, попытайтесь сначала крайне тупое плохо работающее решение, а затем улучшайте. Хотя мне до сих пор не очень ясно, как улучшать рандомное решение, не привлекая достаточно сложную геометрию. Собственно, поэтому я и задаю вопрос в первом предложении.

Posted by: Ferlon (ferlon)
Posted at: November 8th, 2011 02:07 pm (UTC)
Re: Первая номинация

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

Алгоритм такой. Предвычислим все возможные созвездия, которые могут быть видны из каждой звезды со светимостью не более 4. Потом на каждый запрос будем давать ответ, пробегаясь по всем этим созвездиям и набирая в три варианта ответа все те, где хоть одно видимое созвездие совпало, а если там трёх не набралось - добрать рандомом.
Как вычислять созвездия, видимые с конкретной звезды? Возьмём несколько (у нас - 100) звёзд с максимальной видимой яркостью и будем собирать из них. Собирать так: берём какую-то одну, потом идём по списку, каждый раз добавляя, если соблюдается условие на отношение видимых яркостей и на максимальное расстояние от изначально выбранной звезды (у нас - 15° по сфере). Потом смотрим, сколько же в этом кандидате на созвездие получилось штук звёзд: если больше 10 или меньше 4 - выкидываем. Потом из этого набора конструируем собственно видимое созвездие, то есть проецируем на плоскость как надо.
Как сравнивать на совпадение два созвездия, когда они представлены уже в форме двумерной проекции? Прежде всего, в них должно быть одинаковое количество звёзд. Дальше, конечно, в каждой картинке отсортировать звёзды по азимуту относительно геометрического центра созвездия. И потом пробовать, что если взять, что вот эта звезда из одного созвездия - это вот эта из другого (в этом месте вычислить коэффициент масштабирования), то совпадают ли все остальные звёзды по расстоянию от центра и по углу между ними (наши эпсилон-константы: для расстояния - кажется, 5 условных попугаев, для угла, кажется, 0,5 радиана - да, вот такая дикость).

Ну, вот как-то так. Не "A+B", конечно, но и не что-то сверхсложное. Но, с другой стороны, тут ведь надо было ещё догадаться, что такие эвристики будут достаточно хороши.

Posted by: Pavel Khaustov (Pavel Khaustov)
Posted at: November 16th, 2011 12:06 pm (UTC)
ВСО 2011 сенсационно уступила четвертьфиналу 2011

ВНЕЗАПНО! Я почитал твой блог. Кирилл, а "наши тренеры и подкинули Parallels славную идею – вручить два приза: лучшей команде Сибири и лучшей команде Новосибирска" - это художественный вымысел (который сходится с предположениями ВСЕХ сибирских команд) или это стопроцентный факт?
Я, конечно, давно заметил, что ВСО - способ ваших организаторов отмыть деньги для первой команды НГУ, но почему бы не выбить этих денег без всякой олимпиады.
ТГУ подарили только фотоаппараты за 4 тысячи. Неправда ли справедливо? Ну, по правде говоря, такой низости от НГУ я не ожидал. Вообще, вся олимпиада была проведена достаточно стремно. Интернет тур был ужасен - одна из задач вообще имела десятисмысленное условие. Первый тур - постный отстой. Меня больше всего выбесили слова автора задачи: "Да, я предполагал, что большинство команд отправят рандомные решения". Так на$ такую задачу давать тогда? Задачи вообще перестали модерировать? Второй тур был неплохим и можно даже сказать хорошим (несмотря на то, что мы его слили), но это капля меда в бочке дёгтя. Награждение всегда ужасно, потому что Лавреньтев то ли не умеет читать, то ли специально читает неправильно достаточно большую часть имен, фамилий, отчеств, названий команд, названий университетов. Год назад лучшей командой Сибири он назвал НГУ (желаемое за действительное?), а Исенбаева он перманентно называл Владимиром (и это трехкратного-то победителя). И ведь исправились только когда мы вышли на награждении (4 места мы сидели и гадали за что же нас перестали считать за сибирскую команду). В этом году с призами какая-то беда - спонсоры стали отворачиваться от олимпиады или еще какая-то команда НГУ получила сертификат? [долгожданный trollface]
У меня было желание ездить после завершении ACM-карьеры на ВСО в команде друзей, но теперь оно "куда-то" делось.
До полуфинала уже полторы недели. А между тем прошлогодние "Лучшая команда Сибири на ВСО" и "Победитель четвертьфинала" слили полуфинал год назад. Свято верю в то, что эти традиции связаны с титулами, а не ВУЗами :)

Posted by: Ferlon (ferlon)
Posted at: November 17th, 2011 01:00 am (UTC)
Re: ВСО 2011 сенсационно уступила четвертьфиналу 2011

О, вот и Паша Икс наконец-то нарисовался. Рад тебя здесь видеть, а то без регулярных сочных выбросов НЕНАВИСТИ мой блог становится каким-то неприятно сухим. Заходи почаще!

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

Ты можешь поискать мои отчёты о ВСО предыдущих лет и понять, что я тоже от организации далеко не в восторге. В частности, два года назад на вопрос: "Каковы ваши впечатления от олимпиады?.." - я честно ответил: "Говном всегда было, говном и остаётся". Но всё-таки, если судить только по качеству проведения ACM-туров (а это ведь самое главное), в последние годы наблюдается тренд к улучшению. Если тебя сейчас так возмущает, что "одна из задач имела десятисмысленное условие", то ты явно не в курсе, что было года четыре-пять назад. Там был полный, я не побоюсь этого слова, пиздец, обретавший ещё большую тотальность из-за пафоса организаторов. Одно дело, когда контест проводится плохо, но всем плевать, потому что этот контест - чистая формальность, и совсем другое - когда за несправедливо занятые места команды получают хорошие призы, а спонсоры и журналисты, похоже, считают, что ВСО - это чуть ли не чемпионат России.

Я не припомню, чтобы к нам в последние годы приезжал, например, Саратов. И полностью их в этом поддерживаю.

4 Read Comments