Ну ты махнул конечно, что "заметим при помощи Гаусса". Чтобы понять, что последовательность — линейная рекуррента k-го порядка, нужно знать по меньшей мере 2k - 1 её членов (т. к. нам нужно запустить Гаусса на квадратной матрице, i-я строка которой состоит из чисел a_i, ... a_{i + k - 1}). А 72 член, не говоря уже о 143, это очень большое число (72 член — 602929610, а 143, соответственно, должен быть порядка квадрата этого числа).

Возникает вопрос — откуда взять эти 143 члена? Я вот не умею их получать никак, кроме моделирования строки, которым дальше первых 70 членов не убежишь. Я на туре (в Петрозаводске) убил тучу времени на эту задачу, проверил гипотезу о линейной рекурренте вплоть до 30 порядка (Гауссом), не увидел линейной зависимости, пожал плечами, и пошёл думать над другими задачами.

Был весьма раздосадован, узнав, что направление мысли было правильное. Так и не знаю, как бы посчитать первые 143 члена, не вдаваясь в теорию атомарных выражений.

For F, but even if you know they are composed of atomic sequence, how do you find them? I mean different sources say there are around 92 atomic sequence. How can we find all of them?

Утверждается, что любое место вида >< можно "пофксить" за 1 или за 2 [1] и можно жадно проверять, что фиксится за 1, а что не фиксится(тут подробнее не умею)

[1]: В самом деле, пусть нельзя за 1, тогда видим, что это не последний ряд и если добавить ряд снизу, то будет что-то типа

><
^^

а это можно превратить в

v<
>^

Мы сдали такой жадник. Представим все конфликты доминошками. Теперь будем уничтожать такие доминошки, которые можно уничтожить за 1 операцию, при этом не повернув чувака в другую доминошку. То есть условие поворота чувака — он повернется в того, кто в него не смотрит и не в конфликт. Потом можно доказать, что для каждой компоненты связности доминошек мы можем все разрулить, за число доминошек в ней +1.

Не понимаю, как в B можно было придумать mincost, когда там есть куда более очевидное решение. Построим граф. В нём из каждой вершины исходит не более одного ребра. Значит, каждая компонента связности — либо дерево, либо цикл, к каждой вершине которого подвешено дерево. Понятно, что нам нужно избавиться от циклов длины 2. Очевидно, что из двух вершин, смотрящих друг на друга, нужно повернуть только одну. Мы можем повернуть её не более чем тремя способами: чтобы она смотрела за пределы поля, чтобы она смотрела в другую компоненту связности или чтобы она смотрела на одного из своих сыновей. В первых двух случаях новых конфликтов не возникает, в третьем нужно повернуть сына аналогичным способом. Получаем такое решение: запускаем dfs, для каждой вершины считаем минимальную стоимость того, чтобы она смотрела в другую компоненту или за пределы поля, и прибавляем длину пути от корня для неё(весом ребра считаем то, сколько надо заплатить, чтобы родитель посмотрел на сына). Из всех вершин в дереве выбираем вершину с минимальным значением. Потом берём минимум из ответа для каждой из двух вершин лежащих на цикле. По-моему, это самая простая задача контеста.

Разбиваем все прямые на семейства (по параллельности). Далее, отмечаем на абсциссе всевозможные точки пересечения с этими семействами. Строим граф — (точка на абсциссе, номер семейства). По условию задачи нам теперь надо найти максимальное паросочетание Диницем. Да, у меня WA2, ибо решение отправил за три минуты до конца:(

Довольно "потоковый" контест получился — D и H тоже можно свести к потокам.

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

Дальше разобьем прямые на группы по точке пересечения с осью, опять сделаем тот же трюк с фиктивными вершинами — из каждой прямой пустим ребро пропускной 1 в ее фиктивную вершину, из каждой фиктивной в T — ребро с пропускной 1. Так мы выполним второе условие (о различных точках пересечения с осью).

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

H — рассмотрим квадрат евклидова расстояния. При изменении одной из координат вектора изменение значения этого выражения не зависит от других координат, а в сумме (u-v)^2=u*u+v*v-2*u*v нас интересуют только v*v, потому что все остальное — суммарно по всем слагаемым дает константу независимо от нашего максимального паросочетания. Получаем сведение к минкосту — между работниками и работами ребра как в инпуте, из S в каждого работника одно единичное ребро стоимости, равной пенальти (на сколько изменится сумма штрафа) за первую взятую работу, одно единичное ребро стоимости, равной пенальти за вторую взятую работу, и так далее.

Ту же идею "нам выгодно брать как можно более равномерно" многие команды использовали, чтобы вместо минкоста сдать итеративное решение, которое на каждом шаге ищет паросочетание.

E нужно было решать независимо для каждого цикла. Чтобы получить цикл длины 1 нам требуется ноль перестановок, для цикла длины 2 — одна. Если длина цикла больше, чем 2, то нам требуется две перестановки. Пусть цикл состоит из элементов a₁, a₂, ..., a_k. Тогда первая перестановка меняет местами a₁ и a_k, a₂ и a_k - 1 и так далее. Вторая перестановка меняет местами a₂ и a_k, a₃ и a_k - 1 и так далее.

Можете опубликовать апелляцию здесь.

На yandex.contest можно дорешивать сразу после завершения контеста.

У нас такое ва22 по Д. Выложи код

Сначала заметим что все звёздочки можно раскрывать пустой строкой, если раскроем иначе, то ответ не улучшится. А дальше рекурсия. Разобьём выражение на блоки разделенные "|", то что в скобках пока не трогаем. Если получился один блок, то рекурсивно раскроем скобки и вернём то, что получилось. Если блоков два и более, то раскроем их рекурсивно и вернём лексикографически наименьший результат минимальной длины.

Код