Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! need help in Problem B

help
,
1

Why is my code here is showing runtime error, I checked it thoroughly. Can anyone suggest any improvement.
Any sorts of debugging or other way to solve this problem is appreciated.

Question link: - Problem - B - Codeforces

My Solution : -
#include
#include<bits/stdc++.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include
#define wl int t;cin>>t;while(t–)
#define l long
#define ll long long
#define ul unsigned long
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
const unsigned int m= 1000000007;

    int main()
    {
    	fast
    	wl
    	{
    		int n,k;
    		cin>>n>>k;
    		
    		int a[n];
    		for(int p=0;p<n;p++)
    		 cin>>a[p];
    		 
    		
    		 int s = n-k;
    		 int max =0, le=0,j,i;
    		 for( i= 0; i<=s; i++)
    		 {   
    		    int c=0;
    		 	for( j=i+1;j<=j+k-3;j++)
    		 	{   
    		 		if(a[j]>a[j-1] && a[j]>a[j+1])
    		 		 	c++;
    				
    			 }
    			 
    			 if(c>max)
    			  {
    			  max = c;
    			   le = i+1;
    		      }
    		 	
    		 }
    		 
    		 cout<<max+1<<" "<<le<<endl;
    		
    		
    	}
    	return 0;
    }
2

I think you might get TLE with this approach…what verdict did you get when you submitted it ?

1 Like
3

There are many errors. You have used wrong condition in second for loop (j<=j+k-3). Even if you correct it, this will give TLE as 3≤k≤n≤2⋅10^5. Your comp is O(k*n).
You can see the solution of other people or wait for editorial.

1 Like
4

#include <bits/stdc++.h>
using namespace std;

#define lld long long int

int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lld t;
cin>>t;
while(t–)
{
lld n,k,i;
cin>>n>>k;
lld arr[n+1];
for(int i=1;i<=n;i++)
cin>>arr[i];
int peaks=0,res=1;
unordered_set s;
for(i=2;i<k;i++)
{
if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
{
peaks++;
s.insert(i);
}
}
int start=2;
for(i=k;i<n;i++)
{
if(s.find(start)!=s.end())
s.erase(s.find(start));
if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
{
s.insert(i);
//cout<<i<<" “<<s.size()<<” in\n";
}
if(peaks<s.size())
{
peaks=s.size();
res=start;
//cout<<peaks<<" “<<start<<”\n";
}
start++;
}
//cout<<"\n";
cout<<peaks+1<<" “<<res<<”\n";
}
}

1 Like
5

I got RE.

6

Thank you so much @sebastian I got my mistake…appreciate it brother :relaxed:

7

Your welcome :slightly_smiling_face:

8

don’t you think this line doesn’t make any sense instead use for( j=i+1;j<i+k-1;j++). Moreover still it will give tle so use prefix sum and for help you may check my submission Submission #77818057 - Codeforces

1 Like
9

I don’t understand why you need 2 loops, but here’s what I did:

I took an array peak[i] which tells if index i is peak or not.

decrement k twice, so you don’t have to worry about the boundary peak condition.

Now, use a sliding window of length k, and keep updating the answer, when you find, total peaks in sliding window is more than max_so_far.

Here’s the code:

1 Like
10

I got it… thanks :relaxed: :relaxed: