CodeJam 2011: решение для Горошорта?

Ответ 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 раза. (Мы должны оставить их свободными, потому что они образуют один цикл.) Таким образом, этот подход, хотя и более сложный, выполняется так же быстро, как и исходный.

Ответ 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-х плохого состояния, чтобы быть переворотом с вероятностью 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.)

Ответ 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, чтобы никто не находился в правильном месте.
• (n-k)!, количество способов или расположение других элементов

Итак 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+...)

So E[n]=n для n >= 2 доказано (btw E[1] - undefined и count[1]=0)

Таким образом, ответ на эту проблему - это просто подсчет таких чисел не в их правильной позиции.

Я написал решение этого раунда в http://www.chaoswork.com/blog, но этот блог написан на китайском языке, поэтому в этом я отправляю свой идея снова на английском языке.

Ответ 4

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

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

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

цикл 3 - 3,5 (в отличие от 3) цикл 4 - 5,25 (в отличие от 4) цикл 5 - 6.4... (в отличие от 5)

???

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