PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni
DIFFICULTY:
1620
PREREQUISITES:
PROBLEM:
A 1-indexed array is called positive if every element of the array is greater than or equal to the index on which it lies. Formally, an array B of size M is called positive if B_i \ge i for each 1\le i \le M.
For example, the arrays [1], [2, 2], [3, 2, 4, 4] are positive while the arrays [2, 1], [3, 1, 2] are not positive.
You are given an array A containing N integers. You want to distribute all elements of the array into some positive arrays. The elements of a positive array might not occur in the order they appear in the array A.
Find the minimum number of positive arrays that the elements of the array A can be divided into.
Please see the sample cases below for more clarity.
EXPLANATION:
Hint
It is always better to keep smaller elements before larger ones while forming a positive array because this will surely reduce the number of positive arrays required to distribute all the elements in A.
Hence, sorting will surely help!
Solution
From the hint it is clear that we should form positive arrays which have elements in an ascending order. If there are K elements in an existing positive array then the next element should be \geq K + 1.
We can greedily assign each element of A (in the ascending order) to some already existing positive array if it can accommodate the current element (if A[i] \geq number of elements in the positive array + 1) or in the other case we need to create another positive array.
We can maintain the information about all the existing positive arrays by storing the minimum required element for each of them.
If the current element (A[i]) can be part of any of the existing positive arrays i.e. it is \geq the least among all the minimum required elements for the positive arrays then we can just update the minimum required element and there is no need to create another positive array. The least among all the minimum required elements can be easily obtained if we store all the minimum required elements in a priority queue and updating also becomes easy.
On the other hand, if the current element (A[i]) cannot become a part of any of the existing positive arrays then we create a new positive array with the current element (A[i]) being the first element in it i.e. add a new value (minimum requirement of 2) into the priority queue.
At the end of the iteration over A the size of the priority queue denotes the minimum number of positive arrays required i.e. our answer.
TIME COMPLEXITY:
O(NlogN) for each test case.
SOLUTION:
Setter's solution
using namespace std;
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
}
int sum = 0, ans = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
ans = max(ans, (sum + i - 1) / i);
}
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
using namespace std;
int main() {
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<int>v(n);
for(int i=0;i<n;i++)cin >> v[i];
sort(v.begin(),v.end());
priority_queue<int,vector<int>,greater<int>>pq;
pq.push(1);
for(int i=0;i<n;i++){
if(v[i]>=pq.top()){
pq.push(pq.top()+1);
pq.pop();
}
else{
pq.push(2);
}
}
cout << pq.size() << endl;
}
return 0;
}
)