6828. Bread sorting

 

Michael works in a bakery. At the end of his shift, his boss wants the breads sorted in a certain order. She can’t seem to decide on which order, though – every day there seems to be a new one – to Michael’s despair. Michael has worked there for a while now and has learned a neat trick with his wooden bakery paddle. He can take three breads next to each other on his paddle and throw them up in the air such that when they land, the right-most has moved to the left-most position, and the two other breads have moved one place to the right. In other words, he can rotate to the right a subsequence of breads of length three.

Before the end of the shift, his coworkers place the breads in a long line. Michael would like to sort the line of breads using his paddle trick. He can take any three consecutive breads along the line on his paddle, rotate them, and then put them back. Sometimes though, it does not matter how many times he uses his paddle – the line of bread just doesn’t seem to be possible to sort the way the boss wants...

 

Input. The first line contains a positive integer n (3 ≤ n ≤ 105). Then two lines follow: on the first line, a permutation of the integers 1 through n describing the order in which the breads are lined up. On the second line, a permutation of the integers 1 through n describing how Michael’s boss wants the breads sorted.

 

Output. Print “Possible” if Michael can sort the breads with his paddle in the order prescribed by his boss. Otherwise print “Impossible”.

 

Sample input 1

Sample output 1

4

1 3 4 2

4 3 2 1

Possible

 

 

Sample input 2

Sample output 2

6

1 2 3 4 5 6

6 5 4 3 2 1

Impossible

 

 

SOLUTION

number of invertions

 

Algorithm analysis

The paddle trick performs the following permutation with the breads:

It can be obtained as a result of two permutations of adjacent elements:

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

Permutation of adjacent elements changes the parity of the permutation. Therefore, the indicated permutation of breads preserves the parity of permutation.

It is possible to sort the breads as required by Michael’s boss, if only the parities of permutations are the same.

 

The linear solution of the problem is based on the fact that two permutations have the same parity if only the number of cycles into which they are decomposed have the same parity.

 

Example

In the first example, the first permutation contains 2 inversions, the second permutation contains 6 inversions. The number of inversions has the same parity.

Break the permutations into cycles:

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

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

Both permutations have two cycles. The number of cycles in permutations has the same parity.

 

Second sample. The first permutation contains 0 inversions, the second permutation contains 15 inversions. The number of inversions has different parity.

Break the permutations into cycles:

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

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

The first permutation has 6 cycles, the second permutation has 3 cycles. The number of cycles in permutations has different parity.

 

Algorithm realization

Compute the number of inversions in both permutations in O(nlog2n) and compare their parity.

 

#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;

}

 

Algorithm realization – number of cycles in permutation

Compute the number of cycles in each permutation and check them for the same parity.

 

#include <stdio.h>

#define MAX 100010

 

int i, n, p1, p2, res;

int a[MAX];

 

void run(int pos)

{

  int v;

  while(a[pos] != -1)

  {

    v = a[pos];

    a[pos] = -1;

    pos = v;

  }

}

 

int parity(int *a)

{

  int res, i;

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

    if (a[i] != -1)

    {

      run(i);

      res++;

    }

  return res % 2;

}

 

int main(void)

{

  scanf("%d",&n);

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

    scanf("%d",&a[i]), a[i]--;

  p1 = parity(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");

  return 0;

}