GMEDIAN Editorial (Unofficial)

general
, , , ,
1

Problem Link:

 <a href = "https://www.codechef.com/NOV18B/problems/GMEDIAN"> Contest </a>

 

 <b>Author</b>: <a href="https://www.codechef.com/users/teja349">teja349</a> 

 <b>Editorialist</b>: <a href="https://www.codechef.com/users/srvptk">srvptk</a>

Difficulty: Easy

Prerequisites: Maths, Observation, Pre-computation

Problem:

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
A[i1],A[i2],A[i3],…,A[ik] (k>0, 1 &lt= i1 &lt i2 &lt i3 &lt…&lt ik &lt= N ) has its median as an element of this subsequence.

Explanation:

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: 


  <ul>
  <li>
   total_subseq = 0 


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


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


   }


  </li>
  </ul>

Observation:

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

(ele1 = ele2)

Optimization:

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


   }


  </li>
  </ul>

    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


   }


  </li>
  </ul>

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

      Complexity:

      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.

      Implementation

      Editorialist Solution

2

This video will help in finding nCr % mod ( Modulo Inverse For Competitive Programming | nCr % m in O( n ) | Little Fermat Theorem - YouTube )

3

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