Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### flame_boy's blog

By flame_boy, history, 10 months ago,

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

• +17

 » 10 months ago, # | ← Rev. 3 →   0 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. Codevoid solve() { int n, K; cin >> n >> K; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end()); a.push_back(a.back()); n = a.size(); int dp[n][n]; memset(dp, 0, sizeof(dp)); debug(a); vector pref_ok(n); pref_ok[0] = 1; for (int i = 1; i < n; i++) { if (pref_ok[i - 1] && a[i] - a[i - 1] <= K) pref_ok[i] = 1; } for (int j = 0; j < n; j++) dp[0][j] = 1; for (int i = 1; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (a[i] - a[i - 1] <= K) dp[i][j] += dp[i - 1][j]; if (a[j] - a[i - 1] <= K) { if (pref_ok[i - 1]) dp[i][j]++; for (int k = i - 2; k >= 0; k--) { if (a[i] - a[k] > K) break; dp[i][j] += dp[k][k + 1]; if (a[k + 1] - a[k] > K) break; } } } } cout << dp[n - 2][n - 1] - 2 << endl; } We can easily optimize it to $O(n^2log(n))$. Optimized Codevoid solve() { int n, K; cin >> n >> K; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end()); a.push_back(a.back()); n = a.size(); int dp[n][n]; memset(dp, 0, sizeof(dp)); debug(a); vector pref_ok(n); pref_ok[0] = 1; for (int i = 1; i < n; i++) { if (pref_ok[i - 1] && a[i] - a[i - 1] <= K) pref_ok[i] = 1; } vector pref_sum(n); pref_sum[0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1; int last_fail = 1e9; for (int i = 1; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (a[i] - a[i - 1] <= K) dp[i][j] += dp[i - 1][j]; if (a[j] - a[i - 1] <= K) { if(pref_ok[i-1]) dp[i][j]++; int k = min((int)(lower_bound(a.begin(), a.begin() + i,a[i] - K) - a.begin()),last_fail); if(k < i) { dp[i][j] += (i-2>=0 ? pref_sum[i-2]:0) - (k >= 1? pref_sum[k-1]:0); } } } if(a[i] - a[i-1] > K) last_fail = i-1; pref_sum[i] = pref_sum[i-1] + dp[i][i+1]; } cout << dp[n - 2][n - 1] - 2 << endl; } 
 » 8 months ago, # | ← Rev. 2 →   0 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 elementlet 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] <= kPLEASE REPLY IF YOU FIND ANY PROBLEM WITH THE LOGIC