Это и есть условие первой задачи.

Похоже на еще один условно внезачетный

http://acm.spbgu.ru/divone-e.pdf http://acm.spbgu.ru/divone-r.pdf http://acm.spbgu.ru/divtwo-e.pdf http://acm.spbgu.ru/divtwo-r.pdf

Как решать D? Если A == D, B == E, C == F, то вроде есть явная формула; иначе мы не придумали ничего умнее, чем использовать алгоритм для количества полных паросочетаний в планарном графе; но там в конце надо извлечь квадратный корень из определителя, из-за чего Гаусса приходится делать в BigInteger'ах, а это адски долго.

Как решать E? Писали min-cost-flow c кучей оптимизаций, TL 28.

Как решать A?

А кто-нибудь сдал такое очевидное решение по А — покрасить ребра из какой-то вершины в 3 цвета, а дальше пустить из нее dfs и на каждом шаге перебирать 2 варианта покраски? Получается асимптотика O(2ⁿ * m), но что-то не верится, что это зайдет.

Опровергните кто-нибудь идею по Е. Посмотрим как будет работать min-cost (max-cost). Он будет все время искать в графе путь из истока в сток максимальной длины. Он найдет удлиняющую цепь в двудольном графе, которая начинается в вершине v1 и заканчивается в v2 + ребро из истока и ребро в сток. Собственно, для этой задачи все ребра, кроме ребер из истока и в сток нулевые. Тогда отсортируем все пары вершин, первая из первой доли, вторая из второй, отсортируем их по убыванию суммы весов. Потом будем в этом порядке искать удлиняющую цепь начинающуюся в в вершине из первой доли и заканчивающуюся в вершине второй доле (из текущей пары). Если хотя бы одна из вершин пары уже покрыта паросочетанием, не будем ничего делать. Казалось бы, минкост будет делать то же самое. Но наше решение упорно получало ВА4. Кто-нибудь может найти ошибку или у нас таки бага?

Поздравляю ИТМО 1 с досрочной победой в общем зачете

что написали итмо1 в G за такое малое время?

What is the 44th test in Div2 T like?

Я хотел бы, как автор задач A, E, G и H, поделиться некоторыми мыслями/решениями. Если какие-то мысли уже были озвучены, для полноты картины я их приведу еще раз.

0. Все мои решения укладываются в TL >= 4 раз.

1. Задача G.

В задаче G подразумевалось решение за время O(2^k n). Если вы писали решение за O(2^k nk), оно могло получить TL (зависит от оптимальности кода).

Одно из решений за O(2^k n): рекурсивно перебираем 2^k масок "какие символы совпали", в рекурсии на каждом шаге за O(n) пересчитываем хэши n подпоследовательностей и в конце за O(n) с помощью хэш-таблицы проверяем, какие хэши встречаются хотя бы дважды.

2. Задача A

В задаче A я знаю 2 решения. Оба пользуются мыслью, что в графе нет вершин степени больше 3 (иначе ответ — NO).

Первое за O(2ⁿ). По сути то же, что и писал I_love_natalia здесь. Красим компоненты связности не зависимо; пусть граф связен; взяли произвольную вершину v; покрасили ребра, выходящие из v, в произвольные различные цвета; обойдем граф dfs-ом из v; когда мы входим в вершину x, всегда одно из смежных x ребер уже покрашено, покрасить остальные смежные x ребра можно не более чем двумя способами, переберем оба способа. Для этого решения есть мощная оптимизация, после которой оно начинает "летать": при покраске в ровно 3 цвета заметим, что если у какого-то ребра не более двух соседей, можно это ребро выкинуть из графа, покрасить оставшуюся часть графа, а в конце покрасить это ребро в оставшийся третий цвет. Будем выкидывать так ребра, пока можем. От этого граф стал более насыщенным, многие варианты покраски будут сразу отметаться.

Второе за O(3^n / 2 m): пока в графе есть вершина степени 3, берем ее и перебираем, какое из трех смежных с ней ребер мы покрасим в цвет 1. Покрасив ребро в цвет 1, помечаем его "уже покрашенным" и уменьшаем степени концов. Таким образом есть всего 3^n / 2 вариантов свести задачу к случаю "степени всех вершин не больше двух", а это набор путей и циклов, которые можно раскрасить жадно. Всё кроме нечетных циклов красится в 2 новых цвета. В нечетном цикле нужно одно ребро покрасить в цвет 1, проверим, есть ли такое.

3. Задача H

Для начала можно развернуть карту по x и по y так, чтобы идти нужно было только в направлении x++ и y++.

Теперь решение — посчитать динамику f[x,y] = сколько времени займет от точки (x,y) дойти до конца. Зная f[x+1,y] и f[x+2,y] и f[x+1,y+1] и f[x,y+1] и f[x,y+2] легко посчитать f[x,y]. Для этого нужно разобрать несколько случаев и посчитать интеграл от 0 до 2t от кусочно линейной функции f(w). Один из способов посчитать интеграл следующий: разбиваем 0..2t на промежутки 0..t-s..t..2t-s..2t, на каждом отрезке f(w) устроена как min(const₁, const₂ — w). Берем точку излома, делим промежуток еще на два, интегрируем линейную функцию.

4. Задача E

Для задачи E мне известны 3 решения, все за O(VE).

Первое через min cost flow. Похоже на то, что описал tunyash здесь. Есть двудольный граф + исток + сток, веса из истока = w1, веса между долями = 0, веса в сток = w2. Ищем максимальный по весу путь из истока в сток. Он имеет вид "первое ребро — много нулей — последнее ребро". Итого, чтобы максимизировать вес пути, достаточно сделать следующее: переберем вершины первой доли в порядке убывания веса, если мы в вершине еще не были, запустим из нее dfs "по нулевым ребрам". При этом для каждой вершины второй доли мы нашли максимальную по весу вершину первой, от которой существует путь (это та вершина первой доли, из которой мы пришли dfs-ом). Выберем вершину второй доли такую, что "ее вес + вес ее потенциальной пары" максимален, они и образуют дополняющий путь.

Второе такое (его, например, сдала команда SPB Angry Muffin): сперва максимизируем сумму весов в первой доле. Это делается так: сортируем по убыванию веса и в таком порядке ищем дополняющие пути Куном. Теперь рассмотрим два паросочетания: текущее и оптимальное. Рассмотрим их симметрическую разность. Поймем, что нечетных путей быть не может, четные циклы нам не интересны, четные пути начинающиеся и заканчивающиеся в первой доли нам тоже не интересны. Остаются четные пути, начинающиеся и заканчивающиеся во второй доли, улучшающие ответ. Будем их искать следующим образом: отсортируем вершины второй доли по убывания веса и в таком порядке будем запускать dfs-ы, которые ищут дополняющие чередующие пути четной длины (поменять одну вершину 2-й доли, на вершину 2-й доли с большим весом).

Третье описал ilyakor здесь. Кстати, интересно по поводу "можно доказать, что оно всегда найдётся"... Это возможно доказать без матроидов? Например, если веса только в одной доле, очевидно, что жадность работает "потому что min cost flow".