Connection Status:
Competition Arena > BestView

BestView

SRM 436 · 2009-03-11 · by Gluk

SRM 436 · 2009-03-11 · by Gluk · Math
Class Name: BestView
Return Type: int
Method Name: numberOfBuildings
Arg Types: (vector<int>)
Problem Statement

Problem Statement

There are several skyscrapers arranged in a row. You're interested in finding the one from which the maximal number of other skyscrapers can be seen. The i-th skyscraper can be represented as a line segment on a plane with endpoints (i, 0) and (i, heights[i]). A skyscraper can be seen from the roof of another skyscraper if a line segment connecting their roofs does not intersect with or touch any other skyscraper. Return the maximal number of other skyscrapers that can be seen from the roof of some skyscraper.

Constraints

  • heights will contain between 1 and 50 elements, inclusive.
  • Each element of heights will be between 1 and 1,000,000,000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{10}
Returns: 0

There's only a single skyscraper, so you can see no other skyscrapers from its roof.

1)
{5,5,5,5}
Returns: 2

From each skyscraper, you can only see its adjacent neighbors.

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

You can see all the other skyscrapers from the central one.

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

You can see seven skyscrapers from the skyscraper with height 7:

4)
{351,239,157,185,452,129,101,173,78,81}
Returns: 8
64)
{1000000000,999999999,999999998,999999997,999999996,1,2,3,4,5}
Returns: 6

You can see 6 skyscrapers from the skyscraper with height 999999996 - the nearest one to the left and all 5 skyscrapers to the right.

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

Coding Area

Language: C++17 · define a public class BestView with a public method int numberOfBuildings(vector<int> heights) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous