Largest Subsequence

Moderate
0/80
0 upvote
Asked in company
D. E. Shaw India Private Limited

Problem statement

You are given an array of integers 'A' of size 'N' and a maximum score 'M'.


The score of a subsequence [ A[i1-1], A[i2-1] ... A[ik-1] ] is defined as the sum of ( i * k + A[i-1] ) for each element in the subsequence, where 'i' is the 1-based index of the element in the original array 'A' and 'k' is the length of the subsequence.


Your task is to find the length of the largest subsequence whose score is less than or equal to 'M'.


For Example : 
Let 'N' = 4, 'A' = [3, 5, 1, 2] and 'M' = 20.
Let's check if a subsequence of length k = 2 is possible. To minimize the score, we choose the elements that have the smallest contribution ( i * k + A[i-1] ).
The contributions for k = 2 are:
For index 1 (value 3): 1 * 2 + 3 = 5
For index 2 (value 5): 2 * 2 + 5 = 9
For index 3 (value 1): 3 * 2 + 1 = 7
For index 4 (value 2): 4 * 2 + 2 = 10
The two smallest contributions are 5 and 7. The minimum score for a subsequence of length 2 is 5 + 7 = 12.
Since 12 <= 20, a subsequence of length 2 is possible.
Let's check for k = 3. The contributions would be ( i * 3 + A[i-1] ). The sum of the three smallest contributions is (1*3+3) + (3*3+1) + (2*3+5) = 6 + 10 + 11 = 27.
Since 27 > 20, a subsequence of length 3 is not possible.
Therefore, the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains two space-separated integers, 'N' and 'M'.
The second line of input contains 'N' space-separated integers, representing the elements of array 'A'.
Output Format : 
Return an integer representing the length of the largest subsequence whose score is less than or equal to 'M'.
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
1 <= 'N' <= 10^5
1 <= 'M' <= 10^18
1 <= A[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
5 40
10 2 5 8 1
Sample Output 1 :
3
Explanation of sample input 1 :
Let's check if a subsequence of length k = 3 is possible. To minimize the score, we choose the elements that have the smallest contribution ( i * k + A[i-1] ).
The contributions for k = 3 are:
- Index 1 (value 10): `1 * 3 + 10 = 13`
- Index 2 (value 2): `2 * 3 + 2 = 8`
- Index 3 (value 5): `3 * 3 + 5 = 14`
- Index 4 (value 8): `4 * 3 + 8 = 20`
- Index 5 (value 1): `5 * 3 + 1 = 16`
The three smallest contributions are 8, 13, and 14.
The minimum score for a subsequence of length 3 is the sum of these contributions: 8 + 13 + 14 = 35.
Since 35 <= 40, a subsequence of length 3 is possible.
Similarly, it can be shown that a subsequence of length 4 is not possible.
Thus, the largest possible length is 3.
Sample Input 2 :
6 100
1 2 3 4 5 6
Sample Output 2 :
5
Hint

For a fixed 'k', how do you find the minimum possible score?

Approaches (1)
Binary Search

Approach:

  • The problem asks for the maximum possible length 'k'. This structure suggests that we can use binary search on the answer 'k', where 'k' ranges from 0 to 'N'.
  • For the binary search to work, we need a monotonic property. Let min_score(k) be the minimum possible score for a subsequence of length 'k'. If min_score(k) > M, then for any k' > k, it must be that min_score(k') > M. This is because both the number of terms in the sum and the value of each term (i * k + A[i-1]) increase with 'k'. This monotonic property allows us to binary search.
  • Our binary search will require a helper function, is_possible(k), that checks if a subsequence of length 'k' can have a score less than or equal to 'M'.
  • To implement is_possible(k):
    • For a fixed 'k', the score is the sum of i * k + A[i-1] for 'k' chosen indices.
    • To minimize the total score, we should choose the 'k' elements that have the smallest values of i * k + A[i-1].
    • We can create a temporary array to store these N possible contribution values.
    • Then, we find the sum of the smallest 'k' values in this temporary array.
    • If this sum is less than or equal to 'M', is_possible(k) returns true; otherwise, it returns false.

Algorithm:

  • Initialize low = 0, high = N, and ans = 0.
  • Start a while loop that runs as long as low <= high.
    • Calculate k = low + (high - low) / 2.
    • If k == 0, continue the loop.
    • Check if a subsequence of length 'k' is possible:
      • Create a temporary array, COSTS, of size 'N'.
      • For each index i from 1 to N, calculate COSTS[i-1] = A[i-1] + i * k.
      • Find the sum of the 'k' smallest elements in COSTS. This can be done efficiently in O(N) time using a selection algorithm (like nth_element). Let this sum be current_score.
    • If current_score <= M:
      • A subsequence of length 'k' is valid. We store this as our potential answer and try for a larger length.
      • Set ans = k and low = k + 1.
    • Else (current_score > M):
      • The length 'k' is too large. We need to try a smaller length.
      • Set high = k - 1.
  • Return ans.
Time Complexity

O(N * log(N)), where 'N' is the number of elements in the array 'A'.

We perform a binary search on the answer, which can range from 0 to 'N'. This contributes a factor of O(log N). For each candidate length 'k' in our search, we must verify if it's possible. This check involves creating a temporary array of costs of size 'N' and finding the sum of its 'k' smallest elements. This verification step can be performed in O(N) time. Thus, the overall time complexity is of the order O(N*log(N)).

Space Complexity

O(N), where 'N' is the number of elements in the array 'A'.

Within the binary search, for each check, we create a temporary array of size 'N' to store the costs for that particular 'k'. Thus, the overall space complexity is of the order O(N).

Code Solution
(100% EXP penalty)
Largest Subsequence
Full screen
Console