PROBLEM LINK:Setter Adhyyan Sekhsaria DIFFICULTY:Easy PREREQUISITES:Intuition/Logic, TwoPointers, Binary Search on Array PROBLEM:Given a nondecreasing array of length $N$, we need to tell number of subarrays whose arithmetic mean is less than $K$ QUICK EXPLANATION:We first observe that the array is nondecreasing. Hence, we find upto which position, all numbers are $< K$. As all numbers are $< K \implies $ their mean is also $< K$. $\therefore$ ALL subarrays upto that length are to be counted. We can simply use the formula of "Number of subarrays in an array of length $N$= $N*(N+1)/2$. for this. After that, we notice this if we keep more elements $< K$ we keep in the subarray, we can keep a higher number of elements $\ge K$ without having mean become $\ge K$. In other words, say we reached a position/index $pos$ upto which we were able to formed a valid subarray after including all elements $< K$. If we remove one of the elements $< K$, we might have to go backwards (i.e. remove an element $\ge K$) and can definitely not go forward (i.e. include another element $\ge K$). This simple observation allows us to use twopointer approach to count remaining subarrays. EXPLANATION:The editorial will be divided into $2$ sections. One will focus on part where "All elements are $< K$" and the second section will use that and give further solution using twopointers. It is expected that you know the twopointer algorithm. Please go to prerequisites if you dont know and check links there :) 1. If all elements are $< K$ This is the first step towards solution. What will we do if all elements are $< K?$ Obviously, include ALL possible subarrays! Remember $\because$ All elements are $< K$, their mean can never be $\ge K.$ Hence, we would include all the subarrays possible. In an array of length $N$, the number of subarrays is given by $Num=N*(N+1)/2$ where $Num$ is the number of subarrays (obviously!). But, how can we apply this to a general array? Give it a thought first, before proceeding for discussion in next section. Using results above & Two Pointers Recall that our array is sorted! This means, we can easily find a position, say $pos$ such that all elements up to $pos$ are $< K$. We can use the above formula to directly count those many subarrays at once! Now comes the tricky part. Recall the explanation at quick section about twopointer approach. The more elements $< K$ we have, the more elements $\ge K$ we can add, and still not have mean $\ge K$. Check the scenario below. Say we are currently trying to count those valid sub arrays, which start from index $1$ (we will generalize later). All elements till position/index $pos$ are $< K$. All subarrays ending till $pos$ are included in answer by formula above. We need to find how many more valid subarrays exist, i.e. how many valid subarrays exist with at least one element $\ge K$. Lets say, we kept travelling ahead of $pos$, and arrived at a position $pos2$ after which we cannot add any more element $\ge K$ (because it will make mean $>K$). Recall we are currently talking about subarrays starting only from index $1$. We have also, already included subarrays ending upto $pos$. How many new subarrays did we got? Obviously, $pos2pos$. Now, lets say I want to calculate similarly for index $2$. If I do everything again, then finding new position of $pos2$ for every index will take lot of time, and make complexity $O({N}^{2})$, which time outs! Can we somehow use the data of index $1$ to determine data of index $2?$. Yes! We can! Recall what I have been saying till now since the quick explanation section! If we reduce number of elements $< K$, we can definitely NOT include any more elements $\ge K$. This means that $pos2$ for index $2$ is not more than $pos2$ for index $1$! Let me denote $pos2_i$ to represent "$pos2$ calculated for index $i$". Now, $pos2_1 >pos2_2 >pos2_3...$. So, what if, instead of starting from $i$, going to $pos$ and from there finding $pos2_i$, why dont we start at $pos2_{i1}$ (i.e. $pos2$ of previous index) and move backward until we find $pos2_i$! This, is nothing but the basic concept of twopointer which brings the complexity down from $O({N}^{2})$ to $O(N)$. In $O({N}^{2})$ approach, we start from $i$, go to $pos$ and from there find $pos2_i$ and repeat all this again for next index, while in twopointer approach, we only start at $pos2_{i1}$ and find $pos2_i$, from there we find $pos2_{i+1}$ and so on. We can see that no element is visited twice in twopointer approach, while in $O({N}^{2})$ approach, all elements are visited multiple times ,again and again which wastes time. Thus, we can loop from $i=1$ to $i=pos$ ($1based$ $indexing!$) and determine appropriate $pos2_i$ and directly add the number of subarrays to the answer (using the formula I gave above :) ). A formal implementation is given below, but I request you to first to first yourself draft atleast an informal implementation of above idea, and compare yours with ours :). SOLUTION:In case the links dont work, the solutions are also pasted in tabs below for reference. This is, so nobody has to wait while @admin references the links :) $Time$ $Complexity=$ $O(N)$ CHEF VIJJU'S CORNER :D1. No one asked me why we iterate only upto $i=pos$ when I said  "Thus, we can loop from $i=1$ to $i=pos$ ($1based$ $indexing!$) and determine appropriate $pos2_i$ and directly add the number of subarrays to the answer (using the formula I gave above :) )." 2. Some practice problems
This question is marked "community wiki".
asked 04 Jul '18, 01:25

Upd  Since it is already bumped again. So sharing one more approach. Soln starts hereI have subtracted k from all elements. And then made a prefix array.
Now subarray l,r has average less than k. then prefix[r]prefix[l1] < 0 . Because this value is equivalent to sum from l to r  k*(no of elements in this range)
Which can be done in (n*logn) (Suggestions required.). Now the problem reduces to counting no of inversions in an array. Ref here. Soln ends here//Ignore this. answered 21 Jul '18, 01:10
1
Good job dear. Well done :)
(21 Jul '18, 21:09)
1
I too solved for general array. I didn't use prefix array, but compressed values to make segment tree. By the way, I think this DS is called Order Statistic Tree.
(21 Jul '18, 22:24)

I subtracted $K$ from each element in the array and took the mean as $0$ to make things a bit simpler: https://www.codechef.com/viewsolution/19285196 This works because: $$\frac{\sum_{i = 1}^n a_i}{n} = k \implies \frac{\sum_{i = 1}^n a_i  n \times k}{n} = 0 \implies \frac{\sum_{i = 1}^n (a_i  k)}{n} = 0$$ answered 21 Jul '18, 01:30

@aryanc403 we can also use BIT with coordinate compression answered 21 Jul '18, 21:40
Relevant tutorial ??
(21 Jul '18, 21:57)
See my code https://www.codechef.com/viewsolution/19289787 for implementation.
(21 Jul '18, 23:38)

We first observe that the array is nondecreasing. _/\_ Observations are key to success.
HAHAHAHAHHAHA. Happened to me as well xD. I spent 15 minutes at this question and then I saw nondecreasing. And I immediately sent the setter a message that he is way too cruel to not put nondecreasing in bold xD