GMEDIAN Editorial (Unofficial)

Problem Link:

 <a href = ""> Contest </a>


 <b>Author</b>: <a href="">teja349</a> 

 <b>Editorialist</b>: <a href="">srvptk</a>

Difficulty: Easy

Prerequisites: Maths, Observation, Pre-computation


For a sequence A[1],A[2],A[3],…,A[N]. Find the number of good subsequences. A subsequence is good if for a subsequence
(k>0, 1 &lt= i1 &lt i2 &lt i3 &lt…&lt ik &lt= N ) has its median as an element of this subsequence.


First we have to sort our sequence.
We observe that:

  1. The median in a sequence will be formed with a single element if size of sequence if odd.
  2. The median in a sequence will be formed with two elements if size of sequence is even.
Another observation is:
  • For one element (ele) or two elements (ele1 and ele2) will form a median in a sorted sequence if there are equal number of elements on both sides of the element.
     <b> {k elements}, ele, {k elements} </b> 
     <b> {k elements}, ele1, ele2, {k elements} </b> 
For an arbitrary median (med) if the sequence is of the form:
    <b>{x elements}, med, {y elements} </b>

 Number of total subsequence having median <b>med</b> will be: 

   total_subseq = 0 

   for i=0 to min(x,y){ 

   total_subseq += x<b>C</b>i * y<b>C</b>i




For two elements to form a median which is in the sorted sequence, the two elements must be equal.

(ele1 = ele2)


If we perform the computation of :
  • total_subseq = 0
       for i=0 to min(x,y){ 
       total_subseq += x<b>C</b>i * y<b>C</b>i

    for every element, then it will exceed the time limit. So, we have to compute it earlier in the start.

    How to do that?

    Make an array Comp[1000][1000] where:

    • Comp[i][j] = 0
         for k=0 to min(i,j){ 
         Comp[i][j] += i<b>C</b>k * j<b>C</b>k

      Also compute the value of Combination nCr in the start for all values of n and r ranging from 1 to 1000.


      The maximum complexity will be for the computation of Comp array.

      It can be said to be O(N^3) but by adding a constraint, we can compute it in the required time.

      The constraint is:

      For every pair i and j, the value of Comp[i][j] will be computed only if:

      (i+j) &lt= 1000

      as they are a part of sequence whose maximum size can not be greater than 1000.

      Don’t forget to compute the result modulo (10^9+7) since the number may be large.


      Editorialist Solution

This video will help in finding nCr % mod ( )

Or else, one can read this article to compute nCr % mod in O(n*r) time using dynamic programming