Wataru

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

Никак.

Это можно доказать. Вам так или иначе придется посмотреть на все ребра. Допустим, есть алгоритм, который всегда может проверить цикл, смотря не все ребра. Рассморим какой-то граф без циклов. Алгоритм там какие-то ребра посмотрел и сказал, что циклов нет. А мы возьмем и скормим этому алгоритму почти такой же граф, только одно из ребер, которые он вообще не трогал, сделаем обратным какому-то другому ребру в графе, сделав таким образом цикл. Но алгоритм посмотрит на те же самые ребра, увидет все то же самое и сделает точно такой же вывод, что циклов нет, и ошибется. Все потому что мы допустили алгоритм, который всегда смотрит не все ребра. Значит таких алгоритмов нет и там всегда будет хотя бы O(|E|).

Проблема в выводе. Вы пытаетесь вывести переменную unsigned long long через спецификатор "%d". Надо использовать "%llu" какой-нибудь.

Зачем в алгоритме сортировки Кана вначале требуется степень или просчёт всех соединений, вроде и без неё всё работает?

Без нее работает медленно. Смотрите алгоритм. В алгоритме надо брать вершину в которую не входит ни одно ребро, а также удалять вершины. Кончено, можно наивно брать все вершины, потом брать все ребра, смотреть, не удалено ли ребро и не ведет ли оно в эту вершину. Но это будет O(VE) для поиска одной вершины, а суммарно алгоритм будет O(V^2E). Когда как реализация с подсчетом степеней и очередью будет O(V+E).

Есть ли возможность сортировать не узлы, а рёбра сразу?

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

Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?

Можно. Изолированные узлы - это те в которые ни одно ребро не входит. В алгоритме Кана это те, которые можно вывести до удаления любой вершины.

Раз вам надо обойти врешины в топлолгическом порядке, вам нужна топологическая сортировка. Если у вас только одна корневая вершина, то можно и проще - тут сработает любой обход: в ширину или в глубину из корневой вершины. Если корневых вершин несколько, то надо будет использовать какой-либо алгоритм топологической сортировки. Гуглите его. Есть алгоритм основанный на двух обходах в глубину, или нечто основанное на обходе в ширину.

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

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

Потому что теорема Эйлера. А в процессе шифрования значение для текста вовзводится в степень по модулю n. А для дешифровки возводится в еще одну степень. Поэтому показатель степени ищется по модулю Ф(n).

Проблема в том, что сначала пытаетесь вычислить a^(p-2), а потом взять его по модулю. В задаче числа до 10^9 и если вы попытаетесь вычислить что-то вроде 99999^1000005, то у вас int переменная переполнится, потому что там должны быть миллионы знаков в числе, а в int едва 10 влезает.

Надо брать по модулю при каждом умножении в возведении в степень.

Потому что (a*b)%p = (a%p)*(b%p) % p.

Edit:

Еще две ошибки: считать произведение надо в long long, потму что 10^9*10^9 в int не влезает.
И fast_deg(a, deg/2) надо вызывать только один раз, а то у вас функция работает за O(n) вместо O(log n).

Вы расписали то, что в доказательстве скрывается за "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 великих информатиков.

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

Функция задана кусочно, да. Но все куски в точках на границах совпадают и разрывов там нет. Функция не гладкая, но все еще непрерывная.

Для целых координат есть glVertex2i.

Еще надо задать в начале преобразование, чтобы координаты соответствовали экрану (один раз):

glutCreateWindow("Game");
glMatrixMode( GL_PROJECTION );
glLoadIdentity();
gluOrtho2D( 0.0, 600.0, 400.0, 0.0 );

Смотрите внимательно, у вас точка с запятой после цикла. Следующая строка выполняется вне цикла, в котором i и объявлена.

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

Вы доказали, что частичные разницы не возрастают. Тут могут быть 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 и запустить поток дальше. Это будет как если бы вы запустили поток один раз с максимальной пропускной способностью сразу.

Идея этого усечения в том, что если вы ищите gcd(a, b), то можно также искать gcd(a,a-b). Вот эта замена b' = a-b у вас в коде и происходит.

Вы там поддерживаете инвариант x_i*a+y_i*b = r_i

Сответсвтенно, вам надо пересчитать x_cur и у_cur вместе с изменением r_cur.

У вас есть x_prev*a+y_prev*b = r_prev и x_cur*a+y_cur*b = r_cur. Вам надо составить линейную комбинацию r_prev - r_cur. Ну вычтите одно уравнение из другого и все.

Соответственно вам надо сделать вот это при применении вашего усечения:

x_cur = x_prev - x_cur
y_cur = y_prev - y_cur