olg2002 wrote:1. Формула вычисления следующего индекса выглядит коряво, но за ней скрывается очень простая и наглядная идея.
2. Случай N=16 оказывается слишком простым и приводит к неверным обобщениям. Для N=32 один такой цикл это
A5 -> A18 -> A9 -> A20 -> A10
т.е. если мы просто применим такой цикл ко всем нечетным индексам меньше N/2, то поскольку в этом конкретном цикле
встречаются 5 и 9, он будет применен два раза (это то же самое, что происходит в последнем алгоритме Aleksey Kudinov).
Если бы мы могли избежать повторного применения одного и того же цикла, мы бы получили решение на 4 балла.
Применим цикл ко всем нечетным индексам меньше N/2, где N=32, рассматриваем цепочки длины k, такое что N = 2^k
a) Запомним наименьшее значение индекса для всех уже рассмотренных цепочек global min
b) Находим наименьшее значение индекса для текущей цепочки local min
c) Если global min >= local min то отбрасываем цепочку
d) Производим обмены значениями
A16 -> A8 -> A4 -> A2 -> A1 (local min = A1)
A17 -> A24 -> A12 -> A6 -> A3 (local min = A3)
A18 -> A9 -> A20 -> A10 -> A5 (local min = A5)
A19 -> A25 -> A28 -> A14 -> A7 (local min = A7)
A20 -> A10 -> A5 -> A18 -> A9 (local min = A5)
A21 -> A26 -> A13 -> A22 -> A11 (local min = A11)
A22 -> A11 -> A21 -> A26 -> A13 (local min = A11)
A23 -> A27 -> A29 -> A30 -> A15 (local min = A15)
В цепочках нет дубликатов следственно число обменов меньше N.
Отступление 1:
Из этого кстати видно что количество дубликатов будет расти по логарифмическому закону
Число дубликатов = N * (k/4 - 1) = N * (log(N)/4 - 1)
Число дублирующих цепочек = N * (k/4 - 1)/k = N * (log(N)/4 - 1)/log(N)
Отступление 2:
По сути это задача нахождения Эйлерова цикла в графе. Для поиска Эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Ребра графа - это переходы, например A5 -> A18.
Так как есть ограничение по памяти то мы не можем кэшировать уже рассмотренные ребра. Но можем узнать есть ли значение в кэше или нет. Ребро не может находится больше чем в одном простом цикле графа. Сравнивая вершины с минимальными индексами ребер мы можем отсечь те циклы которые являются дубликатами существующих.
Сложность алгоритма линейно зависит от числа ребер (числа переходов) и равна O(N).
Спи быстрее, твоя подушка нужна другому. Copyright Зощенко