JOIN
 Problem Statement
Contest: Marathon Match 87
Problem: PopulationMapping

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 Details

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

Scoring

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:

Tools

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.

Definition

 Class: PopulationMapping Method: mapPopulation Parameters: int, String[], int Returns: String[] Method signature: String[] mapPopulation(int maxPercentage, String[] worldMap, int totalPopulation) (be sure your method is public)

Available Libraries

Class:Population
Method:queryRegion
Parameters:int, int, int, int
Returns:int
Sample Call:val = Population.queryRegion(x1, y1, x2, y2);

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)

```Seed = 0
Width = 50
Height = 50
Total Population = 170099
Target = 30%
Land Area = 697
...........XXXX.....X......XX......X..............
..........XXXXX...................XX..............
..................................XX..............
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..............................................X...
.............................................X..XX
..................X..X..XX..................XXXXXX
X.................XX.X.X.XX.XXX.............XXXX.X
...................XXXXXXXXXX.X............XXXXX..
..................X..XXXXXXX.X..............XXXX.X
...................XX.XXXXXXX...............XXXXX.
...................XXXXXXXXXXXX..............X.XXX
...................XXXXXXXXXXXX.X...........XXX.XX
X...................XXXXXXXXX.XX.............XXX.X
XX................XXX.X.XXXXXX...............XX...
.X..................X..XXXXXXX...............X.X..
.................X..X...X.X..X..............X.....
..................XXX....X.XXX..............X.....
..........X.......XXXX.....XXXX...................
...........XX.....XXX.......XXXX..................
............X.....XX.........XX.XX..........XX....
...X.XX....XX.X................X.XX.........XX....
....XXXX..XXXX..................XX..........X.....
....XXXXX.X.X..............XX.X.XX...........X....
....XXXX.XX.XXX.............XX.X.X..............XX
.....XX.....X...............X...X..........X....XX
.....XXX..........X.X...X.............X.....XX.X.X
..................XXX.X...XXX.X......X......X.XX..
....................XXX...XX.XX........X...XXX...X
....................XX.XXX..X.X........XX..XXX.XXX
.............XXXX....XXXXXX.XX....X....XX.XXXXXXXX
..............XXXXX.X.XXXXXX.X..XXXXXXXXXXX.XXXXXX
...............XX.XXXXXXXXXXX...XXXXXXXXXXXXXXXXX.
.................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
................X.XXXXXXXXXXXXXXXXXXXXXXXXXXXX..XX
.............X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXX
..............X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.XX
X..................XXXXXXXXXXXXXXXXXXXXXXXXX....XX
.....................XXXXXXXXXXXXXXXXXXXXXX.X....X
..........X.X.XX.....XXXXXXXXXXXXXXXXXXXXXXX....XX
....X...XXXX.XX.X..X.XX.XXXXXXXXXXXXXXXXX.X......X
..........X.X......XXXXXXXXXXXXXXXXXXXXXXX.XXXXXXX
.........X.........X.XX....XXXXXXXXXXXXXXXXXXXX.X.
```
1)

