Как известно, на топкодере довольно часто проводятся алгоритмические соревнования высокого уровня, называемые SRM-ами (Single Round Match). Каждый SRM, или попросту матч, длится примерно два часа. Первые 75 минут (называемые Coding Phase) участники занимаются непосредственно решением предложенных задач, затем идёт пятиминутный перерыв (Intermission), затем в течение пятнадцати минут (Challenge Phase) у соревнующихся есть возможность посмотреть на решения, присланные своими противниками, и попытаться их "зачеленджить", т.е. придумать такие данные, для которых решение не будет работать правильно. Потом некоторое время люди ждут окончательных результатов, болтают о том - о сём, сетуют на всё повышающееся количество китайских участников, и расходятся.
Учитывая, что уровень участников очень неоднородный, каждый матч проводится в двух дивизионах. Люди, имеющие более высокий рейтинг, соревнуются в первом, более низкий - соответственно, во втором дивизионе. Главное отличие между дивизионами - это предложенные задачи. В обоих дивизионах их по три. В рамках одного дивизиона задачи делятся на лёгкую, среднюю и сложную. Тем не менее, задачи первого дивизиона на порядок сложнее задач второго (лёгкая задача в первом дивизионе часто используется как средняя для второго). Так или иначе, для проведения матча всегда нужно от 4 до 6 более-менее оригинальных задач разного уровня сложности.
Упомянутое в первом абзаце "довольно часто" в конце 2008 года равнялось примерно четырём матчам в месяц. Человеку, хорошо знакомому со спецификой олимпиадных задач, должно быть понятно, что один и тот же человек или группа людей не в состоянии каждую неделю выдавать оригинальный комплект интересных задач. Так вот топкодер этого и не делает - он даёт возможность самим участникам предлагать свои задачи в обмен на некоторое денежное вознаграждение. То есть любой пользователь, достигший 18 лет, имеющий определённый рейтинг и количество проведённых матчей, может придумать свои задачи и, если они достаточно интересные, он получает шанс стать автором матча.
Провести свой собственный матч уже давно было моим заветным желанием, и ещё осенью у меня были готовы задачи, так что я терпеливо ждал своего шанса. И он появился примерно в то же время, когда мне предложили поработать на сборах. То есть в то время за мной закрепили SRM 433, дата которого была 21 января.
Процесс получения SRMа выглядит примерно так. Сначала человек делает наброски своих задач в специальном приложении MPSQAS, иначе говоря пишет условия, и необязательно оконченные. Потом надо написать администратору, ответственному за выбор задач, с просьбой посмотреть на плоды своих мучений. Рано или поздно ему приходится взглянуть на задачи, и тогда по каждой он или задаёт дополнительные вопросы, потому что наброски часто слишком далеки от совершенства, или сразу отклоняет, чаще всего потому, что она слишком неоригинальная и уже была на топкодере пару десятков раз, или утверждает её. Имея утвержденные задачи всех уровней для обоих дивизионов (в принципе, пару лёгких могут и простить для начала), можно смело просить SRM. Я не уверен, чем админы руководствуются, отдавая тот или иной матч в чьи-то руки, но могу сказать, что лично меня до сих пор не обижали.
Получив SRM, надо доводить его до ума. То есть если не хватало какой-либо задачи, надо её придумать, все условия надо максимально отточить, надо написать авторские решения - причём обязательно на Java, и на всех возможных тестах решение не должно работать больше 1 секунды, и надо добросовестно составить эти самые тесты. Потом за дело берутся люди, на которых возлежит ответственность за то, чтобы всё было максимально точно, правильно и понятно. По моему опыту, таких бывает трое: администратор, ответственный за выбор задач, тестер и PabloGilberto, который занимается исключительно английским языком. Выбор тестера происходит сразу после утверждения матча.
На моём первом SRMе координатором по задачам был OlexiyO, а тестером выступал Иван Метельский. Особо много нам мучаться не пришлось (разве лишь что меня заставили рисовать дополнительные картинки в div1 Medium), и день матча подошел довольно быстро. Перед матчем автору дают специально сгенерированный пароль от ника writer, который обладает разными прикольными функциями. Этот ник в арене обладает администраторскими привилегиями, и позволяет читать все чаты в арене, в том числе шепот. Хотя часто это становится просто проклятием, потому что чата чрезвычайно много. Также во время Coding Phase можно видеть коды любых участников. Вообщем, во время матча не соскучишься.
Что касается моих задач, бегло пройдусь по основным идеям:
Div2 Easy - RoyalTreasurer. Довольно стандартная задача - очевидно, что минимальная сумма достигается, когда наибольшие элементы первого массива сгруппированы с наименьшими элементами второго.
Div2 Medium / Div1 Easy - MagicWords. Несмотря на низкие ограничения, просто перебрать все возможные перестановки слов и проверить каждую тривиальным алгоритмом не получалось, или по крайней мере не должно было получаться. Есть множество методов, с помощью которых можно ускорить эту проверку: хеширование, KMP, технические оптимизации. Авторский вариант основывался на следующем наблюдении: если строка длины L повторяется в своих shift-ах ровно K раз, то она является периодической с периодом, равным L/K - и наоборот. Таким образом, надо было проверять периодичность строки для периодов, равных делителям L.
Ещё одно решение, которое я сначала не заметил, но потом мне очень понравилось, основывалось на том, что сместив последнее слово в нашей перестановке в начало, мы получаем строку с таким же множестов shift-ов. Таким образом, можно было перебирать все перестановки первых (N-1) строк, а последнюю всегда ставить в конец - тогда итоговый ответ получается при умножении полученного количества магических строк на N.
Div2 Hard - MakingPotions. Идеей решение похоже на алгоритм Дейкстры - на каждом шагу помечать полученным то снадобье, которое ещё не получено и имеет наименьшую цену. Если таким образом мы дойдём до LOVE, то получим его за наименьшую возможную цену, если нет - оно не достаётся. Проблемы могли возникнуть при парсировке входных данных, или с теми ситуациями, когда цены становились слишком большими.
Div1 Medium - SettingTents. Задача, которую решили, к моему удивлению, меньше ста человек, что для Medium в принципе маловато. На самом деле в ней проходил даже алгоритм сложности O(N^5), т.е. перебрать обе координаты обеих вершин диагонали ромба, а затем пройти одним циклом по длине второй диагонали и проверить, попадают ли её концы в целочисленные точки. От этого цикла можно было избавиться несложными математическими вычислениями. Во время матча большей частью были имплементированы более быстрые алгоритмы. Недавно я натолкнулся на довольно старый пост в блоге Petr-а, в котором были рассмотрены методы решения подобной задачи - советую посмотреть.
Div1 Hard - BarbarianInvasion. "Праздник потока", как её потом обозвали. Действительно, задача требовала нахождение минимального вершинного разреза, только при условии, что в первую очередь должно быть минимизировано количество вырезанных вершин, а потом их суммарная стоимость. В таком случае применяют следующий фокус: весом вершины делаем её стоимость + некую большую константу X, которая заведомо больше любой возможной суммарной стоимости вырезанных вершин при данных в задаче ограничениях. Тогда, найдя величину минимального разреза ANS между столицей и граничными клетками, мы будем иметь минимальное количество вырезанных вершин как ANS/X и минимальную стоимость этих вершин (при условии минимизации их количества) как ANS%X.
Можете также посмотреть editorial этого матча и его результаты.
Thursday, July 9, 2009
Wednesday, July 8, 2009
Сборы кандидатов в Бакуриани
После полуфинала я решил расслабиться и позволял себе выступать только на топкодере. В принципе, смотря сейчас на мои тогдашние результаты, лучше б и не позволял :)
Не помню, до каких пор я планировал отдыхать, но в последних числах декабря я получил звонок от Deputy Leader'а грузинской сборной школьников по информатике, Гочи Мандария. В начале января планировалось проведение зимних сборов для кандидатов в сборную, и мне предложили позаниматься с детьми несколько дней. Это был первый раз, когда ко мне обратились с предложением подобного рода, а поработать с ребятами мне давно хотелось, поэтому я согласился без лишних раздумий, несмотря на довольно ограниченное время, остававшееся до начала сборов. Таким образом, предновогодние дни я провёл, с большим воодушевлением готовя материал для лекций и соответствующие ему задачи.
Сборы проводились в Бакуриани, на базе тамошней школы №1 (не хочу соврать, но вроде она там и единственная). Компьютерный класс там такой, какому позавидует по крайней мере большинство тбилисских школ, плюс к тому школа оснащена солнечными аккумуляторами и электричество работает без сбоев. А снаружи в это время стояла очаровательная зимняя погода.
В моём распоряжении было 5 дней, один из которых попадал на Рождество, и поэтому заниматься в него никто и не думал. Зато остальные четыре дня я собирался мучать детей по полной. Первые три дня я собирался проводить лекцию, а затем 3часовый контест по школьным правилам, состоявший из 3 задач на тематику объясненного материала. На последний день у меня был припрятан 5часовый контест из 5 задач на все темы вперемешку.
В итоге всё шло примерно по плану. У нас царила здоровая, весёлая атмосфера, которая не мешала ребятам концентрироваться на контестах.
Темы первых дней у меня были следующие: бинарный и тернарный поиск в первый день, битмаски во второй, а на третий ко мне присоединился Леква, и общими усилиями были разобраны деревья отрезков и поиск в ширину на графе с ребрами длины 0 и 1. Задачи, которые я составил для тех сборов, потом появились на различных контестах, к созданию которых я приложил руку - в том числе на туре, проведённом нашей командой на сборах в Харькове, и моём мини-контесте на armcoderе.
А между вторым и третьим днём был вышеупомянутый выходной, и мы вдоволь накатались на лыжах.
Также имела место эпохальная битва в джокер, в которой Ника Габисония и Гоча Мандария были повержены, за что одному пришлось лепить снеговика, а второму его украшать.
Ну а в мой последний день и мне, и Лекве пора была уматывать домой, а нас должны были сменить другие специалисты. Поэтому мы оставили ребятам задачи на 5 часов и сели в маршрутку. С утра погода не предвещала ничего зловещего, но по дороге к Тбилиси собрались тучи, поднялся страшный ветер, пошёл град, и мы были благодарны судьбе, когда наконец доехали. Как потом оказалось, в Бакуриани вообще была буря, так что не поспеши мы тогда, могли застрять надолго. Зато мы пропустили невероятное сражение в снежки, которое разразилось на следующий день в рядах нашей делегации и в результате которой кое-кого накормили большой кучей снега. Что поделать, каждому своё...
[aq unda iyos TovliT naWami varamas suraTi. visac mogepovebaT, dadeT :D]
Не помню, до каких пор я планировал отдыхать, но в последних числах декабря я получил звонок от Deputy Leader'а грузинской сборной школьников по информатике, Гочи Мандария. В начале января планировалось проведение зимних сборов для кандидатов в сборную, и мне предложили позаниматься с детьми несколько дней. Это был первый раз, когда ко мне обратились с предложением подобного рода, а поработать с ребятами мне давно хотелось, поэтому я согласился без лишних раздумий, несмотря на довольно ограниченное время, остававшееся до начала сборов. Таким образом, предновогодние дни я провёл, с большим воодушевлением готовя материал для лекций и соответствующие ему задачи.
Сборы проводились в Бакуриани, на базе тамошней школы №1 (не хочу соврать, но вроде она там и единственная). Компьютерный класс там такой, какому позавидует по крайней мере большинство тбилисских школ, плюс к тому школа оснащена солнечными аккумуляторами и электричество работает без сбоев. А снаружи в это время стояла очаровательная зимняя погода.
В моём распоряжении было 5 дней, один из которых попадал на Рождество, и поэтому заниматься в него никто и не думал. Зато остальные четыре дня я собирался мучать детей по полной. Первые три дня я собирался проводить лекцию, а затем 3часовый контест по школьным правилам, состоявший из 3 задач на тематику объясненного материала. На последний день у меня был припрятан 5часовый контест из 5 задач на все темы вперемешку.
В итоге всё шло примерно по плану. У нас царила здоровая, весёлая атмосфера, которая не мешала ребятам концентрироваться на контестах.
Темы первых дней у меня были следующие: бинарный и тернарный поиск в первый день, битмаски во второй, а на третий ко мне присоединился Леква, и общими усилиями были разобраны деревья отрезков и поиск в ширину на графе с ребрами длины 0 и 1. Задачи, которые я составил для тех сборов, потом появились на различных контестах, к созданию которых я приложил руку - в том числе на туре, проведённом нашей командой на сборах в Харькове, и моём мини-контесте на armcoderе.
А между вторым и третьим днём был вышеупомянутый выходной, и мы вдоволь накатались на лыжах.
Также имела место эпохальная битва в джокер, в которой Ника Габисония и Гоча Мандария были повержены, за что одному пришлось лепить снеговика, а второму его украшать.
Ну а в мой последний день и мне, и Лекве пора была уматывать домой, а нас должны были сменить другие специалисты. Поэтому мы оставили ребятам задачи на 5 часов и сели в маршрутку. С утра погода не предвещала ничего зловещего, но по дороге к Тбилиси собрались тучи, поднялся страшный ветер, пошёл град, и мы были благодарны судьбе, когда наконец доехали. Как потом оказалось, в Бакуриани вообще была буря, так что не поспеши мы тогда, могли застрять надолго. Зато мы пропустили невероятное сражение в снежки, которое разразилось на следующий день в рядах нашей делегации и в результате которой кое-кого накормили большой кучей снега. Что поделать, каждому своё...
[aq unda iyos TovliT naWami varamas suraTi. visac mogepovebaT, dadeT :D]
Friday, May 22, 2009
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-ого числа состоялся банкет, на котором, несмотря на некоторую напряженность, в итоге было очень весело.
Команды из Киева и Сум (Сумы, Сумов, не знаю как правильно склонять) приехали в Тбилиси 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-ого числа состоялся банкет, на котором, несмотря на некоторую напряженность, в итоге было очень весело.
Monday, May 18, 2009
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], но во второй день они были выше, а приоритет отдавался именно ему. Окончательная таблица выглядит так.
Так вот, в 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 командам.
Леква во время четвертьфинала был в Кутаиси, поэтому писали только Ника и я. Задачи, как и в прошлом году, представляли собой упрощенный вариант задач Северного четвертьфинального региона. Первые 50 минут у компа сидел я, а Ника читал задачи и говорил мне алгоритмы. Пустив так 6 задач, я уступил ему место и из оставшихся 5 задач 4 написал уже он. В итоге мы закончили за 126 минут и вскоре покинули место действия, окончательные результаты увидев уже дома. В полуфинал были допущены все команды, решившие хоть что-либо, за исключением Tbilisi SU 5 и 6, потому что квота на количество команд от одного университета для полуфинала в Батуми равна 4 командам.
Спустя несколько месяцев...
После довольно длительного молчания я снова переборол свою чрезвычайную лень и решился написать. С октября событий накопилось достаточно, и я попытаюсь пробежаться по медленно, но уверенно блекнущим в памяти впечатлениям и пересказать как можно больше.
Wednesday, October 15, 2008
Google Code Jam 2008 Semifinal - Zurich
Этот пост будет посвящен полуфиналу Google Code Jam 2008 в регионе EMEA (Europe, Middle East and Africa), вернее, моей поездке в Цюрих на этот onsite и оставшимся впечатлениям.
Для начала немного о предистории этого события, которой на этом блоге не имеется (по крайней мере пока), так как я пишу свой первый пост :D
Google Code Jam - ежегодное соревнование по спортивному программированию, которое проводится всемирно известной компанией Google. До 2007 года оно проводилось по формату и на сервере Topcoder, в 2007 году его не было вообще, а в 2008 его решили провести по совершенно изменённым правилам. Сейчас я не буду в них углубляться, а скажу лишь, что первые 4 раунда проводились онлайн, т.е. по интернету, и в результате последнего из них было избрано 500 человек, которые прошли в онсайт-раунд. Более двухсот из них были из региона EMEA и были распределены по Европейским офисам компании Google - из них наибольшее количество, 93, в Цюрихском офисе - в том числе я и Ника. К сожалению, остальные участники из Грузии не попали в этот этап соревнования, при чём большей частью из-за неспортивных препятствий...
Швейцарскую визу мы получили без особых проблем, и в ночь с 4ого на 5ое октября, совершив пересадку в Стамбуле, долетели до Цюрихского аэропорта.
Первым открытием для меня стала транспортная система Швейцарии. Общественным транспортом являются поезда (которые разъезжают как по туннелям, так и над землей), трамваи и водный транспорт (хотя на последнем мне покататься так и не удалось). Никаких автобусов или троллейбусов - соблюдают экологическую чистоту. Билеты на весь общественный транспорт одни и те же, то есть купив билет можно как сесть на поезд, так и на трамвай. В принципе, сесть-то можно и без билета. Никто не ограничивает доступ в транспорт - билеты проверяют внутри, да и то редко. Зато если попадешься без него, штраф 80 швейцарских франков.
Автомобили по улицам, естественно, ездят, хотя не в таких количествах, как хотя бы у нас в Тбилиси. Тем не менее, каким-то образом все умудряются обходиться без сигналов и шума. Даже в центре города было необычайно тихо.
Другими популярными видами транспорта являются мотоциклы и велосипеды. На велосипеде там, похоже, передвигается каждый третий или даже второй. В городе есть множество этаких гаражей, где можно за 25 франков взять велосипед до конца дня. При этом возвращая велосипед, человек получает свои деньги обратно.
***
В Цюрихе аэропорт находится не где-нибудь за чертой города, а довольно близко к центру, так что поездка в отель не заняла у нас много времени. Не знаю, насколько хорош отель Four Points by Sheraton Sihlcity по тамошним меркам, но я в таком ещё не жил :D
Первый день в Цюрихе я провёл в сладостной дремоте. Проснувшись лишь к шести часам вечера, я услышал жалобные стоны своего желудка и решил найти место, где можно было перекусить. Как оказалось, в воскресенье, да ещё и вечером, это было не так-то легко. Мы с Никой обошли за полтора часа окрестности отеля, нашли лишь один открытый бургер-бан, а потом обнаружили McDonalds и перекусили там. Особо интересного в тот день больше ничего не происходило, разве лишь что мы встретили нескольких других участников, в том числе ребят из Саратова.
Утром второго дня работники Google встречали нас в вестибюле отеля, чтобы отвести в местный офис.
После довольно затянувшейся регистрации мы заняли рабочие места по принципу "в тесноте, да не в обиде": каждому участнику была отведена полоска на столе шириной до 1 метра, где были расположены ноутбуки, external keyboard & mouse и где мы также должны были калякать свои мысли во время соревнования. Старт откладывался несколько раз, чтобы обеспечить сихронизированное начало контеста во всех офисах одновременно, но в итоге двухчасовая борьба наконец началась.
Не буду особо останавливаться на результатах, скажу лишь, что и я, и Ника выступили намного ниже своих возможностей и путевки в финал не заработали. Ну свои-то перспективы я, вообщем-то, и так довольно низко оценивал.
Сама итоговая таблица лежит здесь (надеюсь, ссылка не изменится).
После соревнования нам предложили перекусить (еда в Google потрясающая), а потом устроили office tours. К сожалению, фотографировать там было запрещено, но большинство того, что мы там видели, определённо лежит на youtube :)
Затем у нас был час, который каждый участник мог заполнить одной из презентаций или провести в комнате развлечений. Как и многие codejam'овцы, я избрал последнюю возможность, так что мы вдоволь наигрались в Air Hockey. Правда, шайба не клеилась к столу и часто летала по комнате, создавая угрозу здоровью участников.Для начала немного о предистории этого события, которой на этом блоге не имеется (по крайней мере пока), так как я пишу свой первый пост :D
Google Code Jam - ежегодное соревнование по спортивному программированию, которое проводится всемирно известной компанией Google. До 2007 года оно проводилось по формату и на сервере Topcoder, в 2007 году его не было вообще, а в 2008 его решили провести по совершенно изменённым правилам. Сейчас я не буду в них углубляться, а скажу лишь, что первые 4 раунда проводились онлайн, т.е. по интернету, и в результате последнего из них было избрано 500 человек, которые прошли в онсайт-раунд. Более двухсот из них были из региона EMEA и были распределены по Европейским офисам компании Google - из них наибольшее количество, 93, в Цюрихском офисе - в том числе я и Ника. К сожалению, остальные участники из Грузии не попали в этот этап соревнования, при чём большей частью из-за неспортивных препятствий...
Швейцарскую визу мы получили без особых проблем, и в ночь с 4ого на 5ое октября, совершив пересадку в Стамбуле, долетели до Цюрихского аэропорта.
Первым открытием для меня стала транспортная система Швейцарии. Общественным транспортом являются поезда (которые разъезжают как по туннелям, так и над землей), трамваи и водный транспорт (хотя на последнем мне покататься так и не удалось). Никаких автобусов или троллейбусов - соблюдают экологическую чистоту. Билеты на весь общественный транспорт одни и те же, то есть купив билет можно как сесть на поезд, так и на трамвай. В принципе, сесть-то можно и без билета. Никто не ограничивает доступ в транспорт - билеты проверяют внутри, да и то редко. Зато если попадешься без него, штраф 80 швейцарских франков.
Автомобили по улицам, естественно, ездят, хотя не в таких количествах, как хотя бы у нас в Тбилиси. Тем не менее, каким-то образом все умудряются обходиться без сигналов и шума. Даже в центре города было необычайно тихо.
Другими популярными видами транспорта являются мотоциклы и велосипеды. На велосипеде там, похоже, передвигается каждый третий или даже второй. В городе есть множество этаких гаражей, где можно за 25 франков взять велосипед до конца дня. При этом возвращая велосипед, человек получает свои деньги обратно.
***
В Цюрихе аэропорт находится не где-нибудь за чертой города, а довольно близко к центру, так что поездка в отель не заняла у нас много времени. Не знаю, насколько хорош отель Four Points by Sheraton Sihlcity по тамошним меркам, но я в таком ещё не жил :D
Первый день в Цюрихе я провёл в сладостной дремоте. Проснувшись лишь к шести часам вечера, я услышал жалобные стоны своего желудка и решил найти место, где можно было перекусить. Как оказалось, в воскресенье, да ещё и вечером, это было не так-то легко. Мы с Никой обошли за полтора часа окрестности отеля, нашли лишь один открытый бургер-бан, а потом обнаружили McDonalds и перекусили там. Особо интересного в тот день больше ничего не происходило, разве лишь что мы встретили нескольких других участников, в том числе ребят из Саратова.
Утром второго дня работники Google встречали нас в вестибюле отеля, чтобы отвести в местный офис.
После довольно затянувшейся регистрации мы заняли рабочие места по принципу "в тесноте, да не в обиде": каждому участнику была отведена полоска на столе шириной до 1 метра, где были расположены ноутбуки, external keyboard & mouse и где мы также должны были калякать свои мысли во время соревнования. Старт откладывался несколько раз, чтобы обеспечить сихронизированное начало контеста во всех офисах одновременно, но в итоге двухчасовая борьба наконец началась.
Не буду особо останавливаться на результатах, скажу лишь, что и я, и Ника выступили намного ниже своих возможностей и путевки в финал не заработали. Ну свои-то перспективы я, вообщем-то, и так довольно низко оценивал.
Сама итоговая таблица лежит здесь (надеюсь, ссылка не изменится).
После соревнования нам предложили перекусить (еда в Google потрясающая), а потом устроили office tours. К сожалению, фотографировать там было запрещено, но большинство того, что мы там видели, определённо лежит на youtube :)
Третий день нашего пребывания в Цюрихе был предназначен для собеседования. Моё было назначено на середину дня, поэтому с утра я, Василь и GeKa занялись туризмом в центре города.
Не знаю, как обстоит дело в других крупных компаниях, но собеседование в Google произвело на меня впечатление. В течение почти четырех часов четыре разных человека беседовали со мной о структурах баз данных, алгоритмах, моем опыте работы и т.д., и при этом я получал от этого большое удовольствие. Результаты обещали сообщить в течение двух недель, но вот на дворе уже декабрь, а ответа пока ни я, ни Ника, ни украинцы, приезжавшие сейчас на Чепмионат Южного Кавказа, не получили. Наверное, кризис :)
А нас следующий день мы умотали домой. Ах да, только сейчас вспомнил о печение в отеле - "Speckli". Его приносили после каждой уборки в комнате. Как выразился Вася, оно бессмертное - сколько ни ешь, возвращается снова :D
Subscribe to:
Posts (Atom)