MAXMEX - Editorial

editorial
, , ,
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);

}
}

63

Ignore it . I have not taken long long for sum upto m-1. got AC after contest.

65

Can someone help me whats wrong with my code??
Link - CodeChef: Practical coding for everyone

66

Quick Question

  1. How do we validate assumptions ? For instance in an interview we can interviewer all questions.

For example in this question

  1. How do we assume it always input always starts from 1 ?
  2. How do we assume whether the input is always in increasing order ?
67

bro! you may try sorting initially
still this problem seems to have many loopholes in understanding the statements properly.

68

bro! in order to find desired solution
we assume

M : Smallest integer not present in chosen set(largest as demanded in problem) of elements
X : smallest positive integer not present in given sequence

if(X<M) then -1, coz irresspective whatever subset we choose X will always be resultant MEX and not M
e.g. {1, 2, 4, 6, 5 } ,X=3,M=5

if(X==M) cool the sequence is itself the largest subset with M as MEX
e.g. {2, 1, 5, 7} ,X=3,M=3

if(X>M) remove all occurrences of M , and we form largest subset from rest elements
e.g. { 5, 6, 3, 8 , 4, 3, 1, 2} X=7, M=3 largest subset will be { 5, 6, 8 , 4, 1, 2}

if you still feel some query still then post doubt more clearly
thanks!