 # GMEDIAN Editorial (Unofficial)

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

## Problem:

For a sequence A,A,A,…,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 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

This video will help in finding nCr % mod ( https://www.youtube.com/watch?v=aGjfSTr_0AE&t= )

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

//