MEXPROB - Editorial

editorial
, , , ,
9

Oho…Okayyyy…

10

pls can you tell any more efficient method to find all subarrays
i took this approach mentioned in this article

1 Like
11

Hi, that’s what the editorial is all about.

12

Hey, here is the link to my TLE code for this problem. I don’t know why it is not getting 10 pts.
https://www.codechef.com/viewsolution/52289211

13

i tried the brute force approach but i couldn’t get 10points, may i know the criteria for getting 10points? like whats the max time complexity?

14

N^2

1 Like
16

CodeChef: Practical coding for everyone could you tell where i was exceeding n^2 complexity? (in calculating mexes?)

17

Sorting takes N^2.logn time

1 Like
18

Ya, time limits for this problem were very very strict.

19

anyone who did the Subtask(30 points), what was the approach and Time complexity?

20

CodeChef: Practical coding for everyone… Help!!

21

I am encountering this MEX for the first time. Please can anyone tell me what is MEX of array a=[2]?
I am trying the brute force method first but I don’t know how to calculate the MEX of an array.

22

Dude Your Time Complexity is N^2logN^2 try reducing it to O(N^2) !!

Spoiler

Instead of Taking B array of size 100000000 Take ‘Count’ array of size N+1 since MEX of the array can be [0, N] so each time u get a MEX, update the count of MEX
Now you have count of each number .i. e. how many times each number is MEX now you can just iterate on count array and find kth small MEX;

1 Like
23

MEX for a=[2] is 0
For calculating MEX: take an array of size of N+1 and update all elements to 0

Summary 
   int ans[n+1]={0};
    for(int i=0;i<n;i++)
    {
        int b[N+1]={0},mex=0;
        for(int j=i;j<n;j++)
        {
            b[a[j]]=1;
            while(b[mex])
            {
                mex++;
            }
            ans[mex]++;
        }

Now each time we update count of mex since mex variable has the MEX value

1 Like
24

https://www.codechef.com/viewsolution/52305961

Why this is not passing subtask 1?

25

could you share any youtube video or detailed description for this mex calculating program? i still didn’t get it.

1 Like
26
1 Like
27

sir,what is the use of a[r] in cnt[a[r]]++,i means what is the value of a[r] in cnt[a[r]] in loop,as we dont assign any value in this vector a[maxn]
replie kindly m doubt

28

can you please elaborate I don’t get you!

cnt array is used to keep track number of times a number is MEX

29

Solution: 52856209 | CodeChef

can some 1 plz tell me why code is giving me tle for one test case adn wa for other?