PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Jeevan Jyot Singh
Tester: Takuki Kurokawa
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
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;
}