да. это с петрозаводских сборов.

дорешивание уже открыто на сайте

Мы Гаусса сдали.

Понятно, что нам нужно оставить такое подножество, чтобы XOR любого его подмножества был не равен 0.

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

Код: http://pastie.org/3413601

А кто-нибудь решение M не за K^2 знает?

Я делал так: Представим, что каждая цепь — это вершина графа. Какая-то часть цепей будет сверху, а какая-то снизу. Цепи на одной стороне не пересекаются.

Выходит, что надо разделить граф на две доли, где ребра будут только из одной доли в другую. Делить вершины на двудольный граф можно дфс'ом, там же и проверить на возможность это сделать. Просто если есть цикл нечетной длины, то impossible.

Мы решали М так:

Отсортируем все отрезки по их началу. Заведем 2 стека — нижние и верхние дуги, для каждой дуги будем хранить ее конец.

Для каждого отрезка надо сначала доставать из стека те дуги, которые закончились раньше его начала. Затем пытаемся провести дугу с той стороны, где координата на вершине соответствующего стека меньше. Если так сделать не удается, то пытаемся провести дугу с другой стороны.

Если получается, то заносим в стек координату новой дуги (по нашему алгоритму она всегда будет наименьшей из всех координат в стеке). Если не получается ни с одной, ни с другой стороны, то провести дугу невозможно и надо выдать "impossible".

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

Данное решение работает за один пробег по циклу, каждый отрезок 1 раз кладется в стек и достается из него, то есть асимптотика алгоритма O(K)

Значит сложность не O(|S|*26) (или константа неоправданно большая). Я тоже делал за O(|S|*26) -- и ВА49 как бы намекает, что такая сложность должна заходить по времени.

если кому интересно, вот код зашел с первого раза. Правда там некоторый изврат с определением переполнения, а так вполне понятно =)

Подвешиваем дерево за 0 вершину. Раздваиваем каждую вершину еще одной фиктивной с временем дохода до нее равным 0 и временем обработки d_i (чтобы обработку текущей вершины тоже считать как обход поддерева). Подсчитаем суммарные k_i и суммарные времена обработки t_i каждого из непосредственных поддеревьев. Пусть v_i = k_i / t_i. Тогда нетрудно показать мы должны обходить деревья в порядке от больших v_i к меньшим.

Пишем перебор для мелких n и k=b/a (с помощью map<vector<int>, bool>), распечатываем ответы, находим закономерность.

for(int i = p; i < r; i++)

Это цикл из метода calc. Мне кажется, что здесь должно быть i = l.

Мне кажется хорошо бы если выкладываешь в паблик адекватно называть ролик (например, "2011-2012 Зимние Петрозаводские сборы, контест Саратовского ГУ (открытый кубок), разбор задач") и расставить теги. Просто через годик-другой ссылка потеряется, наплодится еще роликов с похожими именами и трудно будет найти то, что нужно.

для каждого ребра лучший ответ — это длина ребра плюс расстояние от конца ребра до начала

Инициализируем матрицу расстояний d следующим образом: вершина a видит вершину b, если отрезок их соединяющий не пересекает ничего плохого и b находится по часовой стрелке от a, тогда d[a][b] = dist(a,b), во всех остальных случаях (включая a = b) d[a][b] = inf. Запускаем обычного флойда. Величина наименьшего цикла — минимум среди значений d[i][i].

В архиве Петрозаводска четвёртый тест такой:
4
abcdef
edc
baxyzprq
pzyx