I observed that in every case , mex will be equal to that of whole array . Then we can use dp , binary search and mex range query to solve the problem. complexity O(nlognlogn).
Is this approach correct ?
I found how to calculate mex range query very late thus it was too late to code.
Please share other approaches too.
Buddy I could not understand the problem statement! Can u please guide me how to approach to such problems?
It can be done in O(nlogn) as for each range query [l, r] you only need to find largest l such that mex(l, r) = mex(complete array) which can be done without a binary search.
i also didn’t get the question. Most of the time CodeChef questions aren’t hard but problem setters don’t write clear questions.
I also felt that MEX of any subarray should be equal to whole array.
My Approach (Wrong ans)
if zero is not present ans is 2^n-1 as from second element we can combine it to pervious subarray or start new one.
otherwise find shortest prefix and suffix which have MEX equal to MEX of whole array.
and ans will be (no of elements not in suffix or prefix + 1)
as we can combine remaining elements in either prefix of suffix.
and add 1 for whole array
I thought we need to find the smallest l_1 such that [l_1,r] has mex equal to complete array and largest l_2 too . Thus for all l from l_1 to l_2 will have mex equal to whole array and we can sum the answer in that range.
can you elaborate your approach a bit ?
Ok i think smallest l can be found by keeping largest index where “mex” occurred while iterating.
We solve it using DP. dp[i] denotes the answer for the array a[1…i]. So, our transition becomes something like dp[i] = 1 + \sum_{j = 0}^{k - 1} dp[j] where k is the largest index such that mex(k, i) = mex(complete array).
I understood that . Thanks . How to find that largest index k ?
I did it using a segment tree but it can be done using a set too. So basically you store the last index of any element that you encounter. After that, you find the minimum index among indices for elements from 0 to mex - 1. This will give you k.
Assuming most of you would have given today’s Cookoff on Codechef, you can check out my solution video for the Problem Mex Subsequence (Div1 A, Div2 C, Div3 E) here if you weren’t able to solve this one.
