 # FIBFEVER - Editorial

Author, Tester and Editorialist: Rohail Alam

EASY-MEDIUM

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 , 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;
idx = 2;
idx = 3;
idx = 4;
idx = 5;
sub = 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))<<endl;
}
``````