Editorial/Explaination required for MEXDIV snackdown17 elimination

It would be great if someone could explain this problem’s solution:
MEXDIV snackdown17 elimination

1 Like

Quick Explanation

You can solve the problem with sliding window with DP.

Solution

We know that mex\{a_L, ..., a_R\} > k \implies mex\{a_{L-1}, a_L, ..., a_R\} > k. This means that if we fix the right endpoint, we can increment L until we get the smallest subarray with mex > k that ends at R. After this, all subarrays \{a_{L'}, ..., a_R\}, L' > L will have mex not more than k.

Knowing that, we can now find L for every R using two pointers sliding window in O(n) time. Every time we increment R, we try to close the gap for L while the mex is still not k. We can use frequency array or set for this for every number not more than k.

Now how do we count the partitions? We can do DP with range sum. Let the answer (number of partitions) for subarray a[1...R] be dp[R]. We already know L from the sliding window. We can create partitions for all left endpoints greater than L, hence dp[R] = dp[L+1] + dp[L+2] + ... + dp[R-1]. The latter function can be solved optimally with accumulating DP. The final answer is at dp[n].

Complexity

Space and time complexity for sliding window and accumulating DP are O(n).

Link to Solution

3 Likes