fork download
copy 
  1. /*
  2. QUESTION 4: Counting Smooth Difference Subsequences
  3.  
  4. Problem Statement:
  5. You are given an integer array nums.
  6.  
  7. A subsequence is called smooth if the differences between adjacent selected
  8. elements never decrease.
  9.  
  10. For subsequence:
  11. b1, b2, b3, ..., bk
  12.  
  13. It must satisfy:
  14. b2 - b1 <= b3 - b2 <= b4 - b3 <= ...
  15.  
  16. Return the number of smooth subsequences having length at least 2.
  17.  
  18. Hard Constraints:
  19. 1 <= n <= 1000
  20. -1e9 <= nums[i] <= 1e9
  21. Answer modulo 1e9 + 7
  22.  
  23. Example:
  24. nums = [1, 3, 6]
  25.  
  26. Expected Output:
  27. 4
  28.  
  29. Explanation:
  30. Valid subsequences:
  31. [1, 3]
  32. [1, 6]
  33. [3, 6]
  34. [1, 3, 6]
  35.  
  36. Brute Force:
  37. Generate all subsequences and check adjacent differences.
  38.  
  39. Time Complexity:
  40. O(2^n * n)
  41.  
  42. Optimized Approach:
  43. Let dp[j][i] be the number of valid subsequences ending with nums[j], nums[i].
  44.  
  45. To append nums[i] after nums[h], nums[j], we need:
  46. nums[j] - nums[h] <= nums[i] - nums[j]
  47.  
  48. For each middle index j:
  49. - Store all previous differences ending at j.
  50. - Sort them.
  51. - Use prefix sums and binary search to count valid extensions.
  52.  
  53. Time Complexity:
  54. O(n^2 log n)
  55.  
  56. Space Complexity:
  57. O(n^2)
  58. */
  59.  
  60. #include <bits/stdc++.h>
  61. using namespace std;
  62.  
  63. class Solution {
  64. public:
  65.     static const int MOD = 1000000007;
  66.  
  67.     int countValidSubsequences(vector<int>& nums) {
  68.         int n = nums.size();
  69.  
  70.         vector<vector<int>> dp(n, vector<int>(n, 0));
  71.         long long ans = 0;
  72.  
  73.         for (int j = 0; j < n; j++) {
  74.             vector<pair<long long, int>> previous;
  75.  
  76.             for (int h = 0; h < j; h++) {
  77.                 long long diff = 1LL * nums[j] - nums[h];
  78.                 previous.push_back({diff, dp[h][j]});
  79.             }
  80.  
  81.             sort(previous.begin(), previous.end());
  82.  
  83.             vector<long long> diffs;
  84.             vector<int> pref;
  85.  
  86.             for (auto &p : previous) {
  87.                 diffs.push_back(p.first);
  88.  
  89.                 if (pref.empty()) pref.push_back(p.second);
  90.                 else pref.push_back((pref.back() + p.second) % MOD);
  91.             }
  92.  
  93.             for (int i = j + 1; i < n; i++) {
  94.                 long long curDiff = 1LL * nums[i] - nums[j];
  95.  
  96.                 int ways = 1;
  97.  
  98.                 int pos = upper_bound(diffs.begin(), diffs.end(), curDiff) - diffs.begin();
  99.  
  100.                 if (pos > 0) {
  101.                     ways = (ways + pref[pos - 1]) % MOD;
  102.                 }
  103.  
  104.                 dp[j][i] = ways;
  105.                 ans = (ans + ways) % MOD;
  106.             }
  107.         }
  108.  
  109.         return ans;
  110.     }
  111. };
  112.  
  113. int main() {
  114.     Solution sol;
  115.  
  116.     vector<int> nums = {1, 3, 6};
  117.  
  118.     cout << sol.countValidSubsequences(nums) << endl;
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/ss10ZA
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!