not getting the problem statement of ambigous permutation https://www.codechef.com/problems/PERMUT2

codechef permut2

manish_kumar
Manish Kumar Savita
manish_kumar

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

2 Answers

nky_007
nky_007 23:22, Mar 25
Narendra Kumar Yadav

Example: 1 6 3 4 2 5

You have that permutation of 6 numbers(from 1 to 6).

Now, for the inverse you start looking from 1 to 6 the numbers in the example, I mean:

The number 1 in wich position is located at 1 6 3 4 2 5? It is located first. So, the first number in the inverse is 1.

Inverse so far: 1XXXXX

The number 2 in wich position is located at 1 6 3 4 2 5? It is located 5th. So, the second number in the inverse is 5.

Inverse so far:15XXXX

.

.

.

The number 6 in wich position is located at 1 6 3 4 2 5? It is located 2nd. So, the 6th position in the inverse is 2.

Inverse so far:153462

This means this permutation is not ambiguous. Because 1 6 3 4 2 5 !=1 5 3 4 6 2.

Now, with 1 4 3 2(from 1 to 4)

In wich position is located 1 at 1 4 3 2. It's first, so the first number in the inverse is 1

In wich position is located 2 at 1 4 3 2. It's 4th, so the second number in inverse is 4

In wich position is located 3 at 1 4 3 2. It's 3rd, so the third numberse in the inverse is 3

In wich position is located 4 at 1 4 3 2. It's 2nd, so the fourth number in the inverse is 2

1 4 3 2 = 1 4 3 2, so this is an ambiguos permutation.

Notice that you need start looking from 1 until n.

// source : https://discuss.codechef.com/questions/15383/ambiguous-permutations-explain-the-statement




Please make sure the answer is not too short
3 Upvotes
preda2or
preda2or 23:20, Mar 25
Shubham Kumar Gupta



Please make sure the answer is not too short
1 Upvotes
Comments
No Comments yet