A. Дана строка...

Переберём все подстроки, начиная с самых длинных, и для каждой посчитаем, сколько раз она встречается. Сложность — O(L⁴) с маленькой константой.

B. Вечеринка

Ясно, что хотя бы один человек (тот, у кого меньше всех знакомых) должен уйти. Докажем, что должны уйти хотя бы двое. Действительно, пусть ушел только один человек, и у него d знакомых. Тогда у остальных до его ухода было больше d знакомых, а после его ухода стало меньше, чем d + 1, то есть не больше d. Значит, его уход повлиял на количество знакомых у каждого из оставшихся, то есть он знаком со всеми: d = N - 1. Но у него меньше всех знакомых — противоречие.

Итак, ответ не больше N - 2. Покажем, что N - 2 человека могли остаться (если, конечно, N > 1). Организуем граф знакомств следующим образом: возьмем полный граф на N вершинах и удалим одно ребро. Тогда степени двух вершин равны N - 2, а степени остальных N - 1. После удаления первых двух вершин остается полный граф на N - 2 вершинах, и все степени равны N - 3, поэтому больше никто не уйдет.

C. Апельсины и яблоки

Отсортируем ящики в порядке возрастания числа апельсинов. Посчитаем общее число яблок в ящиках с нечетными и четными номерами. Если в ящиках с нечетными номерами яблок не меньше половины, то выберем их (их ровно N). Если же в ящиках с четными номерами яблок не меньше половины, то возьмем их и добавим к ним самый последний ящик (в котором больше всего апельсинов). Нетрудно видеть, что в обоих случаях требуемые условия выполнены.

D. Четырёхугольник

Пусть ABCD — искомый четырёхугольник, а K, L и M — середины равных сторон AB, BC и CD соответственно. Пусть M' — точка, симметричная M относительно L. Тогда BM' = CM = CL = BL = BK, то есть B — центр описанной окружности треугольника KLM'.

Зная B, можно восстановить весь четырёхугольник с помощью симметрий относительно точек K, L и M, и затем проверить, выполнены ли для него условия строгой выпуклости и равенства сторон.
Заметим, что мы не знаем, какая из данных точек является точкой L, поэтому нужно проверить все 3 варианта.

E. Дерево

Лемма. В одном из оптимальных решений отсутствуют простые пути длины 3.
Доказательство. Из такого пути можно выкинуть среднее ребро. Тогда компонента связности распадётся на две компоненты размеров a и b, причём a ≥ 2, b ≥ 2, поэтому ab ≥ a + b.

Подвесим данное дерево за любую вершину. Будем рекурсивно вычислять следующие величины: h_v — решение задачи для поддерева с корнем v и f_v — произведение h_u по всем сыновьям v. Для листов h_v = f_v = 1.

Покажем, как вычислить h_v, зная решение для всех поддеревьев v. Рассмотрим компоненту связности v в оптимальном решении. Из леммы следует, что она имеет один из следующих видов:
1. Единственная вершина v.
2. Вершина v и несколько её сыновей.
3. Вершина v, один её сын — w и несколько сыновей w.

В первом случае результат игры равен f_v.

Во втором случае он равен Πf_i · Πh_j · k = Π(f_i / h_i) · f_v · k, где i пробегает сыновей, входящих в компоненту, j — остальных сыновей, а k есть размер компоненты. Поскольку мы хотим максимизировать это выражение, нас интересуют сыновья с как можно большим значением f_i / h_i. Поэтому наилучший результат во втором случае равен максимуму по s Π_i ≤ s  (f_i / h_i) · f_v · (s + 1), где считается, что сыновья отсортированы по убыванию f_i / h_i.

В третьем случае для каждого сына w можно провести аналогичные рассуждения. Наилучший результат будет равен максимуму по w и s выражения f_v · (f_w / h_w) · Π_i ≤ s (f_i / h_i) · (s + 2); отметим, что сыновья w уже были отсортированы на предыдущем шаге рекурсии.

Таким образом, количество операций, необходимых для определения f_v, пропорционально суммарному количеству сыновей и внуков v, что не превосходит n. Следовательно, сложность алгоритма (не учитывая операции с длинными числами) — O(n²).


P. S. Приношу извинения за формулы, похоже рендерер латеха сломался. Добавления и замечания приветствуются.