Сортування хліба (Розбір)

Трюк з лопаткою здійснює наступну перестановку хлібів:

Її можна представити як дві перестановки сусідніх елементів:

Кожна перестановка сусідніх елементів змінює парність перестановки. Отже, вказана операція над хлібами зберігає парність перестановки.

Відсортувати хліб так, як вимагає бос Майкла, можна лише в тому випадку, якщо парності перестановок збігаються.

Лінійне рішення задачі ґрунтується на тому, що дві перестановки мають однакову парність тоді і тільки тоді, коли парність кількості циклів, на які вони розкладаються, збігається.

Лема. Розглянемо наступний факт теорії перестановок:

Тому для перевірки парності можна:

• розкласти перестановку на цикли;

• порахувати їх кількість.

Якщо дві перестановки мають однакову парність числа циклів, то їхні парності збігаються.

Інтуїтивно це випливає з того, що кожен цикл довжини $k$ можна зібрати з k - 1 обмінів елементів, тому загальна кількість обмінів дорівнює

Приклад

У першому прикладі перша перестановка містить $2$ інверсії, друга — $6$ інверсій. Кількість інверсій в обох перестановках має однакову парність.

Розкладемо перестановки на цикли:

• (1, 3, 4, 2) = (1) (3, 4, 2);

• (4, 3, 2, 1) = (4, 1) (3, 2);

Обидві перестановки складаються з двох циклів, тобто кількість циклів у них також має однакову парність.

У другому прикладі перша перестановка містить $0$ інверсій, а друга — $15$ інверсій. Кількість інверсій у цих перестановках має різну парність.

Розкладемо перестановки на цикли:

• (1, 2, 3, 4, 5, 6) = (1) (2) (3) (4) (5) (6);

• (6, 5, 4, 3, 2, 1) = (6, 1) (5, 2) (4, 3);

Перша перестановка складається з $6$ циклів, а друга — з $3$ циклів. Таким чином, парність кількості циклів у цих перестановках різна.

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

Оголосимо масив для зберігання перестановки.

#define MAX 100010
int a[MAX];

Функція run проходить один цикл перестановки, починаючи з індексу $pos$. На кожному кроці вона переходить до наступного елемента циклу за правилом pos \to a[pos]. Відвідані елементи позначаються значенням $-1$, щоб не обробляти їх повторно. Таким чином, функція повністю обходить один цикл перестановки і позначає всі його елементи як вже відвідані.

void run(int pos)
{
  int v;
  while (a[pos] != -1)
  {
    v = a[pos];
    a[pos] = -1;
    pos = v;
  }
}

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

int parity(int *a)
{
  int res = 0;

Послідовно переглядаємо всі позиції масиву.

  for (int i = 0; i < n; i++)

Якщо елемент ще не був відвіданий (a[i] \ne -1), це означає початок нового циклу. У цьому випадку викликається функція $run(i)$, яка проходить весь цикл і позначає його елементи значенням $-1$.

    if (a[i] != -1) 
    {
      run(i);

Після обходу циклу лічильник $res$ збільшується на $1$.

      res++;
    }

Повертаємо парність числа циклів.

  return res % 2;
}

Основна частина програми. Читаємо першу перестановку. При зчитуванні кожне значення зменшується на 1~(a[i]--), щоб перейти від нумерації елементів з $\mathrm{1..}n$ до зручнішої для роботи 0 .. n - 1.

scanf("%d",&n);
for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;

У змінній $p1$ обчислюємо парність кількості циклів у перестановці $a$.

p1 = parity(a);

Читаємо другу перестановку. У змінній $p2$ обчислюємо парність кількості циклів у перестановці $a$.

for (i = 0; i < n; i++)
  scanf("%d",&a[i]), a[i]--;
p2 = parity(a);

Порівнюємо парності числа циклів у двох перестановках і виводимо відповідь.

if (p1 == p2) printf("Possible\n");
else printf("Impossible\n");