image

Привет, Хабр! 11 июня мы в ВСК провели первую олимпиаду по программированию в Москве, Волгограде и Томске. Поучаствовать мог каждый сотрудник с базовыми навыками программирования. Среди участников были не только профессиональные программисты, но и руководители, аналитики, администраторы.

В головах сотрудников ИТ-подразделения скрыт огромный природный интеллект и потенциал. И нам важно было его раскрыть, важно сделать работу айтишника интересной, интенсивной и продуктивной. Олимпиада – отличный формат! Он позволяет вспомнить участие в университетских и школьных олимпиадах, почувствовать вкус и ощутить эмоции от ожидания оценок.

В этой статье мы

  • расскажем, как настроить «Яндекс.Контест»;
  • приведём задачи;
  • покажем, во сколько нам обошлась олимпиада (сразу признаемся: сумма вышла настолько смехотворной, что мы спрячем её под кат).

Пост будет интересен не только любителям задач, но и всем желающим организовать такую же олимпиаду у себя в команде.

Как мы готовились к олимпиаде и сколько это стоило


image
Пришествие олимпиады

Наше направление сейчас интенсивно меняется: появляются новые способы взаимодействия, интересные фичи, проекты. Вот и олимпиада так же легко зашла в нашу айтишную жизнь. Идея пришла от нашего IT-директора. Для участников это челлендж, возможность проверить себя и отвлечься от рутины. А мы, организаторы, искали таланты среди non-IT-сотрудников и тягались с ними в умении рассуждать логически, искать ответы и вообще шевелить мозгами.

Мероприятие обошлось в 105 тысяч рублей. Почти вся сумма ушла на подарки. На кофе-брейки мы потратили 900 рублей в Волгограде и 1300 рублей в Москве (в томском офисе еда и так была). Олимпиаду проводили в офисах, так что в аренде помещения и оборудования не было необходимости.

На организацию ушло две недели. В каждом из трёх городов мы выделили места в наших офисах. В назначенное время все участники собрались там и вгрызлись в задачи.

image
Вгрызаемся

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

Как организовали техноплощадку для олимпиады


Для проведения олимпиады выбрали площадку «Яндекс.Контест», потому что она бесплатная для группы из ста участников. Там можно писать код на разных языках и организовать автоматическую проверку выполненных задач. Наши сотрудники использовали Python, C++, C#, Java, PHP, Delphi, Pascal.

Мы выработали пошаговую инструкцию по использованию этой площадки и поделимся ею в этой главе.

Настройки соревнования

image
На платформе есть настройки турниров, соревнований, наборов задач и задач

Общие настройки

Сначала открываем «Соревнования». Тут есть несколько разделов:

  • «Монитор» — раздел, в котором мы можем посмотреть, как будет выглядеть наша олимпиада со стороны участника;
  • «Посылки» — раздел с отправленными файлами решений наших олимпийцев;
  • «Сообщения» — раздел для общения с участниками соревнования;
  • «Доступ и участники» — раздел для настройки доступа к олимпиаде;
  • «Настройки» — основные настройки олимпиады;
  • «Задачи» — раздел с добавленными в соревнование задачами;
  • «Скачать архив» — здесь мы можем экспортировать в виде архива настройки соревнования;
  • другие разделы.

Настройки

image
От общего к частному

Вначале открываем раздел «Настройки», выбираем «Другие разделы» и даём соревнованию название (у нас это «Олимпиада ВСК»). Затем выбираем доступ к соревнованию: закрытый, открытый или сделать его тренировкой после завершения. Можно ещё выбрать функцию участия командами, но это не наш случай.

Здесь же, в разделе настроек, устанавливаем время олимпиады, когда все участники увидят задачи. Для этого указываем время старта и финиша. Люди смогут подключиться только в этот промежуток.

Наше мероприятие шло четыре часа одновременно на всех площадках. Но можно было задать интервал «в течение суток» и выбрать время на выполнение задач. Тогда участники решали бы их в течение дня с перерывами, но при этом были бы ограничены теми же четырьмя часами (или сколько укажете в настройках). Кстати, соревнование можно сделать и неограниченным по времени.

Также можно разрешить дорешивание. Тогда участники могут продолжать отправлять решения после завершения соревнования, но они не будут учитываться в общей статистике.

image

Посылки

Выбираем максимальный и минимальный размер посылки — файла или текста, который пользователь может отправить. Здесь содержится набор данных о его «олимпиадном выступлении». Посылка содержит общую информацию, результат тестирования, логи и исходный код решения. В настройках можно выбрать количество попыток (мы выбрали 100). Остальные настройки посылок оставили по умолчанию.

