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

Правка en1, от 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.

Теги median, exam

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский goovie 2015-06-25 19:53:31 849 Initial revision (published)