Как подготовиться к Yandex Сup

Советы по тому, как проявить себя на чемпионате, и разбор задачи 

https://avatars.mds.yandex.net/get-media-platform/1599454/62b80c77-10fd-44b2-8f99-96ad58c5c80b/1240x1240

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 — простое число, а хеш пути  — хеш последовательности секций, в которые нужно заходить, чтобы дойти до задачи.

Получается, что одинаковые задачи должны иметь одинаковый хеш, а разные — разный.

Что ещё почитать

  1. Разбор задач по бэкенду с чемпионата 2020 года
  2. Разбор задач по бэкенду с чемпионата 2019 года
разработкагайд