Командная тренировка №2 (15.08.2013, Southern Subregional 2005)

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

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

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

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

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

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

• A. Sasha vs. Kate (решена на тренировке)

жадность

• B. Fair-play (решена на тренировке)

• C. King Berl VI

• D. Triangle (решена на тренировке)

геометрия, бин. поиск, длинная арифметика

Решение без бинпоиска, решение с бинпоиском. Второе с исходным классом BI получает TL17, так что длинную арифметику пришлось пропатчить. — В. Ф.

• E. Train (решена в дорешивании)

Код решения. Решение гораздо проще тех, что мы писали на тренировке. Требуется найти длину минимальной петли, образованной пересечением отрезков. Если текущий отрезок i [A; B] пересекается с более ранним отрезком j [C; D] в точке E, то петля складывается из отрезка [E; D], всех отрезков от (j + 1) до (i - 1), а также отрезка [A; E]. — В. Ф.

• F. Boring. Hot. Summer...

Дейкстра, бин. поиск, логарифмические структуры данных

• G. BHTML 1.0 (решена на тренировке)

сделать что просят

• H. Great Berland Wall

• I. Mars Stomatology (решена в дорешивании)

динамика

Код решения. Считаем динамику d[i][j] — минимальную стоимость лечения i зубов, последний из которых имеет номер j. Если зубы отсортированы по деснам, то d[i][j] определяется по d[i - 1][] за O(N) (необходимость добавления стоимости десны определяется за O(1)). Итоговая асимптотика O(N^3). — В. Ф.

• J. Exhibition (решена в дорешивании)

максимальное паросочетание

Код решения. Генерируем для каждой прогрессии первые N членов, попадающие в диапазон от 1 до M O(N^2). Ищем максимальное паросочетание на полученном графе. Для поиска максимального паросочетания был использован алгоритм Куна без оптимизаций O(N*M) = O(N^3). Итоговая асимптотика O(N^3). — А. К.