Командная тренировка №1 (12.08.2013, Southern Subregional 2006)

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Участники тренировки

  • Андрей Корнеев
  • Ольга Фирсова
  • Владимир Фолунин
  • Александр Ерофеев (организатор)

Соревнование

9th Southern Subregional Programming Contest (Южный четвертьфинал, 2006 год, Саратов). Для прохода в полуфинал требовалось решить 4 задачи.

Зеркало соревнования (задачи 315 — 325)

Задачи и комментарии

Написать что требуют
Динамика
Базовая динамика получает TL23. Рабочее решение: делаем разреженный массив стойл (ключ — x, значение — t). Теперь, если лошадь стартует из s и имеет расстояние d, то она влияет только на стойла [ lower_bound(s+1); upper_bound(s+d) ). Достаточно один раз пробежать по отсортированному массиву лошадей и обновить стойла в соответствующих диапазонах. Теперь, кто-нибудь, объясните мне разницу в асимптотике на возможном макстесте. — В. Ф.
  • D. Grants (решена на тренировке)
Сжатие координат, дерево отрезков с ботвой, построение графа по генерируемой информации
Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008
Как сдадите допишете
dfs, нахождение циклов
Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании
Более подробно: (1) Ищем MST, (2) Перебираем цвет, (3) Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST
Мой код 2008 года выпуска. Кажется, меньше, чем у вас например.
Жадность, дерево отрезков с ботвой