** UPD : Считается, что все формулы уже исправлены **

163A - Подстрока и подпоследовательность

Кратко о решении: динамика.

Одно из авторских решений: 1415300 (автор = levlam)

Задача решалась следующей динамикой. Пусть f[i, j] — количество равных пар вида "подстрока начинающаяся в позиции i" и "подпоследовательность подстроки t[j..|t|]".

Тогда:

f[i, j] = f[i, j + 1];
if (s[i] == t[j])
  add(f[i, j], f[i + 1, j + 1] + 1)

Answer = f[i,0]

163B - Лемминги

Кратко о решении: сортировка + бинпоиск по ответу.

Одно из авторских решений: 1415306 (автор: Burunduk1)

Нам нужно найти минимальное время T. Давайте сделаем бинарный поиск по ответу.

После этого можно расставлять леммингов жадно или снизу вверх, или сверху вниз. В этом разборе я воспользуюсь способом <снизу вверх>. Из тех леммингов, которые могут забраться на 1-й уступ, выберем лемминга с минимальной массой, а из таких — с минимальной скоростью. Почему так можно сделать? Пусть мы поставили на первый уступ лемминга с большой массой, значит, всех леммингов с меньшей массой мы использовать уже не можем, значит, можно было поставить на первый уступ любого лемминга с меньшей массой. А из леммингов с одинаковой массой всегда выгодно оставить тех, чья скорость больше, они могут залезть на более высокие уступы.

Чтобы быстро расставлять леммингов в таком порядке, отсортируем их заранее, сравнивая сперва по массе, затем по скорости. После этого мы рассматриваем всех леммингов в порядке возрастания массы ровно один раз и каждого или берем, или не берем. Второй раз рассматривать лемминга не имеет смысла, т.к. или мы его уже взяли на i-й уступ (он занят) или мы его на i-й уступ взять не смогли, тогда на i + 1-й и т.д. тоже не сможем.

Итого решение = сортировка + бинпоиск по ответу с линейным проходом внутри. Время работы = O(Nlog?)

Но написать бинпоиск и верную жадность в этой задаче было не достаточно для получения Accepted. Нужно было еще не попасться на проблемы с точностью. Давайте точно оценим число итераций бинпоиска.

0 ≤ T ≤ H * K (максимальное время не больше 10⁹). Нужно понять, насколько могут отличаться два времени. В случае "N = K = 10⁵, H = 10⁴, V порядка 10⁹" времена, за которые некоторые два лемминга поднимаются на какие-то уступы, могут отличаться на 10^- 18. Это следует из того, что времена = рациональные дроби , где X и Y порядка 10⁹.

Т.е. нам нужно сделать число итераций = log₂10²⁷ = 90. На практике моему решению 70 итераций не хватало, а вот 75 было уже достаточно. Рассуждения выше показывают, что 90 точно хватит.

163C - Конвейер

Кратко о решении: события на окружности или бинпоиск.

Одно из авторских решений: 1415310 (автор: Burunduk1)

Одно из авторских решений: 1415316 (автор: arseny30)

Антон, откуда бы он ни начал, пробежит по конвейеру отрезок длины D = (v₂ * l) / (v₁ + v₂). Рассмотрим одну конфету. Чтобы ее скушать, нужно попасть на конвейер в любой момент из отрезка [ a_i — D .. a_i ]. Рассмотрим все точки вида a[i] — D и a[i] , если какие-то из них отрицательны, прибавим 2 * l. Также не забудем добавить в массив точек числа 0 и 2 * l. Отсортируем эти точки. Рассмотрим теперь две соседние — x[i] и x[i+1]. В какой бы момент времени между этими двумя точками Антон ни начал, он съест одно и то же количество конфет.

С этого момента можно получить одно из двух решений:

1) Запуститься от каждой середины отрезка M = (x[i] + x[i+1]) / 2 и бинпоиском по отсортированному удвоенному массиву a найти количество конфет на отрезке [M..M + D].

2) Сказать, что у нас есть события на окружности вида (a[i]-D,+1) и (a[i],-1). Нужно пройти по кругу два раза, и на втором проходе говорить, что мы знаем, сколько раз покрыт текущая точка конфетами-отрезками.

Оба решения работают за время O(NlogN).

163D - Большой холодильник

Кратко о решении: перебор с отсечением по ответу

Одно из авторских решений: 1415320 (автор: Burunduk1)

Решение состоит из трех главных идей:

1. V = ABC, A ≤ B ≤ C тогда A ≤ N^1 / 3, B ≤ (N / A)^1 / 2.

2. A и B — делители V, а поскольку нам уже дано разложение числа V на простые множители, можно перебирать только делители

3. Если зафиксировано A, то оптимальные вещественные B и C = (N / A)^1 / 2 (обозначим эту величину за X). Т.е. площадь поверхности получится в любом случае  ≥ 2(2AX + X²). Таким образом можно использовать отсечение по ответу.

Если применение в лоб этих идей давало TL, то можно было воспользоваться следующими оптимизациями:

1. Отсечение по ответу лучше работает, если перебирать A в порядке убывания

2. A и B — 32-битные целые.

3. Если мы для числа V уже считали ответ, то нужно запомнить ответ (таким образом мы чуть уменьшили max тест).

Если кому-то интересно теоретическое обоснование "Почему это все работает за нужное время?", приведу некоторую статистику:

1. Максимальное количество делителей у чисел от 1 до 10¹⁸ = 103860 (у числа 897612484786617600 = 2⁸3⁴5²7²11 ...)

2. Если использовать только 2 первые оптимизации, количество чисел A, которое переберет наше решение = 10471 (на числе с max количеством делителей)

3. Если использовать только 2 первые оптимизации, количество пар A и B, которое переберет наше решение = 128264 (на числе с max количеством делителей).

163E - Электронное правительство

Кратко о решении: Ахо-Корасик + сумма на пути в дереве суффиксных ссылок

Одно из авторских решений: 1415345 (автор: arseny30)

Предполагается, что читатель знаком с алгоритмом Ахо-Корасик (прочитать о нем можно здесь http://e-maxx.ru/algo/aho_corasick).

Пусть у нас есть бор имен и суффиксные ссылки на этом боре. Также для каждой вершины v посчитано количество имен, кончающихся в этой вершине (end[v]).

Тогда добавить имя i: end[v[i]] += 1, где v[i] — вершина-конец i-го имени

Удалить имя i: end[v[i]] -= 1.

Чтобы ответить на запрос "политизированность текста", нужно увидеть, что суффиксные ссылки образуют дерево. Когда мы проходимся по тексту и параллельно ходим по бору с суффиксными ссылками, если мы находимся в вершине бора v, нужно прибавить к политизированности сумму end[v[i]] на пути по суффиксным ссылкам от v до корня дерева. Теперь нужно научиться быстро решать задачу <сумма весов вершин на пути до корня, веса меняются>.

Это можно сделать например так:

1. Говорим, что вес не в вершине, а на ребре, соединяющем вершину с ее отцом.

2. Храним Эйлеров обход дерева, в котором при спуске вниз записан плюс вес ребра, а при подъеме наверх минус вес ребра.

3. Сумма на пути до корня = сумма на отрезке в Эйлеровом обходе (концы отрезка — произвольные вхождения двух вершин в Эйлеров обход).

Быстрый и удобный способ считать сумму на отрезке — дерево Фенвика.

Мы получили решение работающее за время O(|SumLen| * log). Памяти используется |SumLen| * 26 (бор мы храним не сжатым).