image

Компиляторы

Платформа предоставляет обширный выбор компиляторов (на скриншоте ниже — только часть). Выбираем нужные — они будут доступны участникам при отправке решений. Мы выбрали Python, C++, C#, Java, PHP, Delphi, Pascal.

image

Настройки тестирования

Далее приступаем к непосредственной настройке тестирования. Можно выбрать «Использование AC вместо OK». В данном случае, после успешной компиляции кода решения и прохождения тестов по задаче, решение будет направлено судьям для вынесения вердикта. Ещё можно прервать тестирование при первой найденной ошибке в решении — мы выбрали эту опцию.

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

image

Настройка монитора

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

image
За изучением монитора

Мы выбрали тип монитора SCORING, который выводит таблицу участников по количеству решённых задач. Участники с одинаковым количеством баллов ранжируются по суммарному времени решения задач (чем меньше время, тем выше место). Баллы за успешно решённые задачи выставляли судьи, оценивая алгоритм решаемой задачи по нотации O. У нас не предусмотрено частичного решения задач, поэтому мы выставили пункты: «Игнорировать ошибки компиляции», «Игнорировать ошибки проверки кода».

image

Интерфейс участника

Следом настраиваем интерфейс участника. Для этого решаем, что он увидит: других участников, сообщения, оценку своего решения и т.д.

image

Доступы участникам
В данном разделе отображается таблица всех участников с их учётной записью Yandex, ФИО и ролью. Именно в данном разделе можно назначить судей, администратора и координатора олимпиады. Также можно посмотреть, когда участник приступил к решению задач.

image

Посылки

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

image

Также можно зайти в каждую посылку и посмотреть информацию о ней:

  • «Тесты» — результат пройденных тестов (автоматически);
  • «Логи» — результат компиляции предоставленного решения;
  • «Исходный код» — непосредственно исходный код решения.

image
Как раз по исходному коду судьи выставляли баллы по задаче

Монитор

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

image

В остальных вкладках можно посмотреть на интерфейс олимпиады глазами его участника (в зависимости от настроек):

  • «Задачи» — перечень задач для олимпиады, их условие и ограничения (там же и отправляется решение задач);
  • «Посылки» — список посылок, отправленных участником;
  • «Сообщения» — сообщения от жюри;
  • «Участники» — список участников олимпиады (можно отключить отображение в настройках).

image

Наборы задач

При создании соревнования автоматически создаётся и набор задач. В наборе два раздела:

  • «Доступы» — для настройки доступа к просмотру и редактированию набора задач;
  • «Настройки» — настраиваем перечень задач для олимпиады и их порядок.

image

Задачи

Открываем раздел задач. Нажимаем «Создать задачу» и попадаем в интерфейс настройки задачи, где есть разделы:

  • «Настройки» — общие настройки задачи;
  • «Доступ» — ограничиваем доступ к редактированию задачи;
  • «Тесты и решения» — настраиваем автоматическую проверку решений для задачи;
  • «Условия» — добавляем текст условия с пояснениями;
  • «Комментарии к решению» — можно добавить комментарии к решению задачи;
  • «Файлы» — в данном подразделе можно посмотреть все сгенерированные после настройки задачи файлы (условия, тестовые примеры, генераторы и т.д.);
  • «Скачать архив» — в данном разделе можно экспортировать в виде архива все настройки задачи.

Настройки

В настройках заполняем название задачи и выбираем её тип. Мы выбрали Problem with checker — это стандартные задачи по программированию. Система запускает код решения участника и подаёт на вход данные из тестов. Полученный ответ сравнивается с эталонным, указанным в системе.

image

Далее настраиваются формат ответа участника и настройки файлов ввода входных параметров задачи и вывода итогового ответа. Тут мы оставили настройки по умолчанию, разрешив использование стандартного потока для ввода, вывода или через файлы input.txt и output.txt.

image

Затем настраиваем ограничения по запуску и компиляции. Мы решили использовать настройки по умолчанию.

image

В завершение настраиваем чекер для задачи. Мы выбрали STANDART_CHECKER с идентификатором cmp_file — это чекер, который сравнивает два файла построчно (заготовленный ответ с ответом участника). Ограничения оставили по умолчанию. Набор тестовых данных настроим в разделе «Тесты и решения».

image

Тесты и решение

В данном разделе можно настроить:

  • решения;
  • генератор тестов;
  • валидаторы;
  • наборы тестов.

Для своей олимпиады мы подготовили наборы тестов. Тест представляет из себя два файла: файл с входными данными и файл с результатом решения задачи (выходные данные).

Наборы тестов могут быть типом Sample. Это примеры для задачи, которые будут отображены для участника олимпиады. Все примеры можно посмотреть в разделе «Файлы».

image
Шаблон входного файла описывает, какие файлы с примерами в какой набор тестов попадают. Файлы с ответами обычно отличаются только постфиксом. В нашем случае это «.а»

Завершив настройку наборов тестов, нам остаётся описать условие задачи в разделе «Условия» и дать комментарии к решению в соответствующем разделе, если это необходимо.

Участники: кто они и откуда


Мы пригласили сотрудников на олимпиаду через корпоративную рассылку, причём отправили её только по четырём подразделениям. Это было неправильно: IT-таланты есть почти в каждом подразделении, просто некоторые работают на других должностях. Всего мы сделали три рассылки и пригласили ребят через руководителей подразделений. Сейчас понимаем, что недостаточно проинформировали сотрудников.

В олимпиаде участвовали 12 человек. Изначально записалось вдвое больше желающих. Но многие испугались: не знали, как все пройдёт и что будут делать с результатами. А вдруг накажут за «двойки»? Плюс олимпиада совпала с праздничными выходными. И, конечно, конкуренция задачек и удалёнки была неравной. Нам хотелось привлечь больше людей, но поскольку это наш первый опыт, результат считаем нормальным.

image
Интересно, что среди участников были не только профессиональные программисты, но и руководители, аналитики, администраторы — те, кто умеет программировать, но занимается бизнесом, а не кодом

Задачи: какие и почему выбрали именно их


Интереснее всего нам было выбирать задачи. Мы искали их в интернете и меняли, чтобы участники не могли нагуглить ответы. Всего мы подготовили пять задач. Первые три — классические алгоритмические, их предлагают на собеседовании в международной компании. Четвёртая и пятая задачи — из российских олимпиад. Задачи имеют нетривиальные решения: одну и ту же можно выполнить разными способами.

Боялись, что будет слишком легко или слишком сложно. Мы понимали, что задачи должны быть решаемыми, но в то же время не слишком простыми — иначе какой смысл? Поэтому у них разная градация.

  • Первая задача (была простой)

Дано целое число S и массив numbers, состоящий из нулей и единиц. Верните True, если все единицы расположены на расстоянии как минимум s бит друг от друга, иначе верните False.

image
Следующие три задачи — средние по сложности

  • Вторая задача

Фермер решил перебраться через реку. Река разделена на некоторое количество частей. В каждой части может быть камень, а может и не быть. Фермер может шагнуть в часть с камнем. Если камня в области не окажется, фермер упадёт в воду.

Вам дан список положений камней stoneList (в единицах) в отсортированном порядке по возрастанию. Изначально фермер находится на первом камне (из списка) и может шагнуть на 1 единицу. Добраться необходимо до последнего камня. Если фермер шагнул на i единиц (длина предыдущего шага), то следующий шаг может быть на i-1, i или i+1 единиц. Фермер может идти только вперёд. Верните True, если фермер сможет добраться до последнего камня, иначе False.


  • Третья задача

Есть кормушки feeders с жидкостью, из которых ядовита ровно одна кормушка. Чтобы выяснить, какая из них ядовита, вы кормите этой жидкостью некоторое количество мышей. Мыши, которые ели из кормушки с ядом, умирают через [poisonTime] времени (в минутах). К сожалению, у вас есть только [totalMinutesToTest] минуты, чтобы определить, какая кормушка ядовита.

Вы можете тестировать следующим образом:

1. Выберите живых мышей для кормления.
2. Для каждой мыши должно быть выбрано, какими кормушками её кормить (возможно больше одной кормушки за раз). Считается, что мыши съедят все выбранные кормушки одновременно и это не занимает времени.
3. Подождите [poisonTime] минут. В это время нельзя кормить других мышей.
4. По прошествии [poisonTime] минут мыши, которые ели из отравленной кормушки, умрут, а все остальные — нет.
5. Повторяйте этот процесс, пока не закончится время.

  • Четвёртая задача

Имеются купюры достоинствами С1, С2, …, СM. Клиент пришёл в торговый зал и обнаружил, что у него есть ровно по две купюры каждого типа. Сумма, которую нужно заплатить клиенту, равна S. C помощью разработанного вами алгоритма определите, может ли клиент расплатиться без сдачи.

  • Пятая задача

