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,
Then its partitions would be
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
