Хабрахабр

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

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

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

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

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

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

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

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

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

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

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

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

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

$max\Big(\frac{X}, 0\Big).$

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

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

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. Функцию можно вызывать до её определения, а также в её собственном теле.

Для каждой функции программы необходимо вывести не более $x$ исключений, которые могут вылететь из неё. На вход подаётся программа на языке $EX$ и число $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.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть