Жадные алгоритмы: лекция + олимпиадные задачи

• Обсуждение олимпиадных жадных алгоритмов.  

• Источники информации: сборник лекций зимней компьютерной школы 2013 года.  

• Лекции Сергея Копиловича, разбор задач на контестах.  

• Примеры задач и их решения.  

• Применение жадных алгоритмов в связке с динамическим программированием.  

• Разбор задач на Яндекс Контесте и Олимп.  

• Определение жадного алгоритма.  

• Пример задачи на построение минимального основного дерева.  

• Алгоритм Прима для построения минимального основного дерева.  

• Пример задачи с выбором предметов.  

• Введение понятия "лучше" и "хуже".  

• Сортировка предметов по отношению "лучше" и "хуже".  

• Задача с обработкой фотографий на флешке.  

• Вычисление веса клиента и сортировка по этому критерию.  

• Решение задачи с использованием сортировки и приоритетной очереди.  

• Применение сортировки в жадных алгоритмах.  

• Использование структур данных для хранения ребер.  

• Основной принцип решения жадных задач - сортировка по отношению "лучше" и "хуже".  

• В первой задаче нужно было набрать определенное количество предметов.  

• В некоторых задачах требуется набрать все предметы.  

• Пример задачи: соединить строки так, чтобы получилось географически минимальное соединение.  

• Сформировали ответ из всех строчек.  

• Сортировка строчек в пределах одного ответа.  

• Цель: не ухудшить ответ, а возможно, улучшить его.  

• Рассматриваем, выгодно ли поставить с ит или с жая раньше.  

• Сравниваем ликсиографически: общая часть, длина, соседние элементы.  

• Если длина одинаковая, рассматриваем соседние элементы.  

• Компаратор позволяет менять соседние элементы местами.  

• Компаратор можно использовать в различных сортировках.  

• Пример задачи: соединить строчки для минимальной конкатенации.  

• Задача: победить всех драконов с минимальным количеством солдат.  

• Рассматриваем случай эн равной двойке.  

• Выводим компаратор для выбора порядка сражений.  

• В случае эн равной двойке возможны два варианта ответа.  

• Выбираем вариант с меньшим количеством солдат.  

• Компаратор используется в сортировке для решения задачи.  

• Выводим формулу для ответа через компаратор.  

• Сортировка относительно компаратора для формирования ответа.  

• Пример кода для задачи с драконами.  

• Определение минимального количества армий.  

• Вопросы по сортировке и компараторам.  

• Возможность использования сортировки без бинарного поиска.  

• Рассматриваются задачи, где нужно найти максимальное количество чего-либо.  

• Пример задачи: сортировка клиентов по весу и сбор денег до исчерпания.  

• Применение бинарного поиска по ответу для таких задач.  

• Проверка монотонности: если можно набрать x, то можно и x-1.  

• Если x не можем набрать, то и x+1 не можем.  

• Бинарный поиск всегда работает для жадных алгоритмов.  

• Фиксированная армия и выбор диапазонов для бинарного поиска.  

• Решение задачи без бинарного поиска через график армии.  

• Бинарный поиск проще и эффективнее для таких задач.  

• Пример задачи с бутылками и полками.  

• Решение через бинарный поиск и жадную идею.  

• Заполнение полок в порядке убывания высот бутылок.  

• Задача с существами и монетами для апгрейда.  

• Максимальное количество побед при ограничении на монеты.  

• Применение бинарного поиска для упрощения задачи.  

• Сортировка элементов по убыванию.  

• Выставление самых мощных существ против самых слабых.  

• Донат для победы в каждом бою.  

• Проверка на превышение количества побед.  

• Жадная идея: выставлять самых мощных против самых слабых.  

• Пример задачи, где жадность решает проблему.  

• Различие между числами.  

• Представление множества как цепочки.  

• Удаление запрещенных элементов из множества.  

• Использование множества для хранения чисел.  

