Atcoder Beginner Contest 150 Question C

general
, ,
1

Question link : C - Count Order

Problem Statement

We have two permutations P and Q of size N (that is, P and Q are both rearrangements of (1, 2, …, N)).

There are N! possible permutations of size N. Among them, let P and Q be the a-th and b-th lexicographically smallest permutations, respectively. Find |a−b|.

Notes

For two sequences X

and Y, X is said to be lexicographically smaller than Y if and only if there exists an integer k such that Xi=Yi (1≤i<k) and Xk<Yk

.

Constraints

  • 2≤N≤8

  • P and Q are permutations of size N

  • .

Input

Input is given from Standard Input in the following format:

N

P1 P2 …PN
Q1 Q2 …QN

Output

Print |a−b|

.

Sample Input 1

3
1 3 2
3 1 2

Sample Output 1

3

There are 6

permutations of size 3: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Among them, (1, 3, 2) and (3, 1, 2) come 2-nd and 5-th in lexicographical order, so the answer is |2−5|=3

.

Sample Input 2

8
7 3 5 4 2 1 6 8
3 8 2 5 4 6 7 1

Sample Output 2

17517

Sample Input 3

3
1 2 3
1 2 3

Sample Output 3

0

Now one approach is to find all permutation and calculate which is the given permutation and return result , but how can it solved efficiently if the n is large say 10^5
@ssjgz @aryanc403 @anon55659401 @l_returns @nuttela @s5960r @akshay_1

Means the questions is just reduce to given a permutation find its no. of permutation.

2

To calculate rank of sequence in lexographical order use :
res=0;
for(int i=0;i<n;i++){
res+=(n-1-i)! * ( number index j >i such that a[j] < a[i] );
}
this can be done in O(nlogn)

3 Likes
3

plz expalin kro na ek example deke :slightly_smiling_face:

5

n= 4
a[ ] =3 2 1 4

i=0 , a[i]= 3 ,
clearly if a[0] would have been 0,1 or 2 ( a[j] < a[i] ) the overall sequence will be lexographically smaller, and the number of seuqnce i can form with then is 3! from each
So toal 3*3!
we are not taking sequence from a[i]= 4, because it will make it lexo… bigger
now fixing a[i]= 3 in our sequence, and moving forward

i=1, a[i]=2
now if a[i] would have been 0 , 1 we would have loxo… smaller , and number of sequence we can create from each will be 2! ( remember 3 has been fixed in a[0] ) .
So total= 2*2!

… do this for all indexes

1 Like
6

;ok i will se this after cf contest thnks :slight_smile: