Задачка про перестановки

[Cronopio]

Не уверена что можно пердложить конструктивное решение, но вдруг:

Есть Н шариков на прямой у каждого есть приписанное число ч1,..., чН - перемещаемость
Операция: соседние шарики можно менять местами, при этом перемещаемость шарика, который оказался правее исходной позиции уменьшается на 1.

Нужно: найти как поменять шарики местами так, чтобы все оказались на своих местах и перемещаемость у всех была 0 (рассматриваются только случаи когда это возможно)

[незваный гость]

Cronopio писал(а):

Нужно: найти как поменять шарики местами так, чтобы все оказались на своих местах и перемещаемость у всех была 0 (рассматриваются только случаи когда это возможно)

Уж не стоят ли они сразу на своих местах? А менее иронически, что значит шарик стоит на своем месте? Есть ли е него номер помимо чН? Или имеется в виду то же самое место, с которого шарик начал?

[Руст]

Предлагаю такой алгоритм. Берём шарик с максимальным числом перемещаемостью и начинаем его двигать слева направо, пока у него перемещаемость максимальна или не дошли до правого конца. Потом берём следующий шарик с максимальным числом перемещаемости и перемещаем слева направо, пока он не дошёл до правого конца или не потерял максимальность и т.д. Если задача имеет решение, то этот способ обнуляет все числа перемещаемости.
Только, что значит в свои места я не понял из приведённого условия задачи.

[Cronopio]

извините, плохо сформулировала

у шариков есть еще номера. Изначально первый шарик стоит на месте номер 1, на этому же месте он должен оказаться после перестановок (поэтому проблема, шарик нужно переставлять и обратно, что уменьшает перемещаемость остальных шриков, которая и так могла быть уже 0)

[PAV]

Все шарики изначально стоят на своих местах? Т.е. задача по сути в том, чтобы избавиться от перемещаемости, вернув в итоге все на место? Правильно ли я понял, что при смене местами двух соседних шариков перемещаемость одного уменьшается на 1 (того, который перемещается слева направо), а перемещаемость второго не меняется?

[Cronopio]

PAV
да, именно так

[незваный гость]

Поскольку задача конечна (каждая перестановка уменьшает сумму "подвижностей" на единицу), то возможен полный перебор. Полный перебор является хотя и медленным, но конструктивным алгоритмом, который либо выдаст положительный ответ, либо остановится, доказав, что решения не существует.

1) если сумма подвижностей нечетна, то (если я не ошибаюсь), решения не существует, и искать бесполезно.

2) Задачу уместно решать методами динамического программирования, это заметно сократит переборы (за счет увеличения затрат памяти).

[Cronopio]

незваный гость
Ну шариков 100, перемещаемость у всех порядка 20, суммы естественно четные (на это я поставила проверку)
А сложность алгоритма - порядка Н в степени суммарная перемещаемость... Итого: не реально
Должно быть очень сильно облегчающее пербор соображение, но я догадаться никак не могу

[PAV]

А откуда такая задача, если не секрет? Просто учебная или за ней что-то более существенное стоит?

[Cronopio]

PAV
Честно говоря, скорее учебная. Задачка по программированию, с соревнований, чуть-чуть преобразованная.

Решение точно есть

[Sasha2]

Ну а вообще задача, наверно имеет решение только в том случае, если самый правй шарик имеет самую низкую перемещаемость, то есть стоит на своем месте. Ну а дальше по моему просто элеменарно, меняем местами два соседних туда-сюда, до тех пор, пока эта перемещаемость не обнулится. Или я, что то не так понял?

[Руст]

Sasha2 писал(а):

Ну а вообще задача, наверно имеет решение только в том случае, если самый правй шарик имеет самую низкую перемещаемость, то есть стоит на своем месте. Ну а дальше по моему просто элеменарно, меняем местами два соседних туда-сюда, до тех пор, пока эта перемещаемость не обнулится. Или я, что то не так понял?

Это неверно. Например n шариков с перемещаемостью 1 для всех кроме крайней правой, а у последнего перемещаемость n-1. Задача решается почти однозначно. Вначале все шарики начиная со второго перепрыгивают через этот шарик, а потом он перепрыгывает через остальные.
Неверно и то, что задача решается обнулением чисел перемещаемости начиная с крайнего.
Например 4 шарика с перемещаемостями (2n+1,1,n,n) n>1 (первый ход самим левым шаром)или (n,n,1,2n+1)(первый ход третьим шаром).
Так как шары не должны сместится с места, то количество перепрыгиваний через данный шарик должен равняться числу перемещений этого шарика. Например, если у шарика число перемещений равна нулю, то этот шарик разрывает цепочку шариков, так как нельзя через него перепрыгивать и нельзя его сдвинуть.

[незваный гость]

Cronopio писал(а):

Задачка по программированию, с соревнований, чуть-чуть преобразованная.

В разделе "Математика" интересует только принципиальная разрешимость. По-моему, гвоздь не от этой стенки, а точнее, задача из неправильного форума.

Но это, наверное, уже не важно, коль скоро мы поняли друг друга и задачу вместе.

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

[Руст]

Назовём промежутеи между соседними шарами с числом перемещаемостью 0 связной компонентой. Для этого форьмально добавим ещё шары с номерами 0 и n+1 с числом перемещаемости 0.
Определим для каждой связной компоненты число $S=\sum_i x_i -2max_i x_i.$
Тогда необходимым и достаточным условием существования решения является то, что для каждой связной компоненты S является неотрицательным чётным числом.
О необходимости этого условия уже говорилось и оно очевидно. Достаточность получается алгоритмом обнуления чисел перемещаемости. Так как в каждой компоненте обнуление идёт независимо, будем считать, что что у нас одна компонента связности, т.е. все числа перемещаемости положительные целые.
Для доказательства достаточности можно предъявить соответствующий алгоритм.
Обозначим через y(i) суммы чисел перемещаемости слева от i -го шара, а через z(i) справа.
Тогда можно определить левую (i,k) операцию как k шаров слева по очереди перепрыгивают через i шар, а потом i шар перепрыгивает через них. При этом каждый шар может перепрыгивать t(j)>0 раз через i-ый шар, соответственно их числа перемещаемости уменьшается на t(j), а у i-го шара на t(i-1)+t(i-2)+...t(i-k). Аналогично можно определить правую (I,k) операцию. Каждая такая операция возвращает все шары на свои места и уменьшает числа перемещаемости указанным образом. Несложно доказать, что если исходное положение удовлетворяет необходимому условию, то существует левая или правая операция указанного типа, которая уменьшает числа перемещаемости и после применения этой операции не нарушается необходимое условие. Это доказывает достаточность и составляет алгоритм обнуления.

[Cronopio]

незваный гость
Есть надежда что найдутся хорошие математические соображения, похволяющие ее решить, поэтому сюда и отправлена

Руст Да, об этом я думала и операции такие определяла. Проблема в том, что они кажется не исчерпыва.т все возмодности. Например в такой позиции: 10 1 1 1 1 10 надо свести 10-тки вместе и менять их местами 8 раз а потом вернутьна место. Я не вижу как это получится операциями вида "переместить влево/вправо на к а потом обратно".

На компоненты разбивала. Думала например вычесть из всех перемещаемостей наименьшую и смотреть на получившиеся. Но оно, конечно, честенько приводит к неразрешимым позициям