Problem Statement |
| | You have joined the IT department of the police force. Your first assignment is to develop an intelligent patrol routing system that will utilize historical information about crime rates in the city to minimize the response time for 911 calls and the number of crimes happening in the city.
The city is represented as a square grid of S x S blocks, with streets between each pair of horizontally or vertically adjacent blocks. Rows and columns of blocks are numbered 0 to S-1, starting with the block in the top left corner of the grid. Crime location is given as a block.
The police force has N police cars. Cars move along the streets one block per unit of time, so that after each unit of time each car is located at one of the crossroads. Rows and columns of crossroads are numbered 0 to S, starting with the crossroads at the top left corner of the grid. When the car is at the crossroads in row R and column C, it can answer one 911 call in any of the blocks adjacent to the crossroads: blocks in row R or R-1 and column C or C-1. Patrol cars have the additional benefit of reducing crime rates in blocks adjacent to them (see Crimes Simulation section).
Your goal is to dispatch each car to its next location during the day so that the total response time for all 911 calls is minimized.
Crimes Simulation
Each block has a crime rate associated with it, which changes during simulation. Crime rate is an integer between 0 and 1000, inclusive.
New crimes are generated at the beginning of each step. A crime can happen in a block only if its crime rate is greater than 500, there are no unanswered 911 calls in the block, and there are no patrol cars next to the block. If these conditions are met, a new crime is generated in this block with probability crimeRate/500 - 1.
Next the list of new crimes is reported to your solution, and patrol cars move to new positions. After that 911 calls are answered: each car responds to the earliest 911 call in one of the blocks adjacent to it (if two adjacent blocks have calls reported on the same step, the car responds to the call located earlier in row-wise order).
Finally, crime rates are updated as follows:
-
In each block the crime rate is increased by the greater of two values: 1% of its previous value or by 0.25% of the sum of previous values in the 4 adjacent blocks.
-
Random outbursts of violence happen: each 50th step crime rate at a random block increases by 1000.
-
Each patrol car halves crime rates in up to four blocks adjacent to it. Effects of cars are multiplied: crime rate in a block which has K patrol cars adjacent to it is multiplied by 0.5^K.
-
Finally, new crime rates greater than 1000 are truncated to 1000.
Implementation
Your code has to implement two methods: initialize and dispatch.
initialize(int[] crimeRates) will be called once in the beginning of the simulation to give you the information about crime rates in the city.
crimeRates will contain S * S elements, element R * S + C giving the starting crime rate at the block in row R and column C.
The return value from this method will be ignored.
dispatch(int[] cars, int[] newCrimes, int timeLeft) will be called 1000 times - once for each unit of time.
The input parameters to this method are:
-
cars gives the current positions of the patrol cars. It will contain 2 * N elements, row and column coordinates of the crossroads at which car i is will be given by elements 2*i and 2*i+1, respectively.
-
newCrimes gives the list of 911 calls which were received during the last simulation step. It will contains 2 * (number of new crimes) elements, row and column coordinates of the block where the new crime i happened will be given by elements 2*i and 2*i+1, respectively. Note that calls which were received on previous steps are not reported again, even if they have not been responded to yet.
-
timeLeft gives the number of milliseconds left of the time limit for your solution to use.
The return from dispatch is a String which gives the list of commands for the cars to follow. It must contain exactly N characters, character i giving instruction for car i. Possible instructions are:
-
'N' to decrement row coordinate,
-
'S' to increment row coordinate,
-
'W' to decrement column coordinate,
-
'E' to increment column coordinate,
-
any other character to stay in place.
Car will also stay in place if following the instruction would take it outside of the city borders.
Scoring
The raw score for a test case is calculated as follows. If your solution failed to produce valid instructions for each step of the simulation (timed out, crashed, returned a string of invalid length etc.), raw score will be -1. Otherwise the score starts with 0. Each time a patrol car answers a 911 call, the score is incremented by (step index on which this call was answered) - (step index on which this call was reported) + 1. Once the simulation is over, for each call which was not answered the score is incremented by 2 * (1001 - (step index on which this call was reported)). The resulting sum is your raw score.
The normalized score for each test case (except those that failed and scored -1) is BEST / YOUR, where BEST is the lowest raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases, multiplied by 1,000,000.
Test Case Generation
-
S will be chosen between 30 and 100, inclusive.
-
N will be chosen between S/10 and 3*S/10, inclusive.
-
All cars start at the same crossroads, chosen randomly among all crossroads.
-
Starting crime rates are generated as follows: initially crime rates in all blocks are zeros. A number of random areas of crime are added to the map, each area being a circle with crime rate decreasing from the center to the boundaries.
-
See visualizer source code for the details of test case generation.
Tools
An offline tester is available here. Please refer to its source code for exact implementation of test case generation and simulation.
|
| |
Definition |
| | | Class: | CityPatrol | | Method: | initialize | | Parameters: | int[] | | Returns: | int | | Method signature: | int initialize(int[] crimeRates) | | | | Method: | dispatch | | Parameters: | int[], int[], int | | Returns: | String | | Method signature: | String dispatch(int[] cars, int[] newCrimes, int timeLeft) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | The time limit is 20 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes. |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission (provisional) test cases. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
Number of cars = 3
City size = 30
" | | You can see an example of the simulation here. |
|
|
| 1) | |
| | | Returns: "seed = 2
Number of cars = 30
City size = 100
" | |
|
| 2) | |
| | | Returns: "seed = 3
Number of cars = 10
City size = 81
" | |
|
| 3) | |
| | | Returns: "seed = 4
Number of cars = 19
City size = 73
" | |
|
| 4) | |
| | | Returns: "seed = 5
Number of cars = 11
City size = 86
" | |
|
| 5) | |
| | | Returns: "seed = 6
Number of cars = 6
City size = 63
" | |
|
| 6) | |
| | | Returns: "seed = 7
Number of cars = 8
City size = 64
" | |
|
| 7) | |
| | | Returns: "seed = 8
Number of cars = 27
City size = 93
" | |
|
| 8) | |
| | | Returns: "seed = 9
Number of cars = 14
City size = 96
" | |
|
| 9) | |
| | | Returns: "seed = 10
Number of cars = 3
City size = 34
" | |
|
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.
