Как решить такую задачу?

[Ubermensch]

Самую первую отсюда.
Какой алгоритм решения?

[Munin]

Рассмотрите такие подзадачи:
1. Найти "однобуквенный палиндром", если в исходной строке ровно две одинаковые буквы, а все остальные уникальны.
2. Найти "однобуквенный палиндром", если в исходной строке ровно $n$ совпадающих между собой букв, а все остальные уникальны.
3. Найти "однобуквенный палиндром", если в исходной строке $k$ пар совпадающих между собой букв, а все остальные уникальны.
4. (полная задача) Найти "однобуквенный палиндром", если в исходной строке $k$ подмножеств по $n_i\,\,(i=1,\ldots,k)$ совпадающих между собой букв, а все остальные уникальны.

[Ubermensch]

1. Найдем места, на которых стоят одинаковые символы $a$ и $b$.
Найдем места - $x$ и $y$ - на которые они должны стать по формуле $N-a+1$ и $N-b+1$.
$\max(x,y)-\max(a,b)=c$
$\min(x,y)-\min(a,b)=d$
Количество перемещений равно: $(N-2)+((N-2)-1)...+1+d+c$.

Верно?

[Munin]

Почему они должны встать на места $N-a+1$ и $N-b+1$? Вы их меняете местами, а их надо только подровнять. Прочитайте внимательнее тот пример, который прилагается к задаче.

[Ubermensch]

Вот, например:
$a, b, x, b, r, d > d, r, b, x, b, a$
$1, 2, 3, 4, 5, 6 >1,2, 3, 4,5,6$

координаты наших одинаковых символов $b$ - $2$ и $4$
$6-2+1=5$, $6-4+1=3$. То бишь они должны стать на позиции $5$ и $3$.
А Дальше подставлять $5$ и $3$ в формулу с максимумами и минимумами.

Хотя я почти уверен, что у меня все очень сильно усложнено.

[Munin]

Нет. Символы должны встать на позиции 2 и 5. Или, на позиции 3 и 4.

Продолжайте попытки понять условие.

[Ubermensch]

Что я упускаю из вида?

Ведь любое слово будет удовлетворять тем условиям.
$a,b,c,d,e,f={1,2,3,4,5,6}$
$f,e,d,c,b,a={1,2,3,4,5,6}$
$a_1=a_6$ и так далее.
В чем моя ошибка с понятием условия?

[Munin]

После переворачивания слова задом наперёд, одна буква (не центральная) должна остаться на своём месте.

[Ubermensch]

Значит нам нужно посчитать, сколько нужно сделать перестановок, чтобы любые 2 одинаковые буквы были на одном и том же расстоянии от начала и конца слова. По отдельности, разумеется. То бишь одна буква была на $x$ месте от начала, а другая на $x$ с конца?
И почему не рассматриваются слова с нечетным кол-во букв?

-- 09.08.2012, 16:04 --

Этот алгоритм для общего случая верен?
Найдем центр слова.
Найдем позиции одинаковых символов: $A,B,D,E..$. Пусть позиция $A$ - ближе к центру, $B$ - максимально ближе к $A$. Дальше работаем с $A,B$.
Символ с позиции $A$ нужно переместить на позицию $(N-B)$, а для этого нужно сделать $A-(N-B)-1$ перестановок.

[Munin]

Ubermensch в сообщении #604497 писал(а):

И почему не рассматриваются слова с нечетным кол-во букв?

Можно и рассматривать, но надо быть внимательным, чтобы не посчитать центральную букву как совпадающую саму с собой.

Ubermensch в сообщении #604497 писал(а):

Этот алгоритм для общего случая верен?

Как я понимаю, он решает "подзадачу 2" из сформулированных мной.

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

А, и ещё, $B$ надо выбирать максимально близкой не к $A,$ а к $(N-A),$ но это уже прямая подсказка, не говорите модераторам, а то меня забанят.

[Ubermensch]

Цитата:

чтобы не посчитать центральную букву как совпадающую саму с собой.

Так почему не подходит вариант с тем, что центральная совпадает сама с собой. Если количество букв нечетно, то количество перестановок равно 0. Я так понимаю, что в примерах такой случай не рассматривали, так как он простой.

Спасибо за помощь. Загляните еще сюда завтра, а то сегодня времени нету. К завтрашнему дню к репетитору идти, а я еще не решил 30 задач, которые он задал. Завтра уже проработаю условие и то, что Вы написали, очень детально.

[Munin]

Ubermensch в сообщении #604718 писал(а):

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

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

-- 10.08.2012 15:17:23 --

Перечитал условие. Действительно, строка из нечётного числа букв является уже готовым однобуквенным палиндромом. Я был неправ.

[Ubermensch]

А такой алгоритм.
Ну если нечетное количество в символе, то выводим 0.
Далее находим все одинаковые символы.
Записываем их позиции в массивы.

Далее просто для каждого подмножества одинаковых символов ищем такую пару символов с позициями $A,B$, чтобы $|A-(N+1-B)|$ было минимальным.

[Munin]

Да, правильно.

Теперь реализовать.

-- 11.08.2012 18:01:24 --

И проверить, сколько времени выполняется, и сколько памяти занимает, если:

• символов в строке 300, их значения до 255 - чтобы набрать 50 баллов;
• символов в строке 5000, их значения до 1000 - чтобы набрать 80 баллов;
• символов в строке 250 000, их значения до 65535 - чтобы набрать 100 баллов,

причём брать наихудшие случаи по размеру подмножеств и по числу подмножеств одинаковых символов. Время выполнения должно укладываться в 1 сек, занятая память - в 128 МБ. Боюсь, для 100 баллов придётся изменить алгоритм. Вообще задания олимпиады непростые и рассчитаны на суровую оптимизацию.

[Ubermensch]

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