Statistics

Problem Statement for "ProbabilisticStreamMinimum"

Problem Statement

N elements are going to appear on an input stream. The elements are all comparable, the comparisons are transitive, and the elements are distinct. Hence, the elements have a unique sorted order.

We would like to select the K smallest of these elements.


We are going to do this using a randomized algorithm. We will take K^2 buckets. Each time we process an element, we will assign it a bucket uniformly at random. If the bucket is empty, the element is placed into the bucket. If the bucket already contains another item, we compare the two and keep the smaller one. After processing the entire stream, we pool the items from all buckets and select the K smallest among them.

You do not know anything about the order in which the N items will appear in the input. In particular, it is not guaranteed that they will be in a random order.


Given N and K, calculate the worst-case probability of the above algorithm returning the correct answer.

(That is, imagine that for each possible order of the N items in the input stream we have calculated the probability of the algorithm giving the right answer. You should return the minimum of all those probabilities.)

Definition

Class:
ProbabilisticStreamMinimum
Method:
calculate
Parameters:
int, int
Returns:
double
Method signature:
double calculate(int N, int K)
(be sure your method is public)

Notes

  • As usual, assume that all random choices made by the algorithm are mutually independent.
  • Your answer will be accepted if it has an absolute error not exceeding 1e-9.

Constraints

  • N will be between 1 and 10^6, inclusive.
  • K will be between 1 and min( N, 100 ), inclusive.

Examples

  1. 47

    1

    Returns: 1.0

    The algorithm is guaranteed to work. The minimum element will end in one of the buckets.

  2. 3

    3

    Returns: 0.691358024691358

  3. 20

    4

    Returns: 0.66650390625

    One possible execution of the algorithm starts as follows: An item of size 14576 arrives and it is placed into an empty bucket #13. An item of size 54245 arrives and it is placed into an empty bucket #7. An item of size 81234 arrives and again bucket #7 is chosen. As this item is bigger than the one already in bucket #7, we discard it. Bucket #7 still contains the item of size 54245. An item of size 9127 arrives and it is placed into an empty bucket #2. An item of size 23 arrives and again bucket #13 is chosen. As this item is smaller than the one in the bucket, we discard the item of size 14576 and instead we place the item of size 23 into bucket #13. ... followed by another 15 steps similar to these. The probability we seek is almost, but not exactly, equal to 2/3.

  4. 368939

    2

    Returns: 0.75

  5. 65566

    4

    Returns: 0.66650390625

  6. 451087

    5

    Returns: 0.65286144

  7. 580539

    6

    Returns: 0.6442583701671493

  8. 475715

    7

    Returns: 0.6383429887475824

  9. 598525

    8

    Returns: 0.6340278973402746

  10. 360163

    9

    Returns: 0.6307419125380342

  11. 269942

    10

    Returns: 0.6281565095552946

  12. 604958

    13

    Returns: 0.622907441456657

  13. 7157

    20

    Returns: 0.6169838376712793

  14. 7913

    24

    Returns: 0.6151929479534703

  15. 103225

    27

    Returns: 0.6142065611141312

  16. 350175

    27

    Returns: 0.6142065611141312

  17. 3323

    28

    Returns: 0.6139258512939367

  18. 573595

    32

    Returns: 0.6129820976571815

  19. 492646

    33

    Returns: 0.6127826277606554

  20. 876404

    33

    Returns: 0.6127826277606554

  21. 3052

    38

    Returns: 0.6119455085986218

  22. 5831

    41

    Returns: 0.6115428303592291

  23. 5889

    41

    Returns: 0.6115428303592291

  24. 826957

    41

    Returns: 0.6115428303592291

  25. 465529

    45

    Returns: 0.6110906788433947

  26. 1857

    53

    Returns: 0.6103936916833074

  27. 8385

    57

    Returns: 0.6101194214060622

  28. 963153

    57

    Returns: 0.6101194214060622

  29. 741

    58

    Returns: 0.6100568326946942

  30. 9947

    59

    Returns: 0.609996389585233

  31. 645523

    61

    Returns: 0.6098815134970482

  32. 4755

    64

    Returns: 0.6097228014700677

  33. 690684

    64

    Returns: 0.6097228014700677

  34. 241286

    65

    Returns: 0.6096731864509009

  35. 4335

    72

    Returns: 0.6093648275916982

  36. 9308

    74

    Returns: 0.609287536656543

  37. 7322

    77

    Returns: 0.6091791937118656

  38. 838533

    77

    Returns: 0.6091791937118656

  39. 592926

    79

    Returns: 0.6091115750589324

  40. 1670

    80

    Returns: 0.6090790441400206

  41. 9379

    80

    Returns: 0.6090790441400206

  42. 354857

    80

    Returns: 0.6090790441400206

  43. 330

    82

    Returns: 0.6090163819512175

  44. 1853

    83

    Returns: 0.6089861923957114

  45. 10555

    83

    Returns: 0.6089861923957114

  46. 358609

    87

    Returns: 0.6088724274387354

  47. 5248

    88

    Returns: 0.6088456144125352

  48. 119558

    88

    Returns: 0.6088456144125352

  49. 245982

    90

    Returns: 0.6087937891274775

  50. 537426

    90

    Returns: 0.6087937891274775

  51. 1194

    94

    Returns: 0.6086968014368741

  52. 914394

    94

    Returns: 0.6086968014368741

  53. 405434

    100

    Returns: 0.6085659649572782

  54. 1000000

    100

    Returns: 0.6085659649572782

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: