TopCoder problem "MaintainPlanes" used in ()

Problem Statement



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.


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}.


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

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.


Parameters:int, int, double, double, double[]
Method signature:int[] schedule(int M, int N, double home_lat, double home_lng, double[] positions)
(be sure your method is public)


-Latitude values will be between -90 and 90, inclusive.
-Longitude values will be between -180 and 180, inclusive
-The Earth is treated as a perfect sphere with radius 6378.1km.
-The distance between two points is calculated as the great circle distance
-Note that this problem uses degrees, not radians.
-There are 50 provisional tests.
-M and N are chosen uniformly. All of the landing points are chosen uniformly over the surface of the earth.


-N will be between 30 and 100, inclusive.
-M will be between 5 and 30, inclusive.
-The time limit is 20 seconds per test case.
-The CPU memory limit is 1024MB.


Returns: "seed = 1
<br>M = 5
<br>N = 30
Returns: "seed = 2
<br>M = 5
<br>N = 40
Returns: "seed = 3
<br>M = 11
<br>N = 81
Returns: "seed = 4
<br>M = 13
<br>N = 73
Returns: "seed = 5
<br>M = 28
<br>N = 86
Returns: "seed = 6
<br>M = 18
<br>N = 63
Returns: "seed = 7
<br>M = 23
<br>N = 64
Returns: "seed = 8
<br>M = 25
<br>N = 93
Returns: "seed = 9
<br>M = 30
<br>N = 96
Returns: "seed = 10
<br>M = 30
<br>N = 100

Problem url:

Problem stats url:



Problem categories: