De Shaw OA | CTC 50L

Question

Question 1:
Given an array of integers, a and a max score m . Score of a subsequence [a[i1], a[i2] ... a[ik]] is defined as i1 * k + a[i1] + i2 * k + a[i2] + ... + ik * k + a[ik]. Now, find the length of largest subsequence whose score <= m.
Example:
Input: n = 4, a = [4, 3, 2, 1], max score = 33.
Output: 3
Optimal Subsequence Indexes: [1, 2, 4]. As, score is (1 * 3 + 4) + (2 * 3 + 3) + (4 * 3 + 1) = 29 <= 33
Constriants:

 

1 <= n <= 2e5
1 <= a[i] <= 10000
1 <= max score <= 1e15
It is guarenteed that at least one of the elements of the array is less than max score.