| |
You are given NStar stars in 2D space. You have NShip space ships that can travel between stars. The amount of energy used by a space ship to travel from one star to another is calculated as the Euclidean distance between these stars. There are NUfo unidentified flying objects (UFO) moving around in space. UFO's reduce the energy required to travel between two stars. The energy consumed by your space ship is multiplied by 0.001 when your ship travels in the same direction at the same time as a UFO. For example, if you travel between star A(0,0) and B(10,0) it will cost you 10 energy. However, if one UFO is flying from A to B at the same time, it will cost you 10*0.001=0.01 energy. If two UFO's are flying from A to B at the same time, it will cost you 10*0.001*0.001=0.00001 energy.
Your task is to minimize the total energy used by your ships in order to visit every star at least once.
Implementation Details
Your code should implement the methods init(int[] stars) and makeMoves(int[] ufos, int[] ships). Your init method will be called once and can return any integer. Your makeMoves method will be called until all stars have been travelled to or when you reached a maximum the NStar*4 turns. Your makeMoves method should return a int[] containing your space ship moves for a single turn.
- stars gives you the location of each star. The 2D location of the ith star is given by (stars[i*2], stars[i*2+1]). The range of values will be in [0, 1023].
- ufos gives you the location of each ufo and the star indices where it is travelling towards in the next two turns. The star index of where the ith ufo is located, is given by ufos[i*3]. In the next move, the ith ufo will travel to ufos[i*3+1] and it will travel to ufos[i*3+2] after that.
- ships gives you the location of each space ship. The star index of where the ith ship is located, is given by ships[i]. A space ship can only travel directly between stars, therefor it's location is described by the star index where it is located.
You must return the list of moves for each space ship. The ith element of your return should give the zero based star index of the star where space ship i should travel towards.
Due to the internal timer using only integer values in ms units, an additional external library method has been added. You can call the getRemainingTime method and receive the remaining time in ms. This remaining time is the time remaining before your makeMoves method was called, the result will only change when your makeMoves method is called again. You can pass any integer to this method. Please note that there is some overhead in calling this method and it is advised not to call it within every makeMoves call. The overhead will unfortunately be part of your overall 20 seconds. At this stage we can not modify the makeMoves signature and added the library method instead.
Scoring
For each test case we will calculate your raw and normalized scores. If you were not able to produce a valid return value, then your raw score is -1 and the normalized score is 0. Otherwise, the raw score is equal to the sum of energy used over all space ship moves. The normalized score for each test is 1,000,000.0 * 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.
You can see your raw scores on each example test case by making an example submit. You can also see total scores of all competitors on provisional test set in the match standings. No other information about scores is available during the match.
Clarifications
- Space ships start at randomly selected stars, these stars are not marked as visited initially and need to be travelled to during a turn.
- A space ship may remain stationary at the same star. (The star will be marked as visited).
- You can visit the same star multiple times.
- A maximum of NStar*4 turns are allowed, thereafter you will score zero for the test.
- A space ship can travel from it's current star to any other star.
- NStar will be in the range of [100, 2000] (Except for seed 1).
- NShip will be in the range of [1, 10].
- NUfo will be in the range of [0, NStar/100).
- The range of the integer star coordinates is [0, 1023].
- Stars are generated around a random number of galaxy centres with a Gaussian distribution. See the visualizer source code for exact implementation.
Tools
An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. That page also contains links to useful information and sample solutions in several languages.
|