Блог

Нам дается массив с числами от 1 до n (без дубликатов), где n = размер массива. Нам разрешено выполнить следующую операцию :
arr[i] = arr[arr[i]-1] , 0 <= i < n

Теперь считается одна итерация, когда мы выполняем описанную выше операцию со всем массивом. Наша задача — найти количество итераций после того, как мы столкнемся с ранее встреченной последовательностью.

 Constraints :  
a) Array has no duplicates
b) 1 <= arr[i] <= n , 0 <= i < n  
c) 1 <= n <= 10^6  
 

Пример 1:

 n = 5  
arr[] = {5, 4, 2, 1, 3}  

  
After 1st iteration array becomes : {3, 1, 4, 5, 2}  
After 2nd iteration array becomes : {4, 3, 5, 2, 1}  
After 3rd iteration array becomes : {2, 5, 1, 3, 4}  
After 4th iteration array becomes : {5, 4, 2, 1, 3}    
In the 4th iteration, the sequence obtained is already seen before  
So the expected output is 4.
 

Этот вопрос был задан в одном из тестов по найму на работу, поэтому у меня нет никакой ссылки на этот вопрос.
Было дано 2 примера тестовых примеров, из которых я помню тот, который приведен выше. Я был бы очень признателен за любую помощь по этому вопросу

PS
Я смог закодировать решение методом перебора, в котором я сохранил все результаты в наборе, а затем продолжил переход к следующей перестановке. Но это дало TLE

Во-первых, обратите внимание, что массив длиной n, содержащий 1, 2, …, n без дубликатов, является перестановкой.

Далее обратите внимание, что arr[i] := arr[arr[i] - 1] это возведение в квадрат перестановки. То есть рассматривайте перестановки как элементы симметричной группы S_n, где умножение — это композиция перестановок. Тогда вышеуказанная операция выполняется arr := arr * arr .

Итак, с точки зрения перестановок и их состава, вопрос заключается в следующем:

Вам дается перестановка p (= arr).
Рассмотрим перестановки p, p ^ 2, p ^ 4, p ^ 8, p ^ 16, …
Каково количество отдельных элементов среди них?

Теперь, чтобы решить эту проблему, рассмотрим циклическую нотацию перестановки. Каждая перестановка является произведением непересекающихся циклов. Например, 6 1 4 3 5 2 является произведением следующих циклов: (1 6 2) (3 4) (5) . Другими словами, каждое применение этой перестановки:

• перемещает элементы в позиции 1, 6, 2 по циклу;
• перемещает элементы на позиции 4, 3 по циклу;
• оставляет элемент в позиции 5 на месте.

Итак, когда мы рассматриваем p ^ k (берем перестановку идентификатора и применяем к ней перестановку p k раз), мы фактически обрабатываем три независимых действия:

• перемещение элементов в позиции 1, 6, 2 по циклу, k раз;
• перемещение элементов на позиции 4, 3 по циклу, k раз;
• оставьте элемент в позиции 5 на месте, k раз.

Теперь примите во внимание, что после совместного применения цикла длиной d он просто возвращает все соответствующие элементы на их начальные места. Итак, мы можем фактически сформулировать p ^ k как:

• перемещение элементов в позиции 1, 6, 2 по циклу, (k mod 3) раз;
• перемещение элементов на позиции 4, 3 по циклу, (k mod 2) раз;
• оставьте элемент в позиции 5 на месте.

Теперь мы можем доказать (используя китайскую теорему об остатках или просто используя общие знания теории групп), что все перестановки p, p ^ 2, p ^ 3, p ^ 4, p ^ 5, … различны с точностью до p ^ m, где m — наименьшее общее кратное всего цикладлины. В нашем примере с p = 6 1 4 3 5 2 у нас есть p, p ^ 2, p ^ 3, p ^ 4, p ^ 5 и p ^ 6, все разные. Но p ^ 6 — это перестановка идентификаторов: перемещение шесть раз по циклу длиной 2 или 3 приводит к тому, что элементы находятся на своих начальных местах. Таким образом, p ^ 7 совпадает с p ^ 1, p ^ 8 совпадает с p ^ 2 и так далее.

Однако наш вопрос сложнее: мы хотим знать количество различных перестановок не среди p, p ^ 2, p ^ 3, p ^ 4, p ^ 5, …, а среди p, p ^ 2, p ^ 4, p ^ 8, p ^ 16, …: pв степени степени двух. Для этого рассмотрим все длины циклов c_1, c_2, …, c_r в нашей перестановке. Для каждого c_i найдите предварительный период и период 2^ k mod c_i:

• Например, c_1 = 3 и 2 ^ k mod 3 выглядят как 1, 2, 1, 2, 1, 2, ... , то есть (1, 2) с предварительным периодом 0 и периодом 2.
• В качестве другого примера, c_2 = 2 и 2 ^ k mod 2 выглядят как 1, 0, 0, 0, ... , то есть 1, (0) с предварительным периодом 1 и периодом 1 .

В этой задаче эту часть можно выполнить наивно, просто отметив посещенные числа mod c_i в некотором массиве.

Опять же, по китайской теореме об остатках, после рассмотрения всех предварительных периодов период всей системы циклов будет наименьшим общим кратным из всех отдельных периодов.

Остается рассмотреть предварительные периоды. В любом случае они могут быть обработаны с помощью вашего наивного решения, поскольку длины предварительных периодов здесь не более log_2 n. Ответ — наименьшее общее кратное всех отдельных периодов, рассчитанное, как указано выше, плюс длина самого длинного предварительного периода.