Дивовижний трюк#11320

Дивовижний трюк (Розбір)

Після перетасовки $i$ -та карта зліва — це карта $a [p [q [i]]]$ a[p[q[i]]]. Фокус вдається, якщо для всіх $i$ виконується рівність:

a [p [q [i]]] = i .

a[p[q[i]]] = i.

Позначимо через $p \circ q$ p \circ q композицію перестановок: $(p \circ q) [i] = p [q [i]]$ (p \circ q)[i] = p[q[i]], тобто спочатку застосовується $q$ , а потім $p$ . Нехай $I$ — тотожна перестановка. Тоді умову фокуса можна записати як $a \circ p \circ q = I$ a \circ p \circ q = I.

Застосуємо обернену перестановку $a^{- 1}$ a^{-1} до обох частин рівності зліва, а потім $p^{- 1}$ p^{-1}:

p \circ q = a^{- 1}, q = p^{- 1} \circ a^{- 1} .

p \circ q = a^{-1}, \qquad q = p^{-1} \circ a^{-1}.

Таким чином, перестановку $p$ можна обрати довільно, а потім $q$ визначається однозначно: $q [i] = p^{- 1} [a^{- 1} [i]]$ q[i] = p^{-1}[a^{-1}[i]]. Перестановку без нерухомих точок називають безладом (derangement). Задача зводиться до пошуку такого безладу $p$ , що перестановка $q = p^{- 1} \circ a^{- 1}$ q = p^{-1} \circ a^{-1} також є безладом.

Випадковий вибір. Перебрати всі $n!$ перестановок $p$ неможливо, тому ми обираємо $p$ випадково:

згенерувати випадкову перестановку $p$ ; якщо вона має нерухому точку, перейти до наступної спроби;
обчислити $q = p^{- 1} \circ a^{- 1}$ q = p^{-1} \circ a^{-1};
якщо $q$ не має нерухомих точок, пара $(p, q)$ — відповідь.

Ми робимо не більше $1000$ спроб. Якщо жодна з них не дає відповіді, виводимо "Impossible".

Чому це працює. Відповіді не існує лише у кількох випадках для малих $n$ :

$n = 1$ n = 1 — взагалі не існує перестановок без нерухомих точок;
$n = 2$ n = 2 та $a = (2, 1)$ a = (2, 1) — єдиний безлад $p = (2, 1)$ p = (2, 1) дає $q = (1, 2)$ q = (1, 2);
$n = 3$ n = 3 та $a$ міняє місцями рівно два елементи. Єдині безлади довжини $3$ — це циклічні зсуви $(2, 3, 1)$ (2, 3, 1) та $(3, 1, 2)$ (3, 1, 2). Композиція двох циклічних зсувів знову є циклічним зсувом або тотожною перестановкою, тому перестановку, що міняє місцями два елементи, отримати неможливо.

Для $n \geq 4$ n \ge 4 відповідь завжди існує. Більш того, як показує повний перебір для малих $n$ , частка придатних перестановок $p$ серед усіх $n!$ перестановок становить щонайменше $1/12$ (мінімум досягається при $n = 4$ n = 4), а зі зростанням $n$ вона наближається до $1/ e^{2} \approx 0.135$ 1/e^2 \approx 0.135. Отже, ймовірність не знайти відповідь за $1000$ спроб не перевищує $(11/12)^{1000} < 1 0^{- 37}$ (11/12)^{1000} < 10^{-37}, що практично дорівнює нулю. Якщо відповіді не існує, жодна зі спроб не вдасться, і програма коректно виведе "Impossible".

Приклад

Розглянемо четвертий тест: $a = (5, 1, 4, 2, 3)$ a = (5, 1, 4, 2, 3).

Знайдемо обернену перестановку: якщо $a [i] = x$ a[i] = x, то $a^{- 1} [x] = i$ a^{-1}[x] = i. Оскільки $a [1] = 5$ a[1] = 5, $a [2] = 1$ a[2] = 1, $a [3] = 4$ a[3] = 4, $a [4] = 2$ a[4] = 2, $a [5] = 3$ a[5] = 3, отримуємо $a^{- 1} = (2, 4, 5, 3, 1)$ a^{-1} = (2, 4, 5, 3, 1). На малюнку зліва показана перестановка $a$ , а справа — обернена до неї: всі стрілки розвернуті.

Згенеруємо випадкову перестановку $p$ без нерухомих точок. Нехай, наприклад, $p = (4, 1, 2, 5, 3)$ p = (4, 1, 2, 5, 3). Обернена до неї $p^{- 1} = (2, 3, 5, 1, 4)$ p^{-1} = (2, 3, 5, 1, 4).

