Тренировочная задача "С. Расстояние" от яндекс (у меня решение не проходит по времени)

@DarkShaddow · Регистрация: 03.10.2020

Студворк — интернет-сервис помощи студентам

Сама задача тут https://contest.yandex.ru/cont... /?retPage= (там надо зарегистрироваться, но там есть примеры этой задачи)
Если вкратце, то дан массив чисел и надо для каждого числа этого массива надо найти k ближайших по значению чисел, потом найти расстояние до каждого из ближайших чисел (разность чисел по модулю) и сложить эти расстояния.

Полное описание:
Рассмотрим целочисленный массив a длины n. Назовём расстоянием от индекса i до множества индексов S величину dist(i,S)=∑_j∈S|a_i−a_j|. Зафиксируем целое число k. Рассмотрим функцию f(i)=min dist(i,S), где минимум берётся по множествам S размера k, не содержащим индекс i.
Определите значение f(i) для всех i от 1 до n.

Формат ввода:
В первой строке заданы два целых числа n и k (2≤n≤300000, 1≤k<n), описанные в условии. Во второй строке содержится n целых чисел ai (1≤a_i≤10^9) — элементы массива a.

Формат вывода:
Выведите n целых чисел: значения f(i) для i=1,i=2,…,i=n.

Пример 1 ввода:
5 3
3 2 5 1 2

Пример 1 вывода:
4 2 8 4 2

Пример 2 ввода:
6 2
3 2 1 101 102 103

Пример 2 вывода:
3 2 3 3 2 3

1. Сначала я решил эту задачу тупо перебором и очевидно это было слишком долго.
2. Дальше я попробовал пройтись окном k по отсортированному массиву, что ускорило мое решение (но недостаточно).
3. Потом мне посоветовали найти для отсортированного массива 'a' префиксную сумму, а потом уже идти окном k (только вправо) это значительно ускорило решение т.к. теперь мне не надо пересчитывать суммы каждый раз, но как вы догадались и этого оказалось мало (хотя вполне вероятно, что я просто делаю что-то не так).

Вот мой код на python:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def distance(k, a):
    def prefix_sum(arr):
        sums = [0]
        for i in range(len(arr)):
            sums.append(sums[i] + arr[i])
        return sums
 
    a_order = sorted(a)
    pre_sum = prefix_sum(a_order)
    m = a_order[-1]*(k) # число, которое точно будет больше минимальной суммы
    sum_min = m
    answer = {}
    i2 = 0
    for count, now in enumerate(a_order):
        i = i2
        maximum = count+k
        if i-k < 0:
            i = k
        if maximum >= len(pre_sum)-1:
            maximum = len(pre_sum)-2
        while i <= maximum:
            l = k - (i-count) # длина левой части от now
            sum_now = ((now*l) - (pre_sum[count] - pre_sum[count-l])) + ((pre_sum[i+1]-pre_sum[count+1]) - now*(k-l))
            if sum_now < sum_min:
                sum_min = sum_now
                i2 = i
            i += 1
 
        answer[now] = sum_min
        sum_min = m
    result = []
    for num in a:
        result.append(answer[num])
    print(*result)
 
if __name__ == "__main__":
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    distance(k, a)

Буду очень благодарен, если подскажите решение или объясните, что я делаю не так. Над этой задачкой я бьюсь уже не первый день и почти потерял надежду решить её. Хотя полазив в интернете я смог отыскать решение, но оно было вообще непонятным (ссылка почему-то не отображается)

@Alex Tsiklov · 04.03.2023, 11:02

Врядли ещё актуально, но в этой строчке s += (c[i] - c[i+1]) * ((right - i) - (i - left + 1)) происходит следующее:
1) Мы сдвинулись вправо на дистанцию (c[i] - c[i+1])
2) Надо пересчитать расстояния для всех элементов вокруг
3) До тех, что слева, дистанция увеличилась, до тех, что справа - уменьшилась
4) Если количество элементов слева отлично от правого, общая дистанция (сумма) однозначно изменилась (может уменьшилась, а может увеличилась).
5) Величина изменения равна: (кол-во элементов справа) * (величина сдвига) - (кол-во элементов слева) * (величина сдвига), ну а если вынести за скобки величину сдвига, как раз и получим формулу сверху. При этом величина изменения может быть как положительной так и отрицательной
Надеюсь помог

@nikita_g · 26.07.2023, 16:57

Red white socks, подскажите, пожалуйста.

На какие математические методы вы опирались, когда алгоритм прохода по массиву придумали?

Я всю голову себе сломал об эту задачу, но единственным оптимальным путем решения по формуле заявленной в задаче нашел для себя вычесть из индексного числа в радиусе k и найти минимальную сумму. Т.е. перебор.

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

М.б. данная задача является классической? Или это алгоритм? КАК?

под катом спрятал мое чудище

Кликните здесь для просмотра всего текста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from random import *
ARR_LNGT = 300000
array = [randint(2, 100000000) for i in range(ARR_LNGT)]
 
s_len = -1
with open('input.txt', 'r') as file:
    row_count = file.readline()
    a_len = int(row_count.split()[0])
    s_len = int(row_count.split()[1])
    a_arr = file.readline().split()
 
 
 
temp_arr = []
s_len = 3
s_temp_arr = []
a_arr = [int(x) for x in a_arr] 
a_len = ARR_LNGT
a_arr = array[0:]
b_arr = a_arr[0:]
b_arr = sorted(a_arr)
 
second_vasa = {}
 
len_b_arr = len(b_arr)
for index in range(len(b_arr)):
 
    val_pos = index  
 
    min_bord = val_pos-s_len if val_pos-s_len > 0 else 0
 
    temp_arr=[]
    max_bord = val_pos+s_len+1 if val_pos+s_len < len_b_arr else len_b_arr
    for sub_item in range(min_bord, max_bord):
        if sub_item == index:
            continue
        temp_arr.append(abs(b_arr[index]-b_arr[sub_item]))
 
    temp_arr = sorted(temp_arr)
    second_vasa[b_arr[index]] = str(sum(temp_arr[:s_len]))
 
 
for item in a_arr:
    s_temp_arr.append(second_vasa[item])
   
print(" ".join(s_temp_arr))
with open('output.txt', 'w') as out:
    out.write(" ".join(s_temp_arr))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Alex Tsiklov 1 / 1 / 0 Регистрация: 04.03.2023 Сообщений: 1
	04.03.2023, 11:02
	Врядли ещё актуально, но в этой строчке s += (c[i] - c[i+1]) * ((right - i) - (i - left + 1)) происходит следующее: 1) Мы сдвинулись вправо на дистанцию (c[i] - c[i+1]) 2) Надо пересчитать расстояния для всех элементов вокруг 3) До тех, что слева, дистанция увеличилась, до тех, что справа - уменьшилась 4) Если количество элементов слева отлично от правого, общая дистанция (сумма) однозначно изменилась (может уменьшилась, а может увеличилась). 5) Величина изменения равна: (кол-во элементов справа) * (величина сдвига) - (кол-во элементов слева) * (величина сдвига), ну а если вынести за скобки величину сдвига, как раз и получим формулу сверху. При этом величина изменения может быть как положительной так и отрицательной Надеюсь помог 1