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) | |
| | | Returns:
"Locations = 179<br>Services = 7<br>Budget = 673<br><br>Services:<ol><li>Importance = 84, Cost = 83</li><li>Importance = 70, Cost = 44</li><li>Importance = 95, Cost = 16</li><li>Importance = 56, Cost = 51</li><li>Importance = 87, Cost = 85</li><li>Importance = 45, Cost = 36</li><li>Importance = 67, Cost = 19</li></ol>" | |
|
| 1) | |
| | | Returns:
"Locations = 59<br>Services = 10<br>Budget = 1142<br><br>Services:<ol><li>Importance = 77, Cost = 36</li><li>Importance = 19, Cost = 50</li><li>Importance = 61, Cost = 23</li><li>Importance = 33, Cost = 29</li><li>Importance = 95, Cost = 58</li><li>Importance = 72, Cost = 22</li><li>Importance = 35, Cost = 50</li><li>Importance = 44, Cost = 19</li><li>Importance = 77, Cost = 91</li><li>Importance = 28, Cost = 50</li></ol>" | |
|
| 2) | |
| | | Returns:
"Locations = 145<br>Services = 10<br>Budget = 1520<br><br>Services:<ol><li>Importance = 41, Cost = 61</li><li>Importance = 64, Cost = 23</li><li>Importance = 76, Cost = 75</li><li>Importance = 23, Cost = 60</li><li>Importance = 28, Cost = 19</li><li>Importance = 13, Cost = 14</li><li>Importance = 55, Cost = 65</li><li>Importance = 100, Cost = 36</li><li>Importance = 91, Cost = 41</li><li>Importance = 64, Cost = 79</li></ol>" | |
|
| 3) | |
| | | Returns:
"Locations = 64<br>Services = 10<br>Budget = 1133<br><br>Services:<ol><li>Importance = 87, Cost = 31</li><li>Importance = 78, Cost = 53</li><li>Importance = 93, Cost = 15</li><li>Importance = 44, Cost = 90</li><li>Importance = 46, Cost = 60</li><li>Importance = 65, Cost = 18</li><li>Importance = 19, Cost = 78</li><li>Importance = 74, Cost = 95</li><li>Importance = 71, Cost = 15</li><li>Importance = 85, Cost = 45</li></ol>" | |
|
| 4) | |
| | | Returns:
"Locations = 87<br>Services = 7<br>Budget = 1275<br><br>Services:<ol><li>Importance = 74, Cost = 89</li><li>Importance = 34, Cost = 71</li><li>Importance = 31, Cost = 65</li><li>Importance = 10, Cost = 46</li><li>Importance = 37, Cost = 61</li><li>Importance = 30, Cost = 16</li><li>Importance = 87, Cost = 39</li></ol>" | |
|
| 5) | |
| | | Returns:
"Locations = 155<br>Services = 13<br>Budget = 2153<br><br>Services:<ol><li>Importance = 97, Cost = 21</li><li>Importance = 17, Cost = 39</li><li>Importance = 55, Cost = 19</li><li>Importance = 81, Cost = 54</li><li>Importance = 66, Cost = 88</li><li>Importance = 16, Cost = 77</li><li>Importance = 32, Cost = 81</li><li>Importance = 81, Cost = 22</li><li>Importance = 54, Cost = 85</li><li>Importance = 60, Cost = 53</li><li>Importance = 13, Cost = 19</li><li>Importance = 35, Cost = 88</li><li>Importance = 36, Cost = 34</li></ol>" | |
|
| 6) | |
| | | Returns:
"Locations = 194<br>Services = 12<br>Budget = 923<br><br>Services:<ol><li>Importance = 46, Cost = 38</li><li>Importance = 96, Cost = 11</li><li>Importance = 27, Cost = 39</li><li>Importance = 92, Cost = 42</li><li>Importance = 38, Cost = 26</li><li>Importance = 58, Cost = 13</li><li>Importance = 46, Cost = 90</li><li>Importance = 49, Cost = 54</li><li>Importance = 42, Cost = 50</li><li>Importance = 68, Cost = 79</li><li>Importance = 23, Cost = 87</li><li>Importance = 53, Cost = 12</li></ol>" | |
|
| 7) | |
| | | Returns:
"Locations = 152<br>Services = 10<br>Budget = 1259<br><br>Services:<ol><li>Importance = 70, Cost = 24</li><li>Importance = 76, Cost = 91</li><li>Importance = 41, Cost = 80</li><li>Importance = 28, Cost = 38</li><li>Importance = 63, Cost = 61</li><li>Importance = 96, Cost = 29</li><li>Importance = 72, Cost = 98</li><li>Importance = 80, Cost = 77</li><li>Importance = 30, Cost = 58</li><li>Importance = 10, Cost = 64</li></ol>" | |
|
| 8) | |
| | | Returns:
"Locations = 87<br>Services = 13<br>Budget = 2440<br><br>Services:<ol><li>Importance = 35, Cost = 73</li><li>Importance = 12, Cost = 64</li><li>Importance = 63, Cost = 96</li><li>Importance = 92, Cost = 81</li><li>Importance = 77, Cost = 49</li><li>Importance = 46, Cost = 77</li><li>Importance = 54, Cost = 80</li><li>Importance = 76, Cost = 98</li><li>Importance = 61, Cost = 90</li><li>Importance = 83, Cost = 82</li><li>Importance = 80, Cost = 10</li><li>Importance = 32, Cost = 60</li><li>Importance = 97, Cost = 51</li></ol>" | |
|
| 9) | |
| | | Returns:
"Locations = 73<br>Services = 14<br>Budget = 1100<br><br>Services:<ol><li>Importance = 96, Cost = 66</li><li>Importance = 87, Cost = 34</li><li>Importance = 52, Cost = 90</li><li>Importance = 100, Cost = 77</li><li>Importance = 73, Cost = 22</li><li>Importance = 100, Cost = 46</li><li>Importance = 69, Cost = 27</li><li>Importance = 48, Cost = 54</li><li>Importance = 43, Cost = 98</li><li>Importance = 31, Cost = 47</li><li>Importance = 70, Cost = 92</li><li>Importance = 38, Cost = 89</li><li>Importance = 42, Cost = 57</li><li>Importance = 93, Cost = 90</li></ol>" | |
|
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)2020, TopCoder, Inc. All rights reserved.