задачка (программирование)

[avva]

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

Вы - авиадиспетчер, которому нужно посадить N самолетов в аэропорту, у которого только одна посадочная полоса. Про каждый самолет известно окно времени, в которое он может безопасно приземлиться - оно задается в минутах, от 0 до 1440. Например, про один самолет может быть известно, что его можно посадить в любое время от 7-й минуты до 300-й включительно, про другой - в любое время от 100-й до 200-й, и так далее. Предположим, что вы для каждого самолета выбрали время посадки (его можно задать с точностью до секунды). Будет какое-то минимальное временное расстояние между посадками самолетов. Ваша задача -- это минимальное расстояние максимизировать.

На вход вам дается: число самолетов N, от 2 до 8; для каждого самолета начальная и конечная границы окна, от 0 до 1440. На выход вы должны дать: максимальное значение минимального расстояния между посадками, которое вы беретесь обеспечить.

Комментарии я скрывать не буду - если хотите предложить там свое решение, то пожалуйста, если хотите подумать сами, не заглядывайте туда.

P.S. Я бы сказал, опираясь на собственный опыт, что эта задача несколько сложнее, чем типичная алгоритмическая задача на интервью в Гугле. Если вы можете эту задачу решить и за 45 минут написать работающий код, за разумное время дающий правильный ответ - ваш уровень по крайней мере в алгоритмах вполне подходит и даже превосходит то, что в Гугле просят продемонстрировать на интервью.

Comments

[mikhail edoshin (from livejournal.com)]

это не UVa Online Judge? Если да, то подскажите, пожалуйста, номер задачи.

[avva.livejournal.com]

Знаете, наверное, да, но не уверен - я листал тамошные задачи наугад, и 2-3 книги для подготовки к соревнованиям с задачами в них тоже листал наугад. Номер задачи (если оттуда) у меня не сохранился - это очень важно?

[dimrub.livejournal.com]

Прикольная задача. Первые мысли такие: рассмотрим сначала случай без overlaps (вполне возможно, что это лишнее ограничение). Я подумываю об итеративном алгоритме, который выглядит следующим образом. Сначала мы ставим каждый самолет в середину его интервала. Далее мы находим минимальный интервал между самолетами, и начинаем его раздвигать вправо и влево с одинаковой скоростью, пока он не сравняется с одним из соседних, либо пока один из самолетов не дойдет до конца своего интервала. Теперь находим новый минимальный интервал. Если его нет (все интервалы равны) - мы дошли до оптимума, похлопаем себя по плечу. Если же есть - пытаемся раздвинуть теперь уже его. Если не раздвигается - процесс завершился, опять же, мы дошли до оптимума (как доказать, что этот оптимум глобальный - пока непонятно), прекращаем. В общем, думаю дальше.

[dimrub.livejournal.com]

Поправка: не надо интервал раздвигать сразу и вправо и влево (это муторно). Можно его сдвинуть либо вправо, либо влево, пока он не сравняется с соседним (это просто: допустим, мы решаем попробовать расширить минимальный интервал влево. Берем левый самолет нашего интервала и сдвигаем его влево так, чтобы либо текущий интервал сравнялся с тем, что слева, либо левый самолет уткнулся в свою границу. Если же после этого нынешний интервал все еще является самым маленьким, то теперь сдвигаем его правый самолет вправо).

[lightjedi.livejournal.com]

FindMaxMinGap
Вход: (N окон, Start time, End Time)

