Командная тренировка №4 (20.08.2013, Northern Subregional 2008)

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

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

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

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

Northern Subregional Programming Contest 2008 (Северный четвертьфинал, 2008 год, Санкт-Петербург). Для прохода в полуфинал требовалось решить 6-7 задач.

Зеркало соревнования

Условия задач

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

  • A. Access Control (решена на тренировке)
Код решения.
  • 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 (решена на тренировке)
Код решения.