BOI 2021 P5 aka Sorting Networks
https://oj.uz/problem/view/BOI21_swaps
Задача для расширения кругозора (aka постройте Sorting Network)
Писал виртуалку, а после неё был очень расстроен что задачу эту не сдал, а один участник из Израиля, который к тому же выпускается в один и тот же год со мной, ее сдал. Для меня это было абсолютное поражение, хотя у него результат очень странный: в первый день ~20 баллов, во второй - 280.
Прочитав разбор задачи моя грусть сразу ушла и я понял что задача просто напросто плоха для олимпиад (из-за того что очень известна), а Daniel Weber скорее всего просто был наслышан о ней.
Задача: Построить https://en.wikipedia.org/wiki/Sorting_network
О таком я вообще не задумывался, и тем более не слышал. Sorting Network - это по сути сортировка вообще не учитывая какие элементы больше, а какие меньше. То есть вам надо изначально выбрать какие-то пары элементов которые вы будете сравнивать, а также их порядок, и делать что-то в духе:
for (auto [i, j] : sortingNetwork) {
if (a[i] > a[j]) {
swap(a[i], a[j]);
}
}Задача - построить sortingNetwork, а точнее сделать его кол-во "раундов" (для понятности читайте условие задачи) ~ log(n)^2
Существует алгоритм, который выполняет O(n * log(n)) операций, он очень сложный и у него оооочень большая константа, из-за этого его не используют на практике. Я вам хочу рассказать более практичный алгоритм: Batcher's odd-even Mergesort
Википедию я не понял (потому что там по сути ничего и не написано), советую вам прочитать то что я прикрепил по ссылке, а тут я постараюсь вкратце рассказать что там да как :)
В нем мы делаем заводим две функции: sort и merge
В sort мы сортируем левую половину, сортируем правую, а затем запускаем merge
В merge левая и правая половина массива уже отсортирована, нам надо их смерджить. Возьемем элементы на нечетных позициях и вызовем merge от них. Сделаем тоже самое и с элементами на четных позициях.
То есть если был массив: {1, 3, 7, 9 | 2, 4, 5, 6}, то после этих двух операций он станет {1, 3, 2, 4, 5, 6, 7, 9}. (Взяли 1, 7, 2, 5 и отсортили, поставили обратно на позиции, сделали тоже самое с четными позициями).
Он теперь почти отсортирован: осталось только в sortingNetwork добавить пары {2, 3}, {4, 5}, ... {n - 2, n - 1}. (Индексация с 1).
Доказательство достаточно простое, надо просто понять что элементы в паре
(i-1, i) строго меньше всех элементов в паре (i+1, i+2).
Вот и все! Можно еще глянуть на крутой код без рекурсии. Понять его надо самому, но там мы делаем абсолютно то же самое:
int N = 1 << __lg(n - 1) + 1;
for (int s = 1; s < N; s <<= 1) {
for (int k = s; k > 0; k >>= 1) {
for (int j = k % s; j + k < n; j += 2 * k) {
for (int i = 0; i < k && j + k + i < n; ++i) {
if ((j + i) / (2 * s) == (j + i + k) / (2 * s)) {
sortingNetwork.push_back({j + i, j + i + k});
}
}
}
// round ends here
}
}Еще хотел бы рассказать вам про прикольный факт. Давайте подумаем, как вообще можно проверять, правда ли, что наш алгоритм работает? Можно было бы в целом перебрать n! перестановок, и для каждой проверить, что он выдает правильный ответ. Но можно в каждый элемент поставить либо 0, либо 1, и тогда давайте переберем 2^n возможных массивов, и проверим, что наш sortingNetwork действительно сортирует этот массив.
Понятно, что для немаленьких n 2^n сильно меньше, чем n!
Почему это правда? Если какая-то перестановка отсортируется неправильно (то есть найдутся такие i < j что a[i] > a[j]), то массив b[k] = bool(a[k] >= a[i]) тоже неправильно отсортируется.