В письме ссылка должна быть

Первый отбор (в конце декабря) длился 3 часа.

Сегодняшний отбор будет идти 4 часа.

30

Переберем все пары городов. Далее найдем город x, лежащий на середине пути между текущими рассматриваемыми городами v и u. Расстояние h между городами можно узнать с помощью LCA, город, лежащий посередине между v и u, можно найти двоичным подъемом от более нижнего из городов u, v на h / 2.

Теперь рассмотрим два случая: когда расстояния h четно, и когда h нечетно. В первом случае для того, чтобы данная пара городов являлась "честной" необходимым и достаточным условием является выполненное равенство sz[x] == n — sz[anc[x]], где sz[v] — это размер поддерева с корнем v, anc[x] — предок вершины x. Аналогично для нечетного h необходимо проверить равенство sz[x] == n — sz[x]. Осталось аккуратно рассмотреть случай, когда h[v] = h[u]. В таком случае пара городов является честной, если sz[child[x][v]] == sz[child[x][u]], где child[x][y] — это непосредственный потомок вершины x в поддереве, содержащее вершину y.

Асимптотика O(N * N * logN).

Код: http://pastebin.com/X4WpB33W

Находим сжатую строку для данной. Дальше решаем для неё. Пусть у нас k строк s длины n. Для первых двух строк посчитаем префикс-функцию. Дальше пойдут значения n + 1, n + 2,.., (k — 1) * n — 1, (k — 1) * n. Строгого доказательства этого факта у меня нет.

http://pastebin.com/e6C6z8GA

рассмотрим текущую страницу: найдем для нее максимальный подотрезок 5рок и сравним его с ответом, потом найдем наибольший префикс и суффикс, ans = max(ans, prefSuffix + prefix) запомним суффикс и перейдем к следующей странице. код

Воспользуемся бинпоиском по ответу Для данного значения k будем за O(N) проверять, можно ли построить последовательность пятёрок длины k. Для этого заведём счётчик подряд идущих пятёрок cur, счётчик пятёрок с учётом стертой двойки cur1 и флаг, поднимая который мы говорим, что двойка уже взята. Соотв. Если флаг поднят и встретилась двойка, обнуляем все Если флаг опущен, поднимаем, обновляя cur. При переходе в следующий блок опускаем флаг. Всё. Хотя я сейчас сам не понимаю, зачем нам cur :D

"если одна из них LCA, то для нее количество вершин до, которых расстояние строго меньше, чем до другой равно n — кол-во сыновей второй вершины — расстояние между этими вершинами"

Потому что есть вершины, лежащие между текущей парой городов v и u (lca(v, u) = v), которые находятся ближе к v, чем к u.

Используя Алгоритм Дейкреста.

Я могу только предположить, так как я ее не сдал.

Пустим очередь с тремя параметрами x, y — положение клетки и z — направление.

Переходы будут двух типов:

1) по направлению(если клетка не проходима, то не будем делать переход)

2) мы не можем пойти по направлению, т.к. впереди не проходимая клетка, но в ней можно открыть портал. Посмотрим на свой путь от последнего прохода в портал, он будет от первой непроходимой клетки снизу до верхней. Мы можем перебрать эту клетку. Далее мы можем перейти либо в первую левую непроходимую клетку, либо в правую. (я рассмотрел случай когда наше направление up, для остальных случаев почти аналогично)

P.S: Это всего лишь мои мысли, может оказаться что это неправильно.

Ключевое соображение: мы можем считать, что один из порталов всегда впереди нас. Пусть мы находимся в клетке (x, y) и летим в сторону d (одну из четырех). Тогда мы можем либо пролететь на клетку вперед, либо выстрелить порталом в одну из трех оставшихся сторон, после чего имеет смысл лететь только вперед, пока не пролетим через этот портал. Получаем взвешенный граф на O(hw) вершинах, ищем в нем путь Дейкстрой.

Минимум камней:

Расположим в левом верхнем и нижнем правом углу min(a, b) и min(c, d) камней соответственно. Затем расположим в левом нижнем и верхнем правом углах min(b — min(a, b), d — min(c, d)) и min(a — min(a, b), c — min(c, d)) камней соответственно. Далее доложим в середины сторон камни так, чтобы суммарно получилось a, b, c, d камней на каждой стороне соответственно.

Данная расстановка является минимальной. Действительно, угол является по сути клеткой, принадлежащей обеим сторонам, им образованным. Следовательно каждый камень, который мы кладем в угол, как бы считается за два. Поскольку наша цель — минимизировать общее число камней, то необходимо как можно больше камней положить по углам, что и было сделано.

Максимум камней:

Ситуация противоположна — положим по углам минимально возможное число камней, а именно 0. Далее заполним середины сторон.

Код: http://pastebin.com/1DMW57Ed