Как решал я. Для каждого слова посчитал хэш, запихал все в сет. Потом для каждого префикса каждого слова считал его хэш, и хэш оставшейся части (амортизационно - за О(1) ), и проверял, есть ли хэши обеих частей в сете. Почему-то упорно получал ВА(5). Кто сдавал так же - в чем может быть проблема, и заходило ли такое решение?

Не писал, но вроде бы все что надо - аккуратно построить граф с вершинами-участками и ребрами-стримостями сноса стен между ними, и затем в нем найти минимальное остовное дерево. Вопрос - что делать с внешней территорией. Можно рассмотреть 2 случая: когда она не входит в оптимальное решение (просто строим остовное дерево в исходном графе) и когда входит (по сути, получаем еще одну вершину в исходном графе).

Буду благодарен за разбор

UPD: разбор от Jokser'а см. ниже в комментариях

Противная задача с нечеткими ограничениями, но все, что нужно - как-то написать то, что описано в условии. Для быстрой проверки того, выбрал ли пользователь i приложение j я завел битовую матрицу 10000 x 10000, проверку для каждого пользователя делал фактически в лоб (даже без всяких бинпоисков), логично предполагая, что хитрых тестов с такими раздолбайскими ограничениями не будет. Задача зашла мгновенно.

Почему-то относительно мало участников сдавали, хотя задача, имхо, проще той же D. Выполняем бинпоиск по ответу, для каждой длины в лоб за O(N²) проверяем, подходит ли эта длина. При заданных ограничениях без всяких оптимизаций просто летает.

UPD: как указал jte ниже, задачу можно решать даже целочисленно (если умножить все длины на 2 и потом не забыть разделить ответ на 2), что еще более ускоряет поиск ответа.

Посидев несколько минут с карандашиком, можно было вывести нехитрую формулу при A <= B;