Командная тренировка №1 (12.08.2013, Southern Subregional 2006): различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) м (Ctrlalt переименовал страницу Командная тренировка №1 (12.08.2013, 9th Southern Subregional) в Командная тренировка №1 (12.08.2013, Southern Subregional 2006)) |
||
| (не показано 6 промежуточных версий 2 участников) | |||
| Строка 13: | Строка 13: | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=315 A. The Highway Belt] | * [http://acm.sgu.ru/problem.php?contest=0&problem=315 A. The Highway Belt] | ||
: | : | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=316 B. Code Tanks] (<span style="color: green;">'''решена на тренировке'''<span>) | * [http://acm.sgu.ru/problem.php?contest=0&problem=316 B. Code Tanks] (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: ''Написать что требуют'' | : ''Написать что требуют'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=317 C. Fast Ride] | * [http://acm.sgu.ru/problem.php?contest=0&problem=317 C. Fast Ride] (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: ''Динамика'' | : ''Динамика'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=318 D. Grants] (<span style="color: green;">'''решена на тренировке'''<span>) | :: ''Базовая динамика получает TL23. Рабочее решение: делаем разреженный массив стойл (ключ — x, значение — t). Теперь, если лошадь стартует из s и имеет расстояние d, то она влияет только на стойла [ lower_bound(s+1); upper_bound(s+d) ). Достаточно один раз пробежать по отсортированному массиву лошадей и обновить стойла в соответствующих диапазонах. Теперь, кто-нибудь, объясните мне разницу в асимптотике на возможном макстесте. — В. Ф.'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=318 D. Grants] (<span style="color: green;">'''решена на тренировке'''</span>) | |||
: | : | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=319 E. Kalevich Strikes Back] | * [http://acm.sgu.ru/problem.php?contest=0&problem=319 E. Kalevich Strikes Back] | ||
| Строка 23: | Строка 24: | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=320 F. The Influence of the Mafia] | * [http://acm.sgu.ru/problem.php?contest=0&problem=320 F. The Influence of the Mafia] | ||
: ''Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008'' | : ''Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=321 G. The Spy Network] | * [http://acm.sgu.ru/problem.php?contest=0&problem=321 G. The Spy Network] (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: ''Как сдадите допишете'' | : ''Как сдадите допишете'' | ||
:: ''Красить удобно те рёбра, которые ближе всего к корню. Обходим граф DFS-ом, поддерживая: d — глубину текущей вершины, m — количество покрашенных рёбер на пути до текущей вершины, M — максимальное число рёбер, которые надо дополнительно покрасить в этой ветке (глобальная переменная). Если d <= M + m и ребро в текущую вершину не покрашено, то его надо покрасить и уменьшить M. — В. Ф.'' | |||
* [http://acm.sgu.ru/problem.php?contest=0&problem=322 H. The Great Union] | * [http://acm.sgu.ru/problem.php?contest=0&problem=322 H. The Great Union] | ||
: ''dfs, нахождение циклов'' | : ''dfs, нахождение циклов'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=323 I. Aviamachinations] | * [http://acm.sgu.ru/problem.php?contest=0&problem=323 I. Aviamachinations] (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: ''Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании'' | : ''Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=324 J. The Text Formatting] (<span style="color: green;">'''решена на тренировке'''<span>) | : ''Более подробно: (1) Ищем MST, (2) Перебираем цвет, (3) Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=324 J. The Text Formatting] (<span style="color: green;">'''решена на тренировке'''</span>) | |||
: ''[http://ideone.com/akC09J Мой код 2008 года выпуска]. Кажется, меньше, чем у вас например.'' | : ''[http://ideone.com/akC09J Мой код 2008 года выпуска]. Кажется, меньше, чем у вас например.'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=325 K. Palindrome] | * [http://acm.sgu.ru/problem.php?contest=0&problem=325 K. Palindrome] | ||
Текущая версия от 14:37, 20 августа 2013
Участники тренировки
- Андрей Корнеев
- Ольга Фирсова
- Владимир Фолунин
- Александр Ерофеев (организатор)
Соревнование
9th Southern Subregional Programming Contest (Южный четвертьфинал, 2006 год, Саратов). Для прохода в полуфинал требовалось решить 4 задачи.
Зеркало соревнования (задачи 315 — 325)
Задачи и комментарии
- B. Code Tanks (решена на тренировке)
- Написать что требуют
- C. Fast Ride (решена в дорешивании)
- Динамика
- Базовая динамика получает TL23. Рабочее решение: делаем разреженный массив стойл (ключ — x, значение — t). Теперь, если лошадь стартует из s и имеет расстояние d, то она влияет только на стойла [ lower_bound(s+1); upper_bound(s+d) ). Достаточно один раз пробежать по отсортированному массиву лошадей и обновить стойла в соответствующих диапазонах. Теперь, кто-нибудь, объясните мне разницу в асимптотике на возможном макстесте. — В. Ф.
- D. Grants (решена на тренировке)
- Сжатие координат, дерево отрезков с ботвой, построение графа по генерируемой информации
- Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008
- G. The Spy Network (решена в дорешивании)
- Как сдадите допишете
- Красить удобно те рёбра, которые ближе всего к корню. Обходим граф DFS-ом, поддерживая: d — глубину текущей вершины, m — количество покрашенных рёбер на пути до текущей вершины, M — максимальное число рёбер, которые надо дополнительно покрасить в этой ветке (глобальная переменная). Если d <= M + m и ребро в текущую вершину не покрашено, то его надо покрасить и уменьшить M. — В. Ф.
- dfs, нахождение циклов
- I. Aviamachinations (решена в дорешивании)
- Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании
- Более подробно: (1) Ищем MST, (2) Перебираем цвет, (3) Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST
- J. The Text Formatting (решена на тренировке)
- Мой код 2008 года выпуска. Кажется, меньше, чем у вас например.
- Жадность, дерево отрезков с ботвой