Statistics

Problem Statement for "ThePhantomMenace"

Problem Statement

Obi Wan Kenobi and Qui-Gon Jinn are trying to escape from the Federation to find Queen Amidala. They are currently trapped inside a building and they have to escape through one of the doors.

All doors are on the same side of the building. You are given the coordinate of each door in the int[] doors. The doors are protected by some droids. Currently, all those droids are standing next to the wall with the doors. You are given the coordinates of the droids in the int[] droids.

Our two heroes prefer a door that is as far as possible from all the droids. For example, suppose that the doors are at positions { 2, 5, 8 } and that there are two droids: one at position 1 and the other at position 10. The optimal door for the escape would be the door at position 5. For this door, the two droids are 4 and 5 units of distance away from the door. Hence, the closest droid is 4 units of distance away from the door. Each of the other two doors is closer than that to one of the droids.

Formally, the safety level of a door is equal to the distance between the door and the droid that is closest to that door. Compute the safety levels of all doors and return the maximum of those safety levels.

Definition

Class:
ThePhantomMenace
Method:
find
Parameters:
int[], int[]
Returns:
int
Method signature:
int find(int[] doors, int[] droids)
(be sure your method is public)

Notes

  • The distance between a door at coordinate x and a droid at coordinate y is |x-y|, that is, the absolute value of the difference between x and y.

Constraints

  • doors will contain between 1 and 10 elements.
  • droids will contain between 1 and 10 elements.
  • Each element of doors will be between 0 and 100 inclusive.
  • Each element of droids will be between 0 and 100 inclusive.
  • No number will appear more than once in the concatenation of doors and droids

Examples

  1. {1,2,3,4}

    {5,6,7,8}

    Returns: 4

    There are four doors located at {1,2,3,4} and four droids located at {5,6,7,8}. The safety level of the door at position 1 can be computed as follows: Droid at position 5 is |5-1| = 4 units of distance away from this door. Droid at position 6 is |6-1| = 5 units of distance away from this door. Droid at position 7 is |7-1| = 6 units of distance away from this door. Droid at position 8 is |8-1| = 7 units of distance away from this door. Thus, the closest droid to our door is the one at position 5, and the safety level of our door is 4. The other three doors have safety levels equal to 3, 2, and 1, respectively. Thus, the best choice for the escape is the door at position 1. The correct return value (i.e., the largest of all safety levels) is 4.

  2. {1}

    {10}

    Returns: 9

    When there's only one candidate, there's only one choice.

  3. {2,3,5,7,11}

    {1,8,13}

    Returns: 3

    If you use door at position 2, then you are at distance 1 from droid 1. If you use door at position 3, then you are at distance 2 from droid 1. If you use door at position 5, then you are at distance 3 from droid 2. If you use door at position 7, then you are at distance 1 from droid 2. If you use door at position 11, then you are at distance 2 from droid 3. So all doors have droids at 3 or less units of distance. If you choose door at position 5 you have droids at distances 4, 3 and 8 so that's the best choice.

  4. {1,3,5,7,9,11,13,15,17,19}

    {2,4,6,8,10,12,14,16,18,20}

    Returns: 1

    Every door is a possible choice for this test case.

  5. {2,1}

    {4,3}

    Returns: 2

    Be careful! The input isn't always sorted.

  6. {0}

    {100}

    Returns: 100

  7. {100}

    {0}

    Returns: 100

  8. {54,12,52,56}

    {8,30,44,94,39,65,19}

    Returns: 10

  9. {1,5,89,34}

    {25,58,20,51,38,65,30}

    Returns: 24

  10. {10,51,18,43}

    {71,97,61,26,5,57,70,65}

    Returns: 14

  11. {29,86,93,87}

    {64,75}

    Returns: 35

  12. {100,7,40,37}

    {38,36,44,24,46,95,43}

    Returns: 17

  13. {5,15,58,77,72,95,8,38}

    {69,37,24,27,90,92,31}

    Returns: 19

  14. {30,37,86,33,76,21,77,100,68}

    {8,22,69,81,38,94,57}

    Returns: 8

  15. {65,14,89,69,4,16}

    {24}

    Returns: 65

  16. {21,78,53}

    {17,81,39}

    Returns: 14

  17. {60,93,89,94,30,97,16,65,43,20}

    {24,67,62,78,98}

    Returns: 19

  18. {32,46,49,57,60,56,44}

    {37,75,62,17,13,11}

    Returns: 12

  19. {4,95,100,0,57,82}

    {31}

    Returns: 69

  20. {56,67}

    {30,100,64,72,66,63}

    Returns: 7

  21. {19,44,2,63,81}

    {78,91,64,70,97}

    Returns: 62

  22. {97,39,21,78,70,46,25,54}

    {76,92,84,47,57,31,38,75,40}

    Returns: 10

  23. {84,51,86,41}

    {19,21,37,58,100,97,73,44,67}

    Returns: 11

  24. {58}

    {13,31,49,63,44,73,76,77,16,83}

    Returns: 5

  25. {67,51,56,7,36,77,10,95}

    {28,57,0,54,23,60}

    Returns: 35

  26. {39,40}

    {97}

    Returns: 58

  27. {35,44,25,11,83,8,61}

    {12,27,100,34,0}

    Returns: 27

  28. {10,96,39}

    {87,53,5,40,42,66,15,90,71,55}

    Returns: 6

  29. {5,88}

    {49,97,100,32,4,60,81,83,53,80}

    Returns: 5

  30. {14,94,29,77,99}

    {16,3,22,71,35,4,61}

    Returns: 28

  31. {13,11,30,0,27,94,66}

    {25}

    Returns: 69

  32. {5,47,44,85,29,63,65,89,59,41}

    {87,36,57,7,92,33,34,64,76,55}

    Returns: 8

  33. {48,46,27,12,37,99}

    {25,83,20,77,13,9}

    Returns: 23

  34. {62,76,57,18,72,64,10}

    {4,74,63}

    Returns: 14

  35. {18,91,84,32,36,77,10,39,75,35}

    {87,23,22,30,37}

    Returns: 12

  36. {58,59}

    {7,14,78}

    Returns: 20

  37. {54,83,8,94,12,86,9,97,42}

    {93,95,44,70,5,10,40,36,34}

    Returns: 10

  38. {0,100}

    {50}

    Returns: 50

  39. {50}

    {0,100}

    Returns: 50

  40. {0 }

    {1 }

    Returns: 1

  41. {2, 1 }

    {4, 3 }

    Returns: 2

  42. {1, 2, 3, 4 }

    {5, 6, 7, 8 }

    Returns: 4

  43. {1, 10 }

    {2, 3 }

    Returns: 7

  44. {3 }

    {4 }

    Returns: 1

  45. {1, 2, 3 }

    {4, 5, 6, 7, 8 }

    Returns: 3

  46. {5, 6, 7, 8 }

    {1, 2, 3, 4 }

    Returns: 4

  47. {10 }

    {1 }

    Returns: 9

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: