Statistics

Problem Statement for "RainbowSocks"

Problem Statement

You have a collection of socks of various colors. You are given a int[] socks that describes this collection: each element of socks is the color of one of the socks. You consider two socks to be acceptable as a pair if and only if the absolute value of difference of their colors is less than or equal equal to colorDiff.

In the morning you will choose two different socks from your collection uniformly at random. Compute and return the probability that the two random socks will form an acceptable pair.

Definition

Class:
RainbowSocks
Method:
getPairProb
Parameters:
int[], int
Returns:
double
Method signature:
double getPairProb(int[] socks, int colorDiff)
(be sure your method is public)

Notes

  • Each sock from your collection can be used on either foot.
  • Your return value must have an absolute or a relative error smaller than 1e-9.

Constraints

  • socks will contain between 2 and 50 elements, inclusive.
  • Each element of socks will be between 1 and 50, inclusive.
  • colorDiff will be between 0 and 49, inclusive.

Examples

  1. {1, 2, 3, 4, 5, 6, 7}

    7

    Returns: 1.0

    You are not particularly picky, so any pair of socks is acceptable.

  2. {1, 50, 50, 1}

    0

    Returns: 0.3333333333333333

    There are 6 ways to pick a pair of socks from this collection: one pair (1, 1), one pair (50, 50) and four different pairs (1, 50). Only the first two pairs are acceptable.

  3. {44, 14, 24, 31, 30, 32, 46, 23, 27, 2}

    24

    Returns: 0.8222222222222222

  4. {18, 3, 47, 34, 15, 29, 26, 6, 11, 13, 48, 49, 27, 31, 16, 42, 24, 17, 32, 12, 22, 9, 28, 36, 40, 10, 19, 38, 21, 1, 5, 33, 43, 30, 7, 45, 44, 23, 20, 39, 4, 2, 46, 25, 14, 35, 1, 41, 8, 37}

    0

    Returns: 8.163265306122449E-4

    Two 1 socks, the rest are all different

  5. {19, 4, 48, 35, 16, 30, 27, 7, 12, 14, 49, 38, 28, 32, 17, 43, 25, 18, 33, 13, 23, 10, 29, 37, 41, 11, 20, 39, 22, 2, 6, 34, 44, 31, 8, 46, 45, 24, 21, 40, 5, 3, 47, 26, 15, 36, 1, 42, 9}

    0

    Returns: 0.0

  6. {3, 1, 33, 41, 39, 21, 27, 7, 47, 9, 43, 15, 25, 13, 49, 29, 19, 17, 37, 11, 45, 5, 23, 31, 35}

    1

    Returns: 0.0

  7. {42, 50, 10, 22, 34, 6, 2, 18, 38, 14, 26, 46, 30}

    3

    Returns: 0.0

  8. {45, 10, 5, 35, 30, 50, 25, 20, 40, 15}

    4

    Returns: 0.0

  9. {1, 36, 33, 23, 49, 40, 9, 30, 18, 6, 44, 14, 27}

    2

    Returns: 0.0

  10. {42, 2, 12, 34, 8, 29, 46, 38, 18, 23, 50}

    3

    Returns: 0.0

  11. {17, 37}

    15

    Returns: 0.0

  12. {4, 45}

    41

    Returns: 1.0

  13. {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

    0

    Returns: 1.0

  14. {18, 12, 19, 23, 10, 11, 22, 17, 19, 2, 2, 17, 4, 3, 14, 20, 23, 24, 18, 21, 23, 7, 18, 8, 7, 19, 16, 17, 15, 23, 8, 2, 10, 20, 23, 18, 23, 14, 4, 11, 14, 4}

    22

    Returns: 1.0

  15. {30, 9, 26, 32, 6, 12, 26, 30, 8, 29, 15, 19, 31, 39, 9, 30, 32, 8, 31, 39, 32, 10}

    33

    Returns: 1.0

  16. {36, 24, 33, 38, 33, 24, 24, 32, 36, 42, 40, 38, 42, 31, 34, 35, 33, 41, 26, 38, 32, 32, 27, 23, 29, 33, 30, 36, 32, 43, 39}

    20

    Returns: 1.0

  17. {13, 30, 8, 9, 11, 16, 30, 29, 10, 21, 39, 16, 5, 44, 36, 33, 38, 46, 20, 14, 19, 45, 25, 27, 30}

    41

    Returns: 1.0

  18. {42, 27, 7, 23, 45, 5, 6, 44, 42, 24, 26, 42}

    5

    Returns: 0.2878787878787879

  19. {6, 32, 10, 4, 36, 9, 35, 35, 5, 39, 7, 5, 40, 3, 38, 34, 34, 32, 32, 1, 35, 8}

    9

    Returns: 0.4805194805194805

  20. {10, 11, 8, 8, 13, 11, 13, 13, 28, 26, 28}

    8

    Returns: 0.5636363636363636

  21. {45, 3, 41, 47, 42, 4, 27, 47, 3, 3, 42, 27, 7, 46, 44, 27, 4, 3, 46, 44, 28, 4, 7, 47, 28, 29, 43, 3}

    6

    Returns: 0.3333333333333333

  22. {9, 38, 32, 38, 12, 26, 11, 24, 47, 13, 21, 36, 27, 1, 21, 17, 37, 34, 31, 45, 26, 10, 12, 38, 1, 16, 30, 38, 1, 17, 1, 9, 4, 32}

    34

    Returns: 0.9233511586452763

  23. {9, 8, 42, 5, 21, 14, 42, 49, 14, 14, 16, 1, 47, 46, 45, 25, 7, 8, 12, 7, 24, 41, 46, 26, 9, 46, 36, 15, 27, 33, 31, 35, 40, 25, 42, 10, 38, 33, 11, 4, 47, 26, 6, 43, 23, 2, 17}

    21

    Returns: 0.635522664199815

  24. {29, 48, 46, 7, 30, 26, 44, 22, 2, 35, 33, 42, 17, 43, 45, 15}

    9

    Returns: 0.31666666666666665

  25. {8, 40, 3, 26, 21, 15, 6, 10, 1, 29, 44, 11, 10, 24, 9, 5, 31, 40, 32, 26, 13, 36, 10, 46, 27, 28, 38, 23, 43, 8, 26, 50, 49, 28, 27, 19, 42, 33, 30, 44, 13, 24}

    15

    Returns: 0.5121951219512195

  26. {49, 15, 30, 31, 6, 11, 6, 19, 48, 17, 14, 24, 45, 3, 48, 37, 12, 23, 38, 11, 2, 14, 31, 46, 48, 11, 39, 12}

    6

    Returns: 0.22486772486772486

  27. {35, 34, 9, 14, 15, 17, 27}

    22

    Returns: 0.9047619047619048

  28. {26, 39, 50, 50, 33, 4, 49, 21, 16, 22, 8, 26, 23, 23, 8, 18, 23, 18, 9, 36, 5, 3, 23, 39, 12, 38, 5, 30, 14, 28, 14, 40, 16, 15, 41, 50, 20, 41, 20}

    2

    Returns: 0.09986504723346828

  29. {29, 12, 37, 4, 20, 6}

    22

    Returns: 0.6666666666666666

  30. {14, 13, 44, 17, 35, 34, 30, 23, 40, 9, 38, 17, 24, 29, 35}

    10

    Returns: 0.45714285714285713

  31. {34, 7, 12, 6, 44, 23, 36, 5, 11}

    26

    Returns: 0.6944444444444444

  32. {17, 18, 15, 30, 31, 8, 48, 17, 41, 27, 39, 30, 35, 29, 46, 8, 9, 32, 47, 30, 16, 6, 41, 23, 49, 15, 8, 5}

    7

    Returns: 0.25132275132275134

  33. {31, 44, 16, 47, 25, 46, 4, 25, 15, 46, 1, 5, 25, 38, 33, 22, 47, 42, 4, 46, 23, 21, 1, 15, 43, 1, 31, 50, 7, 8, 50, 37, 3, 16, 33}

    20

    Returns: 0.5563025210084034

  34. {38, 4, 27, 33, 4, 32, 9, 43, 16}

    1

    Returns: 0.05555555555555555

  35. {9, 38, 37, 33, 8, 37, 47, 2, 39, 28, 3, 45, 37, 3, 34, 40, 18, 18, 19, 30, 6, 22, 9, 40, 27, 42, 1, 20, 7, 33, 11, 18, 20, 47}

    33

    Returns: 0.8805704099821747

  36. {30, 23, 18, 20, 40, 36, 3, 8, 27, 44, 7, 26, 3, 28}

    22

    Returns: 0.7472527472527473

  37. {26, 6, 23, 6, 11, 8, 15, 34, 8, 9, 11, 11, 6, 7, 35, 35, 31, 2, 6, 21, 39, 10, 30, 15, 6, 36, 42, 10, 15, 16, 24, 43, 21, 46, 48, 31, 3, 14, 16}

    13

    Returns: 0.5155195681511471

  38. {27, 21, 30, 33, 7, 16, 16, 8, 24, 36}

    8

    Returns: 0.37777777777777777

  39. {15, 12, 40, 2, 5, 49, 19, 20, 22, 11, 40, 17, 10}

    1

    Returns: 0.05128205128205128

  40. {25, 37, 33, 50, 13, 5, 29, 48, 11, 47, 13, 20, 22}

    7

    Returns: 0.20512820512820512

  41. {6, 14, 32, 46, 17, 36, 46, 35, 5, 18, 47, 46, 36, 8, 17, 9, 34, 3, 41, 34, 16}

    20

    Returns: 0.6047619047619047

  42. {15, 9, 10, 27, 30, 33, 26, 48, 39, 41, 29, 36, 9, 16, 31, 44, 20, 50, 42, 15, 36, 2, 31, 46, 35, 33, 38, 18, 50, 34, 32, 14, 42, 43, 42, 23, 26, 19, 20, 16, 9, 50, 1, 20, 15, 31, 13, 36, 33, 6}

    6

    Returns: 0.2506122448979592

  43. {7, 32, 15, 44, 16, 2, 11, 18, 37, 44, 31, 30, 37, 25, 2, 14, 43, 23, 29, 4, 22, 29, 23, 38, 11, 37, 23, 43, 42, 24, 14, 1, 7, 28, 46, 24, 31, 6, 41, 17, 50, 24, 46, 38, 48, 47}

    12

    Returns: 0.41642512077294686

  44. {19, 29, 45, 42, 9, 17, 31, 21, 3, 5, 14, 47, 30, 29, 49, 38, 7, 44, 12, 37, 1, 2}

    28

    Returns: 0.7575757575757576

  45. {25, 1, 39, 24, 48, 41, 16, 18, 21, 10, 12, 29, 27, 44}

    6

    Returns: 0.23076923076923078

  46. {49, 17, 29, 28, 45, 29, 16, 1, 22, 29, 40, 23, 32, 45, 26, 7, 45, 15, 32, 44, 7, 47, 12, 28, 7, 25, 8, 35, 18, 9, 15, 16, 25, 46, 46, 20, 24}

    8

    Returns: 0.31681681681681684

  47. {46, 41, 13, 20, 24, 7, 47, 32, 2, 11}

    30

    Returns: 0.7777777777777778

  48. {12, 39, 28, 36, 36, 20, 48, 7, 44, 5, 4, 25, 8, 16, 40, 4, 35, 2, 14, 33, 19, 47, 39, 23, 50, 5, 41, 19, 47, 6, 34, 9, 46, 14}

    22

    Returns: 0.6274509803921569

  49. {35, 43, 38, 30, 49, 41, 7, 8, 9, 46, 12, 43, 47, 27, 26, 18, 25, 16, 40, 25, 20, 32, 45, 16, 39, 30, 26, 34, 45, 21, 15, 30, 16, 5, 11, 14}

    23

    Returns: 0.765079365079365

  50. {38, 37, 6, 24, 31, 28, 38, 12, 43, 44, 23, 7, 41, 39, 30, 47}

    1

    Returns: 0.075

  51. {1, 1 }

    1

    Returns: 1.0

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: