Всем спасибо за участие! Задачи следуют в порядке, в котором они шли на оригинальном соревновании.

562A - Логистические вопросы

(в трансляции: 566C - Логистические вопросы)

Формализуем задачу. Нам дано необычное определение расстояния по дереву: ρ(a, b) = dist(a, b)^1.5. У каждой вершины есть её вес w_i. Нужно как-то так выбрать место x для проведения соревнования, чтобы минимизировать сумму взвешенных расстояний от всех вершин до неё: f(x) = w₁ρ(1, x) + w₂ρ(x, 2) + ... + w_nρ(x, n).

Давайте изучим свойства функции f(x). Мысленно разрешим себе ставить точку x не только в вершины дерева, но и в любую точку на ребре, доопределив естественным образом расстояние от точки внутри ребра до всех остальных вершин (например, середина ребра длины 4 находится на обычном расстоянии 2 от концов ребра).

Утверждение 1. На любом пути в дереве функция ρ(i, x) является выпуклой вниз. Действительно, функция dist(i, x) на любом пути выглядит как график функции abs(x), то есть сначала линейно убывает до ближайшей к i точки на пути [a, b], а потом линейно возрастает. Взяв композицию с выпуклой возрастающей функциея t^1.5, как нетрудно видеть, мы снова получим выпуклую вниз на пути функцию. Здесь под функцией на пути мы подразумеваем обычную функцию действительной переменной x, где под x мы подразумеваем координату точки x на пути [a, b], или, что то же самое, dist(a, x). Таким образом, каждое из слагаемых в определении функции f(x) выпукло вниз на любом пути в дереве, а значит и функция f(x) выпукла на любом пути в дереве.

Будем называть функции, выпуклые вниз на любом пути в дереве выпуклыми на дереве. Сформулируем пару утверждений про выпуклые функции на дереве.

Утверждение 2. У выпуклой на дереве функции не может быть двух различных локальных минимумов. Действительно, в противном случае на пути между двумя этими минимумами функция сначала возрастает, а в конце убывает, что нарушает условие на выпуклость на этом пути.

Таким образом, у выпуклой вниз функции f(x) есть единственный локальный минимум на дереве, совпадающий с глобальным.

Утверждение 3. Из каждой вершины v дерева существует не более одного ребра, при движении по которому функция убывает. Действительно, в противном случае, если рассмотреть путь, образованный двумя такими рёбрами, то в точке, соответствующей вершине v, функция не будет выпукла вниз.

Назовём направление ребра из вершины v, при движении по которому убывает функция, градиентом функции f в точке x. Согласно утверждению 3, у выпуклой вниз функции f в любой вершине либо однозначно определён градиент, либо вершина является минимумом (глобальным).

Предположим, мы умеем некоторым образом эффективно искать направление градиента из вершины v. Научимся, пользуясь этим знанием и утверждениями 2 и 3 находить глобальный минимум. Если бы наше дерево представляло собой бамбук, то задача бы стала обычной одномерной задачей минимизации выпуклой функции, которая эффективно решается бинарным поиском, т. е. дихотомией. Нам же нужен некоторый эквивалент дихотомии на дереве. Что же это за эквивалент?

Воспользуемся centroid decmoposition! Действительно, возьмём центр дерева (т. е. такую вершину, что размеры всех её поддеревьев не превосходят n / 2). По утверждению 3 можно рассмотреть градиент функции в центре дерева. Во-первых, у функции может не оказаться градиента в центре дерева, что значит, что мы уже нашли оптимум. Иначе, мы знаем, что глобальный минимум расположен именно в поддереве в направлении градиента, значит все остальные поддеревья и сам центр можно выбросить из рассмотрения и оставить только выбранное поддерево. Таким образом, за один подсчёт градиента мы сократили в два раза количество вершин в рассматриваемой части дерева.

Значит, за подсчётов градиента мы практически научились решать задачу. Осталось только понять, где именно расположен ответ. Заметим, что глобальный оптимум, скорее всего, окажется внутри какого-то ребра. Тогда, как нетрудно видеть, оптимальной вершиной является один из концов этого ребра, а именно, одна из двух последних рассмотренных в процессе нашего алгоритма вершин. В какой именно можно определить, явно вычислив значение функции в них и взяв меньшее.

Теперь научимся считать направление градиента в вершине v. Зафиксируем одно поддерево u_i вершины v. Рассмотрим производную всех слагаемых, соответствующих поддереву u_i при движении в поддерево u_i, и обозначим её за der_i. Тогда, как нетрудно видеть, производная f(x) при движении от x = v в сторону поддерева u_i есть  - der₁ - der₂ - ... - der_i - 1 + der_i - der_i + 1 - ... - der_k, где k — степень вершины v. Таким образом, мы можем за один запуск обхода из вершины v определить все вершины der_i, а значит, и направление градиента, найдя с помощью формулы выше направление, в котором производная функции отрицательна.

