company_banner

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


    «Из пункта А в пункт Б вышел пешеход со скоростью … » Помните такие задачки из школьной программы? Они учили нас умению логически мыслить и, в какой-то степени, составлять алгоритмы, то бишь азам программирования. Но вот все мы подросли, и пришло время решать более взрослые задачи. Из пункта А в направлении пункта Б каждый день вылетает десятки самолетов с различными ценами на билет, маршрутами, бонусными программами… это множество вариантов необходимо просчитать таким образом, чтобы найти оптимальный исходя из предложенных критериев, причем просчитать быстрее других.
    Вот вы и познакомились кратенько с условиями конкурса для студентов, аспирантов и школьников «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). Дополнительные призы – на усмотрение организаторов.

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

    Comments 6

      +3
      А спорим, я не могу учавствовать в конкурсе?)
      Хотя и очень хочется.
        +2
        Комментарий очень в тему т.к. в посте нигде не написано, что конкурс только для студентов и школьников.
          0
          да, жаль, что автор не указал об этом в посте. А то я уже скачал и чуток заботал =)
            0
            Спасибо, поправила
          0
          Какие языки можно использовать?
            0
            если по-умолчанию предлагается оптимизация уже написанного кода, то надо полагать, что С++. Или Вы хотите все с самого начала сами сделать? :)

          Only users with full accounts can post comments. Log in, please.