Как мы делали олимпиаду по SQL (окончание)

Продолжаю рассказ о том, как мы делали олимпиаду по SQL. Это продолжение предыдущей статьи, в которую всё просто не уместилось.

Краткое содержание предыдущей серии: прошло два заочных тура олимпиады в декабре 2016 и марте 2017 соответственно, где претенденты на победу прошли жёсткий отбор как с теорией, так и с практикой применения SQL в базах данных Oracle. Далее про третий тур — очный финал олимпиады в Сочи в начале июня 2017 г.

Дисклаймер. На всякий случай повторюсь в чём была моя роль, а то после первой части статьи она оказалась некоторым не столь очевидна. Я сам не являюсь организатором этой олимпиады: анонсы и реклама мероприятия, поиск спонсоров, работа с вузами, организация событий в офлайне — всё это делали другие люди. Наша компания была спонсором и готовила несколько конкурсов на олимпиаде, а лично я готовил техническую (и только техническую!) часть конкурса по SQL. То есть готовил правила проведения этапов, готовил и проверял задачи. Казалось бы не так много, но зато это самое-самое, ради чего собственно и делается всё остальное. Так что излишне скромничать тоже не буду.

Третий тур, он же очный финал, Сочи июнь 2017

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

Чтобы было понятно, о чём вообще тут идёт речь, вот отчёт о финале нашей олимпиады 2016/17 на официальном сайте.

Ссылка на фотоальбом с сайта олимпиады, а то найти его там как-то неочевидно.

Но обо всём по порядку. Сперва про подготовку.

Подготовка заданий

Повторюсь, что изначальная раскладка по турам была такой: первый тур — жёсткий тест-фильтр по теории, второй — практика магического решения задач, третий — блиц. Так как в очном режиме участникам предстоит решать задачи в реальном и весьма ограниченном времени, то это как ни крути будет блиц. А блиц — это конечно не самый лучший способ определять лучшего программиста. И "не лучший" — это ещё мягко сказано. Но ничего более справедливого придумать не удалось.

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

Время поджимало и остановились на такой схеме. Все задачи лежат в базе зашифрованными. Решение каждой задачи позволяет расшифровать следующую задачу и так далее по цепочке. Дальше всё просто: кто дальше всех продвинется, тот и победил. Если двое продвинулись одинаково далеко по задачам, то выиграл тот, кто был первым. Расшифровку задач сделали хранимой функцией, которая заодно логгировала обращение к ней. Это позволило следить за ситуацией в реальном масштабе времени. Также функцию расшифровки специально сделали вычислимо сложной, чтобы один её запуск работал пару секунд. Это чтобы исключить возможность решать задачи перебором. Мы также позаботились о том, чтобы в подготовленных данных этих самых вариантов перебора, если что, было более чем достаточно.

Такая схема проведения финала имеет ряд неоспоримых достоинств. Во-первых, за результатами можно следить в реальном времени. Во-вторых, все участники находятся в абсолютно равных условиях, нет никаких поводов для апелляций. Основной же недостаток следует ровно из этих самых достоинств — если вдруг мозг "заклинило" и решение застопорилось, то дальше не пройти. Для блица это конечно не совсем здорово, потому что раздражает, а столкнутся с этим в том или ином виде предстоит всем участникам. Не могу себе даже представить такого человека, который бы на подобных задачах ни разу "не застрял".

Но очень хотелось попробовать именно такой формат. Альтернатива понятна: задачи, баллы за каждую, автоматизированная проверка результатов — кто больше баллов набрал, тот победил. Не нравится в таком подходе тоже понятно что — балансировка весов задач (баллов) в финальном результате. Очень легко промахнуться и результаты внезапно могут оказаться несправедливыми. А возможности отладить эти веса нет, финал один единственный. Если ещё раз доведётся проводить олимпиады, буду ещё думать, как лучше. Теперь уже с имеющимся опытом.

Так, с подходом определились, нужно готовить задачи. Опять же задачи хотелось иметь, как бы это выразить словами, неолимпиадные. То есть для их решения не должно требоваться специальных знаний по теории чисел, специальных алгоритмов или ещё чего такого подобного. Хотелось, чтобы для решения каждой задачи нужно было осознать условие, представить себе декларативный способ выражения решения и реализацию без особых заморочек. Ну, чтобы похоже на задачи второго тура, только попроще. На второй тур целевое время решения задачи было день, а для третьего — полчаса. В результате задачи придумывать было довольно тяжело. Как раз из-за этого баланса, чтобы не слишком тяжело решалась, но и была при этом нетривиальной. Не забываем также про такую особенность, что в задачах нужно получить правильный результат, а способ решения может быть сколь угодно витиеватый, хоть с потолка ответ записать. Способ решения мы нигде не контролировали, только задачи так составили, что проще всего их решать было именно на SQL.

