Две лиги поровну
Шахматный турнир между городами делят на две лиги, и в каждой должно быть поровну городов — по n/2. Организаторы хотят, чтобы лиги были равны и по населению: суммарное население городов первой лиги должно как можно меньше отличаться от населения второй. В одном из тестов — 36 крупнейших городов мира по данным GeoNames.
Найдите наименьшую возможную разницу населения лиг.
Вход
В первой строке чётное число n (2 ≤ n ≤ 36). Во второй — n чисел w1, …, wn, население городов (1 ≤ wi ≤ 1012).
Выход
Одно число — наименьшая разница суммарного населения двух лиг по n/2 городов.
Примеры
Пример 1
6 10 1 1 1 1 6
4
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Способов выбрать 18 городов из 36 — около 9 миллиардов. Числа до 1012, так что таблица «какие суммы достижимы» тоже не поместится. Что подсказывает ограничение n ≤ 36?
2Подсказка 2
Без требования «поровну городов» это задача из статьи о встрече посередине: две половины по 18 городов, все суммы каждой, двоичный поиск. Попробуйте её решение на примере: оно ответит 0 — город с населением 10 против пяти остальных. Но тогда в лигах один и пять городов. Чего не хватает в ключе встречи?
3Идея
Если в лигу из левой половины взяли c городов, то из правой нужно взять ровно n/2 − c. Поэтому суммы каждой половины раскладываем по числу взятых городов: Lc — суммы подмножеств левой половины из c городов, Rc — правой. Встречаются только Lc и Rn/2−c. Внутри пары групп — обычная встреча: R отсортирован, для каждой суммы a слева двоичный поиск ищет ближайшую к s/2 − a.
4Разбор
Суммы и размеры удобно строить вместе удвоением: начать со списков [0] и [0] и для каждого города дописать к списку сумм его копию плюс население, а к списку размеров — его копию плюс один. Затем разложить суммы по размеру и отсортировать группы правой половины.
Чтобы не делить нечётную сумму пополам, сравнивают удвоенные числа: разница лиг равна |s − 2(a + b)|, и для данного a нужно b, при котором 2b ближе всего к s − 2a. Первое b, у которого 2b ≥ s − 2a, и стоящее перед ним — два кандидата, как и в статье.
Общий приём: если ответ складывается из половин при каком-то условии, условие становится частью ключа встречи. Здесь это размер; бывает остаток по модулю, цвет, последняя вершина пути.
4+Решение
5Сложность
2 · 2n/2 сумм, сортировка групп и по двоичному поиску на каждую левую сумму: O(2n/2 · n). При n = 36 — около 260 тысяч сумм на половину. Память — те же 2n/2 чисел.
6Типичные ошибки
- Забыть про размер лиг. Встреча посередине без групп по размеру отвечает на другую задачу и даёт ответ меньше правильного — на примере 0 вместо 4.
- Жадность. Раздавать города по убыванию в лигу, где людей меньше и есть место. Быстро, но разница выходит больше наименьшей уже на случайных тестах.
- Деление пополам. Если искать b около (s − 2a) / 2 целочисленным делением, при нечётной сумме можно потерять ближайшего кандидата. Удвоенные сравнения этой ловушки не знают.
- Переполнение. Сумма населения доходит до 3,6·1013, в 32-битный тип она не помещается.