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.
Your 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.
- maxPercentage gives you the maximum percentage of the total population that your selected area may contain.
- worldMap gives you the world map containing W columns and H rows. Each String contains a row of the map. Ocean is denoted by the '.' character and land by the 'X' character.
- totalPopulation gives you the total population on the entire given world map.
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:
- x1 <= x2 and y1 <= y2
- 0 <= x1,x2 < W
- 0 <= y1,y2 < H
Your 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 Generation
Please 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:
An 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.