MAXMEX - Editorial

editorial
, , ,
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
50

MEX, i.e. the smallest positive integer which does not occur among the chosen elements.
What does the word among signifies then???

1 Like
51

Well keep justifying but there difference between in and among

1 Like
52

Author should have added more sample test cases to make his point clear

2 Likes
53

Hey bro … can you tell me why I am getting wrong. I did the same and small solution. Due to this my whole contest messed up.
https://www.codechef.com/viewsolution/34599968

54

I solved it thinking that if M is present in the sequence then we cannot have a subset whose MEX=M as M is present in the sequence… but what the setter solution has done is that it has not inserted the number M… and then it has counted all the elements… so my answer is -1 and the setters answer is the total number of elements -1 … Now how am I supposed to know that we can remove the elements from the sequence

55

Hi Guys try This Video Solution it includes all observations and approach: https://youtu.be/vTHH2eblqiU

56

correct

57

solved the first Q quickly only to end up making wrong assumption on this one :confused: this took away the entire time

2 Likes
58

Hi guys try this video solution :raised_hands::raised_hands:

59

where is it written that we are allowed to remove the elements

60

How is this different?

Basically mex is defined for a sequence as the smallest positive integer, which does not appear among the sequence.

Consider A = [1, 3, 5, 2]. It’s MEX is 4, the smallest positive integer not in A. Suppose we have M =3.

Now, we can choose subsequence [1, 5, 2] which shall have MEX 3.

Smallest integer not present in chosen set of elements is same as the smallest positive integer not present in sequence. Give any counter case to clarify your point.

2 Likes
61

Kudos to wrong assumptions. RIP

3 Likes
62

please tell me why i am getting WA

#include <stdio.h>

int main()
{
long long int i,j,n,m,t,z,same,countl,countg,ans,l,count1;

scanf("%lld",&t);

for(z=0;z<t;z++)
{
    scanf("%lld %lld",&n,&m); 

    long long int a[n],b[n];

    for(i=0;i<n;i++)
      scanf("%lld",&a[i]);
      
    if(m>n)
    {  printf("%d\n",-1);
       continue;}
       
    countg=0;
    countl=0;
    same=0;
    
    l=0;
    for(i=0;i<n;i++)
    {
       count1=0;    
       if(i==0)    
         b[l++]=a[i];
       else     
       {
           for(j=0;j<l;j++)
           {     
              if(b[j]==a[i])
              {
                count1++;  
                break;  
              }     
           }
           
       }    
        
        if(count1!=0)
           continue;
        else
           b[l++]=a[i];
           
        if(a[i]>m)
          countg++;
        else if(a[i]<m)
          countl++;
        else
          same++;
    } 

    if(countl==(m-1))
    {
        ans = countl+countg;
        printf("%lld\n",ans);
    }
    else
      printf("%d\n",-1);

}
}