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

3/6 шансов оказаться в 1-м парне в нужном месте и 2-х неправильных парнях:

1 3 2

3 2 1

2 1 3

2/6 вероятность того, что все 3 парня по-прежнему ошибаются:

2 3 1

3 1 2

Рассмотрите возможность выхода из состояния 3-bad с монетой с вероятностью 2/3. В среднем, сколько вам потребуется времени, чтобы добиться успеха? Это геометрическое распределение (google that), поэтому вам потребуется в среднем 3/2 (1,5) сальто. Теперь, предполагая, что вы вышли из плохого состояния, у вас есть вероятность 1/4 решения проблемы и вероятность 3/4 наличия 2 неправильных парней. Таким образом, в среднем у вас есть 0 * 1/4 + 2 * 3/4 ​​шагов после выхода из плохого состояния, или 1,5 шага.

(Утверждение «2 шага, чтобы решить 2 парней не по порядку» в вышеприведенной формуле можно получить с помощью другого приложения ожидаемого значения геометрического распределения с p = 1/2.)

Answer 3

Подтверждение результата:

Пусть 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 чисел из n
• (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,, но этот блог написан на китайском языке, поэтому я снова публикую свою идею ванглийский.

Answer 4

Я не потратил время на то, чтобы понять доказательство, но во время компа я пытался смоделировать ситуацию для разных «циклов».Произвольно генерируется перестановка для цикла 2 [2,1].Сделал это 100000 раз и разделил, чтобы получить среднее.Было примерно 2.

Так что я попробовал цикл 3 [2,3,1].Случайная перестановка, проверка на правильные позиции, замораживание их, оставшаяся случайная перестановка (или на больших циклах я только что добавил результаты цикла предыдущего моделирования - то есть для цикла 2 добавил 2,00 в этой точке).

Я пытался многовещи во время compi, так что, возможно, были неаккуратными, но мои симуляции давали цифры, отличные от тех, которые можно было бы предположить.

цикл 3 - 3.5 (в отличие от 3) цикл 4 - 5.25 (в отличие от 4)цикл 5 - 6,4 ... (в отличие от 5)

???

Это странно?Затем с этими числами я нашел все циклы в наборе и добавил числа, которые я нашел.Очевидно, что это было неправильно, как и мои другие попытки.