STBMEX Editorial

editorial
, , ,
22

Why doesn’t this solution work?
https://www.codechef.com/viewsolution/62216510
I figured I could start checking for segments at the index right after the MEX and avoid having to subtract one at the end.
If I change nothing else but start checking from index 0, set the initial count to 1 instead of 0, and subtract 1 before printing the answer the solution is AC?

23

What’s the mex of an array like
[0,1,2,…n - 1] It is n right.

So you can see for any array like this

0 1 2 3 4 7 8 => the mex of the whole array is same as the mex of the starting 5 elements upto 4 , so this will give you an idea / intuition about working of consecutive segments and mex. Now lets take this example

A = [0 1 2 4 5 6] , MEX(A) = 3

What happens when we subtract some k from the numbers we get our array like

[0 - k , 1 - k , 2 - k , 4 - k , 5 - k , 6 - k] .

All the numbers lesser than equal to k will be replaced by zeroes . Now u see that we have got a zero and the length of smallest segment for getting a mex = m is m.

And since we already got a zero , we need remaining numbers like 1 , 2,… m - 1. Hence the minimum length of segment is mex - 1 .

Say if the length of segment is greater than mex - 1 .(consider the last example and think)
what happens in this case , you simple choose k such that the last (mex - 1) elements of the segments become 1 , 2 , … mex - 1 and we already got 0 as mentioned , thus retaining mex of the original array.

24

Any incorrect solution that gives AC?
I think tests cover a lot of similar cases.

1 Like
25

Hi,
Can a Binary search approach be implemented as well?

26

I don’t think we can apply a binary search here. Binary search requires monotonicity. Say, if the values of K are strictly increasing, then we can do a binary search.

1 Like
27

only mistake i did was
not considering the case x=0 in depth

29

Someone please point out whats wrong with this. It passes only 7/10 of the cases;

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

30

Someone please tell me why this is wrong. I did the exact same thing.

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

31

Hey @twoplusthree :wave:
There is a problem of iteration in your code.
Your working code :

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF INT_MAX
//#define cerr if(0) cerr
#define all(x) x.begin() , x.end()
#define watch(x) cerr << "\t" << (#x) << " = " << (x) << "\n";
#define watchv(x) { cerr << "\t" << (#x) << " = "; for (auto &it : x) cerr << it << " "; cerr << "\n"; }

void solve() {
  int n; cin >> n;
  vector < int > a (n); for (int i = 0 ; i < n ; i++) cin >> a[i];
  vector < int > b (all(a));
  sort(all(b)); b.erase(unique(all(b)) , b.end()); //watchv(b);
  int mex = 0; for (int i = 0 ; i < n ; i++) if (i < b.size() && b[i] == mex) mex++; else break;
  //watch(mex);
  int cnt = 1 , ans = 0;
  if (mex == 0) ans = b[0] - 1;
  else if (mex == 1) ans = -1;
  else {
    for (int i = 1 ; i < b.size() ; i++) {
      if (b[i] == b[i - 1] + 1) cnt++;
      else ans += cnt >= (mex - 1) , cnt = 1;
    }
    ans += (cnt >= (mex - 1));
    ans -= 1;
  }
  cout << ans << "\n";
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  #ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" , stdin);
  #endif
  int tt = 1; cin >> tt;
  while (tt--) solve();
  return 0;
}