Что проверяет задание

Это задание с программированием на полном файле данных. Обычно два набора: демонстрационный A и основной B. Нужно посчитать характеристику большого массива чисел, точек или пар: сумму, количество, расстояние, центр кластера. Алгоритм должен укладываться по времени и памяти.

Определения

Эффективный алгоритм, такой, который не делает полный перебор всех пар, если пар слишком много. Оценка «число операций порядка n» или «n log n» обычно проходит, «n²» на n ~ 10⁵, нет.

Линейный проход, один раз прочитать все элементы, поддерживая несколько накопленных величин.

Кластер, группа близких точек. «Близость» задают порогом расстояния или уже разбиением в файле (сначала все точки одного кластера, потом другого).

Центроид (центр кластера), точка кластера, для которой суммарное расстояние до остальных точек кластера минимально. Иногда берут среднее арифметическое координат, но на экзамене чаще требуют именно точку из набора, минимизирующую сумму расстояний.

Расстояние, обычно Евклидово на плоскости: корень из суммы квадратов разностей координат. Для сравнения «кто ближе» корень можно не брать: достаточно сравнивать квадраты.

Пара с условием, два элемента, разность индексов, сумма или произведение которых удовлетворяет модулю. Полный перебор пар заменяют подсчётом по остаткам или двумя указателями по отсортированному массиву.

Префиксные суммы, массив частичных сумм, чтобы сумму отрезка считать за константу.

Остаток по модулю m, класс, в который попадает число. Для условий делимости пары почти всегда достаточно хранить лучшие представители каждого остатка.

Два файла

Файл A нужен, чтобы проверить, что программа считает то, что задумано. Файл B, источник ответа. Алгоритм один и тот же; меняется только вход.

Формат: первая строка часто содержит n или число кластеров, далее идут записи. Разделитель координат может быть пробелом, табуляцией или точкой с запятой.

Общий алгоритм решения

1. Прочитать условие как задачу на данные: что является объектом, какая характеристика нужна, какие ограничения на n.
2. Оценить, допустим ли квадратичный перебор. Если нет, найти группировку: остатки, сортировка, кластеры, префиксы.
3. Сформулировать, какие величины достаточно хранить вместо всех элементов (лучшие по остатку, минимум слева, сумма кластера).
4. Реализовать один проход или сортировку плюс линейный добор.
5. Проверить программу на файле A: ответ должен совпасть с тем, что получается аккуратным смыслово понятным способом на малых данных.
6. Запустить на файле B и выписать требуемые числа в нужном масштабе (часто «сумму расстояний, делённую на 10 000», с отбрасыванием дробной части).

Программа построчно

В задании 27 встречаются два вида задач: кластеры точек (разбить точки на группы, найти центры) и последовательности из большого числа элементов, где перебор всех пар слишком долгий. Начнём с кластеров.

Кластер - группа не менее чем из трёх точек, которые можно связать цепочкой, где расстояние между соседями не превышает 4.2. Кластеров ровно 2, остальные точки - аномалии. Центр кластера - точка с наименьшей суммой расстояний до остальных. Найдите среднее арифметическое абсцисс и ординат центров, умножьте на 10 000 и возьмите целую часть.

from math import dist

data = [tuple(map(float, s.split())) for s in open("27.txt") if s.strip()]

clusters = []
while data:
    clusters.append([data.pop(0)])
    for p in clusters[-1]:
        sosedi = [x for x in data if dist(x, p) <= 4.2]
        clusters[-1].extend(sosedi)
        for s in sosedi:
            data.remove(s)
clusters = [cl for cl in clusters if len(cl) >= 3]
clusters.sort(key=len, reverse=True)
clusters = clusters[:2]

def centr(cl):
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

centers = [centr(cl) for cl in clusters]
px = sum(c[0] for c in centers) / len(centers)
py = sum(c[1] for c in centers) / len(centers)
print(int(abs(px) * 10000), int(abs(py) * 10000))

from math import dist - функция расстояния между двумя точками.

data = … - список точек из файла. Подробно - в разделе «Чтение точек».

while data: … data.remove(s) - делим точки на кластеры. Подробно - в разделе «Кластеризация «волной»».

clusters = [cl for cl in clusters if len(cl) >= 3] - группы меньше трёх точек - аномалии, отбрасываем; потом оставляем 2 самых больших кластера.

def centr(cl): - центр кластера. Подробно - в разделе «Центр кластера».

px = …, py = … и print(…) - ответ из координат центров. Подробно - в разделе «Ответ: умножить на 10 000».

Чтение точек

data = [tuple(map(float, s.split())) for s in open("27.txt") if s.strip()]

• for s in open("27.txt") - перебираем строки файла;
• if s.strip() - пропускаем пустые строки;
• s.split() - строку «3.25 -1.5» режем на два куска;
• map(float, …) - превращаем куски в дробные числа, tuple(…) - в пару (3.25, -1.5).

Если в файле дробная часть записана через запятую («3,25»), перед split пишут s.replace(",", ".").

dist(p, q) из модуля math - расстояние между точками p и q по формуле √((x₁ − x₂)² + (y₁ − y₂)²).

