Задача g6_1016: Диски (castle.ssu.samara.ru/olymp/ - задача 1004)

На полке имеются N коробок с CD-дисками. (1<=N<=100)
За 1 шаг можно либо снять любой из дисков с полки, либо поставить его между любыми двумя другими, либо с любого края.
За какое минимальное число шагов можно переставить диски так, чтобы в итоге все диски с одинаковой тематикой находились рядом?

input.txt:
название 1, тематика 1
...
название N, тематика N

output.txt:
K

где K - требуемое число шагов.

пример input.txt:
Web-Design 2000, web-дизайн
Quake III, игры
Windows 2000, софт
Коллекция клип-артов, web-дизайн

output.txt:
2

Решение g6_1016:

Эта задача со второго тура Самарской областной олимпиады школьников по программированию(задача 1004 на сервере областной олимпиады).
Итак, мы имеем набор строк с текстом, которые надо преобразовать во что-нибудь более простое для обработки. Для этого используем мою любимую хеш-функцию, считающую суммы ASCII кодов всех символов слова, в данном случае это будет тематика диска.
Теперь у нас есть массив чисел, где количество чисел равно количеству дисков. Теперь совершим над этим массивом преобразование, похожее на сжатие RLE. Заведем два массива, один хранящий хеш-функцию, а другой количество дисков одной тематики, идущих подряд. Т.е.:
1, 1, 1, 2, 2, 1
преобразуется в два массива:
1, 2, 1
3, 2, 1
Теперь найдем самую часто встречающуюся тематику и самую большую группу подряд идущих дисков этой тематики. А теперь начинается самое интересное - то, до чего я дошел сам :).
Мы нашли самую большую группу и теперь будем двигаться в обе стороны, ища группу таких же по тематике(самой частой!) дисков, при этом будем считать, сколько дисков лежат между самой большой и этой группой. Если количество дисков в группе меньше, чем количество дисков между этой группой и максимальной, то возьмем все эти диски и переложим к максимальной группе(обнулим значение количества дисков в этой группе). На каждый диск уходит две операции. Если же количество дисков в группе больше, то вынем все диски между этими группами(обнулим значения счетчиков) и забудем об этих дисках (не забыв прибавить к счетчику перестановок по 2 операции на каждый диск), это значит, что мы одной операцией мы взяли диск, а второй поставили куда душе угодно(куда надо).
Когда все наиболее часто встречающиеся диски будут сложены в одну группу, заменим ее хеш-код на 0, например, чтобы функция поиска наиболее часто встречающейся тематики не обрабатывала 0.
Теперь проведем проверку: если у всех дисков либо код тематики равен 0, либо длина последовательности подряд идущих дисков равна 0, то пишем значение счетчика перестановок и выходим из программы. Иначе повторяем с поиска самой частой тематике, пока не будет выполнено условие выхода.
Как оказалось это еще не все, теперь идет еще интереснее: наш читатель Axel нашел тест, на котором выше приведенное решение не работает.
Мы нашли количество перестановок с помощью эвристического алгоритма, однако это не всегда наименьшее количество. Теперь надо написать рекрсивную процедуру, реализующую полный перебор. Это делается точно также, (т.е. находим группу и идем от нее вправо-влево) но только мы рассматриваем два варианта - удалить диски между группами или перенести группу. При этом не забываем считать количество действие и, в случае если оно превысило значение эвристически найденного или текущего наименьшего в данный момент, то больше рекурсию не запускаем. Это позволит отсечь большую часть ненужных веток и ускорит полный перебор во много раз.
Скачать тесты к задаче