I was solving the question Bogosort | Codechef. The solution (Codechef link) i submitted on Codechef gave me tle where as the same solution (Ideone link) i checked on Ideone ran for 1.17 sec for t=150. Someone please help in optimizing the solution. @admin or someone: please throw some light on what may be the possible reason for the difference in runtimes in both websites, so that i will be careful when submitted codes checked on Ideone.
I used the following method to solve the problem. According to Mathematical Expectation | Codechef, after one shuffle, we may get 0 … n numbers in proper position from either ends. So, E(n) should be something like
E(n) = 1+k=0Σn E(k)*p(k,n)
1 is for one shuffle to get to the state
E(n): expected amount of shuffles needed to sort n elements
p(k,n): probability of the event where k out of n numbers are not in proper place.
Note that E and E are zero. So, we can get the following formula,
E(n) = ( 1 / ( 1-p(n,n) ) ) * (1+k=2Σn-1 E(k)*p(k,n))
Since, p(k,n) is probability of the event where k out of n numbers are not in proper place, number of ways to fix n-k elements on either side is n-k+1. Possible number of permutations such that exactly k out of n numbers are not in proper place is calculated using q(k). q(k) can be calculated as
q(k) = (k-2)(k-2)(k-2)!+(k-1)! = (k-1)!(k2-3*k+3)
The first part corresponds to choosing any element but not the smallest or largest as the first one, then any element but not the largest as the last one, and permute the remaining k-2 elements. The second part corresponds to choosing the largest as the first one and permute the remaining k-1 elements. So,
p(k,n) = (q(k)*(n-k+1))/n!
The method mentioned is similar to the one in the Editorial. But i felt the editorial to be confusing. So, i described the the procedure in detail here. Since E(k)*q(k) are needed more than once, they are memoized in an array EQ in my solution.