Для всех самолетов А из N
- выбрать А первым самолетом в расписании посадок
- Назначить ему время посадки T_A - самое раннее из возможных
- Найти такое T', что
(Уравнение 1): (T'-T_A) = FindMaxMinGap(N-1 оставшихся окон, T', End Time)
(если такого нет, то наибольшее T', для которого левая часть меньше правой)
- вернуть (T'-T_A)

Если N=1, вернуть T_E - Start_time, где T_E = самое позднее время посадки данного самолета.

Ключевой момент - поиск T'. Здесь мы замечаем, что FindMaxMinGap - невозрастающая функция от второго параметра (Start Time), поэтому решение уравнения (1) можно провести бинарным поиском - т.е. порядка 16 попыток для 86400 возможных позиций. Итого сложность будет где-то 16^N * (N!).

[megamihalych.livejournal.com]

Все границы окон упорядочить по возрастанию.
первый самолет посадить в минимальную границу, последний - в максимальную.
Остальные самолеты первоначально расположить произвольно. Затем рассчитать попарные расстояния между соседними. понятно, что расстояния между не-соседними можно не принимать во внимание. после этого начать усреднять эти расстояния. В качестве начальной пары можно взять минимальное и усреднить с бОльшим из соседей. Далее цикл повторяется. Если новое значение оказывается за пределами окна для данного самолета - оставить на ближайшей к этому значению границе.
Поннятно, что при таком алгоритме минимальное расстояние не уменьшается, и ограницено сверху значением 1440/(N-1), поэтому имеет предел. Установить порог изменения в 1 секунду, после чего цикл обрывать при изменениях меньше секунды.

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

[hlodvig.livejournal.com]

А что будет, если у первого самолета допустимое окно 7-300 минуты, а у второго окно 8-9 минуты?

[resolvent.net (from livejournal.com)]

Перебираем все перестановки самолетов (N!).

Делением пополам перебираем размеры минимального расстояния (log(1440/(N-1)).

Пытаемся расставить самолеты с заданным минимальным расстоянием и в заданном порядке (легко сделать за один проход).

Итого: O(N*N!*log(1440/(N-1))) - при ограничении на N <= 8 должно давать разумное время.

[bsivko.livejournal.com]

+1

[lifewalker.livejournal.com]

Люблю дискретную оптимизацию!

[hlodvig.livejournal.com]

Можно уточнение? Задача зациклена? Нужно ли учитывать расстояние между прилетом последнего самолета в этот день с прилетом первого самолета в следующий день? Ведь некоторые алгоритмы могут дать такое значение, что расстояние между последним за сегодня и первым за завтра окажется меньше расчитанного максимума.

[avva.livejournal.com]

Нет, задача не зациклена, есть только один день.

[mike aizatsky (from livejournal.com)]

Навскидку: при заданной перестановке самолетов они себя ведут как линейная система с ограничениями - грузики с пружинками в желобах. Видно как добавление одного шарика меняет систему (или перераспределяет расстояние поровну если может или упирает шарик в стенку). Итого за квадрат в худшем случае можно справиться.

Но вот что с перестановками делать - ума не приложу.

[raydac.livejournal.com]

сажаем сразу все в одно время на одну полосу, процесс снимаем на мобилу и выкладываем на ютюб, миллионы просмотров гарантированы

[timur0.livejournal.com]

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

[huzhepidarasa.livejournal.com]

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

[rusquant.livejournal.com]

это задача линейного программирования размерности ~N^2/2, т.е. вполне разумной. симплекс-метод или interior-point солвер можно конечно написать за 45 минут, но зачем?

[e2pii1.livejournal.com]

> это задача линейного программирования размерности ~N^2/2

Почему ? Как ?

[moon-aka-sun.livejournal.com]

Уточним: Вероятно, окно может быть и от 1400 до 100?

[avva.livejournal.com]

Нет, есть только один день и все промежутки внутри [0,1400].

[rotozeеv (from livejournal.com)]

А в таких задачах нужно доказывать, что алгоритм приведет к оптимальному решению? А то у меня есть простая идея:

Ставим все времена на левые края окон.
Берем 1 самолет и двигаем его по его интервалу - если какое то новое положение 1го самолета дает общий выигрыш, то оставляем его.
Берем 2 самолет и двигаем ...
...
Берем N самолет и двигаем...
И снова берем 1 самолет ...

Продолжать, пока не получим, что ни один из N самолетов нельзя переставить не ухудшив результат.

[mkal.livejournal.com]

Лично я бы не стал много думать и просто решил N! раз задачу линейного программирования.

[rusquant.livejournal.com]

ну да, с той вариацией что можно заведомо не решать "плохие" перестановки. Зная перестановку, можно ведь легко посчитать upper bound на значение функции

[http://users.livejournal.com/_sabiko/]

В порядке бреда - на уровне простого школьника:

- Ищем min левых границ и max правых, этот диапазон разбиваем на равные N-1 частей - получаем "идеальные" точки
- Смотрим, диапазоны, не покрывающие ни одной, ищем среди них минимальное расстояние от границы диапазона до одной из точек, сдвигаем её на границу диапазона, отрезки по обе стороны переразбиваем, диапазон и точку убираем из рассмотрения
- Смотрим точки, не покрытые ни одним диапазоном, та же процедура
- Все диапазоны покрывают хотя бы одну точку и каждая покрыта хотя бы одним диапазоном - можно распределить без дальнейших сдвигов времени вылетов - не будем этого делать, просто смотрим минимум, это результат

В каком случае такой подход ломается?

[avva.livejournal.com]

Честно скажу, что минут 10 думал, не придумал, где ломается, больше времени не было, но моя интуиция говорит, что придумать все же можно.

[173175973.livejournal.com]

Мысль, как оптимизировать N! перебор.
Будем рассматривать частичные последовательности, хранить их в приоритетной очереди и расширять, начиная с текущуей отимальной.
Начнём с (1,2) и (2,1), где цифры - номера самолётов. Пусть в первой интервал меньше, тогра по ней строим (3,1,2), (1,3,2), (1,2,3).
Невозможные выкидываем, медлыенные ставим на нужное место в очереди. Возможно, в оценке медленности стот добавить длинну последовательности.
Ещё пара эвристик - заранее выкинуть невозможные двойки и тройки, на случайных данных они должны хорошо сократить количество вариантов.
PS. Хочу узнать правильный ответ ))

[avva.livejournal.com]

Решение от resolvent.net выше (с небольшой моей поправкой) - то, что я знаю как правильное. Для N<=8 оно мгновенно даст результат, а это все, что требуется.

[mehas.livejournal.com]

Бинарный поиск по ответу + линейный проход с кучей с жадной расстановкой на каждой итерации

[mikkim08.livejournal.com]

Правильный ответ тут уже был, поэтому интересно понять, как можно быстро угадать решение.

Во-первых, никаких симплекс-методов и т.д. такие задачки не подразумевают. Даже думать в эту сторону не надо.

Во-вторых, ограничение на N от 2 до 8 нам явно говорит о том, что ожидаемое решение подразумевает перебор N! А иначе, почему N такое маленькое ?

И в-третьих, вот это mim max условие максимальное значение минимального расстояния очень напоминает пример FairWorkload отсюда (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch)

[avva.livejournal.com]

Разумные вещи пишете. Я тоже не отследил важность этого N<=8, когда думал, как и многие другие.

[sergey doroshenko (from livejournal.com)]

Бинарный поиск: предполагаем, что можно обеспечить минимальный интервал N, проверяем можно ли (кол-во самолетов позволяет), если да -- увеличиваем, если нет -- уменьшаем, rinse-repeat.

[kodt-rsdn.livejournal.com]

Quick-n-dirty решение.
Перебираем N! перестановок самолётов (для N=8 это вполне обозримое количество - 40320 гипотез) задающих очерёдность захода на посадку.
Каждый самолёт сажаем как можно раньше, - разумеется, строго после предыдущего.
Находим минимальное время.

[migmit.livejournal.com]

Э-э-э, два самолёта, первый нужно посадить в момент 0 (без вариантов), второй - от момента 1 до момента 1440. Вы правда считаете, что лучше, чем 1, не сделать?

[mopexod.livejournal.com]

Понятно, что "все пермутации" показались в ответах. Странно, что предлагали другое :)
Еще я не заметил, что самолетов "до 8" - это сразу сводит задачу к "все пермутации и больше ни о чем не думай".
Как решавший эту задачу на практике - выстраивание очереди кораблей к причалу - практически те же условия, как и у самолетов, добавлю, что на практике такое решение не очень годится, если очередь из 20-30.

[migmit.livejournal.com]

А. Блин. Я тоже не заметил.

Тогда, конечно, все перестановки и пошло оно нах.

[migmit.livejournal.com]

Если порядок, в котором садятся самолёты, фиксирован, то оптимум будет, похоже, min{i<j}[(end_j - start_i) / (j - i)]. Находится за N^2. Ну и, соответственно, можно сделать полный перебор, N! вариантов. Общее время O((N+2)!). Суксь, но заработает. Можно ли быстрее - не знаю.

[migmit.livejournal.com]

Да, точно. Именно такой оптимум и будет.

[vasja-iz-aa.livejournal.com]

вообще то это простая задача, если Вы только не ошиблись в формулировке

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

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

[vasja-iz-aa.livejournal.com]

ну и там, конечно, надо тривиальный критерий остановки добавить

[rgu.livejournal.com]

Любопытная задача здесь возникает -- сгенерить непротиворечивые перестановки интервалов.
В худшем случае исходную задачу быстрее решить не удастся, но если интервалы случайно распределены, то или оптимальное время на какой-нибудь перестановке получим или самих перестановок будет существенно меньше, чем N!

[xyli0o.livejournal.com]

Подскажите, пожалуйста, на счет времени выполнения. 34 секунды в худшем случае, это ок?
https://github.com/Alexander-Panin/planes/blob/master/my.py