 < Back to forum

### Help me to solve this problem of cook off

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.

Preview

##### Enter your comment details below:

Preview

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 + dp + dp + ... + 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)`.

mahawarvishal10 last updated on March 20, 2021, 3:40 p.m.

thank you 😊

ANUPAM_DAS last updated on March 23, 2021, 2:34 p.m.

##### Instruction to write good question
1. 1. Write a title that summarizes the specific problem
2. 2. Pretend you're talking to a busy colleague
3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.