0 like 0 dislike
1,036 views

| 1,036 views

0 like 0 dislike

After analyzing 78 OA problems asked in Google for SDE role in 2023; this is one of the most difficult and interesting one which involves DP at its core!

You are given an array A of N elements and an integer K. A subsequence is good if it is a non-decreasing subsequence and the sum of its elements at least K.

Find the minimum length of a good subsequence, or return -1 if there is no such subsequence.

Notes:

A subsequence of array A is a sequence that can be derived from array  A by deleting some or no elements without changing the order of the remaining elements.
. For example, [2, 4, 6] is a subsequence of [1, 2, 3, 4, 5, 6, 7] but [3, 4, 1] is not.

• A subsequence is non-decreasing if every element in the subsequence is greater or equal to its previous element.

• The length of the subsequence is the number of elements in it.

Input Format

The first line contains an integer, N. denoting the number of elements in A.

The next line contains an integer, K, denoting the minimum sum of the subsequence elements.

Each line i of the N subsequent lines (where 0<i<N) contains an integer scribing A[i].

1<=N<=500
1<=K<=100000000

by Expert (111,530 points)
0 0
Please share the segment tree approach
0 like 0 dislike
O(N*N*N) Approach: vector> dp(n+1, vector(n+1, -1)); for(int i = 0; i < n; i++){ dp[i][1] = nums[i]; } int ans = 1e9; for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ if(nums[j] > nums[i]) continue; for(int k = 1; k < n; k++){ if(dp[j][k] != -1) { dp[i][k+1] = max(dp[i][k+1], nums[i] + dp[j][k]); if(dp[i][k+1] >= K){ ans = min(ans, k+1); } } } } }
by (140 points)