×

# SEAEQ - Editorial

Author: Sergey Nagin
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

HARD

# PREREQUISITES:

Dynamic Programming and Maths.

# PROBLEM:

Two arrays are almost equal if the rank of element at each index is the same for both the arrays.Let F(P1, P2) denote number of pairs (l,r) such that P1[l..r] is almost equal to P2[l..r] and array P1[l..r] contain not more then E inversions.Your aim is to output the sum of F(P1,P2) for all permutations P1, P2 for n elements.

# Observation

Sereja call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x.

This is essentially saying that the order of elements in A and B must be the same. For example : (4, 5, 3) is almost equal to (2, 10, 1) because order of elements is (2,3,1) i.e. rank of first element in both the array is 2 , rank of second element in both the array is 3 and that of the third element is 1.

CA(A[i]) returns the rank of the ith element in the array A.

It is clear from the above point that rank of the element matters and not the number's itself.

# Explanation

Let's consider a different problem , we will come back on this problem latter:
Let suppose we are interested in finding number of permutations of array of length l in which number of inversion is not more than E.
To solve this problem , we will need a small dp to handle it. Note that we are interested only in array of lengths less than 501.
Let dp[i][j] denote the number of permutations of length i which has atmost j inversions.
so , dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-(i-1)]
Reason
Let us focus on the ith element, if the ith element is the maximum , then it will give 0 inversions and we need to take from i-1 elements , all possible permutations which has inversions less than or equal to j. Similarly , if the ith element is the second maximum in the array then it will add only 1 inversion , and so on till we use the smallest element which will intoroduce i-1 inversions.

Base Case

dp[i][0] = 1
Number of permutation of length i having 0 inversions is 1 and that permutation is the array sorted in increasing order.

DP state

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-(i-1)]

Pseudo Code

//Base Case
for(int i=1;i<=500;i++)
dp[i][0] = sum_dp[i][0]  = 1;

//sum_dp[i][j] denotes the sum of dp[i][j] + dp[i][j-1] + ...... + dp[i][1]

for(int i=1;i<=500;i++)
E = (i*(i-1))/2         //Maximum number of Inversions
for(int j=1;j<=E;j++)
//dp[i][j] = dp[i-1][j] + dp[i-1][j-1] +....+dp[i-1][j-(i-1)]
dp[i][j] = ( get(i-1,j) - get(i-1,j-i) )%mod ;
if ( dp[i][j]<0)
dp[i][j]+=mod;
sum_dp[i][j] = (dp[i][j] + sum_dp[i][j-1])%mod;

get(i,j):
//returns the value of dp[i][j] + dp[i][j-1] + ... + dp[i][1]
if ( j<0)
return 0
if ( j > (i*(i-1))/2 )
return sum_dp[i][(i*(i-1))/2]
else
return sum_dp[i][j]


Let's get back to the original problem.

Once you have calculated the above dp , the original problem is very easy to solve if you remember the observations we did.

Let us solve the problem for the case l=r.

Number of inversion is 0 when l=r , so total number of such cases are : (C[n][1] * C[n][1]) * (F[n-1] * F[n-1]) * (n) = F[n] * F[n] * n
C[n][r] denotes number of ways to choose r object from n distinct objects and F[n] denotes n!

Reason : Total number of permutation is n! . So total distinct number of pairs (P1,P2) are n! * n! . So from each pair we can choose any element as l.
Another way to see the above answer is : Choose any one element from n elements from both the arrays , arrange the remaining elements in both the array because we are currently not interested in the remaining elements and select the position where the element will appear.

Let's us solve for a more generic case when r = l + d-1 , where d>=1

The solution to the above case would be :

sum_dp[d][E] * ( C[n][d] * C[n][d] ) * ( F[n-d] * F[n-d] ) * (n-d+1)

where E is min ( E, (n * (n-1))/2 ) because maximum value of E for a given n is bounded by (n*(n-1))/2.

Reason

Choose any d elements from both the arrays , arrange the remaing elements by F[n-d] ways in both the arrays , choose the starting position by (n-d+1) ways. Now we need to arrange d elements such that in both the arrays the order is the same. So if we fix the first array , we can get the second array [ Proof is left as an exercise ]. So we can choose position for the d elements for the first array by sum_dp[d][E] ways [ Remember that sum_dp[d][E] denotes that number of permutations of length d whose total number of inversion is atmost E ].

Now you can brute on d to solve the problem .

Pseudo Code

Get_Answer( n , E )
scanf("%d%d",&n,&E)
if ( E> (n*(n-1))/2 )
E = (n*(n-1))/2
for(int len = 1;len<=n;len++)
pans = get(len,E)
select_len_elems = ( C[n][len] * C[n][len] )%mod
arrange_rem_elems = ( F[n-len] * F[n-len] )%mod
choose_position = n-len+1
pans = ( pans * select_len_elems )%mod
pans = ( pans * arrange_rem_elems)%mod
pans = ( pans * choose_position)%mod


get function is as defined above.

Complexity:

O(n^3) , Total number of inversion for a given n is of O(n^2)

# AUTHOR'S and TESTER'S SOLUTIONS:

This question is marked "community wiki".

56273842
accept rate: 0%

7

This was definitely not a problem to be labeled "hard", given the number of successful solutions. Medium-hard, at BEST. It was just changing the order of summation, DP-counting permutations with given length and number of inversions, and binomial coefficients to finish it.

(14 Jul '14, 15:39) 7★
3

And that is exactly how I did it - and got TLE!!! http://www.codechef.com/viewsolution/4324780 Good job problem setters!!! Shouldn't you allocate to a problem at least 10 times as much as your baseline code needs??? Why not make n<300 instead of 500? Wouldn't it still exclude brute-force solutions? Have you even tried submitting in other languages and see how they'do?

(14 Jul '14, 20:00)

 0 Can we solve this problem if the limit on number of inversion(E) was on whole permutation rather than the sub arrays ? answered 15 Jul '14, 19:56 5★abilash 13●1●1●4 accept rate: 0%
 0 really learn something nice editorial :) answered 19 Jul '14, 13:30 10●1●2●7 accept rate: 0%
 0 Hi A great question followed by a nicer editorial. It would be great if you could tell me why exactly do we need to take into account the number of starting positions and the number of ways of arranging the remaining elements? Sum-DP[d][E] will give me total number of permutations of length d that has at-most E inversions. Total number of distinct pairs, (l,r) that can be selected from two arrays( where r=l+d-1) is basically similar to total number of ways of selecting d out of n elements, given by C[n][d]*C[n][d]. Won't the product of the above two suffice? Thanks And Regards LoneCoder answered 19 Jul '14, 19:06 101●2●6 accept rate: 0%
 0 Author's solution gets WA :D answered 01 Sep '14, 22:48 4★reza_h 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,212
×1,359
×1,219
×24
×3

question asked: 14 Jul '14, 15:03

question was seen: 3,097 times

last updated: 01 Sep '14, 22:48