```Seed = 1
Width = 60
Height = 60
Total Population = 310037
Target = 20%
Land Area = 1859
...XXXXXXXXX.................X.X......XXXXXXXXXXX.XX...X.X..
.XXXXXXXXX.X........................XX.XXXXXXXXXX.X...X.X...
..XXXXX................X.........XXXX.XXXXXXXXXX...X.XX.....
XX.XX.X...................X....X...XX..XXXXXXXX.............
XXXX.X......X............X.XXX..........XXXXXXXX............
X....X....X.X.............XXXXXXX......XXXXXXXXX............
.X........X............XXXXXXXXX.......XX.XXXXXX............
.....X.........X.X...X...XXXXXX.X..X.X.XXX.XXXXXX...........
...X.XX...XX...XX.XX.XXXXXXXXXXXXX.XXXXXXXXXXXXXX...........
....XX.....X..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...........
...X......X...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X..........
....XXX.....XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............
....XX.......XX.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXX....X......X
.............XX..X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXX..X...
XXX..X........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXX....XX
XX.............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXX..XXXX
XX...........XXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX..........XX
.X............XX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X...X....XX
X.X...........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..X..XX.XX
XXXX......X..X...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....XX
XX.........XX..X..XX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XX.XXXX
.XX.......X...........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXX
.............X.......XXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXXXX..X
...........XX.X.XXXXXXXXXXXXXXXXXXXXXX..XX..XXXXXXXXXXXXX...
.............XX..X..XXXXXXXXXXXXXXXXXX...X.XXXXXXXXXXXXX....
...............XXXXXXXXXXXXXXXXXXXXXX.X.X.XXXXXXXXXXXXXX....
..............X...XXXXXXXXXXXXXXXXX.X...XX..XXXXXXXXXXXXX..X
X..................XXXXXXXXXXXXXXXX.......XXX.XXXXXXXXXXX.XX
...................XXXXXXXXXXXXXXXXXX....XXX....XXXXXXXXX.XX
...................XXXXXXXXXX.XXXXX......X.X.....XXXXXXXXXXX
...................XXXXXXXXX.XXXXX.X......X......XXXXXXXX.XX
...................XXXXXXXX....XX.X..............XXXXXXXXXXX
....................XXXXXXXX...X.X.......X..X...XXXXXXXXXXXX
X..................X.XXXXXX.X...............X.....XXXXX.XXXX
..................XXXXXXXXXXX.....................XXXXXXXXXX
...................XXXXXXXXX...................X...XXXXXXXXX
..................XX.XXXXX...X......................XXXXXXXX
....................XXXXX.........X.................XXXX...X
.................X.XXXXXXXX.X....X.X.........X.X....XXXXXX..
.................X.XXXXXXXXX.....X.XX........X..X....XXXX...
..............XXX.XXXXXXXXX.................XXXX....XXXX....
..............XXX.X..XXXXXX...XXXX...........XXX............
..............XXX..XXXXXXXXXXXXXXXXX.X......X.XXX.X......X..
......X.X....XXXX.XXXXXXXXXXXXXXXX.........X.XXXXXXXX..X....
......X.......XXXXXXXXXXXXXXXXXXX...XX.....XXXXXXXX..X...X..
.....X.XXX...XXX.XX.XXX...XXX.XX.........X.XXXXXXX.XXXXX....
.....XXXXX.XXXXX.X...X.XX.X...XX............XXXX...XXXXX....
...XXXXXXXXXXXX.X..XXX.XXX....X..............XXXX.X...XX...X
......XXXXXXXXXXXXXXXXX.XXX.X.XXX..........XXXXXX.......X.XX
......XXXXXXXXXXXXXXXXXXXXXXXXXXXXX......X.XXXXXXX...XX.XXXX
X.......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXXXX.X..XX...XX..
.XX.......XXX.XXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXX.....XX.
...........XXXX..XXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXX.X.XXXXXXX.
............XXX...XXXXXXXXXXXXXXXXXXX..X.XXXXXXXX.XXXXXXXXXX
X............X.XX.XXXXXXXXXXXX...XXXX.XXXXXXXXXXXX..XXXXXXXX
XXX...........XXXXXXX.XXXXXXX.....XXXX.XXXXXXXXXXXX.XXXXXXXX
X.............X.....XXXXX..XXXXXX.XXXXX.XXXXXXXXXXX.XXXXXXXX
......X..............XXXX..X.XXX.XXXXXXX..XXXXX.XXXXXXXXX.XX
X............................XXXXXXX.XXX.XXX.X.XX..XXXX.XXXX
..X.............X............XXXXXXX.X.XXXXX....X..XXX..XXXX
```
2)