Таким образом, получилось решение за .

562B - Клика в графе делителей

(в трансляции: 566F - Клика в графе делителей)

Упорядочим числа в искомой клике по возрастанию. Заметим, что чтобы множество X = {x₁, ..., x_k} образовывало клику, необходимо и достаточно, чтобы для (1 ≤ i ≤ k - 1). Таким образом, нетрудно сформулировать задачу динамического программирования: D[x] есть длина наибольшей подходящей возрастающей подпоследовательности, заканчивающейся в числе x. Формула пересчёта: по всем x, лежащим в A.

Если оформлять задачу динамического программирования в виде динамики "вперёд", то легко оценить сложность получившегося решения: в худшем случае количество переходов есть .

562C - Восстановление карты

(в трансляции: 566E - Восстановление карты)

Назовём окрестностью вершины — множество, состоящее из вершины и всех близких к ней вершин. Таким образом, нам известен набор окрестностей всех вершин в некотором произвольном порядке, причём каждая окрестность также перечислена в произвольном порядке.

Назовём вершину дерева внутренней, если она не является листом дерева. Аналогично, назовём ребро дерева внутренним, если оно соединяет две внутренних вершины. Заметим, что если две окрестности пересекаются ровно по двум элементам a и b, то a и b обязаны быть соединены ребром, причём ребро (a, b) является внутренним. Наоборот, любое внутреннее ребро (a, b) может быть найдено как пересечение каких-то двух окрестностей С и D двух вершин c и d, таких что в дереве есть путь c – a – b – d. Таким образом, мы можем найти все внутренние рёбра, рассмотрев попарные пересечения всех окрестностей. Это можно сделать за время порядка n³ / 2 наивно, либо в 32 раза быстрее, воспользовавшись битовым сжатием.

Заметим, что зная все внутренние рёбра, мы можем узнать все внутренние вершины, за исключением случая, когда граф представляет из себя звезду (т. е. вершину, к которой подцеплены все остальные). Случай звезды нужно разобрать отдельно.

Теперь мы знаем все листы, все внутренние вершины и структуру дерева на внутренних вершинах. Осталось только определить для каджого листа, к какой внутренней вершине он подцеплен. Это можно сделать следующим образом. Рассмотрим лист l. Рассмотрим все окрестности, его содержащие. Рассмотрим минимальную по включению окрестность — утверждается, что это есть окрестность L, соответствующая самому листу l. Рассмотрим все внутренние вершины в L. Их не может быть меньше двух. Если их три или более, то мы можем однозначно определить, к какой из них надо подцепить l — это должна быть та вершина из них, которая имеет степень внутри L больше единицы. Если же их ровно две (скажем, a и b), то определить, к кому из них надо подцепить l, несколько сложнее.

Утверждение: l должна быть подсоединена к той из двух вершин a и b, у которой степень по всем внутренним рёбрам — ровно один. Действительно, если бы l была подсоединена к вершине со внутренней степнью два или более, мы бы рассмотрели этот случай ранее.

Если же у обоих вершин a и b внутренняя степень — 1, то наш граф имеет вид гантели (ребро (a, b), и все остальные вершины, подцепленные либо за a, либо за b). Такой случай также придётся разобрать отдельно.

Разбор двух специальных случаев оставляется пытливому читателю как несложное упражнение.

562D - Реструктуризация компании

(в трансляции: 566D - Реструктуризация компании)

Эта задача допускает множество решений с разными асимптотиками. Опишем решение за .

Рассмотрим сначала задачу, в которой присутствуют только запросы второго и третьего типа. Её можно решить следующим образом. Отметим всех работников в ряд на прямой от 1 до n. Заметим, что отделы представляют собой отрезки из подряд идущих работников. Будем поддерживать эти отрезки в любой логарифмической структуре данных, например в сбалансированном дереве поиска (std::set или TreeSet). Объединяя все отделы с позиции x по позицию y, вытаскиваем все отрезки, попавшие в диапазон [x, y] и сливаем их. Для ответа на запрос третьего типа проверяем, лежат ли работники x и y в одном отрезке. Таким образом, мы получаем решение более простой задачи за на запрос.

Добавляя запросы первого типа мы на самом деле разрешаем некоторым отрезкам на прямой относиться к одному и тому же отделу. Добавим в решение систему непересекающихся множеств, которая будет поддерживать классы эквивалентности на отрезках. Теперь запросы первого типа можно реализовать как вызов merge в системе непересекающихся множеств от номеров отделов, к которым принадлежат сотрудники x и y. Также в запросах второго типа надо не забывать вызывать merge от всех удаляемых отрезков.

Получилось решение за время .

562E - Макс и Мин

(в трансляции: 566G - Макс и Мин)

562F - Подбор имён

(в трансляции: 566A - Подбор имён)

562G - Репликация процессов

(в трансляции: 566B - Репликация процессов)