Problem in Max Mex Problem Code: MAXMEX

help
1

can someone please take a look and tell me why was it giving me WA. Your help would be greatly appreciated.
https://www.codechef.com/viewsolution/34620716

1 Like
2

Video Solution!

1 Like
3

Your solution is wrong imo

  1. you not only need to check if the m-1 is not in sequence but all the numbers from 1 to m
    and m can be presented in the given array.
1 Like
4

Thank u :+1:

5

I didn’t understand the logic. As the questions says we have to find the largest number of elements of sequence A such that MEX is equal to M.
There can be more than 1 missing elements in the sequence.
for Ex:-
Input:-
1
9 8
1 2 3 5 6 7 9 10 11
Here according to the question the answer should be [5,6,7,9,10,11] i.e 6
but it gives -1 as output.
Please help me on this. Thanks.

6

the optimal answer could have been [1,2,3,5,6,7,9,10,11] but since 4 is not present so MEX is equal to 4. Hence answer is -1.

7

Thanks Brother, But according to the question:-
MEX, i.e. the smallest positive integer which does not occur among the chosen elements.
This the definition for MEX provided in the question.
According to which if we chose [5,6,7,9,10,11] the MEX would be 8.

8

No, the MEX will be 1 in this case.

1 Like
9

MEX for the sequence u have chosen is 1(not necessary for it to be present in your chosen sequence).

10

Thanks brother. But I don’t think that would be correct. because if that would have be correct than
MEX for [1,2,4] would also have been 1.

1 Like
12

so thats why question had (possibly none or all of them) in it which tell the whole array or -1 in all cases.right?

13

Chef has a sequence of positive integers A1,A2,…,ANA1,A2,…,AN.

He wants to choose some elements of this sequence

(possibly none or all of them) and compute their

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

For example, the MEX of [1,2,4 is 3.

Please help on How it is 1.

1 Like
14

Mex is the smallest positive integer that is not present in the sequence, in the following test case , that number is 4 hence no sequence can be formed out of the given sequence which has mex=8;
Input:
1
7 4
1 2 3 4 4 5 7
here answer should be: [1,2,3,5,7] because mex element in this case would be 4.
happy coding .

15

You have three integers in the array- 1,2,4. Now, look at its complement set but only include positive integers(mind that in the question it is given positive integers, not non-negative integers, otherwise 0 also comes into play). So, our complement set includes {3,5,6,7,8…}. Choose the smallest integer within this set. Voilà!, you get your answer which is 3.

Hope this helps.

16

Thanks, I agree to your logic but I think the question provides some different defination-
Chef has a sequence of positive integers A1,A2,…,ANA1,A2,…,AN. **

He wants to choose some elements of this sequence

** (possibly none or all of them) and compute their **

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

**. For example, the MEX of [1,2,4][1,2,4] is 33.

17

Thanks, but I think, ‘’ either ‘’ would have been a better option than ‘‘possibly’’.
i.e
‘‘either none or all of them’’

1 Like
18

Yup i was also confused and thought like you and i made an solution for it but as you know it was getting WA.I nearly spent 40 min on it.

1 Like
19

I also agree that the question was not written well and thus made us confused

2 Likes
20

Same, I really felt sad as it wasn’t that hard of a problem!

21

bro you are considering set of positive integers as the set of numbers given in the array.
but for[2,3,4,5,8] smallest possible positive integer will always be 1.

compute their means after you choose the elements from the array.
eg- array being: 1,2,4,6,8 and i choose 2,4,6,8 then the smallest possible integer that is not present in the sequence is 1 and not 3.

1 Like