https://www.codechef.com/COOK126B/problems/MEXSUB this is the link of the problem
I cant understand the method they use to solve the problem when mex is not equal to 0....please someone help me
Asked by: ANUPAM_DAS on March 18, 2021, 12:30 p.m. Last updated on March 18, 2021, 12:30 p.m.
One key point to note is that the value of m will be equal to the mex of the
whole array. This can be proven by observing that numbers less than and equal
to m are not present in any subarray. And m+1 is present in all subarrays,
hence it can be said that m is the mex of the whole array.
Now, you have to find the number of ways to partition the array into
contiguous segments so that mex of every segment is m (which is the mex of
the whole array). We use dynamic programming for this. We define the state
dp[i] as the number of ways we can divide the prefix of the given array of
length i into contiguous segments such that the mex of the each segment is
m. Since we only need to fix the last segment we pick, the dp transition can be written as dp[i] = dp[0] + dp[1] + dp[2] +
... + dp[j], where j is the last occurence of m+1 before i. This transition just means that we can pick the left end of the last segment (right end is i) anywhere in the range [0,j]. We need the
last occurrence of m+1 before i, because if a subarray has to have mex
equal to m and there is no element less than or equal to m in the whole
array, then just the presence of m+1 in the subarray makes it's mex equal to
m. We can store the value of prefix sum of dp array in another array to
get the value in O(1) time complexity hence the whole solution is O(n).
thank you 😊
ANUPAM_DAS last updated on March 23, 2021, 2:34 p.m.