JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 29
Problem: ServiceFacilities

Problem Statement

    

You are working on developing a planned city, meaning that you intend to plan and build certain elements of the infrastructure, like services, even before people take up residence. Several points of interest where development is planned, have been mapped.

It now needs to be determined where to build different types of major services, which might include things like airports, schools, hospitals, recycling centers, etc. The goal is to minimize the (Euclidean) distance someone might have to travel in order to reach any of these services. Each different service has been assigned a level of importance, and has an associated cost to build. Any service may be placed at as many locations as you like, within the constraints of your budget, however each service must be placed on at least one location, and no point of interest can contain more than one service.

Your method will be called, and will be given several parameters. int[]s x and y indicate each of the points of interest. You will also be given int[] serviceImportance, where each element indicates the importance of that service, as well as int[] serviceCost indicating the cost of building each service. Finally, int budget indicates the maximum total expenditure.

Test cases will be generated as follows (all ranges uniform):

  • Select the number of points, N = 50...200
  • Select the number of services, S = 4...15
  • Select N lattice points in the range (0, 0) - (100, 100)
  • Select each service imporance in the range 10...100
  • Select each service cost in the range 10...100
  • Select budget in the range minCost...(4*minCost), where minCost is the cost of building each service exactly once

For a proposed set of service locations, the overall convenience is scored by considering each lattice point (x,y) in the range (0,0) - (100,100), inclusive. For each point, we calculate a point-score by taking the sum over all i of serviceImportance[i] * distance[i], where distance[i] is the Euclidean distance from (x,y) to the nearest service of type i. The overall score is then calculated as the mean value of (point-score ^ 2).

Your return should be an array of integers, where each pair of integers represents a service type and a service location. For instance, return[2 * i] is a service number, and return[2 * i + 1] is a location (refering to the index of x and y).

Your goal is to place services in each location as to obtain an overall convenience score as low as possible. The overall scoring will be relative, so you will get BEST/YOU points for each test case, where BEST is the best score on that test case, and YOU is your score on that test case.

A visualizer is available.

 

Definition

    
Class:ServiceFacilities
Method:placeServices
Parameters:int[], int[], int[], int[], int
Returns:int[]
Method signature:int[] placeServices(int[] x, int[] y, int[] serviceImportance, int[] serviceCost, int budget)
(be sure your method is public)
    
 

Notes

-Time limit is 20 seconds, and memory limit is 1GB.
-There are 100 non-example test cases.
-The seeds for the examples are 1-10, in order.
 

Examples

0)
    
Locations = 179
Services = 7
Budget = 673

Services:
  1. Importance = 84, Cost = 83
  2. Importance = 70, Cost = 44
  3. Importance = 95, Cost = 16
  4. Importance = 56, Cost = 51
  5. Importance = 87, Cost = 85
  6. Importance = 45, Cost = 36
  7. Importance = 67, Cost = 19
1)
    
Locations = 59
Services = 10
Budget = 1142

Services:
  1. Importance = 77, Cost = 36
  2. Importance = 19, Cost = 50
  3. Importance = 61, Cost = 23
  4. Importance = 33, Cost = 29
  5. Importance = 95, Cost = 58
  6. Importance = 72, Cost = 22
  7. Importance = 35, Cost = 50
  8. Importance = 44, Cost = 19
  9. Importance = 77, Cost = 91
  10. Importance = 28, Cost = 50
2)
    
Locations = 145
Services = 10
Budget = 1520

Services:
  1. Importance = 41, Cost = 61
  2. Importance = 64, Cost = 23
  3. Importance = 76, Cost = 75
  4. Importance = 23, Cost = 60
  5. Importance = 28, Cost = 19
  6. Importance = 13, Cost = 14
  7. Importance = 55, Cost = 65
  8. Importance = 100, Cost = 36
  9. Importance = 91, Cost = 41
  10. Importance = 64, Cost = 79
3)
    
