Unnecessary wasting precious data structures
This problem has weak test cases.Take for instance-
1
14
2 1 1 1 1 1 1 1 2 1 1 1 2 1
Tester’s Solution gives the correct answer =1 but CodeChef: Practical coding for everyone gives answer=0. I think the @raja1999 should look into this matter.
4 Likes
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 
2 Likes
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.
1 Like
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.