CodeJam 2011: Solution for Gorosort?

Question

The problem can be found here:
http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

I don't understand why
answer = no. of elements that are not in the correct position

For example, assume that I have to sort this array:

3 1 2

So I think it this way:

Array: 3 1 2  
1st: freeze 2 to sort 1 (take 2 hits)  
Array: 1 3 2  
2nd: freeze 1 to sort 2 and 3 (take another 2 hits)

Therefore, my answer is 4 but the correct answer is 3.
Could anyone clarify me this problem?

Answer 1

The solution explained by them is to always hold only the items that are correctly sorted. If you do this for three unsorted elements, then after first try, there's 1/6 chance that you sort all of them (i.e. we're finished after one hit), 3/6 chance that you sort one of the items (and you need 2 more hits on average) and 2/6 chance that none will be sorted (and you still need the same count of hist as when you started). This gives you a simple recurrent formula, which after evaluating gives that, on average, you need 3 hits to sort 3 unsorted items.

The fact that your strategy gives the wrong result just means that it's not the best strategy.

Their solution is not the only one that gives the same results, though, just the simplest. Another possible way is to hold all sorted items (if there are any), plus some of the unsorted. But with the condition that all of the items you are not holding have to be able to get to their correct positions without you letting go of the items you're holding (or in other words, they have to form cycle(s) in the permutation).

Consider the following example:

1 3 2 5 6 4

There is 5 unsorted items, so Google's solution will take on average 5 hits.

The 1 is sorted, so we have to hold it. If we hold 5, 6 and 4 too, the remaining items (3 and 2) can get to their correct position. When we do it, they will get there in 2 hits, on average. Now we have 3 unsorted items and we can sort them, on average, in 3 hits. (We have to keep all of them free, because they form one cycle.) So this approach, while more complicated, is as fast as the original one.

Answer 2

Here's the way to do "3 1 2":

Don't freeze anything, just let all 3 elements randomly re-shuffle.

You have 1/6 chance of solving the problem at once:

1 2 3

3/6 chance of ending up with 1 guy in the right place and 2 wrong guys:

1 3 2

3 2 1

2 1 3

2/6 chance of ending up with all 3 guys still wrong:

2 3 1

3 1 2

Consider getting out of the 3-bad state to be a coin flip with probability 2/3. On average how long will it take you to succeed? This is a geometric distribution (google that), and so you will on average require 3/2 (1.5) flips. Now assuming you have gotten out of the bad state, you have probability 1/4 of being solved and probability 3/4 of having 2 wrong guys. So, on average you have 0 * 1/4 + 2 * 3/4 steps to go after getting out of the bad state, or 1.5 steps.

(The "2 steps to solve 2 guys out of order" claim in the above formula can be gotten by another application of the expected value of a geometric distribution, with p = 1/2.)

Answer 3

Proof of the result:

Let E[n] to be the expected number of hits for n numbers out of order.

If n>=2, E[n] is one plus the sum of the weighted possible results after one hit,

     `E[n] = 1+(E[1]*count[1]+E[2]*count[2]+...+E[n] * count[n])/n!`

Now we must calculate count[k]. It is the product of

• C(n,k), the number of ways taking k numbers from n
• (k-1)!, the number of ways of arranging k numbers so none is in its correct location
• (n-k)!, the number of ways or arranging the other elements

So count[k] = C(n,k)*(k-1)!*(n-k)!=n!/k.

Then we can write

E[n]   = 1+E[1]/1+E[2]/2+...+E[n-1]/(n-1)+E[n]/n   (a)
E[n-1] = 1+E[1]/1+E[2]/2+...+E[n-1]/(n-1)          (b)
E[n]-E[n-1] = E[n]/n                             (a)-(b)
E[n]/n = E[n-1]/(n-1)                         (rearranging)
E[n-1]/(n-1) = E[n-2]/(n-2)                   (substituting)
...
E[3]/3 = E[2]/2                               (substituting)
E[2]/2 = 1                                   (1/2+1/4+1/8+...)

So E[n]=n for n>=2 is proved (btw E[1] is undefined and count[1]=0)

So the answer to this problem is just the count of such numbers not in their right postion.

I have written a solution of this round in http://www.chaoswork.com/blog, but this blog is written in Chinese, so in this, I post my idea again in English.