Оптимизируем… распараллеливаем… взлетаем!

«Из пункта А в пункт Б вышел пешеход со скоростью … » Помните такие задачки из школьной программы? Они учили нас умению логически мыслить и, в какой-то степени, составлять алгоритмы, то бишь азам программирования. Но вот все мы подросли, и пришло время решать более взрослые задачи. Из пункта А в направлении пункта Б каждый день вылетает десятки самолетов с различными ценами на билет, маршрутами, бонусными программами… это множество вариантов необходимо просчитать таким образом, чтобы найти оптимальный исходя из предложенных критериев, причем просчитать быстрее других.
Вот вы и познакомились кратенько с условиями конкурса программистов «Accelerate Your Code», проводимого компанией Intel в ноябре. Для всех заинтересовавшихся и желающих получить призовой ультрабук от Intel – кнопка внизу.

Итак, представьте себе, что вы живете в Берлине и должны поехать на софтверную конференцию в Сан-Франциско. Задача найти самый дешевый билет на прямой рейс нас не интересует как неспортивная, но возможны варианты. Допустим, у вас есть некий запас времени после конференции и возможность потратить несколько больше, чтобы по пути заехать в какое-нибудь интересное место. Например, вы выяснили, что маршрут Берлин – Сан-Франциско – Сан-Паоло – Берлин обойдется вам всего на 100 евро дороже, чем прямой. Это ли не повод задержаться на лишнюю недельку?
Непрямой маршрут предполагает пересадки и, как следствие, возможность использования нескольких авиакомпаний; цена одного перелета зависит от того, каким перевозчиком вы полетите остальные. Если все поездки будут совершены на самолетах одной компании, это обойдется на 30% дешевле. Кроме того, авиакомпании объединяются в «альянсы», чтобы предложить пассажирам более выгодные условия при использовании рейсов только этого «альянса» — экономия составит 20%.
Сейчас решение задачи подобного рода требует умения и затрат умственного труда: сервисы бронирования не в состоянии перебрать такое огромное количество вариантов. Однако оно может быть автоматизировано – на радость потребителей.

В этом конкурсе вам предоставляется два входных списка: всех нужных вам полетов, а также альянсов, сформированных авиакомпаниями (одна компания может входить в несколько альянсов). Исходный код решения, входные данные, ожидаемый формат результата, а также описание задачи (в вольной форме изложенное здесь) вы можете скачать на сайте Intel Software Academic Program. Ваша задача – оптимизировать и распараллелить предложенный код. Конечно, можно начать с нуля и написать всё самому, но, думается, безопаснее использовать имеющееся решение. Оптимизация и параллелизация должна охватывать широкий диапазон условий: мало/много полетов, мало/много альянсов, маленький/большой временной промежуток и т.д.

Задача 1. «Напряженно работаем»

Найти самые дешевые перелеты между двумя городами.
Пример. Найти самый дешевый перелет между Берлином и Сан-Франциско с вылетом туда и прибытием назад в заданном промежутке: туда вылет после 2012-11-08 05:00 GMT – прибытие до 2012-11-08 23:00 GMT, обратно вылет после 2012-11-15 02:00 GMT – прибытие до 2012-11-15 18:00 GMT. Максимальное время пересадки – 4 ч.

Задача 2. «Изо всех сил отдыхаем»

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

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

Призы конкурса

Команда-участник конкурса может состоять из одного или двух человек. Три лучших команды из России и Украины получат главные призы – ультрабуки (по ультрабуку в одни руки, то есть максимум 6). Дополнительные призы – на усмотрение организаторов.

Удачного вам распараллеливания и успешного полета фантазии!