# STBMEX Editorial

Setter: Akshit Monga
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

Easy

None

# PROBLEM:

Chef gives you a sequence A of length N.
Let X denote the MEX of the sequence A. Chef is interested in the count of positive values k, such that, if every element A_i of A is replaced by \texttt{max}(A_i-k,0), the MEX of the sequence still remains X.

Find the count of such values. If there are infinite such values, print -1 instead.

As a friendly reminder, the MEX of a sequence is the smallest non-negative integer that does not belong to the sequence. For instance:

• The MEX of [2,2,1] is 0 because 0 does not belong to the sequence.
• The MEX of [3,1,0,1] is 2 because 0 and 1 belong to the sequence, but 2 does not.

# EXPLANATION:

Let us take three diffrent cases to tackle this problem:

• if mex(A)=0, answer = min(A) - 1, since k can be in the following range: 1 \leq k \leq min(A) - 1

• if mex(A)=1, answer = infinite, since here k can be anything \geq max(A).

• if mex(A) \geq 2, for this case we follow the following approach

Sort A and consider only distinct elements of A
Partition A into segments having consecutive elements. Say,

A=[0,1,2,5,6,10,15,16,17,19]

Then its partitions would be

[0,1,2],\; [5,6],\; [10],\; [15,16,17],\; [19].

Then our final answer would be one less than the number of segments having size greater than or equal to mex(A) - 1

# TIME COMPLEXITY:

O(NlogN) for each test case.

# SOLUTION:

1 Like

what wrong with this solution ? Solution: 62184407 | CodeChef, its same as said in editorial

Consider Case

1
4
0 1 3 3

1 Like

why final ans is one less than number of segments and not the number of segments?

1 Like

Because k should be positive.

what will be the ans for this test case
1
5
0 1 3 5 6

1 Like

The AC codes are linked in the editorial. You can run on that.

whats wrong in this
https://www.codechef.com/viewsolution/62212512

Thanks , I should have checked on unique elements

1 Like

bcz we always need the segment whose largest value is mex - 1 , else mex would change . So initially there always exist such segment,(defination of mex) so we need to subtract it from final count of all continuous segments.

What is wrong with my code i had considered all cases mentioned in the editorial.
Submission during contest

Consider the case :
5
0 1 2 4 5
Your code gives 0 but correct ans is 1

Your AC submission with a small change : Solution: 62214015 | CodeChef

1 Like

Can I ask for tests # 1 and 6?
My Solution if anyone figures the bug
Ignore the comments, it was for personal use
Thanks

Consider only the distinct elements in the array as mentioned in previous comments.

Since your current code will fail on case like

7
0 1 2 4 4 4 4

Thank you.
i thought of something else and coded something else…
Silly me …

2

1 Like

Test Cases Are Weak
Hack !
6
0 1 2 4 5 5
Answer of this test case is 1 when k=3;

https://www.codechef.com/viewsolution/62229209
Failing only on test case 2
can’t figure out why

whats wrong in this code?

Solution: 62221777 | CodeChef

Then our final answer would be one less than the number of segments having size greater than or equal to mex(A) - 1
Can you please explain how is it so? Like what is the logic or intuition behind this