Chef and Rotation - RECNDROT CodeChef Easy Question

Welcome back to my blog and lets continue or discussion .

Here is the link to today's PROBLEM

So , we need to find the value of M.

The solution is simple , we just take a vector and plug in it the given sequence with its indices .

Then we sort the vector and hence we get a sorted vector with the indices of the numbers in the original sequence .

Then we know the first number of the sequence so , we find the minimum index in the original sequence of that number , then we know the next number , so we find the minimum index just greater than first of the second number . if found continue to third , otherwise we increase the answer by one and then we find the minimum index of the second number .

Hence , we try to maximise the number of numbers i can use in the strictly increasing sequence in one appending.

Please take a look at the following C++ code for better understanding :-

Code :-

#include <iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main() {

    int t;

    cin>>t;

    while(t--)

    {

        long int n;

        cin>>n;

        long int i=0;

        long long int x;

        vector<pair<long long int,long int>> v;

        while(i!=n)

        {

            cin>>x;

            v.push_back(make_pair(x,i));

            i++;

        }

        sort(v.begin(),v.end());

        i=0;

        while(i!=n)

        {

            //cout<<v[i].first<<" ";

            i++;

        }

        //cout<<endl;

        i=0;

        while(i!=n)

        {

            //cout<<v[i].second<<" ";

            i++;

        }

        //cout<<endl;

        

        

        long int ans=1;

        i=0;long int min=v[0].second,min1,j;

           min=v[i].second;

           i++;

            j=i;

            while(i!=n && v[i].first==v[i-1].first)

            {

               if(v[i].second<min)

               {

                   min=v[i].second;

               }

               i++;

            }

            //cout<<"min :"<<min;

            

        while(i!=n)

        {   

         

            min1=v[i].second;

            i++;

            while(i!=n && v[i].first==v[i-1].first)

            {

                if(min1<min && v[i].second>min)

                {

                    min1=v[i].second;

                }

               else if(min1>min && v[i].second>min && v[i].second<min1)

               {

                   min1=v[i].second;

               }

               else if(min1<min && v[i].second<min1)

               {

                   min1=v[i].second;

               }

               i++;

            }

          if(min1<min)

          {

              ans++;

              //cout<<i<<" ";

          }

          min=min1;

        }

        cout<<ans<<endl;

        

        

    }

// your code goes here

return 0;

}

Do follow my blog and leave your doubts in the comments section .