Observation, Binomial Coefficients.
Given a sequence A1,A2,…,AN. Find the number of subsequences in which the median of the subsequence is present in that subsequence, modulo 1000000007.
Since we have to sort each subsequence to find its median, we will sort our original sequence (i.e. A1,A2,…,AN) at first itself. The ordering won’t change.
For example, the good (desired) subsequences in the sequence [9,5,7,6,8,1] are same as that in the sequence [1,5,6,7,8,9].
The subsequences having odd length will definitely qualify to be one of our good subsequence (as in the subsequences with odd length, the element at the middle position is the median of the subsequence itself).
The subsequences with even length will qualify as good subsequence if and only if the middle two elements are same. It is so because the array is already sorted. View the content below in case you didn’t understand this statement.
Click to view
Let us suppose the middle elements found in the subsequence B1,B2,…,Bz be x and y.
Now the arithmetic mean of x and y = (x+y)/2 = (let am). am will only exist in the subsequence if there is a number greater than or equal to x or less than or equal to y. Since we have array in the sorted order, this is only possible when x=y, (i.e. both the middle elements are same)
So our answer to this problem is : (Number of subsequences having odd length) + (Number of good subsequences having even length with both the middle elements equal)
It is clearly written in this subtask: A is a permutation of integers 1 through N. Also, the number of elements in the sequence A is N which means each element from 1 to N is present once and only once. This tells us that there is no repetition of any number. So, no subsequence having even length will be counted.
So, answer to this subtask = Number of subsequences having odd length
= Number of ways of selecting 1 out of n elements + Number of ways of selecting 3 out of n elements + Number of ways of selecting 5 out of n elements + … + Number of ways of selecting n or (n-1) out of n elements
=nC1 + nC3 + nC5 + ..... + nCn (if ‘n’ is odd) or nC1 + nC3 + nC5 + ..... + nC(n-1) (if ‘n’ is even)
where nCx denotes the number of ways of choosing x elements out of n elements
See the proof below if you didn’t understand this completely
Click to view
(1+x)^n = nC0 + nC1*x + nC2*x^2 + nC3*x^3 + ... + nCn*x^n = (let S)
putting x = 1 and x = -1 one by one, we get
2^n = nC0 + nC1 + nC2 + nC3 + ... + nCn 0 = nC0 - nC1 + nC2 - nC3 + ... + (-1)^n * nCn
subtracting these two equations,
2^n= 2(nC1 + nC3 + ... + nCn) (if n is odd) or 2(nC1 + nC3 + ... + nC(n-1))
Therefore, nC1+nC3+nC5+.....+nCn or nC(n-1)
= 2^n / 2
Second and Third Subtask:
The tricky part of this question is when the elements in the sequence starts repeating. In this case, we have to find the number of subsequences having even length.
To find the subsequences of even length to be a good subsequence, we traverse through each element which is repeated at least once. For this element to be our median element in one of the subsequences of even length, we must have at least k elements at its index’s left and we must have at least k elements at the other element index’s right (Note that our array was sorted), where k is a non-negative integer.
An example is provided in the section below in case you didn’t understand the lines written above:
Click to view
Consider the sequence(A) : [1,2,2,2,2,3].
Here number of elements (N) = 6.
So, number of subsequences having odd length = 2^(N-1) = 2^5 = 32
Now, to count the number of good subsequences of even length(considering 0-based indexing):
Element at index 1 and 2 are same (2)
So, these 2 elements do form an even length good subsequence of length 2 (i.e. [2,2])
Now, number of elements at left of index 1: 1
Number of elements at right of index 2: 3
Since minimum of these two is 1, we can choose 1 element from left of index 1 and 1 element from right of index 2 to form subsequences of length 4
So, number of ways of forming good subsequences of even length: 1C1 * 3C1 = 1 * 3 = 3
which are: [1,2,2,2],[1,2,2,2] and [1,2,2,3],
Again, elements at index 1 and index 3 are same . Repeat this process until the left index reaches n-2 and right index reaches n-1
Following this process, we get number of good subsequences having even length = 22
So, 32 + 22 = 54, which will be our answer to this sequence
Now, Calculating nCx in each iteration, we may have difficulties passing the time limit provided in the problem. To reduce the time complexity to pass the given time limit, we have to observe the given fact:
Let the repeating elements be found at index i and j
Suppose, there are m elements at the left of the index i and n elements at the right of index j.
So, number of good subsequences: 1 (good subsequence of length 2) + mC1 * nC1 (good subsequences of length 4) + mC2 * nC2 (good subsequences of length 6) + … + mCmin(m,n) * nC(min(m,n)).
By Vandermonde’s identity we can sum up this value as ***(m+n)C(min(m,n))***, details of which can be found here :Vandermonde’s Identity.
Calculating queries of the type nCr % 1000000007 can be solved by precalculating nCr % 1000000007 upto n = whatever you need . Details of this can be found here: nCr % p in O(1)
Time Complexity = O(N^2) (Enough to pass all the subtasks)
Editorialist’s Solution: https://www.codechef.com/viewsolution/21611480