I am getting a time limit exceeded on my code. Can someone please see it and tell me how I can optimize it? CodeChef: Practical coding for everyone
Edit: I have also tried using “reserve” keyword on the vector to allocate storage at once. But I am still getting the time limit exceeded error. CodeChef: Practical coding for everyone
if someone knows these precious ds and can implement the problem using it in only 5 to 7 minutes , then i think its not a wastage 
Many solutions like this have been given AC
so is this solution is always true means how and why this code runs?
please tell me whats wrong in my code…
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,arr[100009];
int main(){
cin>>t;
while(t--){
cin>>n;
ll mid=n/2,high=0;
for(int i=0; i<n; i++){
cin>>arr[i];
if(high<arr[i]) high=arr[i];
}
ll counth=0,p=0;
for(int i=0; i<n; i++){
if(arr[i]==high) counth++;
}
long long int o_cnt=0,z_cnt=0;
ll ans=0;
if(counth>mid/2) cout<<0<<"\n";
else{
for(int i=0;i<n;i++){
if(arr[i]==high) o_cnt++;
else if(arr[i]!=high && (i+1==n || arr[i+1]==high)){
ans=ans+((z_cnt+1)*o_cnt);
z_cnt=0;
}
else z_cnt++;
}
cout<<ans<<"\n";
}
}
}
very weak TC …
for above code this test case:
1
10
1 1 1 1 1 5 1 1 5
gives answer “0” but answer is “1”
Can Anyone suggest some easy problems similar with this problem?
I saw in your code that in the last condition, you used:
if(a[0] == a[n-1])
cout<<n<<endl;
since a is the sorted array, hence a[n-1] points to the max sweetness. since a[0]==a[n-1], means a[0] too refers to the max. Now, if the array is:
2 1 1 1 1 1 2
how is the answer 6? It should be 2, I guess:
1 1 1 2 2 1
1 1 1 1 2 2
Can you please explain?
My solution.
int main(){
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int sum = 0;
int flag;
vector<int> a(n);
vector<int> temp(n);
vector<int> indices;
for(int i =0; i < n; i++)
{
cin >> a[i];
}
int max = *max_element(a.begin(), a.end());
for(int i= 0; i < n; i++)
{
if(a[i] == max) indices.push_back(i);
}
int range = *max_element(indices.begin(), indices.end()) - *min_element(indices.begin(), indices.end());
if(range < (n/2))
cout << (n/2) - range << endl;
else
cout << 0 << endl;
}
return 0;
}
Let me know if you have any doubts.
thanks a lot man
Can someone please explain me the output for:
1 2 3 1 2 1 8 8.
Yes. The solution is incorrect. Judge has weak test cases.
can u explain please @tmwilliamlin
Notice that the elements with maximum value in WWW separate WWW into several subarrays which don’t contain the maximum element. Let the set of such subarrays be SSS. For example, if W=[1,7,2,3,7,4,7,3,2,3,1,1,2,2]W=[1, 7, 2, 3, 7, 4, 7, 3, 2, 3, 1, 1, 2, 2]W=[1,7,2,3,7,4,7,3,2,3,1,1,2,2], SSS consists of W[2,3]] , W[5,5], and W[7,14]***** (the last subarray wraps around to the beginning).
Why this naive method is giving wrong answer?
I have made a separate array of indices of maximum element and have rotated that array only by 1 index each and incremented answer when all the indices are >=n/2.
Please, have a look at it solution.
@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.
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