@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;
}