(1-k/длина слова) где к — количество переходов из маски в саму себя. Очевидно откуда он берется.

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

Теперь немного о решении. Есть замечательный алгоритм Гольдберга для поиска подграфа с максимальной средней степенью: http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-171.pdf В нем мы максимизируем sum(edges)/K, в нашем же случае в знаменателе стоит квадратичная функция. Однако оказывается, что такое же решение можно применить и в данном случае.

Будем делать бинпоиск по ответу. Пусть мы хотим проверить значение g. Тогда мы хотим проверить неравенство

sum(a_ij, i,j \in V1) / 2*(K*(200 - K)) < g

если умножить на знаменатель и перегрупировать получаем

sum(a_ij, i,j \in V1) < 398*g*K + K*(K-1)*2*g

квадратичный член в правой части можно внести внутрь суммы, получим

sum(a_ij + 2*g, i,j \in V1) < 398*g*K

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

Собственно я долго выводил эти выражения, где-то ошибся и в итоге 10 минут подбирал коэффициенты, чтобы прошло тесты :) К сожалению я упустил момент с точностью, буквально исправление одной строки делает решение правильным. Также я не успел написать нормальный поток, так что мое решение проходит в практисе за 1.8 секунды.

У меня было неправильно сведение, но Дима рассказал как надо правильно избавляться от квадратов в знаменателе. Идея следующая: пусть мы хотим проверить, превышает ли наш ответ X или нет. То есть, нам надо узнать, существует ли такой набор из k вершин с суммой весов ребер sum, что sum / (200k - k²) ≥ X.

это эквивалентно sum + k²X ≥ 200Xk

Всего суммарная степень в подграфе (k² - k) / 2. Назначим ребрам новые веса: newcost_ij = cost_ij + 2X. Тогда 2sum + k²X = newsum + 2kX. То есть, нам надо проверить newsum - 398Xk ≥ 0.

Получили задачу: проверить, существует ли в графе с новыми весами подграф, у которого средний вес ребра не меньше 199X. Это уже задача HardLife. Как ее решать, можно почитать здесь.

UPD: Дима сам меня опередил. Правда, у меня оно сдалось только после некоторых плясок с бубном вокруг эпсилона.