STBMEX Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

Easy

PREREQUISITES:

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:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s 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 :sweat_smile:
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