Description:
Mohit wrote down a sequence containing distinct positive integers. Vishal wanted to reorder the elements to get a "mountain sequence". A sequence a0, a1, ..., an-1 is called a mountain sequence if there exists an index j, where 0 < j < n-1, such that the sequence a0, a1, ..., aj is strictly increasing, and the sequence aj, aj+1, ..., an-1 is strictly decreasing. A sequence is strictly increasing if each element is strictly greater than the element before it, and a sequence is strictly decreasing if each element is strictly less than the element before it. Shubham also wanted the resulting sequence to satisfy one additional rule. The absolute difference between each pair of adjacent elements must be less than or equal to K. Find the number of valid sequence modulo 10^9+7.
Input Format
The first line contains an integer T — number of test cases. ( 1 ≤ T ≤ 50). The first line of each test case contains two space-separated integers N, K, (1≤ N ≤ 1000, 1 ≤ K ≤ 1000000000). The second line contains N- space-separated distinct integers (1 ≤ Ai ≤ 1000000000).
Output Format
For each test case print the number of valid sequence mod 10^9+7 in a newline.
Sample Input 1
2 4 6 10 4 1 5 9 44 96 29 21 90 46 77 31 63 79
Sample Output 1
4 126
Explaining the whole idea is a bit difficult, I will just try to give you some idea. First sort the array, now the task is to find the number of subsequences from the first n-1 elements so that they can be put left to the maximum of the array, and the remaining elements go to the right (of course also has to satisfy that additional constraint)
say $$$dp_{i,j}$$$ stores the number of subsequences ending at the index $$$i$$$ satisfying the following condition:
$$$j > i$$$ and $$$a_j - a_p \le K$$$ where $$$p$$$ is the last unselected element in the prefix $$$a[1...i]$$$ (Note that I am calling the elements in the subsequence as selected and the rest as unselected).
You can refer to the below code to understand the transitions. This works in $$$O(n^3)$$$ time.
We can easily optimize it to $$$O(n^2log(n))$$$.
If we do transitions similar to above comment : maybe we can have O(n^2) PLEASE check if there is any problem with the logic
Terminology used in explanation : 1. Left elements : elements present to the left of maximum element and including the maximum element 2. Right elements : elements present to right of maximum element
let dp(i,j) : ways to distribute arrays element from index 1 to min(i,j)-1 to the left and right sides of the sequence given that smallest left element is arr[i] and smallest right element is arr[j]
Transitions : let g = min(i,j) — 1; dp(i,j) = ( dp(g,j) if arr[i]-arr[g] <=k ) + ( dp(i,g) if arr[j]-arr[g] <=k )
Final answer : sigma dp(n,i) for all i such that arr[n]-arr[i+1] <= k
PLEASE REPLY IF YOU FIND ANY PROBLEM WITH THE LOGIC