Challenge Overview
Problem Statement | |||||||||||||
The world, and all the people that live in it, is represented as a rectangular grid, with a certain number of people living in each cell of the grid. For the sake of making pretty maps, you are working on finding areas of the world with population densities of particular interest. Initially you are given the map of the world's oceans and land in terms of grid units, and the total population of the world. People live only on land cells. Because of the wealth of research that various others have already done, it is possible to determine the population of any rectangular section of the world (without regard to the various densities within that region, or the exact population of any cell included in that region). In your quest to answer this question, you may issue any number of such queries. Of course, answering each query comes with a cost, and thus your goal is to balance the accuracy of your answer against the total number of queries you need to issue. Your task is to find the largest possible area of the world such that its total population does not exceed a given percentage of the world's total population, using the least amount of queries. Implementation DetailsYour code should implement the method mapPopulation(int maxPercentage, String[] worldMap, int totalPopulation). Your mapPopulation method will be called once and should return a String[] containing your selected area.
You must return a String[] containing your selected area. The size of your return must be the same as the input worldMap. Each String contains a row of the map. Each cell that you want to select must contain the 'X' character, otherwise unselected cells must contain the '.' character. You can call the queryRegion(int x1, int y1, int x2, int y2) method to get the population size within a specific rectangular region. (x1,y1) specifies the lower left corner and (x2,y2) the upper right corner of the rectangular region. Coordinates are inclusive. A row is specified by y1 and y2. A column is specified by x1 and x2. The method will return an int containing the population size within the region. The following rules apply:
ScoringYour raw score for each test case will be the total land area you selected, multiplied by 0.996 for each query you issued. In other words, your raw score will be: Raw score = (Total land area selected) * (0.996 ^ (Number of queries)) If the area selected contains a total population larger than the target percentage, your score for the test case will be 0. Any queries issued that go outside the bounds of the world, will return a value of -1, and result in failing the test case. Your overall score will use relative scoring, calculated as Sum(yours/best), where yours is your raw score and best is the highest raw score anyone achieved for that test case. The final score will be divided by the number of test cases, and scaled to 1,000,000. 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. Test Case GenerationPlease look at the visualizer source code for the exact details about test case generation. The world size W and H is randomly selected between 50 and 500. The world is filled with ocean and land. A number of cities between 5 and 5+((W+H)/100) is chosen and the population spread to be more dense near cities. Example map below: 
ToolsAn offline tester/visualizer 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, simulation and score calculation. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | The first few examples have artificially small size limits, to help facilitate basic testing and for illustrative purposes. | ||||||||||||
| - | 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) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
| 5) | |||||||||||||
| |||||||||||||
| 6) | |||||||||||||
| |||||||||||||
| 7) | |||||||||||||
| |||||||||||||
| 8) | |||||||||||||
| |||||||||||||
| 9) | |||||||||||||
| |||||||||||||
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.