We optimize ... we parallelize ... we take off!

“From point A to point B a pedestrian walked at a speed ...” Remember these tasks from the school curriculum? They taught us the ability to think logically and, to some extent, to create algorithms, that is, the basics of programming. But we all grew up, and it's time to solve more adult problems. From point A to point B every day dozens of planes take off with different ticket prices, routes, bonus programs ... this set of options needs to be calculated in such a way as to find the best one based on the proposed criteria, and more quickly than others.
So you met briefly with the conditions of the competition for students, graduate students and schoolchildren "Accelerate Your Code" , held by Intel in November. For all interested and willing to get a prize ultrabook from Intel - the button below.

So imagine that you live in Berlin and have to go to a software conference in San Francisco. The task of finding the cheapest ticket for a direct flight does not interest us as unsportsmanlike, but options are possible. Suppose you have a certain amount of time after the conference and the opportunity to spend a little more to come to an interesting place on the way. For example, you found out that the route Berlin - San Francisco - San Paolo - Berlin will cost you only 100 euros more than a direct one. Is this not a reason to stay for an extra week?
An indirect route involves transfers and, as a result, the possibility of using several airlines; the price of one flight depends on which carrier you fly the rest. If all trips are made on the aircraft of one company, it will cost 30% cheaper. In addition, the airlines are united in “alliances” in order to offer passengers more advantageous conditions when using flights of only this “alliance” - the savings will be 20%.
Now the solution of this kind of problem requires the skill and cost of mental work: booking services are not able to sort out such a huge number of options. However, it can be automated - to the delight of consumers.

In this competition, you are given two input lists: of all the flights you need, as well as alliances formed by airlines (one company may be part of several alliances). The source code for the solution, the input data, the expected format of the result, as well as a description of the problem (in free form set forth here) can be downloaded from the Intel Software Academic Program website . Your task is to optimize and parallelize the proposed code. Of course, you can start from scratch and write everything yourself, but it seems safer to use the existing solution. Optimization and parallelization should cover a wide range of conditions: few / many flights, few / many alliances, small / large time spans, etc.

Task 1. “We work hard”

Find the cheapest flights between the two cities.
Example. Find the cheapest flight between Berlin and San Francisco with a flight there and arrival back at a given interval: departure after 2012-11-08 05:00 GMT - arrival before 2012-11-08 23:00 GMT, return departure after 2012- 11-15 02:00 GMT - Arrival before 2012-11-15 18:00 GMT. The maximum transplant time is 4 hours.
')

Task 2. “We are resting with all our strength”

Having set the minimum and maximum duration of rest (before or after a working trip), as well as a list of airports of interest, offer the cheapest flight option for each airport.
Example. How to change the route Berlin - San Francisco, to spend a week vacation (before or after) in the following interesting places (airports): San Paolo, Panama, Cayman Islands. Offer the cheapest option for each airport.

You can find the registration form for the competition, as well as all the technical information related to compiling, benchmarking and uploading programs on the competition website .

Prizes of the competition

A team participating in a competition may consist of one or two people. Three best teams from Russia and Ukraine will receive the main prizes - ultrabooks (ultrabook in one hand, that is, a maximum of 6). Additional prizes - at the discretion of the organizers.

Good luck to you parallelization and successful flight of fantasy!