 # MEXSPLIT - Editorial

Setter: Jeevan Jyot Singh
Tester: Takuki Kurokawa
Editorialist: Kanhaiya Mohan

Simple

MEX

# PROBLEM:

Chef has an array A of length N. Chef wants to select some disjoint, non-empty subarrays from A such that:

• The mex of each of the selected subarray is the same.

Note that the selected subarrays need not cover all the elements of the array.

Chef wants to select the maximum number of disjoint, non-empty subarrays that satisfy the above condition. Can you help him to do so?

# EXPLANATION:

Hint 1

Think of subarrays of length 1.

Hint 2

The MEX of a subarray of length 1 is either 0 (if the element is non-zero) or 1 (if the element is 0).

Solution

We consider all the elements of the array as disjoint subarrays. There are two possible cases for each subarray:

• The subarray is element 0. In this case, MEX of the subarray is 1.
• The subarray is a non-zero element. In this case, MEX of the subarray is 0.

Let the count of zeros in the array A of length N be X. This means that there are (N-X) non-zero elements in the array.

Thus, the total number of disjoint subarrays with MEX equal to 1 are X. Similarly, the total number of disjoint subarrays with MEX equal to 0 are (N-X).

Since we want maximum subarrays with the same MEX, our answer is max(X, N-X).

Note that we cannot have a greater answer in any other selection of subarrays since the total number of disjoint subarrays would reduce.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

void solve() {
int n;
cin >> n;
int ans = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
ans += (x == 0);
}
cout << max(ans, n - ans) << '\n';
}

int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
using namespace std;

int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int zeros = (int) count(a.begin(), a.end(), 0);
cout << max(n - zeros, zeros) << endl;
}
return 0;
}
``````
Editorialist's Solution
``````#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int zero_count = 0;
int nonzero_count = 0;

for(int i = 0; i<n; i++){
int x;
cin>>x;
if(x==0) zero_count++;
else nonzero_count++;
}
cout<<max(nonzero_count, zero_count)<<endl;
}
return 0;
}
``````

Where is it given in the problem that ‘0’ will always be present in the given array?

2 Likes

If there are no zeros present in the array, we can select all the (non-zero) elements as disjoint subarrays since all of them have MEX equal to 0. The answer in this case is max(0, N)=N.

3 Likes

If all zero’s are considered separate subarrays of size 1, how it’s disjoint then?? They all have same values.

If all zero’s are considered separate subarrays of size 1, how it’s disjoint then?? They all have same values?

A group of subarrrays is said to be disjoint if there exists no index 'i' such that i belongs to 2 or more subarrays.
In this case, the values at all indices are same. The subarrays are disjoint as the indices in all the subarrays are different.

3 Likes

Ohh, my bad, I thought values. Thank you.

A=[2,0,1,6,2,1,3,0,7]
For this case maximum disjoint set are :- 7
,,,,,, as mex for all are 0.
then how is answer is 2 ???

The answer should be 7 in this case.

1 Like