Введение 0:00 Разбор задач с контеста на стажировку в Яндекс. Призыв подписаться на телеграм-канал для получения дополнительных материалов.
Задача 1 — Даты 0:21 Даны две даты в формате год, месяц, день, часы, минуты, секунды. Необходимо определить количество целых дней и секунд между датами. Перевод дат в секунды с помощью таблиц в примечании. Нахождение разницы в секундах между датами.
Перевод секунд в дни 1:05 Деление разницы секунд на количество секунд в одном дне. Вычисление остатка для определения секунд в неполном дне.
Задача 2 — Карточная игра 1:36 Два игрока играют в карточную игру, где карты обозначены целыми числами. Алгоритм определения разнообразия коллекций карт. Примеры изменения разнообразия после добавления или удаления карт.
Реализация алгоритма 3:24 Использование словарей для подсчёта количества карт у каждого игрока. Расчёт разнообразия как суммы разностей по всем картам. Обновление разнообразия после каждого запроса.
Задача 3 — База данных 5:56 Применение запросов к таблице базы данных. Запросы выбирают строки, где значение колонки строго больше или меньше заданного значения. Пример работы запросов на таблице с колонками «а» и «б».
Решение задачи 3 8:23 Установка начальных ограничений для каждой колонки. Обновление границ ограничений на основе запросов. Подсчёт суммы значений оставшихся строк после применения всех запросов.
Изменение границ и проверка строк 9:15 Изменение нижней границы для столбца B: 1 > -10^9 - 1, значение меняется на 1. Изменение верхней границы для столбца B: 3 < текущая верхняя граница, значение заменяется на 3. Создание массива для каждой строки: изначально все строки хорошие, отмечены единицами. Пометка строк нулями, если хотя бы одно число не удовлетворяет условиям.
Пример проверки строк 10:33 Проверка первой строки: значение 1 удовлетворяет условиям, строка остаётся хорошей. Проверка второй строки: значение 2 удовлетворяет условиям, строка остаётся хорошей. Проверка столбца B: значение 1 не удовлетворяет диапазону 1–3, строка помечается нулём.
Решение задачи с языковым барьером 11:45 Описание древовидной структуры организации с сотрудниками, говорящими на языках A и B. Генеральный директор знает оба языка. Задача: для каждого сотрудника посчитать языковой барьер — расстояние до первого человека в иерархии, который знает язык сотрудника.
Использование стеков для решения задачи 13:10 Использование двух стеков: один для сотрудников, знающих язык A, другой — для знающих язык B. Начало с генерального директора, который знает оба языка. Расчёт языкового барьера для каждого сотрудника путём сравнения текущего времени с временем на стеке.
Пример расчёта языкового барьера 14:51 Пример расчёта для сотрудника 1: языковой барьер равен 0, так как непосредственный начальник знает язык сотрудника. Пример расчёта для сотрудника 2: языковой барьер равен 1, так как начальник не знает языка, но знает генеральный директор. Пример расчёта для сотрудника 3: языковой барьер равен 1, так как нужно перескочить через одного сотрудника.
Обработка закрывающихся вершин 15:59 Удаление вершин со стека при выходе из них. Уменьшение текущего времени при выходе из вершины. Пример обработки закрывающейся вершины: удаление тройки со стека и уменьшение текущего времени.
Задача о близости массивов 17:44 Определение близости двух целочисленных массивов как длины их наибольшего совпадающего префикса. Задача: для каждой пары массивов посчитать близость и вычислить сумму таких близостей. Ограничения: до 10^5, простое решение работает за O(n^3).
Разделение массивов на классы 18:30 Разделение массивов на классы по числу, которое встречается в массиве. Создание словаря для хранения номера массива и индекса текущего рассматриваемого элемента. Распределение пар массивов на хэш-таблицы или словари для ускорения обработки.
Сравнение массивов по первой цифре 19:16 Сравниваем массивы по первой цифре и вносим их в разные списки. Получаем пары: 00, 10, 20. Разделяем массивы по словарям, используя ключ для идентификации. В словарь по ключу «единица» добавляем пары: 01, 11, 21.
Подсчёт пар и добавление к ответу 20:07 На каждой итерации подсчитываем количество элементов по каждому ключу. Если элементов три, можем составить три пары. Добавляем три к ответу.
Рекурсивное сравнение по второму элементу 20:35 Передаём массив по ключу функции для повторного сравнения. Получаем пары: 02, 12, 22. В словарь по ключу «два» попадают массивы 02 и 22. В словарь по ключу «три» попадает массив 12.
Подсчёт пар для второго элемента 21:15 Считаем количество пар для каждого ключа: два элемента — одна пара, один элемент — ноль пар. Добавляем единицу к ответу.
Завершение рекурсии и подведение итогов 22:09 Запускаем функцию от набора 0222. Удаляем несуществующий элемент из рассмотрения. Остаётся ключ «три» с парой 23. Подсчитываем пары для третьего ключа, получаем ноль пар. Итоговый ответ равен четырём.
