Форум DL

Мой профиль

Тут увидел...
http://www.spoj.pl/status/krishkinn,ABWORDS/
Круто!!!
Эту задачу несколько лет не могли решить всей сферой ;)
Руслан, не хочешь поделиться идеей????

Мой профиль

Я бы не сказал, что это полное решение. Но расскажу. В этой задаче две подзадачи:
1. Быстрое сравнение двух слов
2. Нахождение максимального полного подграфа(количество вершин=1000)

С первой подзадачей я справился так:

Строку переводим в массив чисел. Число на i-той позиции означает сколько букв b идет за i-той буквой a.
Например, строке aabbabab соответствует следующий массив: (0,2,1,1)
Далее пишем рекурсивную функцию для сравнения двух слов(максимально быструю). Хорошей оптимизацией является подсчет нулей. Т.е. если в двух "словах" количество нулей не совпадает, то это разные слова.

Со второй подзадачей возникла проблема. Я до сих пор не знаю, как быстро ее решить.
Я написал рекурсивный перебор и сделал ограничение на количество вызовов процедуры(100000 хватило).

Может есть идеи, как с этой подзадачей справиться лучше?

Мой профиль

По поводу поиска подграфа:
Это по сути поиск максимального независимового множества. Для двудольных графов искать можно(кол-во вершин минус максимальное паросочетание). В общем случае не знаю...
P.S. На SPOJ есть задача INTSS (Rus
Eng) на эту тему. Если придумаем, как решать, то может это поможет и здесь.