SEAEQ - Editorial

PROBLEM LINK:

Practice
Contest

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)

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

4 Likes

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.

7 Likes

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!!

1 Like

Yes, it was tight - but there were 10 days for this and many people still solved it, so it’s not like it was really hard to optimize.

3 Likes

well… @xellos0 - yes that’s right… i should have started working on this problem earlier… my bad i started just today morning :frowning: … nevermind… this was a great question and a great contest!

2 Likes

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?

2 Likes

This is not the point - you shouldn’t have to. Look at Topcoder for the examples of quality in problem setting - if your solution meet the expected complexity criteria - it will never TLE on Topcoder…

1 Like

I agree. I had the right complexity, but I had to resubmit a bunch of times trying to optimize the constant factor in order to get my solution to pass. It just felt like this problem was artificially difficult, and would have been better as a medium with a less strict time limit.

There’s a difference between a contest that takes less than 2 hours with tiebreaking by time and one that takes 10 days with time irrelevant, you know.

And of course, as I said it’s just a medium problem with a bit strict time limit.

To xellos0: did it ever happened to you that the problem you’ve been trying to solve had asymptotically better solution than the one you came up with? Same here - if you have a reasonably written code that gets TLE - you’re not rushing to optimize the crap out of it - you are trying to find better algorithm (which probably does not exist in this case…)

1 Like

If I run my code locally and see that it works in around 1.5 seconds, while the time limit is 1 second, then no, I wouldn’t try to find a better algorithm. I’d try to get rid of obviously slow modulo operations and try to only count up to N(N-1)/2 inversions for each N and not 125000. Because that’s what I did.

This is when you know the time limits well - I found them very confusing on this contest: for example the problem “Game of Numbers” states that time limit is 1 sec and yet the slowest accepted solution was over 30 seconds. When you see that - you don’t trust the descriptions anymore, and you don’t have good reference. Also it is pointless to compare local run vs test machine - they could be very different…

By googling a bit, you can find out what the time shown in the scoreboard means.

Your definition of very different seems to be very loose. Local runs can tell you if your algorithm has a chance of passing, and it’s very unlikely to get more than 2 times slower or faster time than when ran on the test machine, if you’re using a normal computer. And when nothing else works, you can run your code 30 times locally, take the running times’ average, do the same for another code that got AC on another problem and compute the expected time on the test machine. It just needs a bit of effort.

I’ll give you an example: Same problem I mentioned “Game of Numbers” - I was generating random test cases double the size of the limits:
1 ≤ N ≤ 1000 (instead of 400)
1 ≤ Ai, Bi ≤ 10^9
No test case locally took more than 4-5 sec, and my solution got AC with about 26 seconds. And by the way - I have 3 y/o laptop.

Or not all test cases were random. We can assume how much an algorithm should take, but not how all test cases will look.

Also, with 5 test cases that take 4-5 seconds, that runtime is the same as on your laptop.

I meant I ran consecutively all MAXT=10 in 4-5 sec. Anyways if you believe that problem setter did a great job on this one - up to the highest quality standards - I guess I’ll leave you at that…

Test cases as in files. I guess you believe you didn’t solve this problem because of the problem setter’s mistake, not yours. I guess I’ll leave you at that… unless you want to pingpong more, then I’ll be your guest :smiley:

Maybe after the next contest :smiley:

Can we solve this problem if the limit on number of inversion(E) was on whole permutation rather than the sub arrays ?

really learn something nice editorial :slight_smile: