Тренировки по алгоритмам от Яндекса. Разбор домашнего задания по лекции 5 и 6

YOUTUBE · 28.11.2025 06:42

Ключевые темы и таймкоды

Введение и постановка задачи

4:44
  • Разбор задач из пятого и шестого занятий.
  • Задача про счёт в гипер-шашках: три игрока, счёт может отличаться не более чем в k раз.
  • Судья Андрей имеет набор карточек с числами, нужно посчитать количество возможных вариантов счёта.

Подход к решению

6:22
  • Отсортировать карточки или посчитать количество их повторений.
  • Создать словарь, где для каждой карточки будет храниться количество её повторений.

Пример с k = 2

7:07
  • При k = 2 возможные варианты счёта: 1-1, 1-2, 2-3, 3-3, 2-3, 3-3-2.
  • Из всех возможных вариантов остаются только те, где счёт отличается не более чем в два раза.

Использование двух указателей

8:16
  • Использовать упорядоченный словарь или отсортировать уникальные ключи.
  • Левый указатель показывает на первый ключ, правый двигается до тех пор, пока число по правому указателю не окажется больше числа по левому более чем в k раз.

Расчёт количества вариантов

10:09
  • Фиксировать подходящие числа от 1 до r-1 включительно.
  • Определять количество способов выбрать два оставшихся числа из r-1-l-1 вариантов.

Арифметическая прогрессия

12:54
  • Второе число можно выбрать r-1-l-1 способами, третье — меньшим количеством способов для каждого выбранного второго числа.
  • Количество членов арифметической прогрессии равно r-1-l-2.

Перестановки чисел

14:09
  • Три разных числа можно переставить шестью способами: 1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1-2, 3-2-1.
  • Для фиксированного первого числа количество вариантов выбора второго и третьего числа равно сумме арифметической прогрессии длиной r - 2.
  • Количество вариантов перестановки умножается на шесть.

Случай с одинаковыми числами

15:09
  • Рассматривается случай, когда все три числа одинаковые.
  • Если есть две карточки с единичкой, то третье число можно выбрать любым из r - 1 способов.
  • Возможные перестановки: 1-1-x, 1-x-1, x-1-1.

Учёт повторяющихся чисел

16:55
  • Если число встречается два или более раз, оно учитывается дважды.
  • Для каждого отрезка между указателями хранится количество чисел, которые встречаются два или более раз.
  • Количество возможных случаев умножается на три.

Реализация в коде

18:55
  • Ввод и подсчёт чисел с использованием словаря.
  • Сортировка уникальных номеров карточек.
  • Движение двух указателей для перебора возможных вариантов.

Подсчёт дубликатов

20:55
  • Увеличение счётчика дубликатов при повторении числа.
  • Добавление нового числа к подходящим и подсчёт дубликатов.
  • Умножение на три для учёта перестановок.

Итоговая формула

22:55
  • Использование формулы арифметической прогрессии для выбора первого и второго числа.
  • Умножение на три для учёта порядка чисел.
  • Удаление дубликатов и добавление оставшихся к ответу.

Задача про робота

25:49
  • Робот выполняет операции 26 типов, обозначенные строчными буквами.
  • Робот имеет k ячеек памяти для операций.
  • Необходимо посчитать количество экономически целесообразных вариантов использования робота.
  • Пример: строка из n = 8 букв, k = 3, память робота.

Пример использования робота

26:42
  • Робот начинает выполнять операции с первого места.
  • После выполнения трёх операций робот начинает заново.
  • Экономически целесообразно, если робот выполнит хотя бы одну операцию.

Экономически целесообразные операции робота

27:42
  • Робот выполняет операции, начиная с той, что записана в нулевой ячейке его памяти.
  • Если робот начинает с операции «а», он может выполнить четыре операции.
  • При выполнении операции «б» робот может выполнить пять операций, если в его памяти записана «б».

Варианты включения робота

