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


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

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

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

avatar

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.