starboy_9879's blog

By starboy_9879, history, 4 years ago, In English

We have an array of n elements (1 <= n <= 60) We have to determine whats the maximum sum subsequence possible that is less than or equal to a value k (1 <= k <= 10^18). At most 15 of the elements in array, either a[i] >= 2*a[j] or a[j] >= 2*a[i] where j is not equal to i (1 <= a[i] <= 10^17)

This problem was asked in Visa OA and later also in Expedia OA and both the times I couldn't manage to get all test cases passes. The constraints are very big for any regular knapsack approach to work. I thought of dividing the array such that first one will have all those at most 15 elements which shows that mentioned property and rest are the regular ones, since 15 is very less we can use something like bitmasking, so choosing k1 from that set and rest k-k1 from other set. But I couldn't make this idea work it will end up a bruteforce maybe I'm missing some observation. Please help

  • Vote: I like it
  • -2
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

does anyone knows any better approach to this problem

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I see an $$$O(nk + n\log{n})$$$ solution to this. Sort the array. Notice that each element has to be at least twice the previous element. Let $$$dp_{i,j}$$$ denote the maximum sum such that only the first $$$i$$$ elements are used and the length is $$$j$$$. $$$dp_{i,j} = max(dp_{i-1,j}, dp_{l,j-1} + A_i)$$$ where $$$l$$$ denotes the maximum index such that $$$2\times A_l \le A_i$$$. $$$l$$$ can be maintained using two pointers. The answer is just $$$dp_{n,k}$$$

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fix number of choosen elements. Then, foreach there is a limited set of elements which can be choosen in that position, since it must be smaller than half of the next element.

So, the bigger the number of choosen elements gets, the smaller the number of element wich can be choosen at each position. Assume a[] is sorted. Use memoizaton for the (fairly small) array maxSum.

$$$maxSum[idx][0]=0;$$$

$$$maxSum[idx][i]=a[idx]+max(maxSum[nextPossible(idx)][i-1])$$$ // if nextPossible(idx) exists

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have link to original problem?

»
3 years ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

There is an error in the question he reported. It is

"Apart from" At most 15 of the elements in array, either a[i] >= 2*a[j] or a[j] >= 2*a[i] where j is not equal to i (1 <= a[i] <= 10^17)

It can be solved by seperating the 15 elements. The way to do that would be to sort the array in descending order and iterate. If some element is not half or less separate it. Now do brute force on the 15 elements via recursion(two options-choose or not choose for sum). There will be max 2^15 possibilities. At the recursive leaf try to minimize the difference by greedily choosing the descending halving numbers if it makes the sum less than or equal to k. Output the best match.

I think this is what they had in mind while setting the question and how the 15 number is chosen so that it is not too slow.

Time O(nlogn+(2^15)*n) i.e. O(nlogn) Space O(n+(2^16-1)) i.e. O(n)

Actually I faced the same problem in Hackerrank and passed all cases using this approach