JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Round 1
Problem: RoadsAndJunctions

Problem Statement

    You are given a map with NC cities on it. You need to build a road system which would connect all of them. To do this, you can build two types of objects: junctions and roads. A junction is an auxiliary location (distinct from the cities) where one or several roads end. A road is a straight line segment connecting two cities, two junctions or a city and a junction.

To make things worse, you don't have a topographic map of the area, so junction construction might fail and you will only know about it once you've already commissioned it (and, more importantly, paid for it). Fortunately, the road building technology is more sturdy, so you are guaranteed that if you commission a road, it will be built successfully.

Your goal is to commission a system of junctions and roads connecting them and the cities so that all cities are connected (i.e. for each pair of cities there exists a sequence of one or several roads which allow to get from one city to another).

Implementation

Your code has to implement two methods: buildJunctions and buildRoads.

buildJunctions(int S, int[] cities, double junctionCost, double failureProbability) will be called once to give you the information about the map and to let you commission the junctions. The input parameters are:
  • S gives the size of the map. Both coordinates of each junction you commission must be between 0 and S, inclusive.
  • cities gives the locations of the cities. It contains 2 * NC elements, x and y coordinates of city i are given by elements 2*i and 2*i+1, respectively. All cities' locations are distinct. If a location is occupied by a city, you can not build a junction there.
  • junctionCost gives the cost of commissioning one junction.
  • failureProbability gives the probability of junction construction failing. The outcome of each construction is random and independent from the others, and does not depend on the junction location.
The return from buildJunctions is a list of junctions you want to commission. If you want to commission NJ junctions, the return must contain 2 * NJ elements, x and y coordinates of junction i given by elements 2*i and 2*i+1, respectively. You can build at most 2 * NC junctions. All junctions' locations must be distinct.

buildRoads(int[] junctionStatus) is called once (after buildJunctions) to give you the results of junctions building and to let you commission the roads. junctionStatus[i] is the result of building junction i in your return from buildJunctions: 1 if the junction was built successfully and can be used, and 0 otherwise.

The return from buildRoads is a list of roads you want to build. It must contain 2 * (number of roads) elements, endpoints of road i given by elements 2*i and 2*i+1, respectively. Each endpoint of a road is an index of a city or a junction; endpoint j represents a city with index j for 0 ≤ j ≤ (NC-1), and a junction with index j-NC for NCj ≤ (NC+NJ-1). The junctions are indexed in the same order as in your return from buildJunctions; junctions which failed construction are not excluded from indices, but can not be used as a road endpoint. For each road, its endpoints must be distinct. You can build at most one road per pair of cities/junctions. The roads are allowed to intersect each other in points other than their endpoints.

Note that every junction built successfully must also be connected to the road system together with the cities.

Scoring

Your score for an individual test case will be (the total length of the roads constructed) + junctionCost * NJ (regardless of how many of the junctions were built successfully). If your return was invalid (attempted to build invalid road or junction, left some cities unconnected etc.), the score for this test case will be -1.

Your overall score will be calculated in the following way: for each test case where your score is not -1, you will score (best/your)^2 for that test case, where best is the best score anyone achieved on that test, and your is your score for that test. Those values are then added, then multiplied by 1,000,000 and divided by the number of test cases.

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:RoadsAndJunctions
Method:buildJunctions
Parameters:int, int[], double, double
Returns:int[]
Method signature:int[] buildJunctions(int S, int[] cities, double junctionCost, double failureProbability)
 
Method:buildRoads
Parameters:int[]
Returns:int[]
Method signature:int[] buildRoads(int[] junctionStatus)
(be sure your methods are public)
    
 

Notes

-The time limit is 10 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. There will be 2000 test cases in the final testing.
-The match is rated.
 

Constraints

-The size of the map S will be between 100 and 1000, inclusive.
-The number of cities NC will be between 10 and 100, inclusive.
-The cost of building a junction junctionCost will be between 0.0 and 10.0.
-The probability of junction construction failure failureProbability will be between 0% and 40%.
 

Examples

0)
    
seed = 1
S = 100
Number of cities = 10
Junction cost = 0.0
Probability of junction construction failure = 0.0
Cities:
(71,1) (63,58) (17,38) (65,15) (81,74) (95,6) (74,18) (25,45) (12,71) (74,90) 
1)
    
seed = 2
S = 1000
Number of cities = 100
Junction cost = 10.0
Probability of junction construction failure = 0.4
2)
    
seed = 3
S = 681
Number of cities = 29
Junction cost = 1.1968317352293834
Probability of junction construction failure = 0.2194647825451892
3)
    
seed = 4
S = 651
Number of cities = 83
Junction cost = 1.7385606096367434
Probability of junction construction failure = 0.23425666795830125
4)
    
seed = 5
S = 203
Number of cities = 59
Junction cost = 0.4859863179985513
Probability of junction construction failure = 0.3188341206321255
5)
    
seed = 6
S = 159
Number of cities = 36
Junction cost = 6.191817381973387
Probability of junction construction failure = 0.13347629434298006
6)
    
seed = 7
S = 992
Number of cities = 54
Junction cost = 3.0583416639742445
Probability of junction construction failure = 0.2221344433650459
7)
    
seed = 8
S = 290
Number of cities = 30
Junction cost = 5.060138074110352
Probability of junction construction failure = 0.08338352751957268
8)
    
seed = 9
S = 352
Number of cities = 74
Junction cost = 8.319988363621652
Probability of junction construction failure = 0.3555567037630526
9)
    
seed = 10
S = 612
Number of cities = 41
Junction cost = 0.2140484489157679
Probability of junction construction failure = 0.3411403071218978

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.