Dynamic Programming and Maths.
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.
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.
Let's consider a different problem , we will come back on this problem latter:
dp[i] = 1
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-(i-1)]
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] * C[n]) * (F[n-1] * F[n-1]) * (n) = F[n] * F[n] * 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.
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.
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 .
get function is as defined above.
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".
asked 14 Jul '14, 15:03
the time limit was too strict here i think... i got tle .. i replaced x%mod by if(x>mod) x-=mod and got AC after the contest.. or maybe mod operations are simply too expensive!!
answered 14 Jul '14, 17:53
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
really learn something nice editorial :)
answered 19 Jul '14, 13:30
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
answered 19 Jul '14, 19:06
Author's solution gets WA :D
answered 01 Sep '14, 22:48