FIBFEVER - Editorial


Contest Link

Author, Tester and Editorialist: Rohail Alam




Greedy, DP


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.


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.


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})


Click me
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    vector<int> a(n);
    for(int i=0;i<n;++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){
    cout<<(n-(5 * sub[5]))<<endl;