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

×

MEANARRAY - Editorial

PROBLEM LINK:

Contest
Practice

Setter- Adhyyan Sekhsaria
Tester- Adhyyan Sekhsaria
Editorialist- Abhishek Pandey

DIFFICULTY:

Easy

PRE-REQUISITES:

Intuition/Logic, Two-Pointers, Binary Search on Array

PROBLEM:

Given a non-decreasing array of length $N$, we need to tell number of sub-arrays whose arithmetic mean is less than $K$

QUICK EXPLANATION:

We first observe that the array is non-decreasing. 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 sub-arrays 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 sub-array, 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 sub-array 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 two-pointer approach to count remaining sub-arrays.

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 two-pointers. It is expected that you know the two-pointer algorithm. Please go to pre-requisites 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 sub-arrays! Remember-

$\because$ All elements are $< K$, their mean can never be $\ge K.$

Hence, we would include all the sub-arrays possible. In an array of length $N$, the number of sub-arrays is given by $Num=N*(N+1)/2$ where $Num$ is the number of sub-arrays (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 sub-arrays at once!

Now comes the tricky part.

Recall the explanation at quick section about two-pointer 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 sub-arrays ending till $pos$ are included in answer by formula above. We need to find how many more valid sub-arrays exist, i.e. how many valid sub-arrays 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 sub-arrays starting only from index $1$. We have also, already included sub-arrays ending upto $pos$. How many new sub-arrays did we got? Obviously, $pos2-pos$.

View Content

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_{i-1}$ (i.e. $pos2$ of previous index) and move backward until we find $pos2_i$!

This, is nothing but the basic concept of two-pointer 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 two-pointer approach, we only start at $pos2_{i-1}$ and find $pos2_i$, from there we find $pos2_{i+1}$ and so on. We can see that no element is visited twice in two-pointer 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$ ($1-based$ $indexing!$) and determine appropriate $pos2_i$ and directly add the number of sub-arrays 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 :).

View Content

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

Setter

View Content

Editorialist

View Content

$Time$ $Complexity=$ $O(N)$

CHEF VIJJU'S CORNER :D

1. No one asked me why we iterate only upto $i=pos$ when I said -

"Thus, we can loop from $i=1$ to $i=pos$ ($1-based$ $indexing!$) and determine appropriate $pos2_i$ and directly add the number of sub-arrays to the answer (using the formula I gave above :) )."

View Content

2. Some practice problems-

This question is marked "community wiki".

asked 04 Jul '18, 01:25

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 28 Sep '18, 12:12

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

We first observe that the array is non-decreasing. _/\_ Observations are key to success.

(21 Jul '18, 00:54) aryanc4036★
1

HAHAHAHAHHAHA. Happened to me as well xD. I spent 15 minutes at this question and then I saw non-decreasing. And I immediately sent the setter a message that he is way too cruel to not put non-decreasing in bold xD

(21 Jul '18, 00:56) vijju123 ♦♦5★

Upd - Since it is already bumped again. So sharing one more approach.
Generalised Soln

Soln starts here

I 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[l-1] < 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.).
Then By iterating over l=0 to n. With logn time to find no of elements less than prefix[i] are is answer for no of subarray with starting index l.

Now the problem reduces to counting no of inversions in an array. Ref here.

Soln ends here

//Ignore this.

View Content
link

answered 21 Jul '18, 01:10

aryanc403's gravatar image

6★aryanc403
2.5k1516
accept rate: 10%

edited 28 Sep '18, 14:36

1

Good job dear. Well done :)

(21 Jul '18, 21:09) vijju123 ♦♦5★
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) taran_14076★

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$$

link

answered 21 Jul '18, 01:30

the_extractor's gravatar image

4★the_extractor
1527
accept rate: 10%

Yes, thats also correct :)

(21 Jul '18, 01:33) vijju123 ♦♦5★

@aryanc403 we can also use BIT with coordinate compression

link

answered 21 Jul '18, 21:40

hackerwizard's gravatar image

6★hackerwizard
453
accept rate: 16%

Relevant tutorial ??

(21 Jul '18, 21:57) aryanc4036★

See my code https://www.codechef.com/viewsolution/19289787 for implementation.

(21 Jul '18, 23:38) hackerwizard6★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,038
×847
×278
×98
×15

question asked: 04 Jul '18, 01:25

question was seen: 673 times

last updated: 28 Sep '18, 14:36