Видеозаписи лекций ЛКШ
Разбор задачи B ("Объединение отрезков") из контеста третьего дня.
Лектор: Пётр Калинин
2013.Июль
Параллель B'
Отрезки на прямой
Алгоритм покрытия отрезка отрезками. Метод сканирующей прямой. Сжатие координат. Сортировка событий.
Реализация алгоритма покрытия отрезка отрезками
Другие задачи: точка, покрытая максимальным количеством отрезков; объединение отрезков; длина объединения.
Разбор задачи A ("Пересадки") из контеста третьего дня: пересечение двух отрезков на прямой. Пересечение прямоугольников.
Разбор задачи B ("Объединение отрезков") из контеста третьего дня.
Разбор задачи С ("Дорешивание") из контеста третьего дня.
Разбор задачи D ("Минимальное покрытие") из контеста третьего дня: жадный алгоритм и доказательство его оптимальности.
Разбор задачи E ("Китайские часы") из контеста третьего дня.