Чтобы не было скучно, в задачах походу мы ещё знакомили участников с интересными словарными объектами оракловой базы. Для тех, кто не знает, в современных базах есть словарь, в котором есть вся метаинформация по содержимому базы: какие в ней есть таблицы, с какими полями, какие есть процедуры-функции и масса другой полезной информации вплоть до того что и как прямо сейчас в базе происходит. По той же причине, чтобы повеселее было, тексты оформили в стиле Григория Остера.

Вот что получилось. Указание тем в конце каждой задачи не входило в условие, это наши рабочие пометки, тут они уместны.

Задачи финала

Имя                      Отдел    ...
------------------------ -------- ----
Иванов
    Анискин
    Никифоров
        Галкина
        Кирюхин
    Тарасов
Петров
    Бекасов
    Носова
Сидоров

Комментарии к задачам

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

То есть в первых шести задачах совершенно точно нет никаких подвохов, их способен решить каждый, кто пишет на SQL, хватило бы только времени. Да, некоторые дополнительные знания и навыки позволяют решить какие-то из этих задач быстрее. В бонусных задачах уже пошли извраты. В первой это изрядный объём творчески анализируемых данных, во второй это оптимизация. Причём сложность именно в том, что нужно догадаться, что тут нужна оптимизация, потому что решение "в лоб" не работает, так было специально подобрано. В дополнительной бонусной задаче нужна уже алгоритмическая оптимизация, потому что в ней уже не сработает тот же метод, что в предыдущей задаче.

Дальше мы, чтобы гарантировать, что точно никто за отведённое время не пройдёт до конца, поставили две истинно олимпиадных задачи, потому что они были придуманы и выкидывать их в корзину было жаль. И заглушка под номером 12 — это действительно поздравление для сверхчеловеков, если вдруг таковые найдутся. В это мы конечно не верили, но как математики в душе и программисты по профессии, мы должны были рассмотреть и такой случай.

Итого ожидалось, что участники решат максимум шесть задач и застрянут на 7-8-9. Или раньше. Самое страшное было бы, если бы вдруг все застряли на самой первой задаче. Им то (участникам) что — "три часа позора, потом как обычно", а мы бы судорожно метались по какому критерию определять победителей. Наверное надо было себя обезопасить и первым пунктом поставить задачу на какой-нибудь SELECT ROWID FROM DUAL, чтобы уж одну задачу точно решили. Впрочем, расчёты оказались верными, первую задачу и так все решили.

Расшифровка задачи делается следующим образом:

SELECT sql2017.decrypt('ответ-на-предыдущую-задачу', encrypted_text)
  FROM sql2017_tasks
 WHERE task_number = 2;

В процессе подготовки задач для служебных целей были написаны генератор таблиц, генераторы лабиринтов и корректных арифметических выражений (эти ко второму туру), генератор пакетов с кодом и требуемыми параметрами взаимных вызовов, простой генератор человеческих ФИО.

Кое-что как водится не успели. Например, я так и не смог придумать, как в выбранном формате дать задачу на quine.

Подготовка на местности, Сочи июнь 2017

Теперь из лабиринтов "чистого разума" вернёмся на бренную землю.

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

Сервер мы привезли свой, с заранее подготовленной базой. Места участников тоже привезли с собой (правда не сами, но наши коллеги). Было решено, что для создания одинаковых условий у всех будут одинаковые преднастроенные рабочие места. Лично я опасался возможных проблем с подключением всякого экзотического зоопарка, если разрешить участникам использовать свои компьютеры. Найдётся кто-нибудь криворукий и настырный — хлопот будет выше крыши. Так что привезли своих одинаковых ноутов. Поставили на них благоверные SQL*PLUS для фанатов (на самом деле SQLcl) и SQL Developer, как бесплатное средство разработки с GUI от производителя. Не припомню, чтобы кто-то из моих знакомых в реальной жизни активно пользовался SQL Developer, но зато все оказались в одинаковых условиях. Ну и не надо драматизировать, собрать нужный SQL запрос можно в чём угодно, хоть в Notepad-е, а выполнить вполне сгодится и SQL Developer.

Всё это хозяйство мы и притащили с собой в четверг в Олимпийский Университет на улице Орджоникидзе, где и происходила олимпиада. Тут случилась организационная засада. Нам для проведения финала по SQL выделили две маленьких комнатки. В одну мы бы никак не поместились по количеству. Местные сетевики как раз опутывали витой парой столы. Так как других возможностей разместиться не было, нам пришлось провести по сути два одновременных финала в соседних аудиториях. Единственное, что можно было сделать и что я поменял — это рассадку. Нам совсем не с руки было бы, если участники имели возможность видеть мониторы друг друга. Подглядывать специально вряд ли, но блуждающим взглядом наткнуться и не начать разглядывать написанное — это черезчур для человека, который зашёл в тупик при решении задачи. Поэтому я посетовал на уже произведённые старания сетевиков и решительно расставил столы по кругу. На фотографиях кое-где мелькают наши характерно расставленные кружком столы.

Провода, розетки, загрузка и проверка ноутов, настройка подключения к базе — ничего сложного, но долго, так как постоянно возникают всякие мелкие вопросы. То витая пара кончилась, то все дырки в хабе заняты и нужен ещё один, куда спрятать сервер, чтобы никто на него не наступил. Сеть получилась изолированная, соответственно нужно DHCP, чтобы раздать IP-адреса. Легче настроить один DHCP-сервер, чем постоянно бегать и вводить вручную адреса на любой чих изменений в конфигурации сети. Нужен шлюз в интернет для доступа к документации — настроили, заработало. Короче мелких хлопот хватило до самого позднего вечера.

А утром нас ждал...

Финал

Про официальное открытие я ничего не скажу, к нашей номинации по SQL это хоть и имеет некоторое отношение, но мы в этом никак не были задействованы. Скажу только, что народу на олимпиаду набралось много. На регистрации в холле было не протолкнуться. Хорошо, что мы зарегистрировались и получили пропуска накануне.

После тожественного открытия мы собрали в зале своих участников финала и, как пионервожатые, повели их в подготовленные для финала аудитории. Инструктаж, раздача логинов, проверка подключений к базе, объяснение правил проведения финала, проверка всеми расшифровки тестовой задачи на примере задачи №0. На месте первой задачи пока стоит заглушка. По логам расшифровщика заранее написаным запросом следим, кто ещё не смог правильно расшифровать тестовую задачку. О, оно работает!

Все готовы? Меняем первую задачу с заглушки на настоящую, обнуляем логи. Поехали!..

Мы следим за порядком и за ситуацией. За ситуаций следить удобно, делаем выборку из таблицы логов расшифровщика, сортируем по номеру решённой задачи и времени расшифровки — и лидеры у нас перед глазами (осторожно, "живой" код):

select l.oracle_user, name, task
     , (select min(sent_date)
          from sql2017_log l2
         where l.oracle_user=l2.oracle_user
           and l.task = task_number)+3/24 solve_time
     , tries
  from (select oracle_user
             , max(task_number) task
             , count(1) tries
          from sql2017_log
      group by oracle_user) l
     , sql2017_users u
 where u.oracle_user = l.oracle_user
order by task desc, solve_time asc

Вопросов нам задают немного. Всего несколько за всё время финала. Начали мы после торжественной части открытия и инструктажа в 12:15, закончили в 15:30. Время окончания в сущности было не слишком важно, главное было обозначить его заранее. Мы исходили из того что с 15 до 16 был обед. На полчаса задержать участников — это нормально, совсем не пустить на обед — жестоко.

Несколько фактов по ходу финала. Первая задача была решена уже через 4 (sic!) минуты после старта. У нас три раза за время финала менялся лидер, а тройка лидеров и вообще менялась очень динамично. Несколько человек запускали в фоне подбор решения брутфорсом, ни одному не удалось достичь в этом успеха (не зря мы на это закладывались). Один раз база так тормозила (не хватило памяти, сервер ушёл в своп), что мы боялись, что придётся её перезапускать, но постепенно ситуация выровнялась. Лидеры смогли решить все шесть штатных задач и застряли на седьмой. Дошедших до седьмой задачи было четверо.

Последний факт примечателен вот чем. На оргсобрании накануне финала организаторы попросили нас, тех кто проводил финалы, скрыть в тайне победителей, чтобы до понедельника, до самого вручения призов сохранить интригу. Нас это застало врасплох, так как с нашим подходом победителя не заметить можно с теми же шансами, что и не увидеть, кто прибежал первым в масс-старте — только если понадобился фотофиниш. И в нашем случае именно это и произошло. Участники довольно быстро установили между собой, кто насколько далеко прошёл, и четыре кандидата на победу самоопределились. Но вот понять, кто был первым, а кто последним — без логов это было проблематично.

Благодаря выбранной схеме проведения финала протокол соревнований я заполнил буквально с экрана своего компьютера, на котором как раз работал запрос, которым мы следили за ходом соревнований. Вот с последнего его запуска и переписаны были места участников, их баллы (количество решённых задач) и время (решения последней задачи).

Культурная программа

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

В остальном я не участвовал, до награждения тоже не стал задерживаться — дела знаете ли.

Пара слов напоследок

И напоследок. Не могу не восхититься участниками. Сам я, хоть и готовил эту олимпиаду и решал походу самостоятельно почти все задачи, точно не смог бы показать такие же результаты в тех условиях ограниченного времени, в которые мы специально поставили участников.

Финалисты! Пара слов вам лично. Вы — мегакруты! Причём все, даже те, кому по каким-либо причинам не удалось показать себя с лучшей стороны. Извините, если что-то было не так, мы старались, но не всё от нас зависело, а что-то просто не получилось. А Земля, она имеет форму чемодана, и в одном из его тёмных углов мы когда-нибудь обязательно встретимся. Только теперь может оказаться, что уже вы будете устраивать это шоу. Наверное будет интересно, если вы оставите в комментариях свои впечатления, как эти же события смотрелись с вашей стороны.

Автор: bzq

Источник