TheSquareCityDiv2 | Topcoder Archive

Problem Statement

John and Brus have found a nice horizontal plane and they built a square city somewhere on the plane. The city has n rows and n columns of houses. More precisely, John and Brus built a house at each lattice point (x, y) such that 0 ≤ x, y < n.

The winter is coming. Different houses have different heating systems and thus the temperatures inside them are distinct. You are given the int[] t with n*n elements. The temperature inside the house at (x, y) is t[x*n + y] degrees.

Outside there is a lot of snow and the only paths in the snow are along coordinate axes. Thus, moving from the house at (x1, y1) to the house at (x2, y2) takes |x1 - x2| + |y1 - y2| minutes. Additionally, it's freezing outside, so a person can only stay outside for at most r consecutive minutes.

Initially there is exactly one person living in each house. Each person then repeats the following process: They find the warmest house they can reach in a single trip, and they move there. The people repeat the action until there is no warmer house within r minutes of travel from their current house.

Find two values:

a = the number of houses that will contain at least one person once everyone stops moving
b = the maximal number of people who will share the same house

Return a int[] with exactly two elements: {a, b}.

Definition

Class:: TheSquareCityDiv2
Method:: find
Parameters:: int, int[]
Returns:: int[]
Method signature:: int[] find(int r, int[] t)
(be sure your method is public)

Constraints

n will be between 1 and 20, inclusive.
r will be between 1 and 40, inclusive.
t will contain exactly n*n elements.
Each element of t will be between 1 and 1,000, inclusive.
All elements of t will be distinct.

Examples

```
1
```
```
{
9, 1, 6, 
5, 3, 2, 
7, 4, 8
}
```
```
Returns: {4, 4 }
```
There are nine houses in the city. We will identify them by the temperature inside. I.e., "house x" means "the house with temperature x inside". People from house 1 and house 5 will move to house 9 and stay there. The person from house 3 will first move to house 5 and then to house 9. People from house 2 and house 4 will move to house 8 and stay there. All other people (the ones who start in houses 6, 7, 8, and 9) will not move at all. In the end there will be 4 non-empty houses (houses 6 through 9) and the most occupied house will be house 9 with 4 inhabitants.
```
2
```
```
{
9, 1, 6, 
5, 3, 2, 
7, 4, 8
}
```
```
Returns: {2, 6 }
```
This is the same city but the people can stay outside for two minutes at a time. In the end, three people will end in house 8 and the other six will reach house 9.
```
7
```
```
{
9, 1, 6, 
5, 3, 2, 
7, 4, 8
}
```
```
Returns: {1, 9 }
```
Now since r is large everyone will move directly to house 9.

{
59, 22,  2, 17, 77, 43, 67, 
16, 49, 51, 46, 61,  4,  9, 
42, 12, 80, 82, 24, 29,  1, 
27, 63, 65, 26, 10, 28, 83, 
 7, 73,  8, 47, 37, 23, 38, 
75, 54, 71, 58, 78, 21, 45, 
35, 81, 48, 41, 44, 52, 32
}

Returns: {5, 20 }

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)2024, Topcoder, Inc. All rights reserved.