Студенты СПбГУ стали чемпионами мира по программированию, обойдя Гарвард и MIT

Примерный тип задачи:

Представьте, что у нас есть n машин с двумя чипами на каждой, а каждый чип питается от k батарей. Удивительно, но не имеет значения, сколько энергии потребляют чипы, однако важно, чтобы выходные мощности чипов как можно меньше отличались друг от друга, так как в этом случае машина работает наилучшим образом. Выходная мощность чипа — это минимальная выходная мощность среди всех k батарей в чипе. Вы располагаете 2nk батареями, которые вам необходимо распределить по чипам машин. Может оказаться, что нет способа распределить батареи так, чтобы выходные мощности чипов были равны для всех машин. Тем не менее, вам нужно минимизировать разность мощностей. Подробнее, вы хотите гарантировать вашим заказчикам, что разность выходных мощностей чипов во всех машинах не превосходит d, при этом стараясь минимизировать d. Для этого вам нужно найти оптимальное распределение батарей по чипам.

Входные данные. Состоят из одного теста, содержащего две строки. В первой строке два числа n и k (2nk ≤ 106), во второй 2nk целых чисел pi (1 ≤ pi ≤109).

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

Легко :)

Эта задача одна из простых. Нужно из 2nk выбрать n пар (назовем их представителями) батареек, каждая из которых
имеет минимальную мощность на своем чипе, чтобы максимум разности выходных мощностей батареек в паре был минимален. Предположим, что зафиксировано d, тогда можно узнать, существуют ли представители такие, что максимум не превосходит d. Отсортируем мощности p1 ≤ p2… ≤ p2nk и будем жадно набирать пары: в первую пару попадут батареи p1 и p2. Если p2 — p1 > d, то представителей выбрать нельзя. Во вторую пару возьмем батареи (pi2, pi2+1) с разностью не больше d и минимальным индексом i2 ≤ 2k + 1, если это возможно. Аналогично в третью пару — (pi3, pi3 + 1), i3 ≤ 4k + 1.

Если с помощью этого алгоритма не удается набрать n пар, то этого сделать нельзя. Ответ найдем бинарным поиском.