Skyscrapers
SRM 395 · 2008-03-26 · by connect4
Problem Statement
The skyline of the city of Terrapin City has N buildings all in a straight line; each building has a distinct height between 1 and N, inclusive. The building at index i is considered visible from the left is there is no building with a smaller index that is taller (formally, height[j] < height[i] for all j < i). Similarly, a building is visible from the right if there is no taller building with a higher index (height[j] < height[i] for all j > i). For example, if the buildings in order are {1, 3, 5, 2, 4}, then three buildings are visible from the left (1, 3 and 5), but only two are visible from the right (4 and 5).
You will be given N, leftSide and rightSide, corresponding to the total number of buildings, the buildings visible from the left, and the buildings visible from the right, respectively. Return the number of permutations of the buildings that are consistent with these values; as this can be a large number, you should return it modulo 1000000007.
Constraints
- N will be between 1 and 100, inclusive.
- leftSide and rightSide will be between 1 and N, inclusive.
3 2 2 Returns: 2
There are two arrangements of buildings that match these requirements: {1, 3, 2} and {2, 3, 1}.
3 2 1 Returns: 1
Only {2, 1, 3} fits these requirements.
5 3 2 Returns: 18
100 2 1 Returns: 990953332
100 13 21 Returns: 492729563
12 1 1 Returns: 0
With 12 buildings, it is impossible for you to only see one building from each side.
1 1 1 Returns: 1
Minimum N.
77 6 10 Returns: 999993982
Maximal return value
Submissions are judged against all 75 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Skyscrapers with a public method int buildingCount(int N, int leftSide, int rightSide) · 75 test cases · 2 s / 256 MB per case