Командная тренировка №2 (15.08.2013, Southern Subregional 2005): различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) |
Ctrlalt (обсуждение | вклад) м (Ctrlalt переименовал страницу Командная тренировка №2 (15.08.2013, 8th Southern Subregional) в Командная тренировка №2 (15.08.2013, Southern Subregional 2005)) |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 20: | Строка 20: | ||
: ''геометрия, бин. поиск, длинная арифметика'' | : ''геометрия, бин. поиск, длинная арифметика'' | ||
:: ''[http://pastebin.com/gcTBH2Sw Решение без бинпоиска], [http://pastebin.com/ff0HyTEb решение с бинпоиском]. Второе с исходным классом BI получает TL17, так что длинную арифметику пришлось пропатчить. — В. Ф.'' | :: ''[http://pastebin.com/gcTBH2Sw Решение без бинпоиска], [http://pastebin.com/ff0HyTEb решение с бинпоиском]. Второе с исходным классом BI получает TL17, так что длинную арифметику пришлось пропатчить. — В. Ф.'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=300 E. Train] | * [http://acm.sgu.ru/problem.php?contest=0&problem=300 E. Train] (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: | : ''[http://pastebin.com/JbJjQTJe Код решения]. Решение гораздо проще тех, что мы писали на тренировке. Требуется найти длину минимальной петли, образованной пересечением отрезков. Если текущий отрезок i [A; B] пересекается с более ранним отрезком j [C; D] в точке E, то петля складывается из отрезка [E; D], всех отрезков от (j + 1) до (i - 1), а также отрезка [A; E]. — В. Ф.'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=301 F. Boring. Hot. Summer...] | * [http://acm.sgu.ru/problem.php?contest=0&problem=301 F. Boring. Hot. Summer...] | ||
: | : ''Дейкстра, бин. поиск, логарифмические структуры данных'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=302 G. BHTML 1.0] (<span style="color: green;">'''решена на тренировке'''</span>) | * [http://acm.sgu.ru/problem.php?contest=0&problem=302 G. BHTML 1.0] (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: ''сделать что просят'' | : ''сделать что просят'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=303 H. Great Berland Wall] | * [http://acm.sgu.ru/problem.php?contest=0&problem=303 H. Great Berland Wall] | ||
: | : | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=304 I. Mars Stomatology] | * [http://acm.sgu.ru/problem.php?contest=0&problem=304 I. Mars Stomatology] (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: | : ''динамика'' | ||
* [http://acm.sgu.ru/problem.php?contest=0&problem=305 J. Exhibition] | :: ''[http://pastebin.com/ti15BTS8 Код решения]. Считаем динамику d[i][j] — минимальную стоимость лечения i зубов, последний из которых имеет номер j. Если зубы отсортированы по деснам, то d[i][j] определяется по d[i - 1][] за O(N) (необходимость добавления стоимости десны определяется за O(1)). Итоговая асимптотика O(N^3). — В. Ф.'' | ||
: | * [http://acm.sgu.ru/problem.php?contest=0&problem=305 J. Exhibition] (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: ''максимальное паросочетание'' | |||
:: ''[http://pastebin.com/tj9vDWcd Код решения]. Генерируем для каждой прогрессии первые N членов, попадающие в диапазон от 1 до M O(N^2). Ищем максимальное паросочетание на полученном графе. Для поиска максимального паросочетания был использован алгоритм Куна без оптимизаций O(N*M) = O(N^3). Итоговая асимптотика O(N^3). — А. К.'' | |||
[[Category:Командные тренировки — 2013]] | [[Category:Командные тренировки — 2013]] | ||
Текущая версия от 14:37, 20 августа 2013
Участники тренировки
- Андрей Корнеев
- Ольга Фирсова
- Владимир Фолунин
- Александр Ерофеев (организатор)
Соревнование
8th Southern Subregional Programming Contest (Южный четвертьфинал, 2005 год, Саратов). Для прохода в полуфинал требовалось решить 5 задач.
Зеркало соревнования (задачи 296 — 305)
Задачи и комментарии
- A. Sasha vs. Kate (решена на тренировке)
- жадность
- B. Fair-play (решена на тренировке)
- D. Triangle (решена на тренировке)
- геометрия, бин. поиск, длинная арифметика
- Решение без бинпоиска, решение с бинпоиском. Второе с исходным классом BI получает TL17, так что длинную арифметику пришлось пропатчить. — В. Ф.
- E. Train (решена в дорешивании)
- Код решения. Решение гораздо проще тех, что мы писали на тренировке. Требуется найти длину минимальной петли, образованной пересечением отрезков. Если текущий отрезок i [A; B] пересекается с более ранним отрезком j [C; D] в точке E, то петля складывается из отрезка [E; D], всех отрезков от (j + 1) до (i - 1), а также отрезка [A; E]. — В. Ф.
- Дейкстра, бин. поиск, логарифмические структуры данных
- G. BHTML 1.0 (решена на тренировке)
- сделать что просят
- 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). — А. К.