Вот и настало время для первого поста в моём блоге. Отнюдь это не будет кулинарный блог или для тех любителей кайпериньи с хорошей кашасой мегафуло и свежим лаймом...
Данный блог будет большей частью посвящён разбору наиболее интересных задач и алгоритмов с известного сервера задач
acm.sgu.ru. Как мне кажется именно здесь можно найти хоть и небольшое, но в тоже время уникальное множество задач олимпиадного программирования. На текущий момент не предполагается какого-то упорядочивания задач по уровню сложности или по тематикам, материал будет излагаться по мере решения той или иной задачи.
Итак, приступим к трапезе:
В качестве обеденного филе миньён хотелось бы изведать задачу
122. The Book. На мой взгляд задача интересная так как заставляет подумать.
Сразу стоит обратить внимание, что формулировка задачи точь-в-точь как и задача поиска
Гамильтонова цикла на графе. Как известно эта задача относится к числу NP полных, а ограничение говорит нам о 1000 вершин в графе, так что же делать... Замечу сразу, что ответ No Solution - невозможен, ибо согласну теореме Дирака, формулировку которой можно почитать всё на той же wiki статье, для данного графа всегда существует Гамильтонов цикл... Ну чтож дело за малым - отыскать его.
Как будем действовать?
Итеративно будем делать следующее.
1) Очевидно, что можно найти простой путь состоящий из (n+1)/2 вершин, итак получим текущее состояние в минимум (n+1)/2 вершин.
На каждом шаге, если можно продолжить путь из конечной вершины пути, либо начать из начальной, будем расширять ответ. Т.е. имея последовательность вершин X1,X2,X3,...,Xk мы можем либо перейти в состояние X1,X2,X3,...,Xk,Xk+1 такое, что каждая из вершин в данной последовательности смежна предыдущей, либо в X0,X1,X2,X3,...,Xk.
В случае если невозможно совершить вышеозначенные переходы, то
2) Возьмём одну из непросмотренных ранее вершин(т.е. не входящую в текущий ответ).
2.1) Если конечная и начальная вершина текущего пути - смежны, то мы можем перестроить путь с учётом новой добавленной вершины. Допустим имеем X1,X2,X3,...,Xk и взята вершина Xi не просмотренная ранее. Очевидно, что хотя бы одна из вершин X1,.., Xk смежна Xi (k>=(n+1)/2), например Xm. Поэтому новый путь может быть получен как Xi,Xm,Xm-1,...,X1,Xk,Xk-1..Xm-1. Таким образом получим путь на 1 вершину длиннее.
2.2) X1 и Xk не смежны. Тогда необходимо перестроить текущий путь таким образом что бы он по прежнему оставался простым и новые X1 и Xk были смежны и далее применить пункт 2.1. Предлагаю самостоятельно продумать этот момент, в задаче он является достаточно важным.
В конечном итоге мы придем к ситуации, что все вершины будут пройдены и останется лишь правильно сформировать ответ.
