Statistics

Problem Statement for "Wildebeest"

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.

Definition

Class:
Wildebeest
Method:
ensquare
Parameters:
int, int[], int[]
Returns:
int
Method signature:
int ensquare(int diagonal, int[] x, int[] y)
(be sure your method is public)

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

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

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

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

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

  5. 10000

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

    {3,1,3,5,3,3,3}

    Returns: 7

  6. 10000

    {-1000000}

    {-1000000}

    Returns: 1

  7. 7

    {0,2,4}

    {0,-5,3}

    Returns: 1

  8. 8

    {0,2,4}

    {500000,499995,500003}

    Returns: 2

  9. 400

    {700,700,700,700,700,600,600,600,500,800,800,800,900}

    {200,100,0,-100,-200,100,0,-100,0,100,0,-100,0}

    Returns: 8

  10. 401

    {700,700,700,700,700,600,600,600,500,800,800,800,900}

    {200,100,0,-100,-200,100,0,-100,0,100,0,-100,0}

    Returns: 13

  11. 10000

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}

    Returns: 50

  12. 10000

    {1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,14000,15000,16000,17000,18000,19000,20000,21000,22000,23000,24000,25000,26000,27000,28000,29000,30000,31000,32000,33000,34000,35000,36000,37000,38000,39000,40000,41000,42000,43000,44000,45000,46000,47000,48000,49000,50000}

    {1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,14000,15000,16000,17000,18000,19000,20000,21000,22000,23000,24000,25000,26000,27000,28000,29000,30000,31000,32000,33000,34000,35000,36000,37000,38000,39000,40000,41000,42000,43000,44000,45000,46000,47000,48000,49000,50000}

    Returns: 5

  13. 8000

    {1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,14000,15000,16000,17000,18000,19000,20000,21000,22000,23000,24000,25000,26000,27000,28000,29000,30000,31000,32000,33000,34000,35000,36000,37000,38000,39000,40000,41000,42000,43000,44000,45000,46000,47000,48000,49000,50000}

    {1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,14000,15000,16000,17000,18000,19000,20000,21000,22000,23000,24000,25000,26000,27000,28000,29000,30000,31000,32000,33000,34000,35000,36000,37000,38000,39000,40000,41000,42000,43000,44000,45000,46000,47000,48000,49000,50000}

    Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: