Wataru

Если проблема только с тем, что у вас циклов слишком много, то можно 3 последних объединить в 1.

Вы при каком условии должны числа дописывать в ответ? Пока есть число хоть в одном из двух массивов.
Вот и получается:
while (i < M || j < N)
Но внутри уже чуть побольше случаев. Можно просто ваши же условия объединить. Если выполняется условие первого цикла - делаете тело первого цикла. Иначе, проверяете условие второго цикла, делаете его, иначе - тело третьего цикла.

Но можно знатно сократить код, если просто расписать все варианты, когда вы берете число из A. В противном случае, очевидно, берется число из B. Число из A берется, если оно есть и оно "лучше" числа из B - или B вообще нет, или A < B:

if (i < M && (j == N || A[i] < B[j])) {
  C[k++] = A[i++];
} else {
  C[k++] = B[j++];
}

Тут считаются 2 динамических программирования: 1) Сколько вариантов раскрасить поддерево так, что ни одна вершина не изолирована. 2) Сколько вариантов раскрасить поддерево так, что ни одна вершина кроме корня не изолирована, а корень изолирован.

Считается снизу вверх, в "стеке" получаются вершины для которых значения уже подсчитаны - изначально листья. n, k - это как раз значения ДП в текущей вершине и в отце. текущей вершины.

В структуре tree для каждой вершины хранится 2 объекта. Под индексом 0 - пара значений дп, под индексом 1 - список соседей в дереве.

next получается значение этой структуры для отца, cur - для текущей вершины.

Тут считается динамическое программирование f(i,j) - количество перестановок из i элементов с j инверсиями.

База: F(0, 0) = 1, F(i, j) = 0
Переход: F(i,j) = sum_t=0..min(j, i-1) F(i-1, j-t)

Тут мы берем все перестановки из i элементов и группируем их в зависимости от того, где стоит максимальный элемент. Этот максимальный элемент добавляет t - от 0 до min(j, i-1) инверсий. Если мы его выкинем, останеся перестановка из i-1 элемента и, чтобы полная перестановка имела j инверсий, эта урезанная должна иметь j-t.

Оба кода хранят только одну последнюю строку и пересчитывают ее через сумму на предыдущей итерации.
Ведь
F(i,j) = F(i-1, j-i+1) + F(i-1, j-i+2) +... + F(i-1, j)
F(i,j-1) = F(i-1, j-i) + F(i-1, j-i+1) +... + F(i-1, j-1)
Вычтя второе уравнение из первого получаем: F(i,j) -F(i,j-1) = F(i-1, j) - F(i-1, j-i). Или F(i,j) = F(i-1, j) - F(i-1, j-i) + F(i,j-1). Это ровно формула в первом решении.

В первом коде A - это вычесляемая текущая строка, B - копия предыдущей строки.
Во втором коде s - это текущая строка и следующая вычесляется прямо в этом же массиве. В переменной ss поддерживается сумма F(i-1,j-i+1)+..+F(i-1, j-1).

Ответ к задаче - это F(n, k)+F(n,k-2)+F(n,k-4)+...+F(n, k %2), потому что за каждую операцию мы или делаем +1 или -1 к количеству инверсий. Можно сколько-то раз сделать +1 -1, а потом сделать сколько осталось +1 и мы получим перестановки с инверсиями от 0 до k но той же четности, что и k (потому что каждая -1 вместо +1 уменьшает количество инверсий на 2).

Это формула просто уже причесана и разложенна на множители. Это 12Y+8 (не X, кстати) идет в слагаемом (12Y+8)*(X+Y*Ai)

8 там - это 4*2. 4 дерева и 2 новые вершины. Подробнее ниже.

Как подсчитать все расстояния? Давайте отдельно посмотрим на те, которые внутри копии из 4 деревьев. Это даст нам слагаемое 4*Answer. Теперь подсчитаем те, которые идут между двумя разными деревьями. Их можно рзабить на 2 части - куски среди 5 новых ребер длины Ai и куски внутри деревьев. Вот эти куски внутри деревьев они все будут из угла, которым дерево крепится к остальным. Поэтому нам надо считать вот эту вот сумму расстояний от угла дерева (X).

Новые ребра посчитаем отдельно. В скольки путях каждое ребро будет присутствовать? Это надо перемножить количество вершин с одного конца ребра на количество вершин с другого конца. Ведь из каждой из первых есть путь во вторые, проходящий через данное ребро. Для 4-ех новых ребер размеры кусков будут Y и 3Y+2. Вот мы получили 4*Y*(3Y+2)*Ai. Вот тут если 4 внести внутрь мы получим вот это самое 12Y+8 из вопроса. Для одного ребра размеры будут 2Y+1 и 2Y+1. Вот мы получили слагаемое (2Y+1)^2*Ai.

Дальше надо посчитать, сколько раз каждый кусок в дереве из угла пойдет в ответ из путей между деревьями. Опять же, ровно столько раз, сколько вершин можно взять в качестве другого конца. Таких веришин 3*Y+2 - в любом из трех остальных деревьях или 2 новые вершины. Но эти куски в каждом из 4 деревьев, поэтому надо домножить на 4. Это дает нам слагаемое 4*X*(3Y+2). Тут тоже вылезает 12Y+8.

Вот и получается формула там.
Чтобы пересчитать Y, понятно что надо умножить на 4 и прибавить 2. 4 дерева 2 новые вершины.

Вот с X по сложнее. Во-первых. там могут быть пути внутри одного дерева. Получаем слагаемое X. Во-вторых, надо посчитать, сколько раз каждое из новых ребер войдет в ответ. Ребро у дерева с углом с одной стороны имеет ровно одну вершину конец - угол. С другой может быть в любом дереве или в одной из 2 новых вершин. Поэтому получаем слагаемое (3Y+2)*Ai Ребро между новыми вершинами с одной стороны может кончатся в любом из 2 деревьев или в новой вершине. Получаем (2Y+1)*Ai. Оставшиеся 3 ребра ведут только в одно дерево и дают 3*Y*Ai.

Куски путей внутри других деревьев однозначно описываются одной вершиной концом и дают как раз все возможные пути из корня, т.е. получаем еще 3X.

Куски путей внутри корневого дерева - это всегда диаметр дерева Z который идет рвоно столько раз, сколько там других вершин в дереве (3Y+2). Получаем Z*(3Y+2).

Если все сложить и причесать, получим ответ в статье. Возможно там чуть другая логика вывода была, но суть решения такая же. Аккуратно считаем все пути. Чтобы это было проще все пути можно разбить на группы: внутри дерева, между двумя разными, и еще и на части: часть в дереве и часть в новой серединке. И главный инструмент: ребро встречается в сумме путей ровно столько раз, сколько путей через него проходит, а это произведение размеров подграфов с двух концов ребра.

Ваша задача - сделать циклический сдвиг массива на k позиций влево на месте, с O(1) дополнительной памяти.
Вот код:

void ShiftLeft(std::vector<int> &a, int k) {
  int n = a.size();
  int cycles = std::gcd(n, k);
  for (int start = 0; start < cycles; ++start) {
    int tmp = a[start];
    int i = start;
    while (true) {
      int next = i + k;
      if (next >= n) next -= n;
      if (next == start) break;
      a[i] = a[next];
      i = next;
    }
    a[i] = tmp;
  }
}

Работает это так: на место элемента вставет элемент на k позиций правее. Возьмем первый элемент, запомним его в tmp, поставим на его место тот, кто там должен быть. Освободилось место, поставим на него опять того, кто там должен быть и так далее. Рано или поздно мы вернемся к первому элементу. Но там уже стоит второй. Тут можно выйти из цикла и поставить на нужное место тот, кого мы сохранили в tmp. Но мы могли обойти не весь массив, как, например в случае n=6, k=2. Начав с 0 мы тут подвинем элементы 0,2,4, но не 1,3,5. Всего будет циклов gcd(n, k), и они все идут со сдвигом 1. Поэтому можно начинать с каждого из нескольких первых элементов.

Додуматься до этого можно так: сдвиг на 1 позицию понятно как циклом while сделать-то и одной переменной tmp. А на несколько? Надо только заметить что элементы разбиваются на циклы.

Инверсия тут - это из комбинаторики. Инверсия - это когда 2 элемента не в том порядке. Количество инверсий - это сколько пар элементов стоят не так. В массиве (1,2,3,4) инверсий 0. В массиве (1,4,3,2) инверсий 3: 4 и 3, 4 и 2, 3 и 2 - вот эти 3 пары идут по убыванию, вместо нормального порядка. Оставшиеся 3 пары стоят как надо.

Если граф не взвешанный, то запустите обычный bfs, только не кладте в очередь вершины с расчтоянием больше ограничения. Если граф взвешанный, то запустите обычного Дейкстру, только остановитесь, когда зафиксируете вершину с раччтоянием больше допустимого.

Рассмотрите один столбик (допустим, номер i). Какой высоты в нем может быть вода? Обозначим за x. Она не должна выливаться ни слева ни справа. Значит, с обеих сторон должен быть столбик с высотой хотя бы x. Раз есть хотя бы один, то максимум точно должен быть хотя бы x. Отсюда x <= max(h[0..i-1]) и x <= max(h[i+1..n-1]) Значит высота воды в i-ом столбике: min(max(h[0..i-1]), max(h[i+1..n-1])). Уже можно просто вот это подсчитать за 2 прохода и получить решение. Ну, только не забыть что там надо max(x, h[i])-h[i] к ответу прибавить, ведь если текущий столбик слишком высокий, то вся вода с него стечет.

Но можно думать дальше. Давайте обрабатывать не все столбики подряд, а посмотрим с краев. С крайних столбиков все, понятно, вытекает наружу. Пусть крайний левый меньше. Рассмотрим второй столбик слева. Мы уже знаем max(h[0..i-1]) в нем - это один левый столбик. И оно точно меньше max(h[i+1..n-1]), потому что справа уже есть крайний столбик, который выше самого левого. Мы незнаем точное значение max(h[i+1..n-1]), но мы знаем что max(h[i+1..n-1]) >= h[n-1] >= h[0] = max(h[0..i-1]). Вот мы знаем высоту воды в столбике 1, мы же берем минимум из двух значений. Даже если мы не знаем максимум справа, мы знаем, что он точно больше максимума слева и в ответе не участвует.

Вот мы и обработали второй столбик. Теперь перейдем к третьему. При этом можно первые 2 столбика объеденить в один высоты max(h[0], h[1]). Это и есть сдвиг указателя, только при этом мы смотрим не на сам столбик, а аккумулируем максимумы с краев.

Но, если бы мы смотрели на второй справа столбик, рядом с большим их двух крайних, то мы не могли бы сразу сказать, а какая там высота воды. Мы в нем знаем max(h[i+1..n-1]) - высота последнего столбика. Но какое в нем max(h[0..i-1]) мы не знаем и не можем сказать, больше ли оно или нет, а значит, не можем посчитать x.

Тут вопрос определений. Что считать "представить в виде DAG".

В ДП можно составить граф зависимостей: какие состояния участвуют в вычислении каждого. Это будет DAG. Иначе у вас надо вычислять значения через самих себя и у вас уже не рекуррентные соотношения, а система уравнений.
В некоторых задачах эту систему уравнений можно решать иерархически, по частям, отдельно в каждой компоненте сильной связности. Это немного напоминает ДП, но им не является. Суть ДП в том, что у вас рекуррентные формулы. Это некий более общий алгоритм.

Если интерпретировать вопрос как: можно ли сформулировать задачу в виде "дан граф, подсчитать вот такую функцию в каждой вершине", то тут можно натянтуть сову на глобус, придраться к деталям и сказать, что нельзя. Именно это и говорится в SO.

Потому что иногда рекуррентные формулы не симметричные и вам надо, например, одно значение прибавить, другое вычесть. Это не всегда просто определить исключительно в терминах графа. Нельзя сказать что-то вроде "сложить значение во всех вершинах, куда ведут ребра". Но если добавить в этот граф пометки на ребрах или параметры состояний в вершинах, то можно задать нужную функцию (вроде: взять значение для вершины, в которую ведет ребро с пометкой 1 и вычесть значение из вершины, куда ведет ребро с пометкой 2).

