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

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

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

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

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

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

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

• A. The Highway Belt

• B. Code Tanks (решена на тренировке)

Написать что требуют

• C. Fast Ride

Динамика

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

• E. Kalevich Strikes Back

Сжатие координат, дерево отрезков с ботвой, построение графа по генерируемой информации

• F. The Influence of the Mafia

Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008

• G. The Spy Network

Как сдадите допишете

• H. The Great Union

dfs, нахождение циклов

• I. Aviamachinations

Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании

Более подробно:

1. Ищем MST
2. Перебираем цвет
3. Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST

• J. The Text Formatting (решена на тренировке)

Мой код 2008 года выпуска. Кажется, меньше, чем у вас например.

• K. Palindrome

Жадность, дерево отрезков с ботвой