|
Project Information
Links
|
You have just been hired by a cartography company, and your first task is to help them with a map they are trying to make. The owner of the company thinks it should always be possible to color a map using only four colors (such that no touching states have the same color), but so far they have been unable to do so with the map of Familyland. This is quite important to him, as he can print maps using four colors of ink for only $0.00001 per square millimeter. Each additional ink, however, has a base cost of $N/100 and a usage cost of $N/100000 per square millimeter (where N is the number of the ink, so N=5 is the first ink that is more expensive). The company will be printing 100mm x 100mm maps of Familyland, so you can see that the costs will add up quickly if many additional inks are needed. If the map can be made with only 4 inks, it will cost only $0.10 each to make, but if a 5th ink were needed, even on only 1 square millimeter of the map, the cost would rise to $0.15004 (note that you still only pay $0.00001/mm^2 for the first four inks). The problem with this particular map is that the country of Familyland has a representative government, but the citizens would not put up with anyone but a family member being their representative. To deal with this, Familyland declared each family to be its own state. Since not all family members live next to one another, the states are not contiguous. Of course, in making the map, each state must be entirely one color. If you want to keep your new job, you will need to come up with a coloring of the map such that it can be printed as cheaply as possible. Your score on each test case will be the cost in dollars of printing the map using the coloring you return. Your total score (the one displayed in the division summary) will be the sum over all testcases of the lowest cost anyone has achieved for the case divided by your cost for the case. In the unlikely event of a true tie (as computed using high precision numerics), the competitor with the lowest total runtime on all cases will be declared the winner. You will be given the area of each state (in square millimeters in map scale), and an adjacency matrix where character i of string j is '1' if states i and j are adjacent and '0' if they are not. Character i of string i will always be '0'. You must return an ink color for each state such that no two adjacent states have the same color. In the event that your returned coloring is invalid (you return a different number of colors than there are states, or you color two adjacent states the same), or your program exceeds the 30 second time limit, you will receive a 0 on the case. The test cases will be generated as follows (unless otherwise stated, all random choices are uniform and independent and ranges are inclusive): 1. The number of states (S) will be randomly chosen between 10 and 500. 2. The number of properties will be randomly chosen between S and 4*S. 3. For the first S properties, a random x and y will be chosen between 0 and 99 (assuring that no two properties are at the same location). The pixel at the x and y coordinate on the 100x100 map is marked as belonging to the ith state. 4. Each remaining property is placed on the map in the same manner, except that a random state between 0 and S-1 is assigned to the x and y coordinate on the map. 5. The remaining map pixels are assigned to states by randomly picking an unassigned map pixel that borders an assigned pixel, randomly choosing one of the assigned pixels that borders it, and assigning that pixel's state to the unassigned pixel. This process continues until the map is filled. 6. The adjacency matrix and the array of state areas are constructed from this map. Notes - The time limit for each test case is 30 seconds. - There are 50 non-example test cases. - The memory limit is 1GB, and the thread limit is 32. - There will be between 10 and 500 states inclusive. (chosen uniformly) - Returned colors must all be >= 1. - To facilitate testing, the values of S and P were not chosen randomly for example cases 0 through 3. Examples 0) 10 states, 10 properties Areas: 1477, 538, 1429, 1106, 381, 685, 1605, 224, 1807, 748 Adjacency Matrix: 0000011010 0000000111 0000101000 0000011000 0010001101 1001001000 1011110011 0100100001 1100001001 0100101110 |
|