MAXMEX - Editorial

editorial
, , ,
127

You have to first take input for n and then for m.

128

thanks!
author should have explained MEX more clearly in the contest problem.
simple problem though

130

are out your mind
there is written ā€˜amongā€™ and we are allowed to choose our own sequence
to make max length .
1
6 6
4 5 7 8 9 10
for this i will choose[4 5 7 8 9 10] as there 6 is missing.

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.

note that ---- ---- we are allowed choose our own sequence to make m=6.
question is wrong.

m should be defined as lowest positive integer which is not present.

131

that is wrong not confusing

mex should be defined as lowest positive integer >=1 .
and ā€˜amongā€™ must not be used.

132

exactly.
bro its not poorly defined it is wrongly defined.

mex should be defined as lowest positive integer >=1 .
and ā€˜amongā€™ muuuuuuuuuuuust not be used. must not

133

bro its not poorly defined it is wrongly defined.

mex should be defined as lowest positive integer >=1 .
and ā€˜amongā€™ muuuuuuuuuuuust not be used. must not

134

bro its not confusing it is wrongly defined.

mex should be defined as lowest positive integer >=1 .
and ā€˜amongā€™ muuuuuuuuuuuust not be used. must not

135

Very very poorly defined question, atleast give one more test case for clarity. Thatā€™s why people prefer codeforces instead of this.

2 Likes
136

Yes That ā€˜Amongā€™ Word was an obstacle in understanding the problem.

137

EXACTLY!!!

138

https://www.codechef.com/viewsolution/34675656
Why am I getting a WA?

139

@v1shant
can you explain your code?

140

Why am i getting SIGSEVG in this code? It matches the testerā€™s solution

#include<bits/stdc++.h>

using namespace std;

#define ll long long
int arr[100005]={0};
int main(){
int t;
cin >> t;
while(tā€“){
int n,m,c=0,c1=0,x;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>x;
if(x<=m)
arr[x]++;
}

	c=arr[m];
	if(c==n) cout<<-1<<endl;
	else{
	
	for(int i=1;i<m;i++)
	{
		if(arr[i]==0)
		{
			c=-1;
			break;
		}
	}
	if(c1==-1)
		cout<<-1<<"\n";
	else	cout<<n-c<<endl;}

}
return 0;
}

141

Welcome friendā¤ļø.

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