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

@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))

Новые блоги и статьи Все статьи Все блоги /
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .

@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