Bread Sorting (Editorial)

The paddle trick performs the following permutation of the loaves:

It can be represented as two swaps of adjacent elements:

Each swap of adjacent elements changes the parity of the permutation. Therefore, this operation on the loaves preserves the parity of the permutation.

It is possible to sort the loaves in the order required by Michael's boss only if the parities of the permutations coincide.

A linear solution to the problem is based on the fact that two permutations have the same parity if and only if the parity of the number of cycles in their decompositions is the same.

Lemma. Consider the following fact from permutation theory:

Therefore, to check the parity one can:

• decompose the permutation into cycles;

• count the number of cycles.

If two permutations have the same parity of the number of cycles, then their permutation parities coincide.

Intuitively, this follows from the fact that each cycle of length $k$ can be constructed from k - 1 swaps of elements; therefore, the total number of swaps is equal to

Example

In the first example, the first permutation contains $2$ inversions, while the second contains $6$ inversions. The number of inversions in both permutations has the same parity.

Let us decompose the permutations into cycles:

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

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

Both permutations consist of two cycles; therefore, the number of cycles in them also has the same parity.

In the second example, the first permutation contains $0$ inversions, while the second contains $15$ inversions. The number of inversions in these permutations has different parity.

Let us decompose 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 consists of $6$ cycles, while the second consists of $3$ cycles. Thus, the parity of the number of cycles in these permutations is different.

Algorithm implementation

Declare an array to store the permutation.

#define MAX 100010
int a[MAX];

The function run traverses one cycle of the permutation starting from index $pos$. At each step, it moves to the next element of the cycle according to the rule pos \to a[pos]. Visited elements are marked with the value $-1$ to avoid processing them again. Thus, the function completely traverses one cycle of the permutation and marks all its elements as already visited.

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

The function parity computes the parity of the number of cycles in the permutation $a$, that is, it returns the number of cycles modulo $2$. The function sequentially scans all positions of the array.

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

Sequentially examine all positions of the array.

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

If an element has not yet been visited (a[i] \ne -1), this means the beginning of a new cycle. In this case, the function $run(i)$ is called, which traverses the entire cycle and marks its elements with the value $-1$.

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

After traversing the cycle, the counter $res$ is increased by $1$.

      res++;
    }

Return the parity of the number of cycles.

  return res % 2;
}

The main part of the program. Read the first permutation. During input, each value is decreased by 1~(a[i]--) to convert from $1$-based indexing $(\mathrm{1..}n)$ to the more convenient $0$-based indexing (0 .. n - 1).

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

In the variable $p1$, compute the parity of the number of cycles in the permutation $a$.

p1 = parity(a);

Read the second permutation. In the variable $p2$, compute the parity of the number of cycles in the permutation $a$.

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

Compare the parities of the number of cycles in the two permutations and print the result.

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