Задача про магическую перестановку

[Equinoxe]

Нам дана перестановка. За действие мы можем выбрать какое-то подмножество, а затем magic-swapper расставит элементы этого подмножества в некотором порядке, при том любой порядок может выпасть с одинаковой вероятностью. Мы действуем всегда рационально, т.е. чтобы мат. ожидание кол-ва действий было минимально. Каково мат. ожидание кол-ва действий для некоторой перестановки?

Например, для перестановки 2 1 4 3 это 4.0, для 1 3 2 — 2.0

[Equinoxe]

*цель действий — отсортировать перестановку

[ИСН]

У вас есть за пазухой топор вероятностной стратегии в каком-нибудь случае, или мы могли бы just as well сказать "magic-swapper расставит любые k элементов в любом порядке и возьмёт с нас за это k! фишек, найдите самый дешёвый что-то там"?

-- Вс, 2011-05-08, 00:50 --

Дурацкий вопрос; конечно, есть.

[venco]

Попрошу пока воздержаться от советов по задаче, т.к. соревнование ещё не закончилось.

[Equinoxe]

venco, мной уже сдано, да и закончится через час :) А Вы тоже участвуете? Ну как? Под каким ником?
Просто не могла удержаться, так уж понравилось ^_^

[age]

Equinoxe в сообщении #443259 писал(а):

*цель действий — отсортировать перестановку

отсортировать по возрастанию? По убыванию? Как отсортировать?

[Equinoxe]

age, по возрастанию, хотя задачи это никак не меняет :)

(Оффтоп)

Контест закончился, у меня все корректы! Буду ждать онлайн раундов, которые только 21-ого мая начнутся

[venco]

Equinoxe в сообщении #443272 писал(а):

venco, мной уже сдано, да и закончится через час :)

Ну теперь закончился.

Цитата:

А Вы тоже участвуете? Ну как? Под каким ником?

venco5

[Equinoxe]

venco, о, у Вас даже место хорошее :) А я сегодня за несколько часов до конца написала, написала все кроме второй — спортивного интереса не было :(
А Вы доказывали решение последней задачки? Или просто заметили?

(Оффтоп)

Успехов на предстоящих раундах!