Median related problem: Count all contiguous subsequences of given sequence of which median is bigger than b

Revision en1, by goovie, 2015-06-25 19:53:31

Hello everyone. Here is problem I recently encountered on 'Algorithm and data structures' course exam. The problem statement is:

You are given a sequence a1,a2,...,an, and a number b. Your task is to find algorithm which counts all pairs (l,r) such that median of sequence a(l),a(l+1),..,a(r) is bigger than b.

My solution on exam was O(n^2logn) which used order statistics tree. Other solutions were

  • O(n^2) — used sorting to check median of pair in constant time

  • O(nlogn) — related to counting inverses in permutation.

And surprisingly someone came up with O(n) solution. So here is my question, can anyone tell me about this solution to the problem? I'm quite curious how this can be done in linear time.

Tags median, exam

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English goovie 2015-06-25 19:53:31 849 Initial revision (published)