@roshan06 @meluhan
Actually we have to consider a subarray of circular array (circular means Wn-i=Wi)
Now you have to find subarray that does not contain max element.
take eg:
elements—1 2 3 4 5 6 7 1 2 3 4 5
indexes-----0 1 2 3 4 5 6 7 8 9 10 11
so max element here is 7
so my target is to exclude this max element
The subarray found is 1 2 3 4 5 1 2 3 4 5 6
Starting at the index 7 ending at index 5.
now the length of the subarray is 11 so the ans is (11-(12/2)+1)=6
the possible first half could be-
1 2 3 4 5 1
2 3 4 5 1 2
3 4 5 1 2 3
4 5 1 2 3 4
5 1 2 3 4 5
1 2 3 4 5 6
so total 6 found as said by formula.
Also as said by @rioji it is true that if there is valid subarray than it is only one others will have l<n/2. Here in my example also only one valid subarray was found. so if you take several examples and check either there will be one valid subarray or none.
The important thing is understand the concepts and once you understand it you can frame your code.
1 Like
bro i used the same logic and i m also getting wrong answer
anyone tell what is wrong in this logic
can anyone please tell me what is wrong with my solution
https://www.codechef.com/viewsolution/30654376
Your code incorrectly outputs 2 for the following test case:
1
6
1 1 1 2 2 2
The correct answer is 1.
@nishantawasthi Your code also fails this test case. It outputs 0.
because we don’t need to rotate this that’s why it should be 0 ?
I haven’t solved it. I just compared your answers to another AC answer.
This AC solution gives 1
https://www.codechef.com/viewsolution/30680357
1 Like
ohh well thanks for that and tell me when you solve it please
Yes. The question states 0\leq k\lt N .
1 Like
https://www.codechef.com/viewsolution/30680907
My code is giving Runtime Error(SIGSEGV) can someone help me?
line 18 – for (int i = k; i < (n/2)+k; i++)
{int j=i%n;
if(arr[i<**err**>]==maximum)
I don’t know whats you approach is but i can tell you that value of i is getting out of the bound just note that place where i marked <err> i think u wanted to use j instead of i
hope it help
what will be the output for the case-
2 1 1 1 1 2
from above solution it should be 0.But if we move last 4 elements to start we get a solution (1 1 1 2 2 1) and also with last 5 elments (1 1 1 1 2 2) too we can get the answer.
Can you explain these cases.
1 Like
@tmwilliamlin Nice editorial, easy to comprehend. Thank you so much ! 
1 Like
Can anyone please help me out in my naive approach as why am i getting a Runtime error:-
#include
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
vector<int>a(n);
cin>>n;
int max=INT_MIN;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>max)
{
max=a[i];
}
}
int half=n/2;
int count =0;
int flag=0;
for(int i=0;i<n;i++)
{
int j,temp;
temp=a[n-1];
for(int j=n-1;j>0;j--)
{
a[j]=a[j-1];
}
a[0]=temp;
for(int k=0;k<half;k++)
{
if(a[k]==max){
flag=1;break;
}
}
if(flag==0)
count++;
}
cout<<count<<endl;
}
return 0;
}
can u explain me the setters solution please.tell me the logic used by the setter.
Can you please explain me the logic of your code. Why to subtract range from n/2 ??
I think actual output for this case is 3.
1
4
2 1 1 2
shift by k=1:(2,2,1,1)
shift by k=2:(1,2,2,1)
shift by k=3:(1,1,2,2)
Now ,First half does not contain any maximum element.
You are using two for loops , so the time complexity becomes (n^2) and it is more than 1 second , so find a proper solution in O(n).
I was little confused. You are right.