SPOJ PERMUT2

From Algorithmist
Jump to navigation Jump to search

379. Ambiguous Permutations[edit]

http://www.spoj.pl/problems/PERMUT2/

Summary[edit]

Identify whether the inverse permutation of a given permutation of digits is ambiguous.

Explanation[edit]

The inverse permutation is one where the i-th number is the position of the integer i in the permutation. It is ambiguous if it is identical to the normal representation of the permutation. For example, if { 2, 3, 4, 5, 1 } is a permutation, then it's inverse is { 5, 1, 2, 3, 4 } and in this case is not ambiguous.

Implementation[edit]

Plenty of time is allowed for this problem. A brute force comparison of one array with its inverse will satisfy the judge.

Optimizations[edit]

Gotchas[edit]

Input[edit]

The first line of the input is an integer representing the length of the permutation to follow. The next line contains integers representing the permutation. More test cases may follow. The input is terminated by a single 0.

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

Output[edit]

ambiguous
not ambiguous
ambiguous

External Links[edit]