Не могу понять решение 275C (http://mirror.codeforces.com/contest/482/problem/C):
Я понимаю, как определять, является ли подмножество уникальным для строки, но не знаю, как найти вероятность выбора подмножества.
Она может быть различна для разных строк. Например, если даны строки
aax; aay; mnf
то подмножества из первых двух слева символов можно выбрать только для первых двух строк.
Разбор скрыт в черновиках.
Начинаем с пустого множества проверенных символов. Вероятность оказаться в этом состоянии равна 1. затем для всех множеств в которые мы можем перейти добавляем текущую вероятность делённую на
(длина строк - номер_шага), когда оказываемся в подмножестве однозначно идентифицирующем строку останавливаем процесс и прибавляем к ответутекущая_вероятность*номер_шага/n.UPD: Поиск в ширину делаем.
BFS придется прогонять заново для каждой строки, т.к вероятность выбора фиксированной подпоследовательности для различных строк может быть неодинакова
В итоге, O(N*(2^M+P))=O(NP), где P — число переходов между битмасками. Оно значительно меньше, чем 50*(2^N), но этот код все равно работает за 6с. на антитесте:
http://codepad.org/ZMS4Dh4c