Тренировка 28.09.2013

A. Траектория центра мяча - парабола идущая в одной вертикальной плоскости. Обрежем эту параболу по расстоянию до пола. После этого нам нужно проверить, пересекает ли этот кусок параболы данный в условии круг (причем пересечение было на падающей вниз части параболы) и если да, то найти расстояние от окружности кольца до этой параболы (чтобы сравнить его с радиусом мяча). Для этого найдем ближайшую к кольцу точку параболы. Если разбить окружность на 4 части (параллельно и перпендикулярно плоскости параболы), то на каждом участке функция расстояния будет унимодальной и минимум можно будет найти тернарны поиском. Другой вариант - это разбить параболу на кучу частей (10000) и на каждой искать тернарным поиском ближайшую точку к окружности.
B. Идея решения в применении формулы включений и исключений. Для каждого X храним сет встретившихся с ним в паре Y и сет встретившихся с ним в паре Z (аналогично для остальных координат). Когда добавляется новый выстрел пусть вдоль оси Z с координатами x0,y0 проверяем, что такого выстрела еще не было, вычитаем из ответа S, затем прибавляем размеры сетов x0 по Z и y0 по Z. Теперь остается вычесть размер пересечения этих двух сетов. Можно искать его амортизационно за n\sqrt{n}log n, всегда проверяя наличие каждого элемента меньшего сета в большем.
C. Проверяем возможность отдельно для каждой буквы. Можно показать, что если сопоставление существует, то существует и монотонное сопоставление (не меняющее относительного порядка по часовой стрелке). Тогда это сопоставление можно найти перебором.
D. Нужно промоделировать то, что написано в условии.
E. Понятно, что если n нечетное, то разбиение может быть только вида, 2+(n-2) и остается только проверить n-2 на простоту. Если n четное, то согласно сильной гипотезе Гольдбаха (недоказанной, но уж точно проверенной для всех чисел меньших 2^32) оно представимо в виде суммы двух простых. В данной задаче проходила следующая эвристика - генерим все простые до 10^6, потом перебираем эти простые, для каждого n-p_i проверяем его на простоту до тиех пор пока не найдем ответ. Проверять простоту можно как Рабином-Миллером, так и обычной проверкой до корня, заходит все, что угодно.
F. Будем проверять независимо для каждого из 4 направлений, можно ли по нему добраться. Ясно, что с точностью до симметрии нужно уметь проверять горизонтальное и диагональное направления. Чтобы уметь проверять горизонтальное направление (имеет смысл это делать, только если горизонтали у начальной и конечной точки совпадают), достаточно иметь сохраненные отсортированные массивы запрещенных клеток с данной Y координатой и за логарифм проверять есть ли что-то в этом массиве между начальной и конечной точкой. Добраться по диагонали с направлением (1,1) можно, только если (x2-x1)-(y2-y1) кратно gcd(n,m). Далее в этом случае также нужно проверить, есть ли на пути между ними запрещенные точки. Для этого нужно уметь находить порядковый номер заданной точки на соответсвующей торической прямой - это делается решением диофантового уравнения.
G. Будем проверять на пересечение отрезки(стороны прямоугольников) и локатор. Для этого достаточно найти угол обзора отрезка и пересечь его с углом обзора локатора
H. Достаточно добавлять измерения по очереди (сразу всех людей из измерения). Состоянием динамики будет маска заполненности строчек (порядок внутри строчки нигде не важен), всего состояний 7^6. Переход - все возможные маски того, как можно добавить очередное множество людей так, чтобы все были в разных строчках, это не больше C_6^3=20 способов, либо ничего не добавлять (это случай когда кто-то из них в одной строке, и в целевую функцию ничего не добавит. Можно считать, что мы просто добавляем все измерения, которые не давали профита в конце)
I. Генерим хэши, чтобы сравнивать любые две подстроки равной длины за O(1). Теперь решаем задачу динамикой с линейным числом состояний (и с пересчетом за K). Состояние - можем ли мы преобразовать суффикс S длины l в префикс S' длины l. Пересчет - перебор дилны последнего выстреленного суффикса.
J. Конструктив.