Wildebeest

SRM 112 · 2002-09-06 · by dgoodman

Class Name: Wildebeest

Return Type: int

Method Name: ensquare

Arg Types: (int, vector<int>, vector<int>)

Problem Statement

The wildebeest grazing on the plain have to be trapped and innoculated against the rare disease wildebeestiosis. Here is our plan: we will simply drop a huge square enclosure from a helicopter, trapping as many as possible within the enclosure. Create a class Wildebeest that contains the method ensquare that takes the length of the enclosure's diagonal and the x and y coordinates of the wildebeest as inputs and returns the maximum number of wildebeest that we can trap.

The enclosure may be dropped anywhere on the plain, but (because of the prevailing winds) its diagonals will run north-south and east-west. If a wildebeest is exactly on the enclosure boundary it will be crushed to death -- don't count that as a successfully trapped wildebeest.

Notes

there may be more than one wildebeest at a particular location
each wildebeest has negligible size
the enclosure does not necessarily have its corners at integer coordinates

Constraints

diagonal is between 1 and 10,000 inclusive
x contains between 1 and 50 elements inclusive
y contains the same number of elements as x
each element in x is between -1,000,000 and 1,000,000 inclusive
each element in y is between -1,000,000 and 1,000,000 inclusive

Examples

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

| | | | | | | | | | | | | | | | 5 -+---+---w---+---+---+---+---+- -+---+---w---+---+---X---+---+- | | | | | | | | | | | | | X | X | | 4 -+---+---+---+---+---+---+---+- -+---+---+---+---X---+---X---+- | | | | | | | | | | | | X | | | X | 3 -W---+---+---+---w---w---w---+- ==> -W---+---+---X---w---w---w---X- | | | | | | | | | | | | X | | | X | 2 -+---+---+---+---+---+---+---+- -+---+---+---+---X---+---X---+- | | | | | | | | | | | | | X | X | | 1 -+---+---w---+---+---+---+---+- -+---+---w---+---+---X---+---+- | | | | | | | | | | | | | | | | 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 The picture on the left shows the 7 grazing wildebeest. 'w' denotes a wildebeest. 'W' indicates two wildebeest at the same location. We can trap the 3 side-by-side wildebeest by dropping the enclosure with its center at (6,3). Its corners will then be at (4,3) (6,1) (8,3) (6,5). This enclosure is shown in the picture on the right. An infinite number of placements will trap these 3 wildebeest (for example, put the center at 6.1,2.87). There is no other collection of 3 or more wildebeest that can be enclosed.

5
{1,3,5,3,1,6,7}
{3,1,3,5,3,3,3}
Returns: 5

The same picture applies to the wildebeest, but now our enclosure has a diagonal of 5. We can drop it with its center at (3,3) and trap all the wildebeest except for the rightmost 2. (If we had tried this placement when the diagonal was 4, we would have crushed 5 wildebeest and trapped none.)

6
{1,3,5,3,1,6,7}
{3,1,3,5,3,3,3}
Returns: 6

Now we can drop the enclosure with its center at (3.5,3) and trap all but the rightmost wildebeest.

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

Drop the enclosure over the two co-located wildebeest.

10000
{1,3,5,3,1,6,7}
{3,1,3,5,3,3,3}
Returns: 7

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

Coding Area

Language: C++17 · define a public class Wildebeest with a public method int ensquare(int diagonal, vector<int> x, vector<int> y) · 13 test cases · 2 s / 256 MB per case