-1

Given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. We are also given M pairs of integers, where the i-th is (Li,Ri). In a single turn we can choose any of these pairs (let's say with the index j) and arbitrarily shuffle the elements of our permutation on the positions from Lj to Rj, inclusive (the positions are 1-based). We are not limited in the number of turns and you can pick any pair more than once.

The goal is to obtain the permutation P, that is given. If it's possible, output "Possible", otherwise output "Impossible".

Example : Let N=7 and M=4 and array be [3 1 2 4 5 7 6] and queries are :

1 2
4 4
6 7
2 3

Here answer is Possible.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
code test
  • 93
  • 5
  • See [How do I ask and answer homework questions?](https://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions) on Meta. – jww Aug 25 '14 at 17:02

1 Answers1

1

Treat each pair as an interval, compute the union of intervals as a list of non-overlapping intervals, and then test, for each i, whether the value at position i of the permutation either is i or is in the same non-overlapping interval as i.

This works because, if we have a <= b <= c <= d with pairs (a, c) and (b, d), then by repeatedly invoking (a, c) and (b, d), we can get any permutation that we could get with (a, d). Conversely, (a, d) enables any permutation that we could get with (a, c) and (b, d). Once the list of pairs is non-overlapping, it's clear that we can move element i to position j != i if and only if i and j are in the same interval.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120