Locations = 64
Services = 10
Budget = 1133

Services:
  1. Importance = 87, Cost = 31
  2. Importance = 78, Cost = 53
  3. Importance = 93, Cost = 15
  4. Importance = 44, Cost = 90
  5. Importance = 46, Cost = 60
  6. Importance = 65, Cost = 18
  7. Importance = 19, Cost = 78
  8. Importance = 74, Cost = 95
  9. Importance = 71, Cost = 15
  10. Importance = 85, Cost = 45
4)
    
Locations = 87
Services = 7
Budget = 1275

Services:
  1. Importance = 74, Cost = 89
  2. Importance = 34, Cost = 71
  3. Importance = 31, Cost = 65
  4. Importance = 10, Cost = 46
  5. Importance = 37, Cost = 61
  6. Importance = 30, Cost = 16
  7. Importance = 87, Cost = 39
5)
    
Locations = 155
Services = 13
Budget = 2153

Services:
  1. Importance = 97, Cost = 21
  2. Importance = 17, Cost = 39
  3. Importance = 55, Cost = 19
  4. Importance = 81, Cost = 54
  5. Importance = 66, Cost = 88
  6. Importance = 16, Cost = 77
  7. Importance = 32, Cost = 81
  8. Importance = 81, Cost = 22
  9. Importance = 54, Cost = 85
  10. Importance = 60, Cost = 53
  11. Importance = 13, Cost = 19
  12. Importance = 35, Cost = 88
  13. Importance = 36, Cost = 34
6)
    
Locations = 194
Services = 12
Budget = 923

Services:
  1. Importance = 46, Cost = 38
  2. Importance = 96, Cost = 11
  3. Importance = 27, Cost = 39
  4. Importance = 92, Cost = 42
  5. Importance = 38, Cost = 26
  6. Importance = 58, Cost = 13
  7. Importance = 46, Cost = 90
  8. Importance = 49, Cost = 54
  9. Importance = 42, Cost = 50
  10. Importance = 68, Cost = 79
  11. Importance = 23, Cost = 87
  12. Importance = 53, Cost = 12
7)
    
Locations = 152
Services = 10
Budget = 1259

Services:
  1. Importance = 70, Cost = 24
  2. Importance = 76, Cost = 91
  3. Importance = 41, Cost = 80
  4. Importance = 28, Cost = 38
  5. Importance = 63, Cost = 61
  6. Importance = 96, Cost = 29
  7. Importance = 72, Cost = 98
  8. Importance = 80, Cost = 77
  9. Importance = 30, Cost = 58
  10. Importance = 10, Cost = 64
8)
    
Locations = 87
Services = 13
Budget = 2440

Services:
  1. Importance = 35, Cost = 73
  2. Importance = 12, Cost = 64
  3. Importance = 63, Cost = 96
  4. Importance = 92, Cost = 81
  5. Importance = 77, Cost = 49
  6. Importance = 46, Cost = 77
  7. Importance = 54, Cost = 80
  8. Importance = 76, Cost = 98
  9. Importance = 61, Cost = 90
  10. Importance = 83, Cost = 82
  11. Importance = 80, Cost = 10
  12. Importance = 32, Cost = 60
  13. Importance = 97, Cost = 51
9)
    
Locations = 73
Services = 14
Budget = 1100

Services:
  1. Importance = 96, Cost = 66
  2. Importance = 87, Cost = 34
  3. Importance = 52, Cost = 90
  4. Importance = 100, Cost = 77
  5. Importance = 73, Cost = 22
  6. Importance = 100, Cost = 46
  7. Importance = 69, Cost = 27
  8. Importance = 48, Cost = 54
  9. Importance = 43, Cost = 98
  10. Importance = 31, Cost = 47
  11. Importance = 70, Cost = 92
  12. Importance = 38, Cost = 89
  13. Importance = 42, Cost = 57
  14. Importance = 93, Cost = 90

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.