You are not logged in. Please login at www.codechef.com to post your questions!

×

# SHIVIGOD - EDITORIAL

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

CAKEWALK

# 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:

View Content

# 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 :)

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

This question is marked "community wiki".

asked 26 Jan, 18:57

68112
accept rate: 14%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,652
×177
×53
×31
×28
×16

question asked: 26 Jan, 18:57

question was seen: 67 times

last updated: 26 Jan, 19:12