< Back to forum

### 1 Answer(s)

3
Reply
Upvote

##### Instruction to write good question

**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.

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.

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

Refer to Stack Overflow guide on asking a good question.