Connection Status:
Competition Arena > PairsOfHouses

PairsOfHouses

TCO20 Round 2A · 2020-04-13 · by misof

TCO20 Round 2A · 2020-04-13 · by misof · Geometry, Greedy, Math
Class Name: PairsOfHouses
Return Type: int[]
Method Name: design
Arg Types: (int)
Problem Statement

Problem Statement

A city is a rectangular array of buildings. For the purpose of this task, we will imagine each building as a vertical line segment of some height. If you have a city with R x C buildings, the bottoms of these buildings are the points (r, c, 0) with 0 ≤ r < R and 0 ≤ c < C.

The top point of each building contains a four-directional antenna. This antenna can be used to communicate with other buildings in the same row or column of the city. However, direct visibility is also necessary for communication: two buildings in the same row or column can communicate using their antennas if and only if the line segment that connects their tops does not touch or intersect any other buildings. In other words, the segment connecting the tops of those two buildings must go strictly above all the buildings between them.

You are given an int P. Design any city with the following properties:

  • Exactly P pairs of buildings can communicate.
  • The dimensions R, C of the city are both between 1 and 25, inclusive.
  • The height of each building is an integer between 1 and 999,999, inclusive.

Return the description of your city as a int[] with R*C + 2 elements: the dimensions of the city followed by the heights of all buildings in row major order. I.e., the return value should look as follows: {R, C, heights in row 0, heights in row 1, ... }.

Notes

  • For the given constraints a solution always exists. Any valid solution will be accepted.

Constraints

  • P will be between 0 and 15,000, inclusive.
Examples
0)
7
Returns: {1, 6, 1, 1, 2, 2, 3, 1 }

The example return value describes a city with 1 row and 6 columns of buildings. Seen from above, the city looks as follows (numbers are heights): 1 1 2 2 3 1 Seen from the side (numbers at the bottom are column numbers): | | | | | | | | | | 0 1 2 3 4 5 Each building can communicate with its neighbors. This gives us five pairs of communicating buildings. Additionally, buildings at (0,0) and (0,2) can communicate, and buildings at (0,2) and (0,4) can communicate. (Note that buildings at (0,0) and (0,4) cannot communicate, as the top of building at (0,2) is exactly on the line segment that connects the tops of the other two buildings.)

1)
30
Returns: {3, 5, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 }

The returned city has 3 rows and 5 columns of buildings. Seen from above it looks as follows: 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 There are 6 pairs of communicating buildings in row 0, 6 pairs in row 1, and 5 pairs in row 2. There are 2, 3, 3, 2, and 3 pairs of communicating buildings in the columns going left to right. Thus, the total number of communicating pairs is 6+6+5 + 2+3+3+2+3 = 30, as required.

2)
0
Returns: {1, 1, 1 }
3)
1
Returns: {1, 2, 1, 1 }
4)
2
Returns: {3, 1, 1, 1, 1 }

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

Coding Area

Language: C++17 · define a public class PairsOfHouses with a public method vector<int> design(int P) · 124 test cases · 2 s / 256 MB per case

Submitting as anonymous