Connection Status:
Competition Arena > TheSquareCityDiv2

TheSquareCityDiv2

SRM 734 · 2018-05-16 · by Vasyl[alphacom]

SRM 734 · 2018-05-16 · by Vasyl[alphacom] · Simulation
Class Name: TheSquareCityDiv2
Return Type: int[]
Method Name: find
Arg Types: (int, vector<int>)
Problem Statement

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}.

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
0)
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.

1)
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.

2)
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.

3)
3
{
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 }
4)
1
{34}
Returns: {1, 1 }

Submissions are judged against all 48 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheSquareCityDiv2 with a public method vector<int> find(int r, vector<int> t) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous