CHCBOX - Editorial

@kunalcodr first for loop is just for testcases, in my main part there is only one for loop. And I use this type of solution before, it requires less then 1 mins. But I don’t know why this take 2.01 sec. btw thanks for replying!

Look here i think you will get the logic , You have to count how many times half of the shell would not contain the maximum element.
8
1 2 3 1 2 1 8 8
-1 -1 -1 0 0 0 -1 -1
3

You always use python ?
Time taking by python is always high.
So may be sometime it takes more time.

Yes, almost always. Actually, I am learning C++ just for one month, and I only covered logic part in C++, I am still learning it. But I am learning python from last 1 year 2 months.

This test case is wrong. There are no 10 numbers in the array, only 9.

@everule1
for test case

1
6
1 1 1 2 2 2
why is the output 1 ?
if we do one right rotation, shouldn’t be the final result - 2 1 1 1 2 2, which is wrong

1 1 1 2 2 2 itself.

output -
For each test case, print a single line containing one integer ― the number of shifts for which Chef does not become unhappy.

this was what stated in the problem, no shift is zero shift.

Oh, I think you misinterpreted .the number of shifts as in the number of possible shifts, which is only 0, so the answer is 1 possible shift.

Yeah I thought how many shifts are needed. Thanks.

I solved it by storing the first half of the array at the end of the original array

int main(){
fast;
cin>>test;
while(test–){
cin>>n;ll x;ans=0;
vector v(2n);ll max_=-1;
for(int i=0;i<n;i++){ cin>>v[i];max_=max(max_,v[i]);}
for(int i=0;i<n/2-1;i++) v[i+n]=v[i];
int nonm=0,m=0;. //m->no. of max elements nonm->no of non max elements
for(int i=0;i<n/2;i++){
if(v[i]==max_) m++;
else nonm++;
}
if(m==0) ans=1;
for(int i=n/2;i<3
(n/2)-1;i++){
if(v[i-n/2]==max_) m–;
else nonm–;
if(v[i]==max_) m++;
else nonm++;
if(nonm==n/2) ans++;
}
cout<<ans<<"\n";
}
return 0;
}

insert this in main function
ios_base::sync_with_stdio(false);
cin.tie(NULL);

use \n instead of endl;

or use scanf and printf, they are faster the cin and cout.

@tmwilliamlin
If the maximum element occurs only once and if it’s position is less than or equal to n/2 then then length of subarray will be n so according to formula mentioned in the editorial ans should be n/2+1. but it is actually n/2.
it can also be seen clearly in first testcase. please help me out to understand this case i will be really grateful to you.

See, if the range is equal to n/2 , then no matter how many times we rotate the array , there is going to be atleast one element which is in the other half. Similarly, if the range is (n/2 )-1, then there is 1 combination for which there is no max element inside the first half.
So,
n/2 —> 0
n/2 -1 —> 1
.And so, on

So, the general case is to subtract range from n/2.

What is the output if the values of W are 2 1 1 1 1 2?

if range is find using circular queue it does not work ?.
https://www.codechef.com/viewsolution/30759911

Thanks a lot

I tried the solution as per the above explanation but still my code is getting wrong answers.Can anyone tell me where am i wrong??
`#include <bits/stdc++.h>
using namespace std;
void task(vectorvect,int n)
{
int maxm=*max_element(vect.begin(),vect.end());
int ar[n];
for(int i=0;i<n;i++)ar[i]=0;
int k=0,flag=0,count=0;
for(auto it=vect.begin();it!=vect.end();++it)if(*it==maxm)count++;
vector::iterator temp;
vect.insert(vect.end(),vect.begin(),vect.end());
for(auto it=vect.begin();it!=vect.end();++it)
{
if(*it==maxm&&(k+1)<=count)
{
if(flag==0){temp=it;flag++;continue;}
ar[k]=it-temp-1;
printf("%d “,ar[k]);
k++;
temp=it;
}
}int sum=0;
for(int i=0;i<n;i++)
{
ar[i]=max(ar[i]-n/2+1,0);
sum=sum+ar[i];
}
printf(”%d",sum);
}
int main()
{

int t;
int n;
scanf("%d",&t);;
for(int i=0;i<t;i++)
{
    scanf("%d",&n);
    int ar[n];
    for(int j=0;j<n;j++)
    scanf("%d",&ar[j]);
    vector<int>vect(ar,ar+n);
    task(vect,n);
    printf("\n");;
}

return 0;
}`

Can anyone please tell me why I am getting a wrong ans for this question? Here is my code–

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,i,temp;
vector w;
vector max_index;
cin>>t;
while(t–!=0)
{
w.clear();
max_index.clear();
cin>>n;
int max_val=INT_MIN;
int k=0;
for(i=0;i<n;i++)
{
cin>>temp;
w.push_back(temp);
if(max_val<temp)
{
max_val=temp;
}

    }
    for(i=0;i<n;i++)
        if(w[i]==max_val)
            max_index.push_back(i+1);
    if(max_index[0]>n/2) k++;
    if(max_index.size()==1){
         k+=n-max_index[0];
         cout<<k<<endl;
         continue;
    }
    
    for(i=1;i<max_index.size();i++)
    {
        if(max_index[i]-max_index[i-1]-1>=n/2)
            k+=max_index[i]-max_index[i-1]-n/2;
    }
    if(n+max_index[0]-max_index[max_index.size()-1]-1>=n/2)
        k+=n-max_index[max_index.size()-1];
    cout<<k<<endl;

}

}

Thanks!

What is wrong in this please can anyone tell me

#include<bits/stdc++.h>

using namespace std;

int idx1,idx2,moves;

int c=0;

int main()

{

int t;

cin>>t;

if(t<1 || t>5)

    exit(0);

while(t!=0)

{

    int n;

    cin>>n;

    if(n<1 || n>100000 || n%2 != 0)

        exit(0);

    int size=n/2;    

    int ft[size];

    int lt[size];

    for(int i=1;i<=size;i++)

    {   

         cin>>ft[i];

         if(ft[i] < 1 || ft[i]>100000)

         exit(0);

    }     

    for(int j=1;j<=size;j++)

    {    cin>>lt[j];

         if(lt[j] < 1 || lt[j]>100000)

         exit(0);

    } 

     

    int max1=ft[1];

    idx1=1;

    for(int i=2;i<=size;i++)

    {

        if(ft[i]> max1)

        {

            max1=ft[i];

            idx1=i;

        }

    } 

    int idx2;

    int max2=lt[1];

    idx2=1;

    for(int i=2;i<=size;i++)

    {

        if(lt[i]> max2)

        {

            max2=lt[i];

            idx2=i;

        }

    }

    int count =0;

    if(max1 >= max2)

    {

        moves=size+1-idx1;

        idx2=size+1-moves;

        int i=idx2;

        while(i>=1)

        {

            for(int j=i;j<=size;j++)

            {   

                c=0;

                if(lt[j]<max1)

                    continue;

                else

                {

                   c=1;

                   break;

                }

                

            }

            if(c==0)

            {

                count++;

            }

            i--;

        }

    }   

    else

    {

        cout<<"0"<<endl;

        t--;

        continue;

    }

     t--;

    cout<<count<<endl;

    

}    

return 0;

}