Тренировка #14 [Меньшиков]

[Условия задач]                   [Список тренировок]

14A. Марковский цикл
[markovc]
Довольно интересная задача. Во-первых нужно придумать механизм быстрого перебора всех подстрок заданной длины. Лобовой алго за O(N*N) не принимается. Следует подумать как это можно сделать за O(N). Один из самых распространённых методов по решению этой подзадачи – это использование хэш-функции. Дело облегчается тем, что длина максимальной строки не превышает 12, а сама строка состоит из алфавита {A,B,C}. Следовательно любую строку такого вида можно закодировать числом <= 3^12 = 531441.
14B. Д-44
[d44]
Необычная задача. Нужно вспомнить все формулы по физике на тему “бросание тела под углом к горизонту”. Затем промоделировать движение, фиксирую только некоторые дискретные моменты времени и рассчитать в них параметры тела(например проекцию стрости на ось OX и OY). Некоторую сложность может вызвать поиск коэффициента сопротивления воздуха(k). В авторском разборе предлагается это сделать “ручками”. Признаюсь, еле хватило терпения сделать это.  В первую очередь это связано с тем, что в проверяющей системе нужно подобрать такой k, чтобы результирующая длина совпадала вплоть до метра, вместо заявленной погрешности в 10 метров.
14C. Упаковка символов
[folding]
Я очень хорошо помню, когда я был зеленым студентом, какой ужас наводила на меня эта задача. Казалось, что ее может сделать только Петр Митричев. Конечно и сейчас решение представляется каким-то волшебством, но мы уже многому научились за прошлые тренировки и думаю сделаем ее, немного подумав. Как и прошлые задачи на двумерное ДП, эту задачу решаем интервально, постепенно увеличивая интервал до длины исходной строки. Ответ восстанавливаем по аналогичной схеме, как в 13С.
14D. Пирамиды
[pyramids]
Первое мое решение было очень тяжеловесным, но корректным. Опишу его вкратце: на плоскость OXY кладем треугольник ABC. A=(0,0), B= (AB,0). Координаты точки С можно вычислить. Точка D находилась над плоскостью OXY, т.е. Zd>0. Затем нужно было найти проекцию точки D на плоскость OXY. Эта задача сводилась в нахождению точки пересечения двух отрезков. Первый отрезок был возможной проекцией точки D при повороте треугольника ABD на произвольный угол относительно плоскости OXY. Второй отрезок получался из аналогичных рассуждений с треугольником ACD. Когда увидел авторское решение, понял, что перемудрил =). Здесь привожу именно авторское решение, т.к. в данной задаче оно куда уместнее. 
14E. Поле для крикета
Суть решения в переборе нижнего левого угла(O(N*N)) и последующий подбор максимально возможной длины поля с заданным углом. Именно подбор длины является очень интересной задачей.
[cricket] O(N*N*N*logN)
Первое, что пришло в голову это подобрать длину бинарным поиском, что затребует N*logN операций для каждого угла. Общая сложность нас устраивает и при аккуратной реализации получаем законный Accepted.
[cricket] O(N*N*N) 
Но есть более изящное и красивое решение за O(N).
14F. Электронная таблица
[sprsheet]
Задача, которая требует уже неплохой подготовки. Для начала давайте вспомним/узнаем:
1) Топологическую сортировку, которая поможет в нахождении циклических ссылок.
2) Подсчет арифметического выражения методом рекурсивного спуска (второй подход).
Значения ячейки можно хранить не в матрице, а в одномерном массиве.
Я попался на тесте, на котором была циклическая ссылка, не участвующая в подсчете ячейки A1. Получил досадный штраф =).

 
[Все решения]