SHIVIGOD - EDITORIAL

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Kunal Jain
Tester: Kunal Jain, Taranpreet Singh
Editorialist: Akash Bhalotia

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Prefix sums, Sliding Window.

PROBLEM:

Given an array of length N, find the maximum average of the numbers among all subarrays of length between A and B, inclusive.

CONSTRAINTS:

  • 1 \leq T \leq 5
  • 1 \leq N \leq 1000
  • 0 \leq arr[i] \leq 10^{10}

QUICK EXPLANATION:

Compute prefix sums of the array. For all subarrays of size in range A to B, compute the average of the elements efficiently using prefix sums and print the maximum of all these averages.

EXPLANATION:

  • Looking at the constraints, one can
    guess that an O(N^2) solution should work.
  • Remember that a subarray is just like a substring, a contiguous sequence of elements in an array.
  • Let’s consider every subarray of size A to B. We can do this by running two nested loops.
  • We can compute the sum of every such subarray and divide it by its size to get the average, maintaining the max average each time.
  • If we do it naively, i.e., calculate the sum of each subarray each time using a separate loop, its complexity increases to O(N^3), which shouldn’t pass in the ideal case.
  • What we can do is to maintain a prefix sums array. This way we can get the sum of elements of a subarray in constant time, improving the complexity by a factor of N, now making it O(N^2), which is sufficient to work here.
  • Lastly, don’t forget to use a 64-bit data type like double or long to store the values.

COMPLEXITY:

  • Time Complexity: O(N^2) per test case.
  • Space Complexity: O(N) per test case.

ALTERNATIVE APPROACH:

Using Sliding Window:

Click to view

For a subarray of size x, run a sliding window of size x through its elements to get their sum efficiently. Do this for every x in range A to B, each time maintaining the maximum average. This too takes O(N^2).

AC SOLUTIONS:

SIMILAR PROBLEMS:

Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :slight_smile:

Thanks to @taran_1407 and @vijju123 for their constant guidance and support.

1 Like
2

I guess we can answer it in O(N) , just output the maximum element :slight_smile:
Note:-This only works if there were no constraints on the range , i.e, A=1;B=N-1.

1 Like
3

Yes, since the subarray has to be of length between A and B (both inclusive), we can’t do it in O(N). Note that A and B are the range for the length of the subarray, and not the range for the array elements lying between A and B. So 1 \leq A \leq B \leq N :slight_smile:

1 Like
4

Hi what is wrong with this O(N(B-A)) time complexity solution? Is the test case wrong?
Basically I am using a hash map to store the sum and computing the average on the fly.
What is wrong with this? Please help

https://www.codechef.com/viewsolution/40454208

5

Thanks for explanation you had explained everything very nicely and the problems you had attached are also good !

1 Like
6

You can see my submission i had used sliding window approach which is very easy to implement and think
Good luck !

7

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

int main() {
int t;
cin>>t;
while(t–)
{
int n,a,b,i,j;
cin>>n>>a>>b;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
double avg,temp;
avg=0.0;
for(i=a;i<=b;i++)
{
temp=0;
for(j=0;j<i;j++)
{
temp=temp+arr[j];
}
avg=max(avg,temp/i);
for(int j=i;j<n;j++)
{
temp = temp + arr[j]-arr[j-i];
avg = max(avg,temp/i);
}
}
cout<<setprecision(6)<<avg<<endl;
}
return 0;
}
What is wrong in this code?. The sample test case is not running. Can anyone tell the corrections?

8

Sir please share your code link of O(n)

10

use fixed instead of setprecision(6)

11

Can anyone tell me why its giving WA for all the subtasks. I tried with example testcase and the answer is correct.

Code

1 Like
12

You forgot to define variables with long long int (look at constraints).
Your AC solution - Click here

1 Like
13

Hey man thankyou so much :grin:

1 Like