B: Найти совершенный паросоч Куном, потом превращать его в лексмин по порядку. Берем первую вершину, перебираем ребро из нее в порядке возрастания номера, пытаемся найти цикл через это ребро, который можно прочередовать. Это примерно тот же дфс, что и в Куне. used между дфсами из одной вершины чистить не надо, так что одну вершину обрабатываем за квадрат. Потом надо убрать ее вместе с заматченной из графа.

D — была идея, что треугольник ненулевой площади и не содержит внутри или на границе целочисленных точек тогда и только тогда, когда для каждой стороны треугольника противоположная точка лежит на соседней параллельной стороне-прямой. Как такое считать не знаю, но возможно задача была рассчитана на прекалк + OEIS.

Я решал так: за K = 100 шагов с вероятностью очень близкой к 1 все завершится. Для каждой степени простого посчитаем динамику (или формулу) с какой вероятностью оно завершится за не более t ходов. Далее решаем за O(T * K * M). Можно ускорить примерно в M раз, понимая, что мало разных степеней простых в N, но заходит и без этого.

Действуем жадно с концов, подстроки сравниваем хэшами. Доказать жадность довольно легко от противного. В сумме надо сравнить ровно |S|/2 строк

Перевернем строку и вставим ее в саму себя (s₁s_ns₂s_n - 1... s_n - 1s₂s_ns₁). После этого нужно разбить строку на максимальное количество палиндромов четной длины. Решается жадником с манакером (или деревом палиндромов, даа).

Напишем dp_i — минимальное кол-во отрезков, на которые разбиваются первые i чисел. Тогда обновляем dp_i через dp_i - 1, если число не положительное, и через минимальное состояние j такое, что pr_i - pr_j > 0, всегда. Эти состояния будут образовывать некоторый префикс позиций, если отсортить по величине префикс-суммы. Там уже можно пожать все префикс-суммы и делать все в фенвике, например.

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

Звездочки переберем, теперь надо 2⁷ раз решить задачу без звездочек. Несложно понять, что каждое условие преобразуется в одно или два неравенства вида x_i ≤ x_j + c. Это стандартная задача, нужно для каждого такого неравенства провести ребро из j в i весом c, а потом посчитать какие-то кратчайшие расстояния (например Флойдом, хотя Фордом-Беллманом в данном случае быстрее; в любом случае нужно быть аккуратным с отрицательными циклами). Доказательство вроде через двойственность в ЛП, кажется я даже видел это как один из примеров в каком-то учебнике.

На самом деле у нас получается бинарное дерево, при если удалять вершины с конца, то каждый раз удаляется висячая вершина. Таким образом ответ для валидного набора отрезков — это произведение для каждой вершины цешки (общее количество детей в поддереве, количество детей в левом поддереве). Осталось проверить, валидное ли дерево (если нет — ответ ноль). Для этого надо проверить, что l_i <= i <= r_i, есть вершина с l_i = 1 и r_i = n и для любой вершины если отрезки (l_i, i — 1) и (i + 1, r_i) непустые, то они соотвествуют какой-то врешине

Решение основывается на алгоритме Грэхема. Переберём точку, которая будет с минимальной y, x. Меньшие точки выкинем. Отсортируем оставшиеся точки относительно по полярному углу. Теперь посчитаем dp[l][j][k] — минимальная площадь выпуклого многоугольника из l точек, заканчивающаяся на точках j, k.

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

Моё решение B мне немного громоздко. Каждое утверждение задаёт бесконечное множество отрезков t, в которые загорается зеленый цвет, чтобы наблюдение было верно. В диапазоне [0,g+r+y) каждое утверждение задаёт один или два отрезка. Посчитаем длину отрезков, которые попадают в диапазон [0,g+r+y) и покрываются ровно N отрезками. Вероятностью будет отношение длины с учётом вопроса к длине без него.

По задаче C ключевая идея, что есть очень небольшое количество n, для которых правильные n-угольников имеют целочисленные вершины. Поэтому задача решается за O(n^2 log N).

В задаче F пишется очевидное решение с хешами и дп, а потом доказывается, что оно отработает за O(n² * количестводелителейn). Проще доказывать, если перебирать сначала количество открывающих скобок.

Задача D