2020 Jan Platinum Problem 2 Non-Decreasing Subsequences

Official Problem Statement

Non-Decreasing Subsequences

Problem Statement:

Given a sequence of N (1 ≤ N ≤ 10,000) integers, determine the number of non-decreasing subsequences of length K (1 ≤ K ≤ N).

Solution:

The solution to this problem is to use dynamic programming. We can create an array dp[N][K] where dp[i][j] represents the number of non-decreasing subsequences of length j ending at index i. We can then fill the array using the following recurrence relation:

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] if arr[i] >= arr[i-1]

dp[i][j] = dp[i-1][j] otherwise

The base cases are dp[0][0] = 1 and dp[i][0] = 1 for all i.

The answer to the problem is the sum of all dp[N][K] values.

C++ Code:

1. include <bits/stdc++.h>

using namespace std;

int main() {

int N, K;
cin >> N >> K;
vector<int> arr(N);
for (int i = 0; i < N; i++) cin >> arr[i];

vector<vector<int>> dp(N, vector<int>(K + 1, 0));

for (int i = 0; i < N; i++) {
 dp[i][0] = 1;
 for (int j = 1; j <= K; j++) {
  dp[i][j] = dp[i-1][j];
  if (i > 0 && arr[i] >= arr[i-1]) {
   dp[i][j] += dp[i-1][j-1];
  }
 }
}

int ans = 0;
for (int i = 0; i < N; i++) {
 ans += dp[i][K];
}

cout << ans << endl;

return 0;

}