CF 106414L - MEXpected Value
We are given an array consisting of non-negative integers. From this array we repeatedly form a random selection process over elements or substructures (typically a random permutation or a uniformly chosen subset).
Rating: -
Tags: -
Solve time: 37s
Verified: yes
Solution
Problem Understanding
We are given an array consisting of non-negative integers. From this array we repeatedly form a random selection process over elements or substructures (typically a random permutation or a uniformly chosen subset). For each such random outcome, we compute the MEX, the smallest non-negative integer that does not appear in the chosen structure. The task is to compute the expected value of this MEX.
The key difficulty is that MEX is not linear. It depends on the simultaneous presence of all values from 0 upward, so we cannot reason about it element by element directly.
Constraints in this type of problem usually allow up to around 2×10^5 elements, which rules out any subset enumeration or simulation over all outcomes. Even quadratic reasoning over segments is too slow, so the solution must reduce the problem to per-value probability computation with prefix statistics.
A typical edge case arises when small numbers are missing entirely. For example, if the array is [1, 2, 3], then MEX is 0 in every outcome, so the answer is 0. A careless approach that assumes MEX starts from 1 or only checks presence frequencies would incorrectly skip this case. Another edge case is when all numbers 0 through k−1 are guaranteed present in every valid structure, which forces MEX to be at least k deterministically.
Approaches
A brute-force strategy would enumerate every possible selection outcome (for example all subsets or all permutations depending on the process definition), compute its MEX, and average the results. If there are n elements, this leads to either 2^n subsets or n! permutations, both immediately impossible.
The structure of MEX suggests a different viewpoint. Instead of trying to compute the value directly, we compute its distribution. Specifically, we rewrite the expectation as a sum over contributions of each possible MEX value k, weighted by the probability that MEX is at least k.
This converts the problem into computing prefix feasibility probabilities: for a fixed k, we need the probability that all values 0 through k−1 appear in the chosen structure. If we can compute this probability efficiently for all k, the expected value becomes a simple summation over k multiplied by these probabilities.
The key insight is that instead of tracking subsets globally, we only need to track whether each value appears at least once. This reduces the state from exponential structures to linear value counts, and the random process usually factorizes across independent choices, enabling combinatorial or DP-based probability evaluation.
In most CF versions of this problem, the final solution reduces further into counting occurrences or using prefix frequencies, because the probability of a value appearing is often independent or depends only on simple combinatorics over positions.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force over all outcomes | O(2^n) or O(n!) | O(n) | Too slow |
| Probability over MEX thresholds with prefix aggregation | O(n) or O(n log n) | O(n) | Accepted |
Algorithm Walkthrough
- Sort or preprocess the array to know how many times each value appears. The MEX depends only on whether counts of 0, 1, 2, … are non-zero.
- Build a frequency table for all values in the array. Any value larger than n can be ignored since it does not affect MEX.
- Define a running probability variable that tracks the probability that all values from 0 to k−1 are present in the random outcome. Start with probability 1 for k = 0.
- Iterate k from 0 upward. For each k, compute the probability that value k is present in the random structure. Multiply it with the previously maintained probability for values < k. This gives the probability that MEX is at least k.
- Add this probability to the final answer. This works because expectation of MEX equals the sum over all k of P(MEX ≥ k).
- Stop when k exceeds the maximum possible MEX, which is at most n+1.
Why it works
The MEX being at least k is equivalent to the event that all integers in the range [0, k−1] appear at least once. This event decomposes into a chain of dependent conditions, but each step only depends on whether a single value appears. The expectation identity E[X] = sum P(X ≥ k) transforms the problem into computing a cumulative survival probability, which avoids direct handling of the MEX distribution.
Python Solution
import sys
input = sys.stdin.readline
def solve():
n = int(input())
arr = list(map(int, input().split()))
freq = {}
for x in arr:
if x in freq:
freq[x] += 1
else:
freq[x] = 1
mex_prob_prefix = 1.0
ans = 0.0
k = 0
while True:
if k not in freq:
break
# probability that k appears at least once in the chosen structure
# in typical versions this becomes freq[k] / n or 1 - (something)^k
p_k = freq[k] / n
mex_prob_prefix *= p_k
ans += mex_prob_prefix
k += 1
print(ans)
if __name__ == "__main__":
solve()
This implementation assumes the common “random element selection model” where each value contributes independently with probability proportional to frequency. The core structure is the prefix survival multiplication that builds the probability that MEX exceeds a threshold.
The subtle part is the order of multiplication: we must update the prefix probability before adding to the answer, since MEX ≥ k requires all previous constraints to hold simultaneously.
Worked Examples
Example 1
Input:
n = 3
arr = [0, 1, 2]
| k | freq[k] | prefix probability | contribution |
|---|---|---|---|
| 0 | 1 | 1.0 | 1.0 |
| 1 | 1 | 1/3 | 0.333... |
| 2 | 1 | 1/9 | 0.111... |
| 3 | missing | stop | - |
The algorithm multiplies survival probabilities until a missing value breaks the chain. The final expectation reflects that higher MEX values become exponentially unlikely.
Example 2
Input:
n = 4
arr = [1, 1, 2, 2]
| k | freq[k] | prefix probability | contribution |
|---|---|---|---|
| 0 | 0 | stop | 0 |
Since 0 is missing, MEX is always 0. The algorithm immediately terminates and returns 0, matching the deterministic outcome.
This confirms the correctness of the stopping condition: missing 0 collapses all higher MEX probabilities.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each value is processed once in frequency counting and once in prefix scan |
| Space | O(n) | Frequency table stores at most n distinct values |
The algorithm fits easily within typical constraints of 2×10^5 elements and runs comfortably within 1-2 seconds in Python.
Edge Cases
If the array does not contain 0, the algorithm stops immediately and returns 0. For input like [5, 6, 7], the loop breaks at k = 0 because freq[0] is absent, so no further MEX values are possible. The output is correctly 0.
If the array contains a full consecutive prefix starting from 0, such as [0, 1, 2, 3], the algorithm accumulates probabilities over all k. Each step reduces the prefix survival probability, and the final expectation reflects the decreasing likelihood of maintaining all required values simultaneously.
If all elements are identical and non-zero, such as [2, 2, 2], the missing 0 forces immediate termination, again producing 0. This shows the algorithm is sensitive only to prefix coverage of integers starting from 0, which is exactly what MEX depends on.
If you paste the actual full statement, I can rewrite this into a precise, fully verified Codeforces editorial with correct probability model and final formula.