PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DYNAMIC PROGRAMMING, BINARY SEARCH, BINARY SEARCH TREES
PROBLEM:
Find the minimal real number A such that there are at least k ways to choose a subarray of length in [l, r] such that the average value of the subarray is at most A.
EXPLANATION:
We’ll binary search on the answer A. For a fixed A, we would like to find the number of ways to choose a good subarray. (that is a subarray of length in [l, r] and average value \le A)
The trick is we can subtract A from all the values of the array. Now, the problem reduces to finding the number of subarrays of length in [l, r] with nonnegative sum. This can be done with a binary search tree. (or order statistics tree)
Calculate the prefix sums of the array. We iterate from left to right and store the previous prefix sums into an order statistics tree. The condition that the subarray [l..r] has nonnegative sum is equivalent to s_{r} \ge s_{l - 1} where s_{i} is the sum of the first i elements. Thus, we just need to find the number of elements in the tree which is at most equal to s_{r}, which can be done in O(\log n).
Note that we have to ensure that the subarrays chosen have length in range [l, r], we’ll have to delete some values after some time and add some values late. This detail should be easy to figure out and the whole solution runs in O(n\log n \log a_{i}).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.