```Seed = 2
Width = 70
Height = 70
Total Population = 378706
Target = 44%
Land Area = 1853
X............XXXXXXXXXX.XXXXXXX....X.......X..XXXX.......X...XXX......
.............XXXXXXXXXXXX.XXXXX.XX..XXX......X.XXXXXX..X.....XXX.X....
X..............XXXXXXXXXX.XXXX...X..XX........XX.....X.......XX.XXX...
XXX............X.XXX..XXX..X.X..X...XX.X........XXX...X.....XX..XX....
XX............X..XXXX..X........X..X............XX.XX.......XXX..X....
..................X.X................XXX....X.XX.X.X.....X............
....................................XX..XXX.XXXXX..X..................
...................................XXXXXXXX.XXXX.....X....XX..........
X.X...............................XXXXXXXXX..XXXX........X..X.........
X.X............................XXXXXXXXXXX.XXXX.......XX..X...........
.X............................X.XXXXXXXXXX.XXXXXXXX...XX..............
...........................XXXXXXXXXXXXXXXXXXX..XX....................
...........................XXXXXXXXXXXXXXXXXXXX.XXX..............X....
...........................XXXXXXXXXXXXXXXXX.XX..X....X...............
............................XX...XXX.XXXXXX..X..XXX...................
...............................XXX..XXXXX.X...XXXX.............X......
.....................................X.X.X....X.XXX........X..........
X....................................XXXX.......XXX.X.................
.X.....................................X.XXX.X..XX....................
X...............................X...X..XXXX.X..XXX....................
.............................XX......XX.XXX...........................
.............................XXXXXX.XXXXXXX.........XXXX.X.......X....
................................XXX.XXXX.X....XX....XXXXX.X...........
X...........................X.XXXXXXXX.XXX..XX.XX...XXXX.XX...........
............................XX..XXXXXXXXXXXXXXXXX..XXXXXXX.........X..
X..........................X..XXXXXXXXXXXXXXXXXXXXXXXXXXX.XX..........
XX........................X.XXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXX..X.X...
.X..........................X..XXXXXXXXXXXXXXXXXXXX.XXXXXXXXX...XX....
XXX.......................X.XXXXXXXXXXXXXXXXXXXXX.XXXXXXXXXXX....XX...
XX.........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXX..X.
X............................XXXXXXXXXXXXXXXXXX.XXXXXXXXXXXXXXXXXXX.XX
XXXX........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.XX..XXX..
XXX.X......................XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.X.....
..X......................X..X.XXXXXXXXXXXXXXXX.XXXX.XXXXXXX...........
X..X.......................XX.XXXXXXXXXXXXXXX.X.XXXXXX.X.XXX..........
..............................XXXXXXXXXXXXXXX....XXXXXXXXX.......X...X
..............................XXXXXXXXXXXXXXX...XXXXXXX.XX............
X............................X..XXXXXXXXXXXXX.X.XXXXXXXXXXXXX......X..
..............................XX...XXXXXXXXXXX..XXXXXXX.XXXXX.....XXX.
......X.....................XXXX..XXXXXXXXXX.X..XXXXXXXXXXXX.XXX..X.X.
.....X.......................XXXXXXXXXXXX.......XX..XXXXXXXXXXXX...X..
X....XXXX....................XXXXXXXXXXXXXX.....XXXXXXXXXXXXXXXXX.XX..
..XX...XX.................X.XX.XXXXXXXXXXX.X....XXXXXXXXXXXXXXXXX.X.X.
.X.....XXXX................X..XXXXXXXXXXXXX.X...XXXXXXX.XXX.XXXXXXXXX.
......XXX.................X....XXXXXXXXXXXX.....XXXXXXXXXXXXX.XXX.X..X
.....XXX.......................XXXXXXXXXXXXX......XXXX..XXXXXXX.X....X
.X.............................XXXXXXXXXXXX.........XXXXXXXXXX..X....X
..X.X.X........................X.XXXXXX.XXXX.........X..XXX.XX..XX...X
..................................XXXXXXXXXXX.XX.......XXXXX.X......X.
............................X..X.....XXXXXX..XXX...X..X.XX.X.X.....X..
.X.........X..X........................XXXXXXXXX......XXX....X........
X.XX.........XX.....X..............X....XXXXXXX....XXXXX.X.XXXXX.X..X.
..XX........X........................XX.XXXXXXXXX.X..X.X.....X.......X
XXXXXX.............X......X..........XXX.XXXXXX.X.XX.XXXX....X.X......
.XXXXXX.X..........X.X................XXXXXXX....X...X.X.......X..XX..
XX.XXXX.X........XXXXXX......X.......X.XXXXXX.XX.........X...X....XX..
X.X..XX...........X...................XXXXXXXXX..XX.X.XXX...XXXXX..X..
X......................................X.XXXXXXXXXXXX.XX.....XXXXXXX..
X..................XX.XXX.......X.X.....XXXXXXXXXXXXXXXXXX.XXXXXXXX...
............XXX....XXXXXX......X.......XXXXXXXXXX...XXXXXXXXX.X.X.X...
....................XXXXXX...X.......XXXXX..XXXXXXX.XXXXXXX..XXX.X....
.....................XXXXX.XX.XX....XXXXX.XXXX.XX.XXXXX.XX..X.XX......
.........XX........X..XXXX.XX..X..X.XXXX....X.X..X.XXXXX.XX....X..X...
XX.....X.XX........X.XXXXXX.....XXXXXXXXX...X.....XXXX.XXXXX.X..X.X...
.X...................XX...XX.X..XXXXXXXX.XXXX.....XXXX.XXXXXXXX.XX..XX
X........................XXXX..X.XXXXXXX..XXXX.XXXXXX.XXXXXXXXX..XXXX.
...................X......XXXXXXXXXXXXX.X.XXXXXXXX..XXXXXXXXXXXXXX..XX
.X..X..............X..X...XXXXXXXXXXXXXXX.XXXXXXXX.X.XXX.XX.X.X.XXX.XX
....................XX.XXXXXXXXXXXXXXXXXXXXXXXXXXX.XXXX.XXXXXXXXXXX.XX
..X................X.XXXXXXXXXXX.XXXXXXXXX.XXX...XXXXXXXXXX.XXXXXXX.X.
```
3)

```Seed = 3
Width = 78
Height = 142
Total Population = 442930
Target = 8%
Land Area = 1985
```
4)

```Seed = 4
Width = 189
Height = 414
Total Population = 5315367
Target = 32%
Land Area = 16429
```
5)

```Seed = 5
Width = 391
Height = 183
Total Population = 9526812
Target = 40%
Land Area = 28554
```
6)

```Seed = 6
Width = 235
Height = 388
Total Population = 1716922
Target = 15%
Land Area = 3057
```
7)

```Seed = 7
Width = 437
Height = 401
Total Population = 19856833
Target = 37%
Land Area = 68093
```
8)

```Seed = 8
Width = 97
Height = 222
Total Population = 562170
Target = 33%
Land Area = 1316
```
9)

```Seed = 9
Width = 299
Height = 442
Total Population = 4296479
Target = 62%
Land Area = 12836
```

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.