PERMUT2 - Ambiguous Permutations

no tags 

Some programming contest problems are really tricky: not only do they require a different output format from what you might have expected, but also the sample output does not show the difference. For an example, let us look at permutations.
A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.

Input Specification

The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 100000). Then a permutation of the integers 1 to n follows in the next line. There is exactly one space character between consecutive integers. You can assume that every integer between 1 and n appears exactly once in the permutation.
The last test case is followed by a zero.

Output Specification

For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the sample output.

Sample Input

4
1 4 3 2
5
2 3 4 5 1
1
1
0

Sample Output

ambiguous
not ambiguous
ambiguous

Added by:Adrian Kuegel
Date:2005-06-24
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource:own problem, used in University of Ulm Local Contest 2005

hide comments
pk: 2015-05-20 09:18:50

AC in one go... my 30th problem... :)

Arpan Mukherjee: 2015-05-18 19:59:52

For those who're having problem for the language. Check this-http://discuss.codechef.com/questions/15383/ambiguous-permutations-explain-the-statement

AC in 1 go ^_^

Subhashis Bhowmik: 2015-05-07 10:51:58

Getting a WA, even though the given test case works :(

arjun: 2015-03-27 19:05:44

Thanks @Adrian Kuegel.
Ac on 1st go. Done in O(n);
read the comment of Adrian Kuegel, The Main Logic is given there.

Parikshith Rai: 2015-03-07 10:01:02

@gulbarga master check whether ur writing ambiguous and not ambiguous properly....cost me 1 wa. :)

gulbarga master: 2015-02-20 06:59:41

can i pls have some additional test cases for this ? The ones given, work for me and yet i get a WA.

thelazycoder: 2015-02-17 21:56:56

good question :D

Adrian Kuegel: 2012-09-20 12:35:58

"You create a list of numbers where the i-th number is the position of the integer i in the permutation."
So where is number 1? At position 5. Where is number 2? At position 1.
and so on.
That is how you get 51234 as inverse permutation of 23451

Abhimanyu: 2012-09-17 15:07:37

can anybody please help me understand how 51234 is the inverse permutation of 23451 ???