ProbabilisticStreamMinimum
SRM 822 · 2022-01-16 · by misof
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.)
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.
47 1 Returns: 1.0
The algorithm is guaranteed to work. The minimum element will end in one of the buckets.
3 3 Returns: 0.691358024691358
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.
368939 2 Returns: 0.75
65566 4 Returns: 0.66650390625
Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ProbabilisticStreamMinimum with a public method double calculate(int N, int K) · 54 test cases · 2 s / 256 MB per case