Разбор VK Cup 2015 — Finals

Revision ru2, by Zlobober, 2015-07-30 21:05:00

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

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.

562B - Clique in the Divisibility Graph

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

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)

History

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