CodeJam 2011：Gorosort的解决方案？

问题可以在这里找到：
http://code.google.com/codejam/contest/dashboard?c=975485#s=p3 CodeJam 2011：Gorosort的解决方案？

我不明白为什么
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.
任何人都可以澄清我这个问题吗？

来源

2011-05-08 Tianissimo

你应该请阅读证明：http：//code.google.com/codejam/contest/dashboard?c=975485#s=a&a=3 – 2011-05-08 16:27:57

他们还写道，策略只保留已排序的元素。在你的数组中，没有元素位于正确的位置，所以你不会按住任何元素。你得到4是因为你使用了错误的策略。 *为什么*这个策略的作用是证明（我不能向你解释，我必须花更多的时间与我自己;）） – 2011-05-08 16:39:22

感谢您的帮助。但不，我不这么认为。根据问题页面底部的说明部分：http://code.google.com/codejam/contest/dashboard?c=975485#s=p3&a=3。可以保留不正确位置的元素。 – Tianissimo 2011-05-08 16:59:32

他们解释的解决方案是始终只保存正确排序的项目。如果你这样做了三个未分类的元素，那么在第一次尝试之后，你有1/6的机会对它们进行排序（即我们在一次命中后完成），3/6的机会你排序其中一个项目（和你平均需要2次点击）和2/6的机会都不会被分类（并且您仍然需要与开始时相同的hist数）。这给你一个简单的经常性公式，经过评估后，平均来说，你需要3次击中排序3个未排序的项目。

事实上，您的策略给出错误的结果只是意味着它不是最好的策略。

尽管他们的解决方案并不是唯一能够提供相同结果的解决方案，但它是最简单的。另一种可能的方法是保存所有已排序的项目（如果有的话）以及一些未排序的项目。但是，条件是你没有持有的所有物品必须能够到达正确的位置，而不必让你持有的物品（或换句话说，它们必须在排列中形成cycle(s)）。

请看下面的例子：

1 3 2 5 6 4

有5个无序项目，因此谷歌的解决方案将采取平均为5次命中。

1已排序，因此我们不得不保留它。如果我们同时持有5,6和4，则其余项目（3和2）可以到达正确的位置。当我们这样做时，他们平均会以2次命中。现在我们有3个未排序的项目，我们可以平均排序3次。（我们必须保持所有人都是自由的，因为他们形成了一个循环。）所以这种方法虽然比较复杂，但与原始方法一样快。

来源

2011-05-08 17:28:51 svick

我还没有花时间去理解证明，但是在comp中，有一次，我尝试模拟不同的'cycles'的情况。随机产生一个2 [2,1]周期的置换。做了10万次，并分成平均值。这大致是2.

所以我尝试了一个3 [2,3,1]的循环。随机置换，检查正确的位置，冻结它们，随机置换剩余的（或在较大的周期上，我刚刚添加上一个模拟的周期结果 - 即2的周期在该点添加2.00）。

我在compy期间尝试了很多东西，所以可能一直是草率的，但是我的模拟给出的数字不同于证明应该提出的。

周期3 - 3。5（相对于3）周期4 - 5.25（与4相对）周期5 - 6.4 ...（与5相对）

???

这是不是很奇怪？然后用这些数字，我找到了所有的循环，并添加了我找到的数字。显然这是不正确的，像我的其他尝试。

来源

2011-05-08 19:37:41

当它！我只是看看模拟和固定和错误。然后当我运行它 - 你不知道它循环3 = 3，循环4 = 4 ... ARGG如果我不会对我的模拟器如此草率，即使我肯定会注意到模式:) – 2011-05-08 23:31:28

证明结果：

让E[n]是命中为n个乱序的预期数量。

如果n> = 2，E[n]是一加的加权的可能结果的一重击后的总和，

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

现在我们必须计算count[k]。它是

C（N，K），由正服用k个路的数目的乘积
（K-1）！的布置k个所以没有处于路的数目及其正确的位置
（NK）！路数或安排其他元素

所以count[k] = C(n,k)*(k-1)!*(n-k)!=n!/k。

然后，我们可以写

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

所以E[n]=n为n> = 2，证明（顺便说一句E[1]是不确定的和count[1]=0）

所以回答这个问题，只是没有这样的数字的计数在他们的正确位置。

我已经在http://www.chaoswork.com/blog中写过这一轮的解决方案，但是这个博客是用中文写的，所以在这篇文章中，我用英文发表了我的想法。

来源

2011-05-09 04:48:14 huangchao

尼斯推导。我大量编辑并扩展了你的英语。希望它是好的。我还修复了一个错误：你有“E [n]/n = E [n] /（n-1）”。 – xan 2012-05-09 11:35:58

这里做“3 1 2”方式：

不要冷冻什么，只是让所有的3个元素随机重新洗牌。

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

：

1 2 3

3/6用在正确的地方1个家伙和2种错人结束了的机会

2/6的几率仍然是错的所有3人结束了的：

2 3 1 

3 1 2

考虑让出3坏状态是一个硬币翻转概率2/3。平均需要多长时间才能成功？这是一个几何分布（谷歌），所以你平均需要3/2（1.5）翻转。现在假设你已经摆脱了糟糕的状态，你有可能解决四分之一的问题，并且有两个错误球员的概率是3/4。所以，平均来说，在退出不良状态或1.5步后，你有0 * 1 4 + 2 * 3/4步。

（其中“2周的措施来解决2人无序”上述式中，如权利要求可通过几何分布的期望值的另一应用来得到，其中p = 1/2）

来源

2011-05-09 21:48:42 user691307

CodeJam 2011：Gorosort的解决方案？

回答

相关问题