MAXMEX - Editorial

editorial
, , ,
28

Please explain your approach. Did you consider multiple occurence of integers?

29

I think the problem statement could have been made a little more clear with 1 or 2 more input-output examples.

6 Likes
30

How though?

31

I made the same incorrect assumption and ended up solving only one question :’(

1 Like
32

Unless specified that array elements are unique, you ought to assume that only.

1 Like
33

You are right bro

34

MEX, i.e. the smallest positive integer which does not occur among the chosen elements

M=3
Given set = {1, 2, 4}
Acc to answer chosen set is {1, 2, 3}. So the elements which donot occur among the chosen elements are : NULL
Smallest among NULL is 3? Please explain

1 Like
35

When you are using the word among the elements , it signify that you are using some lower and upper bound

3 Likes
36

made the same assumption :pensive:

37

Because

Editorial : MEX of a sequence is the smallest positive integer not present in the sequence.
Problem: MEX, i.e. the smallest positive integer which does not occur among the chosen elements.

chosen elements is a subset of sequence

38

Yeah, but which elements you chose depends on you.

39

Subsequence is also a sequence. Isn’t it?

41

even I thought that we need to pick elements on our own from the sequence. :disappointed: and I think someone in the comments even said that it’s okay to pick it :sob:

1 Like
42

if (small.size()<m-1) then also print -1, since all elements less then m should be present otherwise no solution is possible,
also you are using sets but multiple occurrence of elements is possible so use some other container.
my solution

43

According to editorial we have to find a subsequence in which the smallest positive integer not present in that subsequence is M (here M is MEX of the subsequence).
Now M=3 means MEX of the subsequence shoul be 3. Given set is {1,2,4} and if I choose the full set then MEX is 3 as 3 is the smallest integer not present in the set.

44

yes it depends but in that case it will not give -1
e.g.
1)as per editorial
smallest integer not present in [1,2,4,6] is 3 and answer will be 4 if value of m is 3 but if value of m is 5 answer will be -1
2)as per problem statement
smallest integer among the chosen element
[1,2,4,6] and if m is 5
I will go for [4,6] cause among chosen element 5 is smallest not present in the subsequence

5 Likes
46

Please help me to find out the mistake in my approach.
My approach was if given M=x, then I would check if all the numbers less than x are present in the sequence at least once or not , if not then any subset would be impossible.
Please have a look on my code
https://www.codechef.com/viewsolution/34615037

1 Like
47

The explanation of question was really bad.

7 Likes
48

Your code fails when we have duplicate elements less than M. For example :
1
3 3
1 1 4
Just use a set, instead of count.

49

The problem statement says " the smallest positive integer which does not occur among the chosen element. " Now, if you chose [4,6] than according to this statement 1 is the smallest positive integer which is not present among your chosen elements. Is it too hard to understand?

4 Likes