Но эти помеченные графы все еще будут DAG.

Квадратичное. При вставке каждого элемента в среднем отсортированная часть будет на треть состоять из 0, на треть и 1 и на треть и 2. Если текущий элемент 2, то вставка за O(1), если текущий элемент 1, то вы потратите i/3 операций. Если элемент 0, то 2/3i. В среднем i/3 операций на один элемент. Если просуммировать это от 1 до n, то получится n(n-1)/6. Значит общее количество операций O(n^2).

Вы расписали то, что в доказательстве скрывается за "clearly, any 2-factor of G translates into a perfect matching of G' and vice versa". Можно было бы чуть поформальнее, но основная идея правильная. Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.

Действительно, полное парсочетание становится циклами. Да, если граф не ориентированный, или содержит "тривальные" циклы (длины 2), то они могут войти в покрытие. Если найдется не полное паросочетание, то в графе будут какие-то непересечающиеся циклы и возможно пути. Он может быть даже не весь покрыт при этом.

Да, можно. Для этого надо в качестве pivot'а выбрать медиану. если это сделать за O(n) в худшем случае, то общая сложность QuickSort'а будет O(n log n).

Для выбора медианы за O(n) есть, например, вот такой алгоритм. В каких-то источниках его еще называли алгоритмом кнута-пратта-мориса-ривеста-тарьяна. Кажется, но я их найти не могу, так что я какие-то фамилии напутал, но помню, что там было 5 великих информатиков.

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

В унимодальной функции разности соседних элементов сначала неотрицательные а потом неположительные. И наоборот, если разности такие, то, очевидно, сначала функция возрастает (возможно, ступенчато) а потом убывает.

Вы доказали, что частичные разницы не возрастают. Тут могут быть 3 варианта:
1) они все неотрицательные. Функция унимодальна (монтонность с максимумом в конце - частный случай унимодальности).
2) они все неположительные. Монотонно убывающая функция.
3) есть и положительные и отрицательные. Но раз разности не могут возрастать, после первого 0 могут идти только нули а после отрицательного только отрицательные. А заначит разности выглядят ровно так, как у унимодальной функции.

У вас ошибка в понимании остаточной сети. Раз фиолетовые ребра насыщены, то на самом деле в остаточной сети есть обратные им ребра. И вершина v отлично найдется обходом из s.

Без этих обратных ребер алгоритм поиска потока не работает, ведь у него не будет возможности "отменять" потоки.
Например в графе:

________    
  a-b-c
 /  |   \
s   |     t
\   v   /
  d-e-f

Если сначала найдется поток по пути s-a-b-e-f-t, то дальше единственный способ его дополнить - это взять путь s-d-e-b-c-t, и надо будет "отменить" поток по перекрестному ребру b-e.

Именно max flow, а не mincostmaxflow? Потому что есть очевидное решение с mincostmaxflow.

Граф почти такой же. Раздвоенное ребро. В середину каждого ребра вход из истока пропускной способностью 1 и стоимостью 0. Вдоль ребра в обе стороны такие же ребра - пропускной способности 1 и стоимости 0. Из вершины делаем degree(v) ребер в сток. Каждое пропускной способностью 1 и прогрессивно увеличивающимися стоимостями. Первые ребра стоимостью 1. Вторые - n+1, сделующие (n+1)^2 и т.д.

Стоимость полного потока будет тем меньше, чем меньше максимальная степень, ведь даже одно ребро стоимостью (n+1)^k для вершины степени k+1 хуже чем если бы все вершины имели степень k и ответ был бы n*(n+1)^(k-1).

Если нужен именно просто поток, а не минимальной стоимости, то возможно можно изменить алгоритм потока, чтобы искать его итеративно для всех возможных значений x в вашем графе. Ведь алгоритм итерационно ищет дополняющий путь в остаточной сети. И ответ для x можно использовать в качестве стартового потока для задачи с x+1. Т.е не надо логарифм раз запускать поток для разных графов, а после выполнения увеличить пропускные сопособности нужных ребер на 1 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.