Wataru

Да, можно. Для этого надо в качестве 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

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

Можно применять тот же прием, что и в задаче коммивояжора - расслоите граф на 2^n слоев. Пуст у вас n вершин в изначальном графе. В новом графе каждая вершина соответсвует подмножеству комнат и одной комнате. Фактически, вершина обозначает, какие комнаты вы обошли и где сейчас находитесь.

Ребра есть:
Из вершины ({}, 0) во все вершины ({v},v) ценой goblinTime[v]: это мы можем зайти в лабиринт в любую комнату и должны там гоблина победить.
Из вершины (S, v) в вершину (S,u) ценой path[v,u], если u в S - это мы идем в ранее посещенную комнату.
Из вершины (S, v) в вершину (S+{u},u) ценой path[v,u]+goblitTime[u], если u не в S - это мы идем в ранее не посещенную комнату и бъем там гоблина.

В этом графе на n2^n вершин вам надо найти все кратчайшие пути из начальной ({},0) во все вершины (например, дейкстрой). Потом переберите все вершины в графе (S, v) и, если вершина соответствует комнате с выходом и вы до нее дошли за время не превосходящее время обрушения, то берите сумму количества золота в комнатах в множестве S в качесвте варианта ответа. Из всех них берите максимум.

Вам нужен 2-дольный граф. Левая доля соответствует строкам, правая - столбцам. Из истока ребора в левую долю (ценой ri), из правой доли - в сток (ценой ci). Ребра между долями ценой aij.

Любой разрез тут соответствует покрытию всех вершин. Вы должны разрезать ребро между ij или si или jt что чоответствует покрытию клетки, строки иои столбца.

Доказательство не верно из-за индуктивного перехода. Вы рассматриваете только уже отсортированные наборы задач. Не ясно, что добавляя задачи в другом порядке вы получаете варианты не лучше. Вы так же не показали, что вот эти 2 варианта дают оптимальное время для k+1 задачи.

Правильное доказательство весьма простое и без индукции. Общее время будет

Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))

.
Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится. Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное.
Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.

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

Рассмотрим теперь один уровень, который описан 4 числами a,b,c,d и нам надо оставить как можно больше шаров белого цвета (их d). За один ход мы можем приравнять к 0 одно из 4 чисел и вычесть по 1 из отсавшихся ненулвевых. Ясно, что нет смысла занулять d. Т.о. за 3 хода мы можем получть 0,0,0,max(0,d-3). Но, например, если у нас было 2 2 2 3, то занулив a и b мы уменьшениями на 1 зануляем и c. Т.е. для маленьких чисел имеет смысл подумать в каком порядке их занулять. Но мне лень даже думать как именно - ведь их всего 3 числа - можно тупо перебрать все 6 перестанвок и выбрать ту, в которой за наименьшее количество ходов мы их все занулим.

Алгоритм, в общем-то оптимален. Но реализация допускает некоторые микро-оптимизации.

Во-первых, StringBuilder можно указать итоговый размер в конструкторе. Тогда там не будет лишних выделений памяти. Вы же знаете, что там будет сумма двух длин в итоге.
Во-вторых, основной цикл лучше гнать не до максимальной длины из двух, а до минимальной. Тогда в цикле не надо никаких проверок, что индекс не вышел за границы строки. После цикла надо будет добавить к собираемой строке кусок одной из двух входных строк. Проверьте, какая строка длиннее и добавьте ровно len1-len2 символов с конца. Используйте метод substring(), чтобы получить этот суффикс и сразу передавайте его в append().

Вторую часть про символы на четных местах тоже можно соптимизировать. Вы знаете длину ответа заранее, инициализируйте StringBuilder с нужной вместимостью.
На четных местах будет вторая строка. Ну и в конце только какие-то символы через один из второй строки или из первой, в зависимости, какая длинее. Если передавать в функцию не результат работы первой, а 2 строки, то можно сначала append в stringbuilder substring от второй строки, а потом циклом взять нужное количество символов через один из первой или второй строки. Нарисуйте на бумаге несколько случаев, первая строка длиннее второй или наоборот. Длина второй строки четная/нечетная, длина первой четная/нечетная. В каждом из этих случаев будет +-1 где-то в формулах для индексации. Можно это все удачно записать с помощью деления на 2 нацело и остатка от деления на 2.

Вы правильно начали, заведите vector и делайте туда push_back.

Читайте циклом while, пока чтение не вернет ошибку:

int x;
ifstream f("file.txt");
while (f >> x) {
  v.push_back(x);
}

а общее число перераспределений для n добавлений уменьшается как O(logn). Почему тогда в таком случае для n последовательности append-ов общая сложность равна O(n), а не O(n logn)?

Потому что эти распределения разного размера. Первое - совсем маленькое. Второе чуть больше и т.д. Чтобы суммарно было O(n Log n), каждое из них должно быть пропорционально n.

1+4+10+⋯≤O(n)

Вот это и есть ответ. Первые слагаемые маленькие. Получается геометрическая прогрессия, которая дает линейную сумму от n.