562A - Logistical Questions -------------- (в трансляции: 566C - Logistical Questions) Формализуем задачу. Нам дано необычное определение расстояния по дереву: ρ(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 - Clique in the Divisibility Graph -------------- (в трансляции: 566F - Clique in the Divisibility Graph) Упорядочим числа в искомой клике по возрастанию. Заметим, что чтобы множество X = {x₁, ..., x_k} образовывало клику, необходимо и достаточно, чтобы для (1 ≤ i ≤ k - 1). Таким образом, нетрудно сформулировать задачу динамического программирования: D[x] есть длина наибольшей подходящей возрастающей подпоследовательности, заканчивающейся в числе x. Формула пересчёта: по всем x, лежащим в A. Если оформлять задачу динамического программирования в виде динамики "вперёд", то легко оценить сложность получившегося решения: в худшем случае количество переходов есть . 562C - Restoring Map -------------- (в трансляции: 566E - Restoring Map) Назовём окрестностью вершины — множество, состоящее из вершины и всех _близких_ к ней вершин. Таким образом, нам известен набор окрестностей всех вершин в некотором произвольном порядке, причём каждая окрестность также перечислена в произвольном порядке. Назовём вершину дерева _внутренней_, если она не является листом дерева. Аналогично, назовём ребро дерева _внутренним_, если оно соединяет две внутренних вершины. Заметим, что если две окрестности пересекаются ровно по двум элементам 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 - Restructuring Company -------------- (в трансляции: 566D - Restructuring Company) Эта задача допускает множество решений с разными асимптотиками. Опишем решение за . Рассмотрим сначала задачу, в которой присутствуют только запросы второго и третьего типа. Её можно решить следующим образом. Отметим всех работников в ряд на прямой от 1 до n. Заметим, что отделы представляют собой отрезки из подряд идущих работников. Будем поддерживать эти отрезки в любой логарифмической структуре данных, например в сбалансированном дереве поиска (std::set или TreeSet). Объединяя все отделы с позиции x по позицию y, вытаскиваем все отрезки, попавшие в диапазон [x, y] и сливаем их. Для ответа на запрос третьего типа проверяем, лежат ли работники x и y в одном отрезке. Таким образом, мы получаем решение более простой задачи за на запрос. Добавляя запросы первого типа мы на самом деле разрешаем некоторым отрезкам на прямой относиться к одному и тому же отделу. Добавим в решение систему непересекающихся множеств, которая будет поддерживать классы эквивалентности на отрезках. Теперь запросы первого типа можно реализовать как вызов merge в системе непересекающихся множеств от номеров отделов, к которым принадлежат сотрудники x и y. Также в запросах второго типа надо не забывать вызывать merge от всех удаляемых отрезков. Получилось решение за время . 562E - Max and Min -------------- (в трансляции: 566G - Max and Min) Сформулируем задачу в геометрической интерпретации. У Макса и у Мина есть набор векторов из первой координатной четверти на плоскости и точка (x, y). За свой ход Макс может прибавить любой из имеющихся у него векторов к (x, y), а Мин — вычесть. Мин хочет добиться, чтобы точка (x, y) оказалась строго в третьей координатной четверти, Макс пытается ему помешать. Обозначим вектора Макса за Mx_i, вектора Мина за Mn_j. Сформулируем очевидное достаточное условие для Макса, чтобы тот мог выиграть. Рассмотрим некоторое неотрицательное направление на плоскости, т. е. вектор (a, b), такой что a, b ≥ 0, при этом хотя бы одно из чисел a, b — не ноль. Тогда если среди ходов Макса есть такой вектор Mx_i, что он не короче всех векторов Мина Mn_j вдоль направления (a, b), то Макс может гарантировать себе победу. Здесь под длиной вектора v вдоль направления (a, b) подразумевается скалярное произведение вектора v на вектор (a, b). Действительно, пусть Макс постоянно ходит в этот вектор Mx_i. Тогда за пару ходов Макса и Мина точка (x, y) сдвинется на вектор Mx_i - Mn_j для некоторого j, а значит её сдвиг вдоль вектора (a, b) составит ((Mx_i - Mn_j), (a, b)) = (Mx_i, (a, b)) - (Mn_j, (a, b)) ≥ 0. Значит, так как исходно скалярное произведение ((x, y), (a, b)) = ax + by > 0, то и в любой момент времени ax + by будет строго положительно. А значит, Мин ни в какой момент времени не сможет добиться чтобы x и y стали оба отрицательными (так как это значило бы, что ax + by < 0). Теперь сформулируем некоторый вариант обратного утверждения. Пусть вектор Макса Mx_i лежит строго внутри треугольника, образованного векторами Мина Mn_j и Mn_k. При этом, вектор Mx_i не может лежать на отрезке [Mn_j, Mn_k], но может быть коллинеарен одному из векторов Mn_j и Mn_k. Заметим, что раз Mx_i лежит строго внутри треугольника, натянутого на Mn_j и Mn_k, то его можно продлить до вектора Mx'_i, конец которого лежит на отрезке [Mn_j, Mn_k]. В силу линейной зависимости Mx'_i и Mn_j, Mn_k, имеем, что Mx'_i = (p / r)Mn_j + (q / r)Mn_k, где p + q = r и p, q, r — целые неотрицательные числа. Это эквивалентно rMx'_i = pMn_j + qMn_k, а значит, если на каждые r ходов Макса в Mx_i мы будем отвечать p ходами Мина в Mn_j и q ходами Мина в Mn_k, то суммарный сдвиг составит  - pMn_j - qMn_k + rMx_i =  - rMx'_i + rMx_i =  - r(Mx'_i - Mx_i), то есть вектор со строго отрицательными компонентами. Таким образом, мы можем мажорировать данный ход Макса, т. е. он ему невыгоден. Естественным образом возникает желание построить выпуклую оболочку на ходах Мина и посмотреть на все ходы Макса относительно неё. Если ход Макса лежит внутри выпуклой оболочки ходов Мина, то из предыдущего утверждения этот ход Максу невыгоден. В противном случае, возможно два варианта. Либо этот ход пересекает выпуклую оболочку, но выходит из неё наружу — в таком случае этот ход Макса не короче всех ходов Мина в некотором неотрицательном направлении, а значит Макс победил. Либо же, вектор Макса находится сбоку от выпуклой оболочки ходов Мина. Пусть для определённости вектор Mx_i В таком случае, требуется отдельный анализ. Рассмотрим самый верхний из векторов Мина. Если вектор Mx_i не ниже самого верхнего из ходов Макса Mx_j, то по первому утверждению Макс может выиграть, ходя исключительно в этот вектор. В противном же случае, как несложно видеть, разность Mn_i - Mx_j — это вектор со строго отрицательными компонентами, ходя в который мы можем мажорировать соответствующий вектор Макса. Значит, полная версия критерия победы Мина выглядит следующим образом. Рассмотрим выпуклую оболочку ходов Мина и продлим её от самой верхней точки влево и от самой правой точки вниз. Если все ходы Макса попадают строго внутрь образованной фигуры, то Мин побеждает. Иначе побеждает Макс. [problem:562F] -------------- Сформиурем бор из всех имён и псевдонимов. Отметим красным все вершины, соответствующие именам, и синим все вершины, соответствующие всем псевдонимам (одна вершина может быть отмечена несколько раз, в том числе разными цветами). Заметим, что если мы сопоставили имя a и псевдоним b, то качество такого сопоставления может быть выражено как lcp(a, b) = 1 / 2(2 * lcp(a, b)) = 1 / 2(|a| + |b| - (|a| - lcp(a, b)) - (|b| - lcp(a, b))), что представляет собой константу 1 / 2(|a| + |b|), из которой вычитается половина длины пути между a и b по бору. Таким образом, мы должны соединить все красные вершины с синими, минимизировав суммарную длину путей. Нетрудно видеть, что такая задача решается жадным образом следующей рекурсивной процедурой: если у нас есть вершина v, в поддереве которой x красных вершин и y синих вершин, то мы должны сопоставить min(x, y) красных вершин этого поддерева синим вершинам, а оставшиеся max(x, y) - min(x, y) красных или синих вершин "отдать" на уровень выше. Корректность данного алгоритма легко объясняется следующим соображением. Ориентируем ребро каждого пути по направлению от красной вершины к синей. Если ребро получает две разных ориентации, то два пути, на которых оно лежит, легко "развести", уменьшив их суммарную длину. Таким образом, получается несложное решение за O(sumlen), где sumlen — суммарная длина всех имён и псевдонимов. (в трансляции: [problem:566A]) [problem:562G] -------------- (в трансляции: [problem:566B]) Эту задачу можно решить симулируя процесс реплицирования. Будем к каждому шагу поддерживать список всех репликаций, которые в текущий момент можно применить. Применяем любую репликацию, после чего обновляем список, добавляя/удаляя все подходящие или переставшие быть подходящими репликации со всех затронутых на данном шаге серверов. Список репликаций можно поддерживать в структуре данных "двусвязный список", которая позволяет за O(1) добавлять и удалять элемент в/из множества и вынимаь произвольный элемент множества. Доказательство корректности этого алгоритма несложно и оставляется как упражнение (впрочем, если будет большое количество желающих, оно появится здесь позднее). Получается решение за O(n) операций (впрочем, константа, скрытая за O-нотацией весьма немаленькая — один только ввод составляет 12n чисел, да и само решение оперирует по меньшей мере константой 36).