Обчислимо $q [i] = p^{- 1} [a^{- 1} [i]]$ q[i] = p^{-1}[a^{-1}[i]]:

q [1] = p^{- 1} [2] = 3, q [2] = p^{- 1} [4] = 1, q [3] = p^{- 1} [5] = 4, q [4] = p^{- 1} [3] = 5, q [5] = p^{- 1} [1] = 2

q[1] = p^{-1}[2] = 3, \quad q[2] = p^{-1}[4] = 1, \quad q[3] = p^{-1}[5] = 4, \\ q[4] = p^{-1}[3] = 5, \quad q[5] = p^{-1}[1] = 2

Отримуємо $q = (3, 1, 4, 5, 2)$ q = (3, 1, 4, 5, 2). Перестановка $q$ не має нерухомих точок, тому пара $(p, q)$ — відповідь. Вона збігається з відповіддю з прикладу.

Переконаємося, що фокус вдається, тобто $a [p [q [i]]] = i$ a[p[q[i]]] = i:

a [p [3]] = a [2] = 1, a [p [1]] = a [4] = 2, a [p [4]] = a [5] = 3, a [p [5]] = a [3] = 4, a [p [2]] = a [1] = 5

a[p[3]] = a[2] = 1, \quad a[p[1]] = a[4] = 2, \quad a[p[4]] = a[5] = 3, \\ a[p[5]] = a[3] = 4, \quad a[p[2]] = a[1] = 5

У першому тесті $n = 2$ n = 2 та $a = (2, 1)$ a = (2, 1), тому $a^{- 1} = (2, 1)$ a^{-1} = (2, 1). Єдина перестановка довжини $2$ без нерухомих точок — це $p = (2, 1)$ p = (2, 1), і $p^{- 1} = (2, 1)$ p^{-1} = (2, 1). Тоді $q = p^{- 1} \circ a^{- 1} = (1, 2)$ q = p^{-1} \circ a^{-1} = (1, 2) — тотожна перестановка, всі точки якої нерухомі. Відповідь — "Impossible".

Реалізація алгоритму

Функція print виводить елементи масиву $a$ , починаючи з першого.

void print(vector<int>& a)
{
  for (int i = 1; i < a.size(); i++)
    printf("%d ", a[i]);
  printf("\n");
}

Функція is_valid перевіряє, чи містить перестановка $v$ нерухомі точки.

bool is_valid(vector<int>& v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] == i) return false;
  return true;
}

Оголосимо масиви.

vector<int> a, p, p1, q;

Основна частина програми. Зчитуємо вхідні дані.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

Ініціалізуємо масиви.

  a.resize(n + 1);
  p1.resize(n + 1);
  p.resize(n + 1);
  q.resize(n + 1);

Зчитуємо вхідну перестановку $a$ та одразу зберігаємо обернену до неї у масиві $a$ . Тобто масив $a$ містить перестановку $a^{- 1}$ a^{-1}, де $a$ — вхідна перестановка.

  for (i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    a[x] = i;
  }

mt19937 — один зі стандартних генераторів псевдовипадкових чисел у C++ (вихор Мерсенна з періодом 19937). Він дуже швидкий і має хороші статистичні властивості, що робить його відмінним вибором для більшості задач, що потребують генерації випадкових чисел.

  mt19937 gen(random_device{}());

У змінній $f o u n d$ позначатимемо, чи знайдено розв'язок для поточного тесту.

  found = false;

Виконуємо $1000$ ітерацій.

  for (it = 0; it < 1000; it++)
  {

Генеруємо випадкову перестановку. Для цього заповнюємо масив $p$ числами $0, 1, 2, ...$ 0, 1, 2, ..., і використовуємо функцію shuffle для перемішування елементів, починаючи з першого (ненульового) елемента. Ми працюємо з перестановками від $1$ до $n$ .

    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), gen);

Перевіряємо, чи є перестановка $p$ допустимою (тобто чи не містить вона нерухомих точок).

    if (!is_valid(p)) continue;

Обчислюємо перестановку $p_{1} = p^{- 1}$ p_1 = p^{-1}.

    for (i = 1; i <= n; i++)
      p1[p[i]] = i;

Обчислюємо перестановку $q = p_{1} ° a^{- 1} = p^{- 1} ° a^{- 1}$ q = p_1 ° a^{-1} = p^{-1} ° a^{-1}.

    for (i = 1; i <= n; i++)
      q[i] = p1[a[i]];

Якщо перестановка $q$ допустима, виводимо результат.

    if (is_valid(q))
    {
      puts("Possible");
      print(p);
      print(q);
      found = true;
      break;
    }
  }

C++

Якщо після $1000$ ітерацій розв'язок не знайдено, то відповіді не існує.

  if (!found) puts("Impossible");
}