Разбор задачи «Совместимость наставников»

Идея задачи

Даны два массива a и b длины n. Нужно посчитать количество пар индексов (i, j), где i < j, для которых выполняется условие:

a_i + a_j > b_i + b_j

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

Перенесём всё, что связано с b, вправо:

(a_i - b_i) + (a_j - b_j) > 0

Теперь введём новый массив:

d_i = a_i - b_i

Тогда задача сводится к следующей:

Нужно посчитать количество пар (i, j), где i < j, таких что d_i + d_j > 0.

Это уже стандартная задача, которую удобно решать после сортировки.

Почему преобразование полезно

После замены d_i = a_i - b_i каждый индекс начинает описываться всего одним числом:

• если d_i > 0, то элемент сам по себе скорее «полезный»;
• если d_i < 0, то он скорее «мешает»;
• если d_i = 0, то сам по себе ничего не меняет.

Теперь нам нужно просто найти, сколько пар чисел дают положительную сумму.

Наивное решение

Можно перебрать все пары i < j и проверить условие.

Идея

Для каждой пары:

• считаем d_i + d_j;
• если сумма больше нуля, увеличиваем ответ.

Почему это плохо

Всего пар порядка n^2, а n в задаче до 200000. Такой перебор не пройдёт по времени.

Сложность наивного решения:

• O(n^2) по времени;
• O(1) дополнительной памяти.

Нужно искать более быстрое решение.

Эффективное решение: сортировка + два указателя

Пусть у нас есть массив d. Отсортируем его.

После сортировки хотим быстро считать число пар (i, j), для которых:

d[i] + d[j] > 0

Будем использовать два указателя:

• l — на левый конец массива;
• r — на правый конец массива.

Наблюдение

Если

d[l] + d[r] > 0,

то подходят все пары:

• (l, r)
• (l + 1, r)
• (l + 2, r)
• ...
• (r - 1, r)

Почему? Потому что массив отсортирован, значит:

d[l] <= d[l + 1] <= ... <= d[r - 1] <= d[r]

Если самый маленький элемент среди рассматриваемых уже даёт положительную сумму с d[r], то все элементы правее него тоже дадут положительную сумму.

Значит, можно сразу добавить в ответ:

r - l

и уменьшить r.

А если сумма не положительная?

Если

d[l] + d[r] <= 0,

то элемент d[l] слишком маленький. Даже в паре с самым большим доступным d[r] он не подходит. Значит, с ним уже не получится образовать подходящую пару ни с кем слева от r.

Поэтому такой элемент можно отбросить: увеличиваем l.

Пошаговый алгоритм

1. Считываем массивы a и b.
2. Строим массив d, где d[i] = a[i] - b[i].
3. Сортируем d.
4. Ставим два указателя: l = 0, r = n - 1.

5. Пока l < r:

   • если d[l] + d[r] > 0, добавляем r - l к ответу и уменьшаем r;
   • иначе увеличиваем l.
6. Выводим ответ.

Разбор на примере

Пусть:

n = 5
a = [4, 8, 2, 6, 2]
b = [4, 5, 4, 1, 3]

Построим массив разностей:

d = [0, 3, -2, 5, -1]

После сортировки:

d = [-2, -1, 0, 3, 5]

Теперь запускаем два указателя.

Шаг 1

• l = 0, r = 4
• d[l] + d[r] = -2 + 5 = 3 > 0

Значит, подходят все пары с правым элементом 5:

• (-2, 5)
• (-1, 5)
• (0, 5)
• (3, 5)

Добавляем 4, уменьшаем r.

Шаг 2

• l = 0, r = 3
• d[l] + d[r] = -2 + 3 = 1 > 0

Подходят:

• (-2, 3)
• (-1, 3)
• (0, 3)

Добавляем 3, уменьшаем r.

Шаг 3

• l = 0, r = 2
• d[l] + d[r] = -2 + 0 = -2 <= 0

Левый элемент слишком маленький, увеличиваем l.

Шаг 4

• l = 1, r = 2
• d[l] + d[r] = -1 + 0 = -1 <= 0

Снова увеличиваем l.

Теперь l = r, процесс заканчивается.

Итоговый ответ:

4 + 3 = 7

Доказательство корректности

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

Случай 1: d[l] + d[r] > 0

Так как массив отсортирован, для любого k, где l <= k < r, верно:

d[k] >= d[l]

Тогда:

d[k] + d[r] >= d[l] + d[r] > 0

Значит, все пары (k, r) подходят. Их ровно r - l, поэтому мы можем сразу добавить это число к ответу и перейти к следующему r.

Случай 2: d[l] + d[r] <= 0

Так как d[r] — максимальный элемент среди ещё не рассмотренных справа, то для любого k < r:

d[k] <= d[r]

Но нам важнее другое: если даже с самым большим элементом d[r] число d[l] не даёт положительную сумму, то с любым другим элементом слева от r положительной суммы тоже не получится.

Значит, индекс l не может входить ни в одну подходящую пару, и его можно безопасно отбросить.

Следовательно, на каждом шаге алгоритм делает корректный переход, не теряя подходящих пар и не считая лишние.

Оценка сложности

По времени

• построение массива d — O(n);
• сортировка — O(n log n);
• проход двумя указателями — O(n).

Итого:

O(n log n)

По памяти

Храним массив d длины n, значит:

O(n)

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n), b(n), d(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    for (int i = 0; i < n; i++) {
        d[i] = a[i] - b[i];
    }

    sort(d.begin(), d.end());

    long long ans = 0;
    int l = 0;
    int r = n - 1;

    while (l < r) {
        if (d[l] + d[r] > 0) {
            ans += (r - l);
            r--;
        } else {
            l++;
        }
    }

    cout << ans << '\n';
    return 0;
}

Реализация на Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

d = []
for i in range(n):
    d.append(a[i] - b[i])

d.sort()

ans = 0
l = 0
r = n - 1

while l < r:
    if d[l] + d[r] > 0:
        ans += r - l
        r -= 1
    else:
        l += 1

print(ans)

Частые ошибки

1. Использовать тип int для ответа в C++

Количество пар может быть большим:

n * (n - 1) / 2

При n = 200000 это уже десятки миллиардов, поэтому ответ нужно хранить в типе long long.

2. Перебирать все пары

Такое решение слишком медленное и не пройдёт по ограничению времени.

3. Забыть преобразование a[i] - b[i]

Если пытаться работать сразу с исходным условием, решение получается заметно сложнее. Главное упрощение задачи — перейти к одному массиву d.

4. Ошибиться в условии строгого неравенства

Нужно проверять именно:

d[i] + d[j] > 0

а не >= 0.

Краткий вывод

• заменяем каждую пару значений одним числом d[i] = a[i] - b[i];
• ищем количество пар, для которых d[i] + d[j] > 0;
• сортируем массив;
• считаем ответ двумя указателями за линейное время после сортировки.

Итоговая сложность:

O(n log n)