CodeJam 2011:Gorosort的解决方案？

Question

可以在此处找到问题:http:
//code.google.com/codejam/contest/dashboard？c = 975485#s = p3

我不明白为什么
answer = no. of elements that are not in the correct position

例如,假设我必须对此数组进行排序:

3 1 2

所以我这样想:

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)

因此,我的回答是4,但正确答案是3.
有人能澄清这个问题吗？

Answer 1

他们解释的解决方案是始终只保留正确排序的项目.如果你为三个未分类的元素执行此操作,那么在第一次尝试之后,有1/6的机会对所有这些元素进行排序(即我们在一次击中后完成),有3/6的机会对其中一个项目进行排序(和你一样)平均需要2次点击)和2/6几率不会被排序(你仍然需要与你开始时相同的组织计数).这为您提供了一个简单的循环公式,在评估后,平均而言,您需要3次点击才能对3个未排序的项目进行排序.

您的策略产生错误结果这一事实意味着它不是最佳策略.

然而,他们的解决方案并不是唯一能够提供相同结果的解决方案.另一种可能的方法是保存所有已排序的项目(如果有的话),加上一些未排序的项目.但是,与所有你不持有的项目都能够得到自己的正确位置,没有你,让你拿着的物品去的条件(或者换句话说,他们已经形成循环(一个或多个)在排列).

请考虑以下示例:

1 3 2 5 6 4

有5个未分类的项目,因此Google的解决方案平均需要5次点击.

这1是排序的,所以我们必须持有它.如果我们认为5,6与4太外,其余项目(3和2)可以得到自己的正确位置.当我们这样做时,他们平均会在2次点击中到达那里.现在我们有3个未分类的项目,我们可以平均按3次点击对它们进行排序.(我们必须保持所有这些都是自由的,因为它们形成一个循环.)因此,这种方法虽然更复杂,但与原始方法一样快.

Answer 2

这是做"3 1 2"的方法:

不要冻结任何东西,只需让所有3个元素随机重新洗牌.

你有1/6的机会一次解决问题:

1 2 3

在正确的位置和2个错误的家伙结束了1个人的概率:

1 3 2

3 2 1

2 1 3

2/6的机会最终与所有3个家伙仍然错误:

2 3 1

3 1 2

考虑从概率为2/3的3-bad状态退出硬币翻转.平均需要多长时间才能成功？这是一个几何分布(谷歌那个),所以你平均需要3/2(1.5)翻转.现在假设你已经摆脱了糟糕的状态,你有1/4的概率被解决,概率3/4有2个错误的家伙.因此,平均而言,在退出不良状态或1.5步之后,您需要执行0*1/4 + 2*3/4步骤.

(上述公式中的"解决2个人乱序"的"2个步骤"可以通过几何分布的期望值的另一个应用得到,p = 1/2.)