Как найти сумму чисел на нечетных позициях после сортировки массива?

Question

[asdsdsdafsdafdsaf]

Дан массив из N чисел, как найти сумму тех чисел, которые будут стоять на нечетных местах после сортировки массива?
Понятно, что можно отсортировать массив и пройтись по нему ещё раз, но как сделать быстрее?
Сама задача:

Comments

[Akina]

Понятно, что можно отсортировать массив и пройтись по нему ещё раз, но как сделать быстрее?

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

[asdsdsdafsdafdsaf]

Akina, ну скажи, какую сортировку применить. Я пробовал слиянием, но Time Limit

[asdsdsdafsdafdsaf]

Akina, прикрепил полное условие задачи, может это поможет

[Wataru]

asdsdsdafsdafdsaf, Какие ограничения на время, N, L?

[asdsdsdafsdafdsaf]

Wataru, 5000000⩽N⩽60000000, 0⩽K,L,M⩽2^32 - 1

[asdsdsdafsdafdsaf]

Пробовал по мере генерации делать мердж сорт и параллельно подсчитывать результат, но тоже тайм лимит.

[Wataru]

asdsdsdafsdafdsaf, Ну, делать merge по мере генерации - это почти гарантированно O(N^2). Там надо очень сильно извратиться, чтобы логарифм в итоге получить.

Answer 1

[Wataru]

Никак. Есть методы получить число, которое будет стоять на заданной позиции (или числа на отрезке) в отсортированном массиве быстрее сортировки (алгоритм QuickSelect). Как-то быстрее сортировки найти все числа на нечетных позициях - нельзя.

Edit: Если стандартная сортировка не работает и L большое, то стоит посмотреть в сторону radix sort. Если бы L было относительно небольшим - то лучший вариант был бы сортировка подсчетом.

Comments

[asdsdsdafsdafdsaf]

Хорошо, если без сортировки нельзя, то скажите, как правильно реализовать. Я пробовал merge sort, но это слишком долго

[asdsdsdafsdafdsaf]

Прикрепил полное условие задачи, может это поможет

[Wataru]

asdsdsdafsdafdsaf, Посмотрел ограничения - удивился. Что, встроенная в язык сортировка (например std::sort в C++) не проходит? Ваша реализация merge sort наверняка далеко не оптимальна.

[asdsdsdafsdafdsaf]

Wataru, не пробовал std::sort, это было бы слишком просто же, не? Сейчас сделаю такое решение и отправлю

[asdsdsdafsdafdsaf]

Wataru, попробовал std::sort, прошло побольше тестов, но все равно решение валится из-за ограничения по времени. На 6 из 13 тестов падает

[Wataru]

asdsdsdafsdafdsaf, Точно такие ограничения? L до 2^32?

[asdsdsdafsdafdsaf]

Wataru, да, я скопировал их и вставил сюда

[asdsdsdafsdafdsaf]

Wataru, а какие у тебя есть идеи, если ограничения были бы чуть другие?

[Wataru]

asdsdsdafsdafdsaf, Хм... память под последовательность аккуратно один раз выделяете (capacity или resize у вектора)? Если все-равно не проходит, то, наверно, придется писать какой-нибудь radix sort. Естественно, сортировать надо не по десятичным цифрам, а, допустим, по байтам. Или по 4 бита в разряде.

[Wataru]

asdsdsdafsdafdsaf, А если бы L было поменьше, то можно было бы делать сортировку подсчетом.

[asdsdsdafsdafdsaf]

Wataru, пишу на плюсах, синхронизацию с stdio выключил, прописал cin.tie(0), память под массив выделяю через resize. Про radix sort не слышал, сейчас буду смотреть, спасибо

[asdsdsdafsdafdsaf]

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

[Wataru]

asdsdsdafsdafdsaf, можно попробовать по 2 байта. Тогда будет в 2 раза меньше проходов, но они сами медленнее из-за большего разброса в памяти.

Иначе остаются микрооптимизации: не делить нацело, а использовать битовые маски, не выделять лишнюю память.

[Wataru]

asdsdsdafsdafdsaf, кстати, вы же нормально radix sort сделали - без рекурсии, начиная с младших разрядов?

[asdsdsdafsdafdsaf]

Wataru, без рекурсии, сейчас переписываю сортировку на использование двусвязных списков, раньше делал через векторы

[Wataru]

asdsdsdafsdafdsaf, неееет! Зачем там списки! Нужен лишь один вектор размера с сортируемый. За один проход в массиве на 256/65536 элементов считаете, сколько раз данная цифра в текущем разряде встречается. Потом за один проход пересчитываете, сколько чисел содержат меньшие данной цифру. Это будут индексы отрезков в результирующем массиве, куда надо поместить все числа с данной цифрой. Потом за второй проход все числа перемещает, увеличивая эти индексы.

[asdsdsdafsdafdsaf]

Wataru, вы про штуку, описанную здесь https://algolist.manual.ru/sort/radix_sort.php в разделе Поразрядная сортировка для массивов?

[Wataru]

asdsdsdafsdafdsaf, да, похоже на правду. Вот тут есть вообще код. Только его можно еще соптимизировать. Не надо копировать результат в начальный массив - лучше пусть функция принимает два вектора одинакового размера и по какому разряду надо сортировать. А дальше вызывайте ее перекладывая данные из одного вектора в другой и назад. Для этого удобно завести массив из двух векторов и класть из i%2 в (i+1)%2.

Answer 2

[Alexandroppolus]

Есть подозрения, что задача не на пустом месте появилась.
По сути, у нас тут только 4 входных параметра.
Теоретически эта сумма должна вычисляться за О(1).
Попробуй повычислять на разных наборах параметров, найти какие-то закономерности в результатах...

Comments

[Wataru]

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

Метод генерации псевдослучайный как раз, чтобы шибко умные не придумали такую формулу.