28:42
  • Если робот включается не с первой операции, а с «б», он может выполнить только три операции.
  • Аналогично, при включении с «ц» робот выполнит только три операции.
  • При включении с «абц» робот выполнит один вариант операций.

Общее количество экономически целесообразных способов

29:42
  • Для всех возможных начальных позиций робота количество экономически целесообразных способов выполнения операций равно десяти.

Решение задачи за линейное время

30:42
  • Задача решается путём перебора строки и проверки совпадения букв на разных позициях.
  • Используется переменная «привлен» для подсчёта количества совпадений.
  • Ответ формируется путём сложения значений «привлен».

Пример работы алгоритма

31:42
  • Пример показывает, как алгоритм подсчитывает количество экономически целесообразных программ для робота.
  • При совпадении букв «привлен» увеличивается, и это значение добавляется к ответу.
  • Если совпадение отсутствует, «привлен» устанавливается в ноль.

Программа для решения задачи

34:28
  • Программа считывает число «к» и строку, заводит переменную «привлен» и ответ.
  • Ищет совпадения букв в строке, увеличивая «привлен» при совпадении.
  • Печатает ответ после завершения алгоритма.

Задача про треугольники

35:28
  • Необходимо посчитать количество равнобедренных треугольников на заданных точках плоскости.
  • Ограничение в 1500 точек позволяет использовать квадратичный алгоритм.
  • Перебираются все точки и их соседи для определения равнобедренных треугольников.

Использование двух указателей

37:28
  • Два указателя используются для сортировки точек по расстоянию и подсчёта количества равных сторон.
  • Подсчёт количества равнобедренных треугольников выполняется через комбинаторику.

Учёт вырожденных треугольников

39:28
  • Вырожденные треугольники учитываются путём добавления информации о длине сторон.
  • Метод двух указателей модифицируется для учёта вырожденных случаев.

Оптимизация алгоритма

40:28
  • Для устранения проблем с вырожденными треугольниками

Проблема с сортировкой сторон

41:22
  • Необходимо определить, есть ли у фиксированной стороны другая сторона такой же длины, направленная в другую сторону.
  • Идея использования тригонометрии для сортировки сторон по длине и тангенсу.
  • Проблемы: деление на ноль и потеря точности при работе с вещественными числами.

Альтернативный подход

43:15
  • Решение: хранить координаты точек явно, избегая деления и работы с вещественными числами.
  • Для каждой точки вычислять расстояние до соседа и его координаты.

Удаление дубликатов

44:15
  • Использование множества для удаления дубликатов точек.
  • Проверка наличия точки с противоположными координатами в множестве.
  • Вычитание единицы из количества треугольников при обнаружении дубликата.

Обработка равносторонних треугольников

46:15
  • Проблема: равносторонние треугольники могут быть посчитаны несколько раз.
  • Решение: либо забыть о равносторонних треугольниках, либо использовать теорию чисел для их исключения.

Реализация алгоритма

47:15
  • Перебор точек и вычисление координат и длин векторов.
  • Проверка использования векторов и вычитание единиц при необходимости.
  • Сортировка соседей по длине и подсчёт количества треугольников.

Проблемы с Python

50:01
  • Сортировка кортежей на Python работает медленно, что замедляет выполнение программы.
  • Сложность подбора тайм-лимита для задач на Python.

Задача про субботник

51:01
  • Формирование бригад школьников для переноски брёвен.
  • Минимизация разницы в росте между самым высоким и самым низким школьником в бригаде.
  • Идея использования бинарного поиска для решения задачи.

Анализ идей

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

Формирование бригад по росту

54:01
  • Определяется максимально допустимая разница в росте.
  • Формируются бригады, учитывая разницу в росте.
  • Чем больше допустимая разница, тем больше бригад можно сформировать.

Бинарный поиск и жадное формирование

55:01
  • Используется бинарный поиск для определения правой границы.
  • Жадное формирование бригад: если можно сформировать бригаду, то формируем её.
  • Увеличение правой границы приводит к правильному ответу.

Пример с бинарным поиском

