Разбор VK Cup 2015 — Finals

Правка ru8, от Zlobober, 2015-07-30 21:21:43

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

562A - Logistical Questions

(в трансляции: 566C - Logistical Questions)

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

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

Утверждение 1. На любом пути в дереве функция ρ(i, x) является выпуклой вниз. Действительно, функция dist(i, x) на любом пути выглядит как график функции abs(x), то есть сначала линейно убывает до ближайшей к i точки на пути [a, b], а потом линейно возрастает. Взяв композицию с выпуклой возрастающей функциея t1.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. Зафиксируем одно поддерево ui вершины v. Рассмотрим производную всех слагаемых, соответствующих поддереву ui при движении в поддерево ui, и обозначим её за deri. Тогда, как нетрудно видеть, производная f(x) при движении от x = v в сторону поддерева ui есть  - der1 - der2 - ... - deri - 1 + deri - deri + 1 - ... - derk, где k — степень вершины v. Таким образом, мы можем за один запуск обхода из вершины v определить все вершины deri, а значит, и направление градиента, найдя с помощью формулы выше направление, в котором производная функции отрицательна.

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

562B - Clique in the Divisibility Graph

(в трансляции: 566F - Clique in the Divisibility Graph)

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

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

562C - Restoring Map

(в трансляции: 566E - Restoring Map)

562D - Restructuring Company

(в трансляции: 566D - Restructuring Company)

562E - Max and Min

(в трансляции: 566G - Max and Min)

562F - Matching Names

(в трансляции: 566A - Matching Names)

562G - Replicating Processes

(в трансляции: 566B - Replicating Processes)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en17 Английский Zlobober 2015-07-31 00:14:11 1476
en16 Английский Zlobober 2015-07-31 00:03:21 2448
en15 Английский Zlobober 2015-07-30 23:55:15 8371
ru19 Русский Zlobober 2015-07-30 23:30:29 134
en14 Английский Zlobober 2015-07-30 23:29:46 2420
en13 Английский Zlobober 2015-07-30 23:08:34 5839
en12 Английский Zlobober 2015-07-30 22:55:43 1241
ru18 Русский Zlobober 2015-07-30 22:48:21 19
en11 Английский Zlobober 2015-07-30 22:48:06 19
ru17 Русский Zlobober 2015-07-30 22:47:47 19 (опубликовано)
en10 Английский Zlobober 2015-07-30 22:47:16 4
en9 Английский Zlobober 2015-07-30 22:47:07 138
en8 Английский Zlobober 2015-07-30 22:46:12 66
en7 Английский Zlobober 2015-07-30 22:45:40 9434
en6 Английский Zlobober 2015-07-30 22:23:52 62 Initial revision for English translation
en5 Английский Zlobober 2015-07-30 22:23:00 152 Initial revision for English translation
en4 Английский Zlobober 2015-07-30 22:19:53 21 Initial revision for English translation
en3 Английский Zlobober 2015-07-30 22:19:31 22 Initial revision for English translation
en2 Английский Zlobober 2015-07-30 22:19:06 14 Initial revision for English translation
en1 Английский Zlobober 2015-07-30 22:18:47 16596 Initial revision for English translation
ru16 Русский Zlobober 2015-07-30 22:16:35 216
ru15 Русский Zlobober 2015-07-30 22:15:29 6028
ru14 Русский Zlobober 2015-07-30 21:42:27 3190
ru13 Русский Zlobober 2015-07-30 21:26:10 785
ru12 Русский Zlobober 2015-07-30 21:23:01 14 Мелкая правка: 'text{if}~y,2015-07-30~\vert~x))$' -> 'text{if}~y ~ \vert~x))$'
ru11 Русский Zlobober 2015-07-30 21:22:43 2 Мелкая правка: 'text{if}~y,2015-07-30~\vert~x))$' -> 'text{if}~y ~ \vert~x))$'
ru10 Русский Zlobober 2015-07-30 21:22:17 0 Мелкая правка: 'тобы $x_i~|~x_,2015-07-30{i+1}$ для' -> 'тобы $x_i~\bar~x_{i+1}$ для'
ru9 Русский Zlobober 2015-07-30 21:22:01 17 Мелкая правка: 'тобы $x_i~|~x_,2015-07-30{i+1}$ для' -> 'тобы $x_i~\bar~x_{i+1}$ для'
ru8 Русский Zlobober 2015-07-30 21:21:43 5 Мелкая правка: 'тобы $x_i~|~x_,2015-07-30{i+1}$ для' -> 'тобы $x_i~\bar~x_{i+1}$ для'
ru7 Русский Zlobober 2015-07-30 21:21:26 16 Мелкая правка: 'тобы $x_i~|~x_,2015-07-30{i+1}$ для' -> 'тобы $x_i~\bar~x_{i+1}$ для'
ru6 Русский Zlobober 2015-07-30 21:18:43 0 Мелкая правка: 'text{if}~y,2015-07-30~|~x,2015-07-30))$ по все' -> 'text{if}~y~|~x))$ по все'
ru5 Русский Zlobober 2015-07-30 21:18:43 7 Мелкая правка: 'text{if}~y,2015-07-30~|~x,2015-07-30))$ по все' -> 'text{if}~y~|~x))$ по все'
ru4 Русский Zlobober 2015-07-30 21:18:40 0 Мелкая правка: 'text{if}~y,2015-07-30~|~x,2015-07-30))$ по все' -> 'text{if}~y~|~x))$ по все'
ru3 Русский Zlobober 2015-07-30 21:12:54 1028
ru2 Русский Zlobober 2015-07-30 21:05:00 4609
ru1 Русский Zlobober 2015-07-30 20:26:09 615 Первая редакция (сохранено в черновиках)