Кластеризация «волной»

clusters = []
while data:
    clusters.append([data.pop(0)])
    for p in clusters[-1]:
        sosedi = [x for x in data if dist(x, p) <= 4.2]
        clusters[-1].extend(sosedi)
        for s in sosedi:
            data.remove(s)

• while data: - пока остались нераспределённые точки;
• data.pop(0) - достаём первую свободную точку, она начинает новый кластер clusters[-1] (последний в списке);
• for p in clusters[-1]: - идём по точкам кластера. Список растёт прямо во время цикла, и цикл дойдёт и до новых точек - так кластер расходится «волной» от первой точки;
• sosedi - все свободные точки на расстоянии не больше порога от p;
• extend добавляет соседей в кластер, remove убирает их из свободных.

В итоге в кластер попадают все точки, до которых можно дойти цепочкой с шагом не больше порога.

Центр кластера

def centr(cl):
    return min(cl, key=lambda p: sum(dist(p, q) for q in cl))

• для каждой точки p считаем сумму расстояний до всех точек кластера: sum(dist(p, q) for q in cl);
• min(cl, key=…) выбирает точку, у которой эта сумма наименьшая, - это и есть центр;
• для «края» (антицентра) - то же с max.

Ответ: умножить на 10 000

Координаты дробные, а в ответ записывают целые числа: значение умножают на 10 000 и берут целую часть int(…). По условию часто берут модуль: abs(px).

• среднее по центрам: sum(c[0] for c in centers) / len(centers) - сумма абсцисс, делённая на количество;
• наименьшая абсцисса центров: min(c[0] for c in centers).

Кластеры по энергии

Частицы делят на кластеры не по координатам, а по кинетической энергии:

def energy(m, vx, vy):
    return 0.5 * m * (vx * vx + vy * vy)

E = m · v² / 2, где квадрат скорости v² = vx² + vy².

Частицы сортируют по энергии и идут по порядку: в кластер попадают частицы, энергия которых отличается от первой частицы кластера не больше чем на R. Первая частица, которая отличается сильнее, начинает следующий кластер. Центр - частица с наименьшей суммой разностей энергий до остальных частиц кластера.

Чтение входного файла

В задачах на последовательность в первой строке - количество чисел N, дальше - по числу в строке:

with open("27.txt") as f:
    n = int(f.readline())
    a = [int(f.readline()) for _ in range(n)]

Остатки: подсчёт пар

«Количество пар (i < j), сумма которых делится на 6». Чисел может быть сто тысяч - пар тогда пять миллиардов, перебор не успеет. Нужна идея: сумма делится на K, если остатки слагаемых в сумме дают 0 или K.

K = 6
cnt = [0] * K
total = 0
for x in a:
    total += cnt[(-x) % K]
    cnt[x % K] += 1
print(total)

• cnt[r] - сколько уже просмотренных чисел имеют остаток r;
• для очередного x подходящий партнёр - любое предыдущее число с остатком (-x) % K (например, для остатка 2 при K = 6 нужен остаток 4, для 0 - тоже 0); таких ровно cnt[(-x) % K];
• после этого добавляем x в счётчики - для следующих чисел он станет «предыдущим».

Один проход по списку вместо перебора всех пар.

Префиксные суммы

Префиксная сумма - сумма всех чисел от начала до текущего. Сумма отрезка от i + 1 до j равна разности префиксов s[j] − s[i]. Она делится на K, если префиксы дают одинаковый остаток.

cnt = [0] * K
cnt[0] = 1
s = total = 0
for x in a:
    s += x
    r = s % K
    total += cnt[r]
    cnt[r] += 1

• cnt[0] = 1 - «пустой» префикс до первого элемента: сумма 0, остаток 0. Он нужен для отрезков, начинающихся с первого элемента;
• total += cnt[r] - каждый более ранний префикс с тем же остатком даёт подходящий отрезок.

Для наибольшей суммы отрезка, делящейся на K, для каждого остатка хранят наименьший префикс: сумма отрезка s - best[r] тем больше, чем меньше ранний префикс.

Пары на расстоянии: окно остатков

«Наибольшая сумма Aᵢ + Aⱼ, где j − i ≥ 5 и сумма делится на 7». Для каждого j партнёр должен стоять не ближе чем за 5 позиций. Идём по j и постепенно «открываем» элементы, которые стали достаточно далеко:

K, D = 7, 5
best = [-1] * K
ans = -1
for j in range(D, n):
    x = a[j - D]
    best[x % K] = max(best[x % K], x)
    y = a[j]
    if best[(-y) % K] != -1:
        ans = max(ans, best[(-y) % K] + y)
print(ans)

• best[r] - наибольшее число с остатком r среди элементов, отстоящих от j хотя бы на D;
• на шаге j «открывается» элемент a[j - D] - он ровно на D позиций левее;
• для y = a[j] лучший партнёр - наибольшее открытое число с остатком (-y) % K;
• -1 означает «таких чисел пока нет».

Для наименьшего произведения, делящегося на K, хранят наименьшие числа по остаткам и проверяют все остатки r, у которых (r * y) % K == 0.