Как подготовиться к Yandex Сup
3 октября заканчивается регистрация на чемпионат по программированию Yandex Cup — вы ещё успеете зарегистрироваться и пройти пробный этап. Например, по бэкенд-разработке.
Бэкенд-разработчики занимаются в Яндексе самыми разными задачами: проектированием высоконагруженных сервисов, оптимизацией производительности, обработкой данных, созданием продуктовой логики и реализацией пользовательских сценариев. Двадцать финалистов Yandex Cup смогут пройти отбор в Яндекс по упрощённой схеме — нам всегда нужны сильные специалисты.
Чтобы узнать, зачем разработчику участвовать в чемпионатах по программированию, каких задач ждать на Yandex Cup и как готовиться к треку по бэкенд-разработке, мы поговорили с Никитой Макаровым, руководителем направления и начальником группы функциональности универсального поиска.
Советы по подготовке
Участие в чемпионате — это хорошая возможность проверить себя, понять, что у вас хорошо получается, а что — не очень. Даже если вы с чем-то не справитесь, это не помешает вам при отборе в Яндекс, а наоборот покажет, на что обратить внимание при подготовке. Перед чемпионатом обязательно потренируйтесь решать задачи и писать код, а не просто повторяйте теорию. Например, это можно сделать на LeetCode или Codeforces. Ещё рекомендуем посмотреть тренировки по алгоритмам от Яндекса.
Вам понадобятся знания о базовых структурах данных и простейших алгоритмах, например, сортировках или обхода графов. В прошлом году мы предлагали участникам решить задачу на формирование SQL-запроса к базе данных. Возможно, в этом году мы повторим эту практику.
Будьте готовы решать задачи в рамках заданных ограничений: например, по времени выполнения или по используемым методам. Во время контеста не запрещено пользоваться интернетом, поэтому, если что, можно будет подсмотреть какой-то метод или его сигнатуру.
В день чемпионата выспитесь и настройтесь на хорошее. Всё должно быть в радость. Чем вы спокойнее, тем лучше у вас будет получаться. Помогать вам будут опыт и свежая голова. Главное — быть уверенным в том, что знание языка программирования вас не подведёт, и получить удовольствие от процесса.
Разбор задачи с прошлогоднего чемпионата
Предлагаем проверить себя. Перед вами задача, которую решали участники финала Yandex Cup в 2020 году. Это задание решили не больше 10 участников — но это не значит, что пытаться не стоит. А его разбор подготовил Альмир Муллануров, разработчик из группы разработки голосовых сценариев и медиатехнологий Яндекса.
Условие
Алексей — программист. Его младший брат постоянно просит у него помощи с домашней работой. Сначала Алексей всё решал и объяснял сам, но с каждым годом это отнимало у него всё больше времени. После долгих раздумий Алексей посоветовал брату искать разборы задач в учебниках: например, на сайтах с решениями домашних работ. Однако иногда и там они оказывались неверными. Поэтому Алексей задумал написать программу, которая для каждой задачи сможет искать такие же задачи на других сайтах. Помогите ему!
Важные детали
— У учебника древовидная структура: он состоит из глав и задач.
— Внутри одной главы могут быть либо другие главы, либо задачи.
— Одинаковыми учебниками можно назвать издания, у которых структура глав и задач совпадает.
— У одинаковых учебников название глав может и не совпадать, так как каждый сайт называет их по-разному.
— На одном сайте двух одинаковых учебников не бывает.
— Две задачи одинаковы, если они взяты из двух одинаковых учебников, их структура совпадает, а сами задачи находятся на одинаковых позициях.
В задаче приходит два типа запросов:
add X BOOK — когда сайт X добавил к себе новый учебник BOOK.
find PROBLEM — когда нужно найти все задачи, которые считаются одинаковыми.
Формат ввода
Сначала для каждого запроса приходит единственная строка: add и find.
Для запросов первого типа в следующей строке приходит строка X, состоящая из букв латинского алфавита. Это название сайта, который разместил у себя новый учебник. Затем в следующей строке приходит само описание учебника в формате JSON с полями title и sections (или problems).
— Каждый элемент списка sections содержит одно из дополнительных полей: title, sections (или problems).
— Каждый элемент списка problems содержит только поле id.
— Гарантируется, что внутри одного сайта у всех задач уникальный id. Все поля состоят из букв латинского алфавита и цифр без escape-символов.
Для запросов второго типа приходит описание задачи в виде двух строк X и id , разделённых пробелом. Это название сайта и id задачи на сайте. Гарантируется, что количество запросов не превышает 105, а суммарное количество в полях sections и problems не превосходит 106.
Формат вывода
Для каждого запроса второго типа сначала выведите единственное целое число M. Это количество задач, одинаковых с этой задачей, кроме самой задачи из запроса. Затем в следующих M строках выведите описание задач в том же формате. Суммарное количество задач, которое нужно вывести, не превышает 106.
Решение
По условию две задачи считаются одинаковыми, если они взяты из двух одинаковых учебников и при этом находятся в них на одинаковых позициях.
Чтобы понять, являются ли два учебника одинаковыми, представим их в виде скобочной последовательности. Открытие секции отмечено открывающейся скобкой, закрытие секции — закрывающейся, а сама задача — звёздочкой. Эту скобочную последовательность можно представить в виде хеша или кода в структуре данных trie (бор). С их помощью мы можем хранить все учебники и понять, какие из них одинаковые.
Чтобы можно было находить конкретные одинаковые задачи, достаточно сохранять их номера внутри скобочной последовательности. Если у двух задач из одинаковых учебников совпадает внутренний номер, то они являются одинаковыми. Таким образом, для каждой задачи нужно вывести все задачи с таким же внутренним номером из учебников, которые имеют такой же хеш или код. В качестве альтернативного решения можно было посчитать значение хеш-функции для всех задач следующим образом:
хеш задачи = хеш учебника * P + хеш пути,
где P — простое число, а хеш пути — хеш последовательности секций, в которые нужно заходить, чтобы дойти до задачи.
Получается, что одинаковые задачи должны иметь одинаковый хеш, а разные — разный.
Что ещё почитать