Разбор квалификации чемпионата по программированию среди бэкенд-разработчиков

в 8:03, , рубрики: Блог компании Яндекс, Занимательные задачки, Карьера в IT-индустрии, конкурсы, конкурсы разработчиков, Программирование, Спортивное программирование, Яндекс.Блиц

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

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

Разбор квалификации чемпионата по программированию среди бэкенд-разработчиков - 1

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

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

A. Будильники

Условие задачи

Работа в большинстве IT-компаний имеет много преимуществ: нет дресс-кода, можно иногда поработать удалённо, классные и умные коллеги и, конечно же, свободный график! Однако свободный график и возможность работать удалённо требуют большой силы воли.

Программист Алексей любит работать по ночам и не любит приходить на работу поздно. Чтобы точно проснуться с утра, Алексей каждый вечер заводит $N$ будильников на своём телефоне. Каждый будильник устроен таким образом, что он звонит каждые $X$ минут с того момента времени, на который его завели. Например, если будильник был заведён на момент времени $t_i$, то он будет звонить в моменты времени $t_i$, $t_i + X$, $t_i + 2 cdot X$ и т. д. При этом если какие-то два будильника начинают звонить в один момент времени, то отображается только один из них.

Известно, что прежде чем проснуться, Алексей каждое утро слушает ровно $K$ будильников, после чего просыпается. Определите момент времени, когда Алексей проснётся.

Все будильники звонят в целочисленные моменты времени, и у всех будильников один и тот же период повтора звонков. Если два будильника заведены на моменты времени $t_i$ и $t_j$, причём эти моменты времени дают одинаковый остаток при делении на $X$, можно оставить только один будильник — тот, что прозвенит первым.

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

Теперь научимся определять, сколько будильников прозвенело к некоторому моменту времени $T$. Если будильник заведён на время $t_i$, количество его звонков к моменту $T$ будет равно

$maxBig(frac{T-t_i}{X}, 0Big).$

Сложив эти величины по всем будильникам, получим общее количество прозвеневших будильников к моменту времени $T$.

После этого исходная задача решается бинарным поиском по $T$: с увеличением $T$ количество прозвеневших будильников не уменьшается (т.е. функция монотонна); начальной левой границей можно выбрать 0, а правой — максимально возможный в задаче ответ.

B. Спортивный турнир

Условие задачи

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

Эту задачу можно решить, восстанавливая граф игр турнира. Начнём с того, что для каждого участника ясно, до какой стадии турнира он дошёл: это определяется по количеству игр с его участием.

После этого можно распределить игры по турам. Скажем, во всех играх первого тура один из участников вылетел в первом туре, а другой вылетел не раньше чем во втором. При обработке игры тура с номером $x$ необходимо проверить, что все участники этой игры на текущий момент сыграли одинаковое количество игр, соответствующее номеру $x$, в противном случае турнир невалиден.

После восстановления схемы турнира остаётся только вывести ответ.

C. Интересная игра

Условие задачи

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

Как только кто-то из участников наберет количество очков, которое назвал в начале игры Вася, игра прекращается и этот игрок становится победителем. Если никто из участников не набрал нужного количества очков, но при этом все карточки закончились, то победителем считается игрок, у которого больше очков. Если все карточки закончились, а очков поровну, то объявляется ничья.

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

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

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

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

Эта задача ожидаемо стала самой простой среди всех задач квалификации.

D. Анализатор исключений

Условие задачи

Опишем синтаксис языка программирования $EX$:

  1. func f() {...} — объявление функции (в скобочках — тело)
  2. maybethrow Exc — команда, которая может выбросить исключение вида Exc, а может и не выбросить.
  3. try {...} suppress Exc — если внутри этого блока происходит исключение вида Exc, то оно подавляется.
  4. f() — вызов функции f.

В языке $EX$ все инструкции, кроме объявлений функций, могут находиться только в теле какой-либо функции. Функции нельзя объявлять внутри других функций. Функцию можно вызывать до её определения, а также в её собственном теле. Имена функций и исключений в языке $EX$ должны подходить под регулярное выражение $[a-zA-Z0-9_]+$, быть уникальными и не совпадать с ключевыми словами func, try, suppress, maybethrow.

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

Эта задача оказалась самой сложной из всех задач квалификации.

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

Выберем некоторое исключение и все функции, которые могут его породить. Эти функции вызываются из других функций; возможно, вызовы находятся внутри блока try {...} suppress — в этом случае исключение не распространяется на функцию, в которой происходит вызов. Таким образом, можно при помощи обхода графа в ширину определить все функции, из которых может быть выброшено это исключение.

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

E. Раскодирование

Условие задачи

В интернете появился новый сервис. К сожалению, у него нет документации. Опытным путем от сервера была получена строка s. Однако некоторые символы в этой строке закодированы — чтобы получить настоящий ответ, нужно эту строку раскодировать несколько раз. Поскольку документация на сервис отсутствует, для дальнейших экспериментов нужно определить, какое максимальное число раз можно нетривиальным образом раскодировать эту строку. Процедура раскодирования следующая: нужно найти все подстроки вида ~XY, где X и Y — большие или маленькие шестнадцатеричные цифры и заменить их одновременно на символ с ASCII кодом $16X + Y$ (у каждой подстроки свой). Раскодирование называется тривиальным, если подстрок такого вида нет.

В единственной строке выведите максимальное число последовательных нетривиальных раскодирований исходной строки.

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

Для каждого символа получающейся раскодированной строки необходимо помнить, сколько раз для его получения пришлось раскодировать оригинальную строку. Ясно, что вновь добавляемый в строку символ раскодировался ноль раз. Если же в очередной операции раскодирования принимают участие символы, раскодировавшиеся $r_1, r_2,..., r_k$ раз, то образованный ими символ требует $max(r_1, r_2,..., r_k) + 1$ операций раскодирования.

Пусть конечная раскодированная строка содержит символы $a_1,...,a_k$, для получения которых потребовалось осуществить раскодирование, соответственно, $r_1,...,r_k$ раз. Тогда ответом является величина

$max(r_1,...,r_k).$

F. Поиск ломающего коммита

Условие задачи

В Поиске Яндекса реализована так называемая политика «зелёного транка»: любой код, попадающий в репозиторий, с некоторыми оговорками гарантированно не ломает сборку и тесты.

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

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

В целях экономии ресурсов тестирующая система может проверять только один коммит за раз. Вам требуется написать программу, которая будет определять номер m.

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

Разные варианты задачи отличались количеством коммитов, которые нужно проверять одновременно.

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

Разобранные задачи квалификационного раунда доступны в виде тренировки на Codeforces. Также мы сделали тренировку по задачам финала.

Автор: Алексей Шаграев

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js