56:01
  • Для границы 17 формируется только одна бригада.
  • Для границы 20 формируются две бригады.
  • Минимальный ответ для примера — 20.

Реализация в коде

57:01
  • Считывание данных, сортировка и применение левого бинарного поиска.
  • Функция проверки минимального количества бригад.
  • Жадное формирование бригад с перемещением людей по росту.

Задача про медиану объединений

58:47
  • Необходимо найти медиану объединения двух последовательностей.
  • Проблема: количество пар последовательностей огромно.
  • Решение: использование бинарного поиска для эффективного поиска медианы.

Принцип бинарного поиска медианы

1:00:47
  • Проверка числа x как медианы через подсчёт количества чисел меньше и больше x.
  • Критерий медианы: количество чисел меньше x должно быть не больше длины списка, а количество чисел больше x — не больше длины списка.

Реализация бинарного поиска

1:03:47
  • Подсчёт количества чисел меньше и больше x в каждой последовательности.
  • Вложенный бинарный поиск для проверки медианы.
  • Изменение границ бинарного поиска в зависимости от результатов проверки.

Сложность алгоритма

1:05:47
  • Сложность алгоритма: O(n^2) возможных пар последовательностей.
  • Каждый бинарный поиск занимает O(log n) времени.

Код для задачи про медиану

1:06:34
  • Генерация последовательностей для избежания долгого ввода данных.
  • Перебор пар последовательностей и вызов функции для нахождения медианы.

Бинарный поиск медианы

1:07:34
  • Перебирает левую и правую границу бинарного поиска.
  • Медиана находится между минимальными и максимальными числами в последовательности.
  • Проверяет количество чисел меньше и больше медианы.

Условия завершения поиска

1:08:19
  • Если количество меньших чисел меньше или равно длине последовательности, а количество больших чисел не превосходит это количество, медиана найдена.
  • При необходимости меняет левую или правую границу.

Реализация функций

1:09:19
  • Функции реализованы аналогично лекции.
  • Обсуждается использование трёх условий в бинарном поиске как признак непрофессионализма.

Профессиональный подход к бинарному поиску

1:10:19
  • Обычно в бинарном поиске оставляют только два условия.
  • Пример: проверка наличия числа в отсортированной последовательности.

Проверка треугольников

1:11:19
  • Рассматривается задача проверки треугольников по трём точкам на плоскости.
  • Проблема возникает, если точки расположены на одной прямой.

Бинарный поиск в C++

1:12:19
  • Стандартные функции бинарного поиска в C++ не подходят для поиска по множеству целых чисел.
  • Рекомендуется писать собственный бинарный поиск для реальных задач.

Обучение алгоритмам

1:13:19
  • Чтение книг полезно, но важнее практиковаться в написании алгоритмов.
  • Наработанная база алгоритмов позволяет применять новые идеи.

Рекомендации по чтению

1:15:13
  • Рекомендуется книга Кормана, Лейзерсона и Ривеста «Алгоритмы построения анализа».
  • Чаще всего требуется разрабатывать новые алгоритмы на основе существующих.

Решение задач

1:16:05
  • Решайте задачи, читайте разборы и справочники.
  • Подсказки помогают понять алгоритмы и улучшить навыки.

Завершение

1:18:05
  • Приглашение задавать вопросы в чате.
  • Обещание ответить на вопросы на следующем занятии.
Похожие пересказы
Лучшая мотивационная песня для тренировки //Песня для тренировки 🔥🔥 // вирусная песня для тренировки
YOUTUBE 24.11.2025
Тренировки по алгоритмам 5.0 Открытие Тренировок Лекция 1: Сложность, тестирование, особые случаи
YOUTUBE 30.11.2025
Тренировки по алгоритмам от Яндекса. Лекция 7: «Сортировка событий»
YOUTUBE 16.11.2025
Тренировки по алгоритмам от Яндекса. Лекция 5: «Префиксные суммы и два указателя»
YOUTUBE 16.11.2025