6828. Сортировка хлеба

Майкл работает в пекарне. В конце каждой смены его босс требует отсортировать хлеб в определённом порядке. Однако она никак не может решить, каким именно должен быть этот порядок – по наблюдениям Майкла, каждый день он оказывается новым.

Майкл уже некоторое время работает в пекарне и успел освоить хитрый трюк со своей деревянной хлебной лопаткой. Он может подхватить лопаткой три соседних хлеба и подбросить их так, что при приземлении самый правый хлеб окажется слева, а два остальных сдвинутся на одну позицию вправо. Иными словами, он может выполнять циклический сдвиг вправо для любой подпоследовательности из трёх соседних хлебов.

Перед окончанием смены его коллеги уже выложили хлеб в одну длинную линию. Майкл хочет отсортировать хлеб, используя свой трюк с лопаткой. Он может брать любые три последовательных хлеба на линии, вращать их описанным образом и затем класть обратно. Однако иногда не имеет значения, сколько раз он воспользуется лопаткой – отсортировать хлеб в требуемом боссом порядке всё равно невозможно.

Вход. Первая строка содержит целое число n (3 ≤ n ≤ 10⁵). Затем следуют две строки:

· первая строка содержит перестановку чисел от 1 до n, задающую текущий порядок хлебов;

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

Выход. Выведите “Possible”, если Майкл сможет с помощью своей лопатки отсортировать хлеб так, как требует босс. В противном случае выведите “Impossible”.

Пример входа 1	Пример выхода 1
4 1 3 4 2 4 3 2 1	Possible
Пример входа 2	Пример выхода 2
6 1 2 3 4 5 6 6 5 4 3 2 1	Impossible

РЕШЕНИЕ

количество инверсий

Анализ алгоритма

Трюк с лопаткой совершает следующую перестановку хлебов:

Её можно представить как две перестановки соседних элементов:

(a, b, c) → (a, c, b) → (c, a, b)

Каждая перестановка соседних элементов меняет чётность перестановки. Следовательно, указанная операция над хлебами сохраняет чётность перестановки.

Отсортировать хлеб так, как требует босс Майкла, можно только в том случае, если чётности перестановок совпадают.

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

Лемма. Рассмотрим следующий факт теории перестановок:

четность перестановки = (n – число циклов) mod 2

Поэтому для проверки чётности можно:

· разложить перестановку на циклы;

· посчитать их количество.

Если две перестановки имеют одинаковую чётность числа циклов, то их чётности совпадают.

Интуитивно это следует из того, что каждый цикл длины k можно собрать из k – 1 обменов элементов, поэтому общее число обменов равно

n – число циклов

Пример

В первом примере первая перестановка содержит 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 циклов. Таким образом, чётность количества циклов в этих перестановках различна.

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

Вычислим количество инверсий в обоих перестановках за время O(nlog₂n) и сравним их четность.

#include <cstdio>

#include <string>

#include <vector>

#define MAX 100010

using namespace std;

int m[MAX];

int n, i, j;

long long swaps, sw;

void merge(int *a, int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] -> res[]

// res[0..len-1] a[cleft..cright] are merged into a[bleft..cright]

// we copy only half of array

int i, len = bright - bleft + 1, resCur = 0;

int *res = new int[len];

memcpy(res,a + bleft,len*sizeof(int));

while((resCur < len) && (cleft <= cright))

{

if (res[resCur] <= a[cleft]) a[bleft++] = res[resCur++];

else a[bleft++] = a[cleft++], swaps += len - resCur;

}

while (resCur < len) a[bleft++] = res[resCur++];

delete[] res;

}

void mergeSort(int *a, int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a,left,middle);

mergeSort(a,middle+1,right);

merge(a, left, middle, middle + 1, right);

}

int main(void)

{

scanf("%d",&n);

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

mergeSort(m, 0, n - 1); sw = swaps % 2;

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

mergeSort(m, 0, n - 1); swaps %= 2;

if (sw == swaps) printf("Possible\n");

else printf("Impossible\n");

return 0;

}

Реализация алгоритма – количество циклов в перестановке

Объявим массив для хранения перестановки.

#define MAX 100010

int a[MAX];

Функция run проходит один цикл перестановки, начиная с индекса pos. На каждом шаге она переходит к следующему элементу цикла по правилу pos → 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] ≠ -1), это означает начало нового цикла. В этом случае вызывается функция run(i), которая проходит весь цикл и помечает его элементы значением -1.

if (a[i] != -1)

{

run(i);

После обхода цикла счётчик res увеличивается на 1.

res++;

}

Возвращаем чётность числа циклов.

return res % 2;

}

Основная часть программы. Читаем первую перестановку. При чтении каждое значение уменьшается на 1 (a[i]--), чтобы перейти от нумерации элементов с 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");