Подсказки к задачам

C. Шаги сортировки слиянием

Используйте стандартную сортировку слиянием, но перед выходом из рекурсии выводите все элементы от a[l] до a[r].

F. Сорок миллионов

Вы, разумеется, помните, что массив такой длины не успеют отсортировать не только алгоритмы со сложностью O(N²), но и даже алгоритмы со срожностью O(NlogN).

Значит, нужно искать в условии задачи что-то, что всё-таки позволит вам её решить. Обратите внимание, какими числами заполняется массив.

Программа будет работать быстрее, если не хранить весь массив в памяти.

G. Порядковая статистика

Размер массива в этой задаче очень велик. Если в быстрой сортировке мы выбираем опорный элемент следующим образом:

swap(a[l], a[rand() % (r - l + 1)]);

то из-за того, что константа RAND_MAX на сервере равна 32767, обмен будет неравномерным (опорный элемент случайно выбирается не из всего диапазона [l; r], а только из его первых 32 тысяч элементов), и решение будет получать TL.

Следует использовать другой способ выбора случайного опорного элемента, например, такой (этот способ также не идеален, но в данном случае лучше):

int random(int l, int r) {
    return l + (double)rand() / RAND_MAX * (r - l);
}

swap(a[l], a[random(l, r)]);

Кроме того, у этой задачи есть очень короткое стандартное решение, но его предлагается отыскать самостоятельно.

Обратите внимание, что при вычислении элементов массива может произойти переполнение.

H. Сортировка асимптотик

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

Помните, что алгоритм, имеющий сложность f(N), более эффективен по сравнению с алгоритмом, имеющим сложность g(N), если при неограниченном увеличении N предел отношения f(N)/g(N) равен нулю.

В решении этой задачи вам может оказать большую помощь Wolfram Alpha.

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