Командная тренировка №1 (12.08.2013, Southern Subregional 2006): различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
==9th Southern Subregional Programming Contest==
== Участники тренировки ==
====(Южный четвертьфинал, 2006 год)====
* Андрей Корнеев
* Ольга Фирсова
* Владимир Фолунин
* Александр Ерофеев (организатор)


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


Где сдать - [http://acm.sgu.ru/problemset.php?contest=0&volume=3] - задачи 315-324.
[http://acm.sgu.ru/problemset.php?contest=0&volume=3 Зеркало соревнования (задачи 315 — 325)]


{| class="wikitable" style="text-align: center;"
== Задачи и комментарии ==
! Название
* [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=317 C. Fast Ride] (<span style="color: green;">'''решена в дорешивании'''</span>)
|-
: ''Динамика''
|The Highway Belt (315)
:: ''Базовая динамика получает TL23. Рабочее решение: делаем разреженный массив стойл (ключ &mdash; x, значение &mdash; t). Теперь, если лошадь стартует из s и имеет расстояние d, то она влияет только на стойла [ lower_bound(s+1); upper_bound(s+d) ). Достаточно один раз пробежать по отсортированному массиву лошадей и обновить стойла в соответствующих диапазонах. Теперь, кто-нибудь, объясните мне разницу в асимптотике на возможном макстесте. &mdash; В. Ф.''
|
* [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=320 F. The Influence of the Mafia]
|Code Tanks (316)
: ''Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008''
|Написать что требуют
* [http://acm.sgu.ru/problem.php?contest=0&problem=321 G. The Spy Network] (<span style="color: green;">'''решена в дорешивании'''</span>)
| +
: ''Как сдадите допишете''
|
:: ''Красить удобно те рёбра, которые ближе всего к корню. Обходим граф DFS-ом, поддерживая: d &mdash; глубину текущей вершины, m &mdash; количество покрашенных рёбер на пути до текущей вершины, M &mdash; максимальное число рёбер, которые надо дополнительно покрасить в этой ветке (глобальная переменная). Если d <= M + m и ребро в текущую вершину не покрашено, то его надо покрасить и уменьшить M. &mdash; В. Ф.''
|
* [http://acm.sgu.ru/problem.php?contest=0&problem=322 H. The Great Union]
|
: ''dfs, нахождение циклов''
|-
* [http://acm.sgu.ru/problem.php?contest=0&problem=323 I. Aviamachinations] (<span style="color: green;">'''решена в дорешивании'''</span>)
|Fast Ride (317)
: ''Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании''
|Динамика
: ''Более подробно: (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://acm.sgu.ru/problem.php?contest=0&problem=325 K. Palindrome]
|-
: ''Жадность, дерево отрезков с ботвой''
|Grants (318)
 
|
[[Category:Командные тренировки &mdash; 2013]]
| +
|
|
|-
|Kalevich Strikes Back (319)
|Сжатие координат, дерево отрезков с ботвой, построение графа по генерируемой информации
|
|
|
|-
|The Influence of the Mafia (319)
|Довольно хитрая реализация. Нечто похожее по хитрости (хотя, наверно, попроще) было нужно для уверенного прохода в 2008
|
|
|
|-
|The Spy Network (320)
|Как сдадите допишете
|
|
|
|-
|The Great Union (321)
|dfs, нахождение циклов
|
|
|
|-
|Aviamachinations (322)
|Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании
|
|
|
|-
|The Text Formatting (323)
|
| +
|
| [http://ideone.com/akC09J] - Мой код 2008 года выпуска. Кажется, меньше, чем у вас например.
|-
|Palindrome (324)
|Жадность, дерево отрезков с ботвой.
|
|
|
|}

Текущая версия от 14:37, 20 августа 2013

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

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

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

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-ом, поддерживая: d — глубину текущей вершины, m — количество покрашенных рёбер на пути до текущей вершины, M — максимальное число рёбер, которые надо дополнительно покрасить в этой ветке (глобальная переменная). Если d <= M + m и ребро в текущую вершину не покрашено, то его надо покрасить и уменьшить M. — В. Ф.
dfs, нахождение циклов
Едет MST через MST. Неплохо решить, если кто захочет осилить Краскала чтобы потренироваться в написании
Более подробно: (1) Ищем MST, (2) Перебираем цвет, (3) Для каждого цвета находим какой-то остовный лес (добавляем ребра в dsu, чтобы не было циклов), а потом достраиваем его до дерева, используя найденное MST
Мой код 2008 года выпуска. Кажется, меньше, чем у вас например.
Жадность, дерево отрезков с ботвой
Источник — https://acm.khpnets.info/w39/index.php?title=Командная_тренировка_№1_(12.08.2013,_Southern_Subregional_2006)&oldid=665