Командная тренировка №4 (20.08.2013, Northern Subregional 2008): различия между версиями
Перейти к навигации
Перейти к поиску
| (не показано 8 промежуточных версий 3 участников) | |||
| Строка 8: | Строка 8: | ||
Northern Subregional Programming Contest 2008 (Северный четвертьфинал, 2008 год, Санкт-Петербург). Для прохода в полуфинал требовалось решить 6-7 задач. | Northern Subregional Programming Contest 2008 (Северный четвертьфинал, 2008 год, Санкт-Петербург). Для прохода в полуфинал требовалось решить 6-7 задач. | ||
[http://algorithm.contest.yandex.ru/contest/84/enter Зеркало соревнования] | [http://algorithm.contest.yandex.ru/contest/84/enter Зеркало соревнования] | ||
[http://www.pdf-archive.com/2013/08/20/problems/problems.pdf Условия задач] | |||
== Задачи и комментарии == | == Задачи и комментарии == | ||
* | * A. Access Control (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: '' '' | : ''[http://pastebin.com/qaPHTxpQ Код решения]. '' | ||
: ''[http://pastebin.com/QF1uZUKU Код решения]. Решение аналогично предыдущему, но использует стандартный set вместо декартового дерева. Время исполнения и объем потребляемой памяти совпадает с предыдущем решением. '' | |||
: '' | : ''И кода^W мест для багов на 50 строк меньше - А.Е.'' | ||
* B. Billboard (<span style="color: green;">'''решена на тренировке'''</span>) | |||
: '' | : '' [http://pastebin.com/cguAKaxv Код решения]. Построим дерево отрезков для максимума на отрезке. Теперь мы можем эффективно выбирать самый левый элемент >= b. Для этого нужно спуститься от корня до листа дерева следуя следующему правилу: если значение в левом поддереве >= b, тогда рекурсивно вызваваться из левого поддерева, иначе - из правого. Если значение в корне < b - тогда ответ на запрос -1. '' | ||
: '' Итоговая асимптотика O(N*log N). — А. К. '' | |||
: '' | * C. Class (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: ''[http://pastebin.com/WTMDpbMV Код решения]. '' | |||
: '' | * D. Deposits (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: ''[http://pastebin.com/dpcisQnn Код решения]. '' | |||
: '' | * E. Enchanted Mirror (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: ''[http://pastebin.com/haK4x6p4 Код решения]. '' | |||
: | * F. Fenwick Tree (<span style="color: green;">'''решена в дорешивании'''</span>) | ||
: ''[http://pastebin.com/vbE2VtvV Код решения]. Для каждой вершины v := 1..N: если l(v) > 1, считаем сумму s = sum(a[v - l(v) + 1], .., a[v - 2]); присваем элементу a[v - 1] = -s. '' | |||
: '' | : '' Итоговая асимптотика O(N*log N). — А. К.'' | ||
* | * G. Ground Works | ||
* | |||
: '' '' | : '' '' | ||
* [http:// | * H. Holes (<span style="color: green;">'''решена на тренировке'''</span>) | ||
: ''[http://pastebin.com/PwcbS07i Код решения]. '' | |||
* I. Important Wires (<span style="color: green;">'''решена на тренировке'''</span>) | |||
: ''[http://pastebin.com/RrV3fCQs Код решения]. Если формула f_n(x_1, x_2, ..., x_n) является общезначимой, то формула f_(n+1) = f_n(x_1, x_2, ..., x_n) | x_(n+1) также является общезначимой. Читаем ввод, для первого pin'a x_1 строим общезначимую формулу x_1 | ~x_1, далее прицепляем остальные pin'ы через ИЛИ.'' | |||
: '' Итоговая асимптотика O(N). — А. К. '' | |||
* J. Just Too Lucky | |||
: '' '' | : '' '' | ||
* K. Key to Success (<span style="color: green;">'''решена на тренировке'''</span>) | |||
: ''[http://pastebin.com/mXGne193 Код решения]. Обозначим через S(n) сумму первых членов последовательности b. Пусть a - отсортированная по возрастанию последовательность неотрицательных чисел длины L. При помощи суммирования некоторых элементов последовательности a можно получить любое число от 1 до S(L) тогда и только тогда, когда для любого i : 1 < i <= L справедливо S(i) <= S(i-1) + 1. Теперь считаем последовательность a и отсортируем ее. Пусть b - пустая последовательность. Будем набирать последовательность b, пока в нее не будет добавлено m элементов, не присутсвующих в последовательности a. a_min - минимальный элемент в последовательности a, Sum(b) - сумма всех элементов в последовательности b. Если a_min <= Sum(b) + 1, добавим элемент a_min в b и удалим его из a, иначе добавим в b элемет со значением Sum(b) + 1.'' | |||
: '' Итоговая асимптотика O(N + M). — А. К. '' | |||
[[Category:Командные тренировки — 2013]] | [[Category:Командные тренировки — 2013]] | ||
Текущая версия от 22:21, 21 августа 2013
Участники тренировки
- Андрей Корнеев
- Ольга Фирсова
- Владимир Фолунин
- Александр Ерофеев (организатор)
Соревнование
Northern Subregional Programming Contest 2008 (Северный четвертьфинал, 2008 год, Санкт-Петербург). Для прохода в полуфинал требовалось решить 6-7 задач.
Задачи и комментарии
- A. Access Control (решена на тренировке)
- Код решения.
- Код решения. Решение аналогично предыдущему, но использует стандартный set вместо декартового дерева. Время исполнения и объем потребляемой памяти совпадает с предыдущем решением.
- И кода^W мест для багов на 50 строк меньше - А.Е.
- B. Billboard (решена на тренировке)
- Код решения. Построим дерево отрезков для максимума на отрезке. Теперь мы можем эффективно выбирать самый левый элемент >= b. Для этого нужно спуститься от корня до листа дерева следуя следующему правилу: если значение в левом поддереве >= b, тогда рекурсивно вызваваться из левого поддерева, иначе - из правого. Если значение в корне < b - тогда ответ на запрос -1.
- Итоговая асимптотика O(N*log N). — А. К.
- C. Class (решена на тренировке)
- D. Deposits (решена на тренировке)
- E. Enchanted Mirror (решена на тренировке)
- F. Fenwick Tree (решена в дорешивании)
- Код решения. Для каждой вершины v := 1..N: если l(v) > 1, считаем сумму s = sum(a[v - l(v) + 1], .., a[v - 2]); присваем элементу a[v - 1] = -s.
- Итоговая асимптотика O(N*log N). — А. К.
- G. Ground Works
- H. Holes (решена на тренировке)
- I. Important Wires (решена на тренировке)
- Код решения. Если формула f_n(x_1, x_2, ..., x_n) является общезначимой, то формула f_(n+1) = f_n(x_1, x_2, ..., x_n) | x_(n+1) также является общезначимой. Читаем ввод, для первого pin'a x_1 строим общезначимую формулу x_1 | ~x_1, далее прицепляем остальные pin'ы через ИЛИ.
- Итоговая асимптотика O(N). — А. К.
- J. Just Too Lucky
- K. Key to Success (решена на тренировке)
- Код решения. Обозначим через S(n) сумму первых членов последовательности b. Пусть a - отсортированная по возрастанию последовательность неотрицательных чисел длины L. При помощи суммирования некоторых элементов последовательности a можно получить любое число от 1 до S(L) тогда и только тогда, когда для любого i : 1 < i <= L справедливо S(i) <= S(i-1) + 1. Теперь считаем последовательность a и отсортируем ее. Пусть b - пустая последовательность. Будем набирать последовательность b, пока в нее не будет добавлено m элементов, не присутсвующих в последовательности a. a_min - минимальный элемент в последовательности a, Sum(b) - сумма всех элементов в последовательности b. Если a_min <= Sum(b) + 1, добавим элемент a_min в b и удалим его из a, иначе добавим в b элемет со значением Sum(b) + 1.
- Итоговая асимптотика O(N + M). — А. К.