MAXMEX - Editorial

editorial
, , ,
142

It’s your problem if you can’t keep an eye to details. Don’t blame the problem setters or the codechef platform. They work very hard to host a contest. Do you think all the problems setters, testers, statement verifiers did not set the question carefully? All of the 5*, 6*, 7* coders are wrong and you are right? Please try not to blame others for your mistakes and for code’s sake respect the platform you are using. You aren’t paying them!!!

1 Like
143

yes,you are right

144

They work hard for us .
So , respect them.

1 Like
145

set is [1,2,4,5,6,8,9] and given M=7 , then largest subset can be [4,5,6,8,9].
MEX = 7 (MEX, i.e. the smallest positive integer which does not occur among the chosen elements.)
Thus, answer should be 5. Please explain why it’s -1.

146

For {4,5,6,8,9} MEX is 1. Read the question carefully

147

Here is my approach:

Conditions the sub sequence should follow:

  • No element should be >= M
  • It should contain all sequences between 1 and M-1

How to carry it out:

Create a list to keep track of all the numbers from 1 to M. For each such number, this list should tell whether it exists in the subset or not.
For each integer in A, do the following:

  • If the integer can be in the subset (if i != M): Add it to the subset
  • if the integer is less than M, change exists accordingly.

If there is a single value that does not exist, output -1, else output the subset size.

My code extract: 
Exists = [False,]*M # All values are set to false initially
for i in A:
    if i != M: # If the subset can contain i
        subset_size += 1 # Note, we don't need to output the subset itself, only the size
            if i < M: # It should be known that it is below M and exists in A
                Exists[i] = True
if False in Exists[1:]: # Exists[0] is out because it is not positive
    output = -1
else:
    output = subset_size
148

Is input array always Sorted ???

149

@rezwanarefin01 what will happen if A contains any element more than 1 copy then set st will insert anyone of them .it will decrease the count of inserted element so why its not giving weightage on submission.

Only in case of MEX==M

150

https://www.codechef.com/viewsolution/35485550
plz tell me why i’m getting WA

151

what you have mentioned above the question is judging like that only ???

152

i don’t understand why you have checks for a[i] > m ?

things that matter in the problems are … first that there should be all values in range [1,m-1] available in array…
if first condition is true print (size of array - count of m’s in array)

here is my submission.

153

in the setters solution ,it will make more sense if the mex should be initialized by the first ele of the set instead of 1…

1 Like
154

Please take a minute to see my code.
My whole day is gone in WA for this question. I dont know whats wrong in this CodeChef: Practical coding for everyone

155

plzz tell me why i am getting wrong answwer
https://www.codechef.com/viewsolution/35767343

156

i believe you code’s logic is incorrect.

you are finding tha maximumvalue out of first N number which is not available in the array?
and then checking if maximum is == m?

you didn’t understand the concept of MEX, it is minimum excluded, not maximal excluded.
that means MEX of following arrays are :
[2,3,5,9,8,10,12,13,14] = 1 not 9.
[1,2,3,5,6,7,8,9,15,16,17] = 4 not 10.

157

my code is correct its giving 1 as mex and not 9
i am using break so if we first encounter any number which is missing thats mex and break

see my code again plzz.

1 Like
158

did u found out anything that i should change in my code??

159

i believe you method of finding MEX was wrong ←
as you were assuming that array is going to be sorted i guess and array will not contain dublicate values.

CodeChef: Practical coding for everyone ← i modified that part and got AC.

160

Can we not think of Peageonhole principle for this problem ?
As is N<=10^5 , So possible MEX can be between 1 to 100001 . If m>100001, we can simply output -1
Else we can have a frequency array of size 100002 (index from 0 to 100001), in this we can save frequencies of the elements.
If the m>100001, we can traverse the freq array and check that all elements which are between 1 to m-1 should be present ,
if (they are all present then ans will be the sum of no. of elements between 1 to m-1 plus the sum of no. of elements greater than m)
else ans should be -1

Time Complexity - O(n)
Space - same

Please review my approach. Is it right ? Or tell me some counter test case. Thanks in advance !!

161

I verified it. My code
https://www.codechef.com/submit/MAXMEX