| | Introduction
Airlines have to perform routine maintenance on their fleets. However, they do
not want this maintenance to interrupt their flight schedules. You work for
AAFE (An Airline that Flies Everywhere) and have been tasked with scheduling
the AAFE maintenance crew.
AAFE has N planes in its fleet. Every day, each plane flies a number of
routes, ending the day at some location. As the airline flies everywhere, the
planes end up scattered all over the world, sometimes even landing in the
ocean or at the poles (the planes are all equipped for this).
The maintenance crew can service one plane per night, and getting to the
correct location during the day is never a problem. However, they are paid per km traveled
(in addition to a base salary and generous healthcare package) so AAFE would
like for them to travel as little as possible. Furthermore, if they travel
more than 4500km in one day, they will be paid double.
Problem
Your task is thus to determine a schedule for the maintenance crew under which
the crew travels as little as possible. The crew will start at a home location (as
specified by latitude and longitude) and must service one as-yet-unserviced plane
per night for the next N nights. After the final plane has been serviced, the
crew will return home for one night off before the next maintenance cycle
begins. Night is used loosely in this context, as the crew will end up
in many different timezones, and night refers to night UTC.
Implementation Details
You will be given an int N, indicating the number of planes, and an
int M indicating the number of cycles. You will also be
given the crew's home location as two doubles, start_lat and
start_lng. The schedule for the N planes will be given to you as a
single double[]. The simulation will have (N+1)*M
nights for the M cycles of N planes plus one night off per cycle. The input
will thus contain 2 * N * (N+1)*M elements. The ending
latitude of plane j on night i of the simulation will be given by
element 2 * (i * N + j) of the input. The longitude will
be the next element: 2 * (i * N + j) + 1.
The planes are numbered 0..N-1. You should return a int[] with N*M elements
indicating the planes to be served in each cycle. The first N elements
of your return should be a permutation of the integers 0..N-1, as should the
next N and so on.
For example, imagine that there are two planes and two maintenance cycles
(N=M=2). The input might look like
{
10, 0, 40, -90, //ending locations for two planes on day 0
20, 105, -25, 43 //day 1
-20, -15, -65, -143 //day 2
50, -45, -35, 13 //day 3
10, -175 , 15, 74 //day 4
-5, -85, 25, 18 //day 5
}
Imagine that the maintenance crew starts at 0,0. They need to service planes
at the end of days 0,1, 3, and 4. If they service plane 0 on nights 0 and 4,
and plane 1 on nights 1 and 3, then their route would be:
0,0 -> 10,0 -> -25,43 -> 0,0 -> -35,13 -> 10,-175 -> 0,0
In this case, you would return {0,1,1,0}.
Scoring
The average cost, AVG, of travel by the crew is determined by the first finding the great circle
distance (km) between consecutive points on the crew itinerary. Any of those that are 4500km or more will then be doubled. The average of these costs is then taken.
Your score for each individual test case will be 10000/AVG. Your overall score will
simply be the sum of your individual scores. If you fail a test case (your
program doesn't return an answer, or your answer is invalid) you will receive
a 0 for that test case.
Visualizer/Offline Tester
You may download a tool to aid your development at
http://www.topcoder.com/contest/problem/MaintainPlanes/vis.html.
Environment & Target Configuration
NVIDIA Tesla C1060 with 4GB of Global Memory
Intel Q8200 CPU
4GB of system memory
Centos 5.3 Linux
NVIDIA GeForce GPU for graphics
Your application should use NVIDIA CUDA 2.3 SDK.
gcc, g++, CUDA 2.3 drivers, tookit and SDK are installed on the servers, and execution path and Library paths setup. |