PROBLEM LINK:
Author: Sergey Nagin
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal
DIFFICULTY:
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 )
answer =0
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
answer = ( answer + pans )%mod
get function is as defined above.
Complexity:
O(n^3) , Total number of inversion for a given n is of O(n^2)
… nevermind… this was a great question and a great contest!