image
…была очень сложной

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


Разбор полётов: статистика и призы


  1. С первой задачей справились шесть человек.
  2. Вторая задача выглядит простой, а на самом деле имеет пять решений разной сложности. Когда мы её выбирали, было интересно посмотреть, какие решения выберут участники. В итоге её решили всего два человека: у одного было стандартное решение, а у другого — скажем так, решение с очень высокой производительностью.
  3. К решению третьей задачи был близок один человек, но ему не хватило времени. Там решение в одну формулу, но ведь её сперва надо вывести.
  4. С четвёртой задачей справился только один человек.
  5. Пятую задачу никто не осилил: мы её и выбрали, потому что у неё маленький процент решений на олимпиадах. Кроме того, участникам просто не хватило времени на решение.

image
Всех задач не решил никто. Победитель решил правильно только три задачи

Мы подготовили призы на выбор для трёх победителей: iPhone, поездку в Геленджик с семьёй в наш корпоративный санаторий, обучение на любом курсе стоимостью до 40 тысяч рублей и расширенную страховку здоровья. Победитель предпочёл iPhone 12 Pro, второй призёр выбрал поездку в Геленджик, третий — обучение. Все призёры получили кубки, а другие участники — памятные грамоты.

Наши итоги и задел на будущее


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

Сейчас мы запустили на платформу всех желающих сотрудников. Они решают эти задачи удалённо и анонимно, просто ради тренировки. Так что у нас получилась заочная часть олимпиады. На данный момент за решение взялись 25 человек, но результаты прислал пока только один. Каждый день в среднем по пять человек приходят на платформу и получают доступ к заданиям.

Вдобавок с нами связался Томский политехнический университет: там хотят предложить наши задачи своим студентам, поскольку любят такое. Мы же планируем повторять олимпиаду каждый год.

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

Комментарии (9)


  1. remova
    25.11.2021 14:00

    Молодцы! Олимпиадного программирования многие боятся, потому, полагаю, если бы все задачи были бы как первая, результаты были бы лучше, а людей пришло бы больше. Ну и, понятно, при условии, если бы успокоили всх заранее, что только такие, простые, задачи будут. Спасибо за ценный опыт!


  1. Sm1le291
    25.11.2021 14:41

    4ая интересная, это на динамическое программирование как я понял?


    1. developerxyz
      25.11.2021 15:57

      Оптимальный метод решения — динамическое программирование. Просто продублируем каждый элемент массива и проверим, существует ли подмножество с необходимой суммой.


      1. dvserg
        25.11.2021 16:00

        Странно, что один смог решить. Без рюшей там строк 50 кода на С++


        1. Sm1le291
          26.11.2021 14:58

          Не совсем понятен посыл вашего комментария, вы мне напомнили моего начальника со сбера который оценивал работу по строкам.

          Ну во первых, тут может быть и меньше строк, а может даже внимание: ОДНА, главное поставьте точки с запятой.

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

          В третьих, возьмем число фибоначи, его можно вычислить как всем известным способом через рекурсию, можно немного заморочиться ииспользовать DP. А можно, тадам... Формулу Байнета, решить в одно действие. Но 99.9% программистов сходу вам не назовут эту формулу. Но зато что мы все знаем, так это то что в комментариях писать, это не мешки ворочать


          1. dvserg
            26.11.2021 15:33

            Добрый день, Игорь.

            Вот идея уважаемого developerxyz . Я посмел удивиться ее несложности, и тому, что участники не все решили данную задачу. А 50 строк - это примерно столько потребовалось сделать задачу на-коленке.


            1. Alexandroppolus
              26.11.2021 16:14

              ДП - не слишком известная штука. Причем многие, кто об этом слышал, не имеют навыков. Без них очень маловероятно смекнуть это за ограниченное время.

              Меня куда сильнее удивило, что целых 6(!) программистов не справились с первой. Это на 6 человек больше, чем должно быть.


  1. developerxyz
    25.11.2021 15:50

    Вторая задача — упрощенная версия задачи 505C — Мистер Китаюта, охотник за сокровищами


  1. Alexandroppolus
    26.11.2021 11:50
    +1

    В третьей задачи действительно одна формула.

    Если у нас M мышей и K = Math.floor(totalMinutesToTest/poisonTime) раундов кормлений, то можем найти одну ядовитую среди (K+1)^M кормушек. Это обобщение известной задачи с одним раундом, и легко доказывается через бином Ньютона.

    Решением этой задачи были математические выкладки, записанные в комментарии к коду? )