JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Round 2
Problem: StarTraveller

Problem Statement

    

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.

 

Definition

    
Class:StarTraveller
Method:init
Parameters:int[]
Returns:int
Method signature:int init(int[] stars)
 
Method:makeMoves
Parameters:int[], int[]
Returns:int[]
Method signature:int[] makeMoves(int[] ufos, int[] ships)
(be sure your methods are public)
 

Available Libraries

    
Class:Server
Method:getRemainingTime
Parameters:int
Returns:int
Sample Call:val = Server.getRemainingTime(ignore);
    
 

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.
-The match is rated.
 

Examples

0)
    
seed = 1
NStar = 20
NShip = 1
NUfo = 4
1)
    
seed = 2
NStar = 472
NShip = 1
NUfo = 0
2)
    
seed = 3
NStar = 1991
NShip = 7
NUfo = 16
3)
    
seed = 4
NStar = 520
NShip = 3
NUfo = 4
4)
    
seed = 5
NStar = 1909
NShip = 8
NUfo = 2
5)
    
seed = 6
NStar = 1330
NShip = 2
NUfo = 3
6)
    
seed = 7
NStar = 1006
NShip = 3
NUfo = 1
7)
    
seed = 8
NStar = 1612
NShip = 5
NUfo = 8
8)
    
seed = 9
NStar = 769
NShip = 6
NUfo = 3
9)
    
seed = 10
NStar = 1434
NShip = 1
NUfo = 4

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.