@Timur Abdullaev

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

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

То есть:
Массив = {5, 7, 4, 9}
К = 2

min_sum(5) = dist(5, {4, 7}) = |5-4|+|5-7|=3
min_sum(7) = dist(7, {9, 5}) = |7-9|+|7-5|=4
min_sum(4) = dist(4, {5, 7}) = |4-5|+|4-7|=4
min_sum(9) = dist(9, {7, 5}) = |9-7|+|9-5|=6

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

Если сперва отсортировать массив, тогда можно будет рассматривать только +-К элементов вокруг i-того элемента. Но К может быть размера вплоть до размера самого массива.

Можно хранить массив разностей между элементами отсортированного массива, но не понимаю можно ли это использовать эффективно.

Ограничение на входные данные:
n - количество элементов массива
k - размер подмножеств
a[i] - элемент массива

2 <= n <= 350 000
1 <= k < n
1 <= a[i] <= 10^9

Ограничение по времени: 2 сек.

С таким ограничением нужно как-то решить эту задачу быстрее, чем за O(n^2)

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

0

@Mikhaylo

Ну и что, что K ~ n? Это же проблема не только для алгоритма с предварительной сортировкой, но и любого другого, какой придумаете. Начинайте уже кодить с сортировкой!

0

@Shamil1

Где тут искомый массив размера К? Или исходный массив "зациклен"?

Добавлено через 5 минут
Или можно выбрать любые К из оставшихся элементов, даже если они расположены не рядом?

0

@Gdez

numpy - для 10^7 элементов массива обработка меньше 1 сек для любого "k"

0

@Timur Abdullaev

Посмотрите на ограничение по времени сначала. Это задание не тупо на "кодирование", а на "алгоритмы".

Добавлено через 3 минуты
Да, для каждого элемента массива можно выбирать любые К из оставшихся.

Добавлено через 3 минуты
Нельзя использовать сторонние библиотеки. Да и не может numpy так быстро считать, вы наверно находите только для 1 элемента массива, а надо для каждого, для N. C решением в лоб - это 10^10 операций. Решение на С++ отрабатывает за 2 минуты при N=350000, K= 150000.

0

@Mikhaylo

Отсортируйте массив. Рассмотрим некоторое фиксированное K. Пусть для данного K уже посчитана минимальная сумма некоторого числа q, т.е. известно min_sum(q, K). Также для данной пары (q, K) известно число элементов element_count, которые при вычислении min_sum были больше числа q. Тогда легко вычислить, что количество элементов, которые были меньше q, равно (K - element_count(q, K)).

Пусть надо найти min_sum(p, K), где p входит в множество оптимальных соседей числа при вычислении min_sum(q, K).
Так как числа p и q расположены достаточно близко, то наверняка у них достаточно большой набор общих оптимальных соседей. Самое худшее, что может случиться, это то, что числа p и q имеют близкие индексы, но очень большой разрыв по значениям. В этом случае среди оптимальных соседей чисел p и q может не оказаться ни одного общего. Но нет худа без добра, так как любой такой разрыв хоть и отдаляет числа p и q, но "сближает" числа p и r, если они находятся по одну сторону разрыва.

Пересчитываем min_sum*(p, K) = min_sum(q, K) + (p - q) * (K - element_count(q, K)) + (p - q) * element_count(q, K), где min_sum*(p, K) - это минимальная сумма для числа p, при условии, что у пар (q, K) и (p, K) множества оптимальных соседей совпадают. Далее мы пересчитываем min_sum*(p, K), сдвигая множество оптимальных соседей влево или вправо на один индекс в сторону числа p от числа q и проверяя, не нашли ли мы более оптимальное множество. Делаем это, пока min_sum перестало уменьшаться или число q не оказалось на краю этого множества.

Добавлено через 14 минут
Пересчет min_sum(p, K) через min_sum(q, K) по предлагаемому алгоритму занимает не K шагов как в случае вычисления в лоб, а от 1 до K.
Например, для равномерного распределения чисел алгоритм сработает за время O(n). Можно показать, что наихудшее время составляет O(n^2/K). А вы так боялись этого K.

Добавлено через 49 секунд
Могу в деталях ошибаться.

1

@Shamil1

После сортировки массива нужно пройтись по нему один раз.
У нас два курсора. Один указывает на текущий элемент (для которого мы вычисляем минимальную сумму). Второй - "окно" - указывает на границы подмассива размером К+1.
Так как оба курсора могут двигаться только вперёд, мы пройдём по массиву за О(n). Продвижение второго курсора останавливается, когда его правая граница совпадёт с правой границей массива.

1. Для первого элемента лучшим "окном" будут первые К+1 элементов. (Включение самого элемента не влияет на сумму, так как "расстояние до себя" равно нулю).

2. Выбираем следующий элемент и за О(1) вычисляем сумму расстояний для текущего "окна".

3. (Если правая граница окна не достигла правой границы массива И левая граница окна не достигла текущего элемента)
За О(1) вычисляем сумму расстояний до следующего "окна".
Если эта сумма меньше, то сдвигаем "окно". Повторяем 3.
Если эта сумма больше, то записываем минимальную сумму для текущего элемента и переходим к следующему (пункт 2).

0

@Timur Abdullaev

Думаю, что должно быть: min_sum*(p, K) = min_sum(q, K) + (p - q) * (K - element_count(p, K)) - (p - q) * element_count(p, K)
А затем эту сумму модифицируем, сдвигая границы только влево или только вправо, смотря, где сумма меньше.

0

@Mikhaylo

Ну да.

Я обобщил на почти произвольные числа p и q, то есть развил целую теорию. Но на практике проще взять соседние числа, об этом сказал Шамиль.

0