PROBLEM LINK:
Author, Tester and Editorialist: Rohail Alam
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Greedy, DP
PROBLEM:
Find out the minimum number of elements to be individually removed an array to make it ‘good’ , the definition for which has been described in the problem statement.
QUICK EXPLANATION:
The number of elements to be removed from the array will be nothing but the difference between the size of the array and 5 times the number of good arrays. To be more direct :
Elements removed = n - 5*(number of good arrays)
Where ‘n’ is the size of the given array.
EXPLANATION:
Let sub{1} be the number of subsequences [1], sub{2} be the number of subsequences [1,2], and so on , and sub{5} be the number of subsequences [1,2,3,5,8].
Now we will iterate through the given array, and increment sub₁whenever we come across a 1, implying that we are starting a new subsequence (of [1,2,3,5,8]). In case of any other number, we would simply be continuing a previously existing subsequence - since we want to complete the [1,2,3,5,8] sequence.
Code-wise, what we would simply be doing is increment sub{1} whenever a 1 is encountered (as said before, we do this to essentially start a new subsequence). If otherwise, say I have come to the ith value in the required sequence[1,2,3,5,8] (i ≠ 1), then we would be continuing an existing subsequence (if it of course, does indeed exist) by decrementing sub{(i-1)} and incrementing sub{i} provided that sub{(i-1)} is greater than zero (implying that the subsequence it is to be added to does exist)
The final number of good arrays will be indicated by the value of sub{5}, using which we can find the number of elements to be removed as shown in the quick explanation :
Elements removed = n - 5*(sub{5})
SOLUTION:
Click me
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;++i){
cin>>a[i];
}
vector<int> idx(10),sub(6,0); // idx can also be used as an STL map
idx[1] = 1;
idx[2] = 2;
idx[3] = 3;
idx[5] = 4;
idx[8] = 5;
sub[0] = n; //Decremented when we come across ‘1' (for generalization).
for(int i=0;i<n;++i){
if(sub[idx[a[i]]-1] > 0){
sub[idx[a[i]]-1]--;
sub[idx[a[i]]]++;
}
}
cout<<(n-(5 * sub[5]))<<endl;
}