• Удаление минимальных элементов, умноженных на k.  

• Перебор минимумов и удаление запрещенных элементов.  

• Максиму нужно купить все товары за минимальную сумму.  

• Использование скидок несколько раз.  

• Сортировка товаров по убыванию и использование минимальной скидки.  

• Использование минимальной скидки и набора товаров.  

• Сортировка товаров по убыванию.  

• Нахождение минимальной скидки и набор товаров.  

• Вопросы отсутствуют.  

• Рассматривается задача о покраске листьев яблони в разные цвета.  

• Для каждого поддерева нужно использовать минимальное количество цветов.  

• Листья одного поддерева должны быть покрашены в разные цвета.  

• Для каждой вершины подсчитывается количество листьев в поддереве.  

• Используется поиск в глубину для подсчета листьев.  

• Выбираются минимальные поддеревья по размеру.  

• Рассматриваются случаи, когда может не хватить цветов.  

• Листья в одном поддереве не могут быть покрашены в один цвет.  

• Поддеревья либо полностью включены друг в друга, либо не пересекаются.  

• Для каждого поддерева используется количество листьев.  

• Оставшиеся цвета распределяются по оставшимся деревьям.  

• Используется рекурсивный поиск в глубину для подсчета листьев.  

• Количество листьев в поддереве считается рекурсивно.  

• Массив с количеством листьев сортируется по возрастанию.  

• Выводится количество листьев для каждого поддерева.  

• Обсуждение вопросов по задаче.  

• Уточнение алгоритма подсчета листьев и сортировки.  

• Проверка корректности решения и его публикация на GitHub.  

• Задача взята с олимпиады и лекции 2013 года.  

• Нужно сконструировать правильную скобочную последовательность из нескольких строк.  

• Пример: сначала открывающие скобки, затем закрывающие.  

• Подсчет минимального баланса и суммарного баланса для каждой строки.  

• Пример: минимальный баланс -2, итоговый баланс -1.  

• Соединение скобок в правильном порядке для минимизации потерь.  

• Солдаты могут воскресать и умирать.  

• Порядок действий: сначала добавлять солдат, затем нейтральные, потом удалять.  

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

• Сортировка строк по минимальному балансу.  

• Сравнение двух соседних строк для выбора оптимального порядка.  

• Приоритет выживания солдат: сначала положительные, затем нейтральные, потом отрицательные.  

• Проверка баланса в конце: если баланс равен нулю, то последовательность правильная.  

• Решение сводится к задаче про драконов.  

• Возможность формулировки задачи в разных форматах.  

• Чтение строк как векторов и вызов функции для нахождения порядка.  

• Разделение на три группы: положительные, нулевые, отрицательные.  

• Подсчет баланса для каждой строки и сортировка по компаратору.  

• Формирование ответа: проверка баланса и добавление индекса в ответ.  

• Проверка баланса в конце: баланс должен быть равен нулю.  

• Сравнение с задачей про драконов: использование компаратора для сортировки.  

• Рассматриваются базовые задачи из учебников 70-х годов.  

• Первая задача: выполнение заказов с минимальным временем выполнения.  

• Вторая задача: выполнение всех заказов до их дедлайнов.  

• Нужно выстроить коробки в вертикальную башню.  

• Каждая коробка имеет свою массу и выдерживает определенный вес.  

• Важно, чтобы массы коробок были правильно упорядочены.  

• Рассматриваются компараторы для сортировки по весу и массе.  

• Оценочная функция используется для сортировки по времени выполнения и штрафам.  

• В задачах с дедлайнами штрафы добавляются за каждую минуту просрочки.  

• Рассматриваются задачи на последовательное соединение строк.  

• Приведены примеры и решения для общего случая.  

• Для углубленного изучения рекомендуется скачать лекцию с GitHub.  

• Приведены ссылки на дополнительные материалы и задачи.  

• Вопросы по теме и не по теме.  

• Завершение лекции и прощание.