CodeJam 2011: Solution for Gorosort?

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 a开发者_StackOverflow社区re 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?

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.

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.)

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.

I haven't spent the time to understand the proof, but during the comp, at one point, I tried simulating the situation for differnt 'cycles'. Randomly generated a permutation for a cycle of 2 [2,1]. Did it 100000 times and divided to get the average. It was roughly 2.

So I tried a cycle of 3 [2,3,1]. Random permutation, check for correct positions, freeze them, random permute remaining (or on larger cycles I just added previous simulation's cycle results - ie for cycle of 2 added 2.00 at that point).

I was trying alot of stuff during the compy, so may have been sloppy, but my simulations were giving different numbers than that proof sould suggest.

cycle 3 - 3.5 (as opposed to 3) cycle 4 - 5.25 (as opposed to 4) cycle 5 - 6.4... (as opposed to 5)

???

Is that weird? Then with those numbers I found all cycle's in the set and added the numbers I found. Obviously that was incorrect like my other tries.